Csc 4330/6330, Programming Language Concepts (Spring 2020)
Homework 4 (Due: Friday, February 28)
Handin under Assignment 4Note: Since solutions will be discussed on Wednesday, all submitted homeworks will get full credit, but only if you make the submission (-:
-
Eliminate left recursion in the following grammar:
S --> SX S --> SSb S --> XS S --> a
SOLUTION:
Original grammar: S --> SX S --> SSb S --> XS S --> a α1 = X, α2 = Sb, β1 = XS, β2 = a Modified grammar S --> XSS' | aS' S' --> XS' | SbS' | ε
- Determine if the following grammar passes the pairwise disjointness test.
A --> aB | b | CBB B --> aB | ba | aBb C --> aaA | b | caB
SOLUTION:
Consider the A-rules: A --> aB | b | CBB FIRST(aB) = { a } FIRST(b) = { b } FIRST(CBB) = { a, b, c } There are common terminals in these firsts, so A rules FAIL the pairwise disjointness test. Consider B-rules: B --> aB | ba | aBb first(aB) = { a } first(ba) = { b } first(aBb) = { a } There are common terminals in these firsts, so B rules FAIL the pairwise disjointness test. Consider C-rules: C --> aaA | b | caB first(aaA) = { a } first(b) = { b } first(caB) = { c } There are no common terminals in these firsts, so C rules PASS the disjointness test. Overall, the grammar FAILS the disjointness tests because at least one non-terminal FAILS the disjointness tests.
- Using the Grammar on slide 4-33 and LR Parsing table on slide 4-34 of Chapter 4 slides,
show a rightmost derivation (if possible) and the Stack/Input/Action for the following strings:
- (id + id) * id
- (id + id( * id
SOLUTION:
(id + id) * id Stack Input Action 0 (id + id) * id$ S4 0(4 id + id) * id$ S5 0(4id5 + id) * id$ R6 (Use GOTO [4,F]) F -> id 0(4F3 + id) * id$ R4 (Use GOTO [4,T]) T -> F 0(4T2 + id) * id$ R2 (Use GOTO [4,E]) E -> T 0(4E8 + id) * id$ S6 0(4E8+6 id) * id$ S5 0(4E8+6id5 ) * id$ R6 (Use GOTO [6,F]) F -> id 0(4E8+6F3 ) * id$ R4 (Use GOTO [6,T]) T -> F 0(4E8+6T9 ) * id$ R1 (Use GOTO [4,E]) E -> E + T 0(4E8 ) * id$ S11 0(4E8)11 * id$ R5 (Use GOTO [0,F]) F -> (E) 0F3 * id$ R4 (Use GOTO [0,T]) T -> F 0T2 * id$ S7 0T2*7 id$ S5 0T2*7id5 $ R6 (Use GOTO [7,F]) F -> id 0T2*7F10 $ R3 (Use GOTO [0,T]) T -> T * F 0T2 $ R2 (Use GOTO [0,E]) E -> T 0E1 $ ACCEPT E 2=> T 3=> T * F 6=> T * id 4=> F * id 5=> (E) * id 1=> (E + T) * id 4=> (E + F) * id 6=> (E + id) * id 2=> (T + id) * id 4=> (F + id) * id 6=> (id + id) * id (id + id( * id Stack Input Action 0 (id + id( * id$ S4 0(4 id + id( * id$ S5 0(4id5 + id( * id$ R6 (Use GOTO [4,F]) F -> id 0(4F3 + id( * id$ R4 (Use GOTO [4,T]) T -> F 0(4T2 + id( * id$ R2 (Use GOTO [4,E]) E -> T 0(4E8 + id( * id$ S6 0(4E8+6 id( * id$ S5 0(4E8+6id5 ( * id$ ERROR; blank entry for ACTION(5,'(')