Can a left associative operator be expressed in a way such that top-down LL(1) parsers can understand?

Question

I was trying to implement a LL(1) top-down parser for a calculator language. It only allows us to sum, subtract, divide and multiply numbers. No parentheses.

S -> A

A -> B + A
   | B - A
   | B

B -> int * B
   | int / B
   | int

As this grammar is not suited to a LL(1) parser, I had to change it quite a bit:

S -> A

A -> B A'
A'-> + A
   | - A
   | λ

B -> int B'
B'-> * B
   | / B
   | λ

The problem is that now the grammar is not left associative for the 4 shown operators, and I need it to be so. How to solve this problem? Is it even possible to accomplish so?

Marital

I suppose that you're not looking for the answer "don't use an LL(1) parser, then" :). But that's the reality: LL(1) parsers are not a good match for parsing expressions; if you don't want to use LR(1) for some reason, write a Pratt parser or a operator precedence parser (see "Shunting Yard algorithm") – Pinko

Well, I'm just learning about parsers. I intended in trying to implement a simple calculator language for several kinds of parsers. Are you stating that it's not possible to accomplish a calculator with a LL(1)? – Marital

I'm not stating that it's impossible, just that it's not trivial. You can do it by using the LL(1) parser to generate a parse tree for the modified grammar, and then reverse the transformation on the parse tree to create the parse tree for the original grammar. – Pinko

Oh, I was asking whether it was possible without that kind of gimmick. – Marital

Are you aiming for a table-driven parser or a handwritten recursive-descent parser? If the latter, there's a fairly straightforward way to implement it (by replacing recursion with iteration). – Tigges

@ebohlman: Hand-written. – Marital

Answer 1

You can get left-associativity by replacing recursion with iteration. The following sort-of-pseudocode directly computes values just for simplicity, but you could generate a parse tree using the same method.

function A() {
   val = B();
   t = peek();
   while (t=='+' || t=='-') {
     match(t);
     val1 = B();
     if (t=='+')
       val = val + val1;
     else
       val = val - val1;
     t = peek();
   }
   return(val)
}

where peek() returns the next token without eating it, and match() eats the next token. You'd do the same thing for B().

Tigges

Hi, I need to generate a LL(1) parse table, instead of ad-hoc code. Is it possible? Thanks! – Lem