3) Removing Empty Strings

Ensure only top-level symbol can be nullable

program ::= stmtSeq� stmtSeq ::= stmt | stmt ; stmtSeq� stmt ::= “” | assignment | whileStmt | blockStmt� blockStmt ::= { stmtSeq }� assignment ::= expr = expr� whileStmt ::= while (expr) stmt� expr ::= identifier

How to do it in this example?

3) Removing Empty Strings - Result

program ::= “” | stmtSeq � stmtSeq ::= stmt| stmt ; stmtSeq | � | ; stmtSeq | stmt ; | ;� stmt ::= assignment | whileStmt | blockStmt� blockStmt ::= { stmtSeq } | { }� assignment ::= expr = expr� whileStmt ::= while (expr) stmt� whileStmt ::= while (expr)� expr ::= identifier

3) Removing Empty Strings - Algorithm

3) Removing Empty Strings

• Since stmtSeq is nullable, the rule� blockStmt ::= { stmtSeq }�gives� blockStmt ::= { stmtSeq } | { }
• Since stmtSeq and stmt are nullable, the rule� stmtSeq ::= stmt | stmt ; stmtSeq�gives� stmtSeq ::= stmt | stmt ; stmtSeq � | ; stmtSeq | stmt ; | ;

4) Eliminating unit productions

• Single production is of the form

X ::=Y

where X,Y are non-terminals

program ::= stmtSeq� stmtSeq ::= stmt � | stmt ; stmtSeq� stmt ::= assignment | whileStmt� assignment ::= expr = expr� whileStmt ::= while (expr) stmt

4) Unit Production Elimination Algorithm

• If there is a unit production

X ::=Y put an edge (X,Y) into graph

• If there is a path from X to Z in the graph, and there is rule Z ::= s₁ s₂ … s_n then add rule

X ::= s₁ s₂ … s_n

At the end, remove all unit productions.

4) Eliminate unit productions - Result

program ::= expr = expr | while (expr) stmt � | stmt ; stmtSeq� stmtSeq ::= expr = expr | while (expr) stmt � | stmt ; stmtSeq� stmt ::= expr = expr | while (expr) stmt � assignment ::= expr = expr� whileStmt ::= while (expr) stmt

5) Reducing Arity:�No more than 2 symbols on RHS�

stmt ::= while (expr) stmt

becomes

stmt ::= while stmt₁� stmt₁ ::= ( stmt_2� stmt₂ ::= expr stmt₃� stmt₃ ::= ) stmt

6) A non-terminal for each terminal

stmt ::= while (expr) stmt

becomes

stmt ::= N_while stmt₁� stmt₁ ::= N₍ stmt_2� stmt₂ ::= expr stmt₃� stmt₃ ::= N₎ stmt� N_while ::= while� N₍ ::= (� N₎ ::= )

Order of steps in conversion to CNF

• remove unproductive symbols (optional)
• remove unreachable symbols (optional)
• make terminals occur alone on right-hand side
• Reduce arity of every production to <= 2
• remove epsilons
• remove unit productions X::=Y
• unproductive symbols
• unreachable symbols
• What if we swap the steps 4 and 5 ?
• Potentially exponential blow-up in the # of productions

​

Ordering of �Unreachable / Unproductive symbols

S := B C | “”

C := D

D := a

R := r

First Unreachable then Unproductive

S := “”

C := D

D := a

S := B C | “”

C := D

D := a

S := B C | “”

C := D

D := C

R := r

​

First Unproductive then Unreachable

S := “”

S := “”

C := D

D := a

R := r

Exercises on LL(1) grammars

Exercise 1:

Consider a grammar for expressions where the multiplication sign is optional.

ex ::= ex + ex | ex * ex | ex ex |ID

​

• Find an LL(1) grammar recognizing the same language
• Create the LL(1) parsing table.

​

Exercise 1 – Solution

Exercise 1 – LL(1) parsing table

LL(1) parsing table

Exercise 2

Prove that every LL(1) grammar is unambiguous.

​

Intuition:

There is a unique way to derive / parse a string because, for any given non-terminal, at most one alternative is applicable on scanning an input character.

This means we have unique left most derivations / parse trees for every string

Formal proof is presented in the next slide

​

Solution to Exercise 2 [Cont.]

Solution to Exercise 2 [Cont.]

Corollary of the proof

Exercise 3

Solution to Exercise 3

Exercise 4

Show that the regular languages can be recognized with LL(1) parsers. Describe a process that, given a regular expression, constructs an LL(1) parser for it.

​

​

Solution for Exercise 4

Exercise 5