CS606 Final Term Combined

The following procedure encodes this strategy.

Let’s apply the algorithm to the expression grammar.

Put $ in FOLLOW(E ). By rule (2) applied to production ? ( E ), ‘)’ is also in FOLLOW(E ). Thus, FOLLOW(E ) = { ), $}. By rule (3) applied to production E ? T E' , $ and ‘)’ are in FOLLOW(E' ). Thus, FOLLOW(E ) = FOLLOW (E' ) = { ), $ }. Similarly, FOLLOW(T ) = FOLLOW (T' ) = { +, ), $ } and FOLLOW(F ) = { +, is not clear how to predict; the two productions start with the non-terminal T. A grammar must be left factored before use for predictive parsing. The procedure to left-factor a grammar is as follows:

A graphical explanation:

Example: consider following fragment of expression grammar

Factor ?

id id [ ExprList ] id ( ExprList )

After left factoring, the grammar becomes

Factor ? id Args Args ? [ ExprList ] | ( ExprList )

| ε

Given a CFG that does not meet the LL(1) condition, it is un-decidable whether or not an equivalent LL(1) grammar exists.

Lecture 20

Bottom-up Parsing

Bottom-up parsing is more general than top-down parsing. Bottom-up parsers handle a large class of grammars. It is the preferred method in practice. It is also called LR parsing; L means that tokens are read left to right and R means that the parser constructs a rightmost derivation. LR parsers do not need left-factored grammars. LR parsers can handle left-recursive grammars.

LR parsing reduces a string to the start symbol by inverting productions. A derivation consists of a series of rewrite steps

Each γi is a sentential form. If γ contains only terminals, γ is a sentence in L(G). If γ contains ≥ 1 nonterminals, γ is a sentential form. A bottom-up parser builds a derivation by working from input sentence back towards the start symbol S.

S → aABe A → Abc | b B → d

The sentence abbcde can be reduced to S:

abbcde aAbcd e aAde aABe S

These reductions, in fact, trace out the following right-most derivation in reverse:

S  aABe aAde aAbcde abbcde

S aBy aγy xy