A simple implementation of a recursive-descent parser for a language of boolean expressions.

myeval.py

"""A simple implementation of a recursive-descent parser for a language of boolean expressions."""
import readline


def eval_str(expr):
    """Evaluate a boolean expression with the symbols '0', '1', '|', '&', '(' and ')'. All binary
    operators must be wrapped in parentheses, even when it would be unambiguous to omit them.
    """
    tokens = tokenize(expr)
    ast = match_expr(tokens)
    return eval_ast(ast)


def eval_ast(ast):
    """Evaluate an AST as returned by match_expr."""
    if isinstance(ast, list):
        if ast[0] == '&':
            return eval_ast(ast[1]) and eval_ast(ast[2])
        elif ast[0] == '|':
            return eval_ast(ast[1]) or eval_ast(ast[2])
        else:
            raise ValueError('unknown AST node "{}"'.format(ast[0]))
    else:
        return bool(ast == '1')


def match_expr(tokens):
    """Given a list of tokens (as strings), return the abstract syntax tree as parsed by the grammar

            START -> EXPR
            EXPR -> VALUE 
            EXPR -> ( EXPR OP EXPR )
            OP -> &
            OP -> |
            VALUE -> 1
            VALUE -> 0

    The return value is either a tree (actually just a Python list whose first element is the node
    value, either '|' or '&', and whose next two elements are the left and right children of the
    tree) or the literal values '1' or '0'.
    """

    tkn = next_token(tokens)
    if tkn == '1' or tkn == '0':
        return tkn
    elif tkn == '(':
        left = match_expr(tokens)
        op = next_token(tokens)
        if op not in ('&', '|'):
            raise SyntaxError('expected "&" or "|", got "{}"'.format(op))
        right = match_expr(tokens)
        tkn = next_token(tokens)
        if tkn != ')':
            raise SyntaxError('expected ")", got "{}"'.format(tkn))
        return [op, left, right]
    else:
        raise SyntaxError('expected "(", "0" or "1", got "{}"'.format(tkn))


def next_token(tokens):
    try:
        return tokens.pop(0)
    except IndexError:
        raise SyntaxError('premature end of input') from None

        
TOKENS = ('1', '0', '&', '|', '(', ')')
def tokenize(expr):
    """Return a list of tokens from the expression."""
    # Quick and dirty tokenizing. Don't do this in real life!
    for tkn in TOKENS:
        expr = expr.replace(tkn, ' ' + tkn + ' ')
    return expr.split()


while True:
    try:
        expr = input('>>> ')
    except EOFError:
        break
    try:
        print(eval_str(expr))
    except SyntaxError as e:
        print('Error:', e)