Convert C- grammar to LL(1)

Question

I am currently building a compiler for C-. I am currently working on the parser, and for some reason, I can't seem to resolve the first-sets collision (of terminal id) origination from the EXPRESSION production. Below, Is a subset of the grammar I have now, could someone point me in the right direction as to how to resolve the collision (or convert to a an equivalent LL(1) parseable grammar).

EXPRESSION ->   id VAR eq EXPRESSION |  SIMPLEEXPRESSION 

VAR ->  lbracket EXPRESSION rbracket |  empty

SIMPLEEXPRESSION -> ADDITIVEEXPRESSION FADDITIVEEXPRESSION 

FADDITIVEEXPRESSION ->  RELOP ADDITIVEEXPRESSION |  empty

RELOP ->    ltoreq |    lt |    gt |    gtoreq |    doubleeq |  noteq 

ADDITIVEEXPRESSION ->   TERM ADDITIVEEXPRESSION1 

ADDITIVEEXPRESSION1 ->  ADDOP TERM ADDITIVEEXPRESSION1 |    empty

ADDOP ->    plus |  minus 

TERM -> FACTOR TERM1 

TERM1 ->    MULOP FACTOR TERM1 |    empty

MULOP ->    times | divide 

FACTOR ->   lparen EXPRESSION rparen |  id FACTOR1 |    num 

FACTOR1 ->  a | b

Try deleting as much as you can in a way that preserves the shape of your (sub)grammar and preserves the problem. (First step, throw away the rest of the grammar and concentrate on what you've shown us). When you can't delete anything else without making the problem go away, stare at what's left; often you'll be able see how to change the remaining grammar to avoid the problem. Then add everything back. If you can't figure it out at that point, show us the stripped down grammar as an extension to your question, and tell what what you think the problem is. You'll get more advice. — Ira Baxter

500 - Internal Server Error 500 - Internal Server Error · Accepted Answer · 2016-10-05T12:58:43

C does not lend itself very well to LL(1) parsing, so what you are trying to do here could be quite difficult to achieve and may not even be possible for the full grammar.

But for the problem at hand, for the top-level production

EXPRESSION ->   id VAR eq EXPRESSION |  SIMPLEEXPRESSION

it's easy to see that id can be the start of either alternative, so an LL(1) parser will not know which alternative to pick.

One solution to the immediate problem would be to split the EXPRESSION production into two alternatives, one that always starts with an id terminal, and one that never does:

EXPRESSION        ->   EXPRESSION_id |  EXPRESSION_non_id

For the id alternative, we would require the id terminal up front and then create id-only versions of the productions that follow:

EXPRESSION_id     ->   id (VAR eq EXPRESSION |  SIMPLEEXPRESSION_id)

Similarly, for the non-id side, we would create non-id versions of the productions that follow:

EXPRESSION_non_id ->   SIMPLEEXPRESSION_non_id

The required sub-productions to complete the grammar would look something like this:

SIMPLEEXPRESSION_id -> ADDITIVEEXPRESSION_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_id ->   TERM_id ADDITIVEEXPRESSION1 
TERM_id -> FACTOR_id TERM1
FACTOR_id ->   FACTOR1

SIMPLEEXPRESSION_non_id -> ADDITIVEEXPRESSION_non_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_non_id ->   TERM_non_id ADDITIVEEXPRESSION1
TERM_non_id -> FACTOR_non_id TERM1
FACTOR_non_id ->   lparen EXPRESSION rparen |  num

You can make similar transformations for other conflicts, but the resulting grammar can become quite unwieldy.

Convert C- grammar to LL(1)

1 Answers