Recursive descent expression calculator - lyriarte/Cm7b5 GitHub Wiki

LL(1) grammar

• Read input from left to right
• Leftmost derivation

Bare-bones parser

git checkout simple_expression_parser_recursive
cat recursive.c

Example expression:

a + b + c

Parse tree:

  +
 / \
a   +
   / \
  b   c

Right-recursive expression calculator

git checkout recursive
git clean -f
make
echo "(123 - 5 * 4 - 3) / 4" | ./recursive

Explicit parenthesis are needed to get a correct interpretation.

echo "((123 - 5 * 4) - 3) / 4" | ./recursive

Supporting left recursion with a recursive parser is possible by building a parse tree and re-parenting the nodes.