Home

Survey of Expression Parsing Algorithms in the Wild

Shunting Yard Algorithm

Norvell Article also leads to it

Bottom Up Methods

Pratt parsing and precedence climbing are both http://eli.thegreenplace.net/2009/03/20/a-recursive-descent-parser-with-an-infix-expression-evaluator/

Survey

I sent this to someone.

• Python: grammar method with LL() parser pgen.c

• recursive descent: wirth method?

TODO: Send me links to how your favorite programming language does it! I will put them here.

Or edit the Wiki:

• Python uses a generated parser from a grammar with just a few levels of precedence, using LL parsing. Actually I don't quite understand what you did with left recursion there -- can you clarify?
• The original C compiler by Ritchie and Thompson used the shunting yard algorithm.
• Lua uses something like Pratt parsing, but in a single function like precedence climbing.
• bash uses a hand-written recursive descent parser (I think of it as the Wirth style)
• GNU expr also uses recursive descent in the same style

• busybox has a clone of GNU expr I believe

• dash

  • arith_yacc.c
  • mix of Wirth method (assignment(), and(), or(), but with precedence table. Only 7 levels of precedence.

• mksh

  • expr.c
  • evalexpr.c -- precedence climbing.
  • parses and evaluates at the same time?

• zsh

  • math.c, mathparse() -- precedence table
  • precedence climbing?
  • SINGLE precedence table.

• I contributed code to toybox using Pratt parsing/precedence climbing

• clang

  • ParseRHSOfBinary
  • special case handling of ? :

• gcc ?

Which should I Use?

Hand-written or generated?

If hand-written, top-down or bottom-up?

Pratt Parsing is easiest.

They are all kind of the same?

• original papers?

For reference, here are two articles on other methods for

Other articles:

• Shunting Yard eliben

• precedence climbing eliben -- he agreed it was the same

• Wirth method

For example, here's expr.c in bash. You can see from these function prototypes that it uses plain recursive descent to encode precedence. This works fine, but results in more code, and in theory it's less efficient. Processing a single token requires making make dozens of function calls.

static intmax_t expcomma __P((void));
static intmax_t expassign __P((void));
static intmax_t expcond __P((void));
static intmax_t explor __P((void));
static intmax_t expland __P((void));
static intmax_t expbor __P((void));
static intmax_t expbxor __P((void));
static intmax_t expband __P((void));
static intmax_t exp5 __P((void));
static intmax_t exp4 __P((void));
static intmax_t expshift __P((void));
static intmax_t exp3 __P((void));
static intmax_t exp2 __P((void));
static intmax_t exppower __P((void));
static intmax_t exp1 __P((void));
static intmax_t exp0 __P((void));