CODEWITHSUNDEEP
parsingcontext-free-grammarcompiler-construction
devoured elysium
devoured elysium

Reputation: 105037

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

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?

Upvotes: 6

Views: 1979

Answers (1)

ebohlman
ebohlman

Reputation: 15003

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().

Upvotes: 7

Related Questions