A parser must say exactly what went wrong and where.
What to build
A program that evaluates an integer expression, or reports its first syntax error by token number.
Requirements
- Grammar:
+ -(lowest, left),* /(left,/is//), prefix-, numbers and brackets. - Errors:
error at token K: unexpected Tfor a token that cannot appear there,error at token K: unexpected endwhen an operand is missing at the end,error at token K: expected )for a missing bracket.
Input
One line: an expression.
Output
The value, or one error line.
Constraints
At most 60 characters; no division by zero.
Example
Input:
1 + 2 * 3
Output:
7
Why it works
Because the parser always knows which token it is looking at, it can name the first one that breaks the grammar.
Examples
Example 1 · Input
1 + 2 * 3
Expected output
7
Example 2 · Input
1 + * 2
Expected output
error at token 3: unexpected *
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Count tokens from 1; the position just after the last token is n + 1.
Hint 2
Raise an error carrying the token number and message, and catch it once at the top.
Solution
Show one correct solution (try it yourself first)
import re
tokens = re.findall(r"\d+|\S", input())
pos = 0
class ParseError(Exception):
pass
def peek():
return tokens[pos] if pos < len(tokens) else None
def take():
global pos
pos += 1
return tokens[pos - 1]
def fail(message):
raise ParseError(f"error at token {pos + 1}: {message}")
def expr():
value = term()
while peek() in ("+", "-"):
value = value + term() if take() == "+" else value - term()
return value
def term():
value = unary()
while peek() in ("*", "/"):
value = value * unary() if take() == "*" else value // unary()
return value
def unary():
if peek() == "-":
take()
return -unary()
return atom()
def atom():
token = peek()
if token is None:
fail("unexpected end")
if token == "(":
take()
value = expr()
if peek() != ")":
fail("expected )")
take()
return value
if token.isdigit():
take()
return int(token)
fail(f"unexpected {token}")
try:
result = expr()
if peek() is not None:
fail(f"unexpected {peek()}")
print(result)
except ParseError as error:
print(error)