Csc 4330/6330, Programming Language Concepts (Summer 2020)

  1. 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' | ε
    
  2. 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.
    
  3. 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,'(')