How does an LL parser evaluate this expression?

Question

Considering this expression:

3 + 2 + 2 * 2 = ?

Would it be 14?

Answer 1

No. That's what you'd get in left-to-right evaluation. An LL parser would build the same parse tree as an LR parser,

  +
 / \
3   +
   / \
  2   *
     / \
    2   2

and evaluate it as

(+ 3 (+ 2 (* 2 2))

which is 9, as you'd expect.

What is special about LL parsers is that, for a restricted grammar, they can always proceed left to right with limited look-ahead. This makes them easy to describe and easy to parse; some Pascal is one of the most common languages that is LL.

You might have a look at the Wiki article on leftmost derivation.