Recursive descent parser with precedence

parser.py

from collections import deque

PRECEDENCE = { "+": 100, "*": 110 }

def precedence( token ):
    try:
        return PRECEDENCE[token]
    except KeyError:
        return None

PREFIX_SYNTAX = {}

def prefixSyntax( token ):
    try:
        return PREFIX_SYNTAX[token]
    except KeyError:
        return lambda x, _: {"token": x}

def tryReadPrimaryExpression( items_deque ):
    if items_deque:
        item = items_deque.popleft()
        return prefixSyntax( item )( item, items_deque )

def tryReadExpression( items_deque, prec ):
    # print( 'INPUT', items_deque )
    expr = tryReadPrimaryExpression( items_deque )
    if expr:
        while items_deque:
            item = items_deque.popleft()
            q = precedence( item )
            if not q:
                items_deque.appendleft( item )
                break
            if q >= prec:
                rhs = tryReadExpression( items_deque, q )
                expr = { "op": item, "lhs": expr, "rhs": rhs }
            else:
                items_deque.appendleft( item )
                break
    # print( 'EXPR', expr, items_deque )
    return expr

def mustReadToken( token, items_deque ):
    if items_deque:
        t = items_deque.popleft()
        if t != token:
            raise Exception( f"Unexpected item '{t}', expecting '{token}'")
    else:
        raise Exception( "Unexpected end of file" )

def reserved_word( item, items ):
    raise Exception( "Unexpected reserved word: " + item )

def open_parenthesis( item, items_deque ):
    expr = tryReadExpression( items_deque, 0 )
    mustReadToken( ")", items_deque )
    return expr

PREFIX_SYNTAX["("] = open_parenthesis
PREFIX_SYNTAX[")"] = reserved_word


if __name__ == "__main__":
    input = deque( "2 + 3 * ( 6 + 1 )".split() )
    print( tryReadExpression( input, 0 ) )