Csc 4330/6330, Programming Language Concepts (Spring 2022)

Homework 3b (Not to be turned in)

1. Consider the grammar for regular expressions:

   re : re PLUS term
   re : term
   term : term factor
   term : factor
   factor : factor STAR
   factor : niggle
   niggle : LETTER
   niggle : EPSILON
   niggle : LPAREN re RPAREN
   

   Draw Parse trees and Expression trees for the following regular expressions:
   • a*bb*a
   • (aa+bb)*aaa

   Continue with the expression trees and produce equivalent DFAs based on the RE2DFA algorithm.

2. Eliminate left recursion in the following grammar:

   S --> SX
   S --> SSb
   S --> XS
   S --> a
   

3. Determine if the following grammar passes the pairwise disjointness test.

   A --> aB | b | CBB
   B --> aB | ba | aBb
   C --> aaA | b | caB
   

4. Using the Grammar on slide 10 and LR Parsing table on slide 20 of Chapter 4 Part II slides, show a rightmost derivation (if possible) and the Stack/Input/Action for the following strings:
   • (id + id) * id
   • (id + id( * id