Compilers: Evaluate, or explain the syntax error

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 T for a token that cannot appear there, error at token K: unexpected end when 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)

Lesson: Recursive-descent parsing →