Sun, 27 Apr 2008 23:36:54 -0500

Related articles |
---|

I don't see how they arrive at the parsing table cdalten@gmail.com (grocery_stocker) (2008-04-26) |

Re: I don't see how they arrive at the parsing table cdodd@acm.org (Chris Dodd) (2008-04-27) |

From: | Chris Dodd <cdodd@acm.org> |

Newsgroups: | comp.compilers,comp.theory |

Date: | Sun, 27 Apr 2008 23:36:54 -0500 |

Organization: | Compilers Central |

References: | 08-04-100 |

Keywords: | parse, LL(1) |

Posted-Date: | 28 Apr 2008 22:43:39 EDT |

grocery_stocker <cdalten@gmail.com> wrote in news:08-04-100@comp.compilers:

*> The question stems from the following URL*

*> http://en.wikipedia.org/wiki/LL_parser*

*>*

*> For the following grammar rules*

*>*

*> 1. S -> F*

*> 2. S -> ( S + F )*

*> 3. F -> 1*

*>*

*> They have a parsing table for ( 1 + 1 ) that looks like*

*>*

*> | ( | ) | 1 | + | $ |*

*> --+---+---+---+---+---+*

*> S | 2 | - | 1 | - | - |*

*> --+---+---+---+---+---+*

*> F | - | - | 3 | - | - |*

*> --+---+---+---+---+---+*

*>*

*> How do they arrive at this table? For example, they use first '(' from*

*> the input stream. How do they know know to apply rule 2 and say not*

*> rule 1?*

The table is computed directly from the FIRST sets of the grammar. If

rule N is A -> RHS, then for each terminal t in FIRST(RHS), we put N in

the table for A,t.

In this example, for rule 1, FIRST(F) is '1', so we put 1 in the table at

S,'1'. Similarly, FIRST( "( S + F )" ) is '(', so 2 goes in S,'('. Finally,

FIRST(1) is '1' so 3 goes in F,'1' and the table is complete.

If there are multiple rules for the same terminal that have non-disjoint

FIRST(RHS) sets, then you'll put two rules in the same spot (a conflict)

and the grammar is not LL(1). You also need special handling for any RHS

that may expand to epsilon (the empty string), in which case you also need

to add the rule to A,t for every terminal t in FOLLOW(A) as well.

Chris Dodd

cdodd@acm.org

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.