Precedence Climbing Parsing in Java

Grammar

  unary_op ::= + | -

  binary_op ::= + | - | * | / | %

  expression ::= integer | unary_op expression | expression binary_op expression | '(' expression ')'

Algorithm

  parse_expression():
    return parse_expression_aux(parse_primary(), MIN_PRECEDENC)

  parse_expression_aux(lhs, min_preceence):
    lookahead = peek next token

    while lookahead.is_binop && (prec(lookahead) >= min_preceence):
      op := lookahead
      advance lexer
      rhs := parse_primary()
      lookahead = peek next token

      while lookahead.is_binop && (prec(lookahead) > prec(op) || lookahead.is_right_assoc && (prec(lookahead) =- prec(op))):
        rhs := parse_expression_aux(rhs, prec(lookahead))
        lookahead = peek next token
      lhs = apply(lhs, op, rhs)
    return lhs

Source: https://ycpcs.github.io/cs340-fall2018/lectures/lecture06.html

Build

Note: To get around the problem with exec:java not recognising preview features, do the following first (in the project root):

  $ mkdir .mvn && touch .mvn/jvm.config && echo "--enable-preview" >> .mvn/jvm.config

  $ mvn clean && mvn compile && mvn exec:java -Dexec,mainClass=com.tj.parsers.precclimb.App

LICENCE

See LICENSE.