Debugging the LL parser

Compiling an LL parser with -debug -debug=parser, will output the whole search tree, that looks like this:

Expr "4+*2"
  MulExpr "4+*2"
    Atom "4+*2"
    *Atom "+*2"
    Atom "4+*2"
    *Atom "+*2"
  *MulExpr "+*2"
  Expr "*2"
    MulExpr "*2"
      Atom "*2"
      -Atom "*2"
      Atom "*2"
      -Atom "*2"
    -MulExpr "*2"
    MulExpr "*2"
      Atom "*2"
      -Atom "*2"
      Atom "*2"
      -Atom "*2"
    -MulExpr "*2"
    MulExpr "*2"
      Atom "*2"
      -Atom "*2"
      Atom "*2"
      -Atom "*2"
    -MulExpr "*2"
  -Expr "*2"
  MulExpr "4+*2"
    Atom "4+*2"
    *Atom "+*2"
    Atom "4+*2"
    *Atom "+*2"
  *MulExpr "+*2"
  MulExpr "4+*2"
    Atom "4+*2"
    *Atom "+*2"
    Atom "4+*2"
    *Atom "+*2"
  *MulExpr "+*2"
*Expr "+*2"

This shows you what calls the recursive descent parser actually made while trying to match the input. First Expr with input 4+*2 called MulExpr, which in turn called Atom, which succeeded, which is denoted by another line with the non-terminal name preceded by a *. As you can also see, the first symbol (the 4) was removed from the input. But since the first rule of MulExpr expects an Atom to be followed by a *, the rule fails and the next rule is tried. That one succeeds, such that the MulExpr rules succeeds.

We're still in the first Expr rule, which matches the terminal + now, followed by a non-terminal Expr, which is again printed in the debug output. After entering the MulExpr again, the calls to Atom fail this time, which is denoted by a - before the second line for the non-terminal call. Therefore MulExpr fails, and the Expr call tries it's next rule. And so on...

In the end, Expr matched only the 4, the remaining input is +*2. The parse function will therefore return false, although Expr returns true, since it requires all input to have been matched.