Exercises for COP-4020

PROBLEM 1. 

Convert the following regular expression to a NFA, 
then transform the NFA to a right-linear regular grammar,
and finally transform the grammar to the original regular
expression.
Show your work.

(ab* + c)* de* + f*

SOLUTION:

NFA:
                          f                                
                        +---+                              
                        |   V                              
                        +---+                  
    +------------------>| F |-----------------------+
    |                   +---+                       |
    |         c                                     |        
    |         +---+                                 |
    |         |   V                                 V
  +---+       +---+       +---+   d   +---+       +---+  
  | A |------>| B |------>| D |------>| E |------>| G |
  +---+       +---+       +---+       +---+       +---+
              |   ^                   |   ^                   
            a |   |                   +---+                   
              V   |                     e                    
              +---+       
              | C |      
              +---+      A is the start state, G is final
              |   ^                                         
              +---+                                         
                b                                           
                                                          
                                                          
                                                          
Grammar:

A -> F
  -> B
B -> cB
  -> aC
  -> D
C -> bC
  -> B
D -> dE
E -> eE
  -> G
F -> fF
  -> G
G ->

Equations:

A = B + F = (ab* + c)* de* + f*
B = cB + aC + D = cB + ab*B + D = (c+ab*)B + D = (ab* + c)* de*
C = bC + B = b*B
D = dE = de*
E = eE + G  = e*G = e*
F = fF + G  = f*G = f*
G = 


PROBLEM 2.

1. Consider the following context-free grammar:

               S -> S B
                 -> y
               B -> B x
                 -> A x
               A -> z
                 -> z S y

   a) Show that the grammar is not LL(1).

   b) Modify the grammar so that it becomes LL(1).

   c) Construct the corresponding LL(1) parse table.

   d) Hand-simulate the execution of the classical top-down
      parsing algorithm, using your parse table, for the input string
      "yzxzyyxx<eof>".  For each step, show the stack, the
      input, and the result of OPF.  Then take the sequence of
      productions produced by OPF and use them to derive the input string.  
   e) Write the skeleton of the corresponding recursive descent parser.

   f) Add output statements to the code of part e) so that the
      parser generates (in reverse order) the sequence of productions
      from the original grammar (not the modified grammar) that
      can be used to derive the input parsed.


SOLUTION:


  a) Nonterminal B is left recursive, hence the grammar is not
     LL(1).

  b) Modified grammar:

               S -> y X
               X -> B X
                 -> 
               B -> A x Y
               Y -> x Y
                 ->
               A -> z Z
               Z -> S y
                 -> 

   c) LL(1) Parse Table:

       Stack Top       x            y            z          <eof>
    +---------------------------------------------------+------------+
    |     S      |            | S -> y X   |            |            |
    +------------+------------+------------+------------+------------+
    |     X      |            | X ->       | X -> B X   |  X ->      |
    +------------+------------+------------+------------+------------+
    |     Y      | Y -> x Y   | Y ->       | Y ->       |  Y ->      |
    +------------+------------+------------+------------+------------+
    |     Z      | Z ->       | Z -> S y   |            |            |
    +------------+------------+------------+------------+------------+
    |     A      |            |            | A -> z Z   |            |
    +------------+------------+------------+------------+------------+
    |     B      |            |            | B -> A x Y |            |
    +------------+------------+------------+------------+------------+

   d) 
       Stack               Input                    OPF
    -----------------------------------------------------------
        S                  yzxzyyxx<eof>            S->yX
        yX                 yzxzyyxx<eof>
        X                   zxzyyxx<eof>            X->BX
        BX                  zxzyyxx<eof>            B->AxY
        AxYX                zxzyyxx<eof>            A->zZ
        zZxYX               zxzyyxx<eof>
        ZxYX                 xzyyxx<eof>            Z->
        xYX                  xzyyxx<eof>
        YX                    zyyxx<eof>            Y->
        X                     zyyxx<eof>            X->BX
        BX                    zyyxx<eof>            B->AxY
        AxYX                  zyyxx<eof>            A->zZ
        zZxYX                 zyyxx<eof>
        ZxYX                   yyxx<eof>            Z->Sy
        SyxYX                  yyxx<eof>            S->yX
        yXyxYX                 yyxx<eof>
        XyxYX                   yxx<eof>            X->
        yxYX                    yxx<eof>
        xYX                      xx<eof>
        YX                        x<eof>            Y->xY
        xYX                       x<eof>
        YX                        <eof>             Y->
        X                         <eof>             X->
        ---                         ---

   Derivation of input:
 
         S
      => yX                       using S->yX
      => yBX                      using X->BX
      => yAxYX                    using B->AxY
      => yzZxYX                   using A->zZ
      => yzxYX                    using Z->
      => yzxX                     using Y->
      => yzxBX                    using X->BX
      => yzxAxYX                  using B->AxY
      => yzxzZxYX                 using A->zZ
      => yzxzSyxYX                using Z->Sy
      => yzxzyXyxYX               using S->yX
      => yzxzyyxYX                using X->
      => yzxzyyxxYX               using Y->xY
      => yzxzyyxxX                using Y->
      => yzxzyyxx                 using X->
      => yzxzyyxx<eof> 
 
   e) Skeleton of recursive descent parser:

                    procedure S;
                       begin
                          Read(T_y);
                          X;
                       end;
                                
                    procedure X;
                       begin
                          if Next_Token = T_z then
                            begin
                              B;
                              X
                            end;
                       end;
                    
                    procedure B;
                       begin
                          A;
                          Read(T_x);
                          Y
                       end;
                    
                    procedure Y;
                       begin
                          if Next_Token = T_x then
                             begin
                                Read(T_x);
                                Y
                             end;
                       end;
                    
                    procedure A;
                       begin
                          Read(T_z);
                          Z
                       end;
                    
                    procedure Z;
                       begin
                          if Next_Token = y then
                             begin
                               S;
                               Read(T_y);
                             end;
                       end;
                    
                    begin  { main }
                       S
                    end;
                    
   f)  Code with output statements added:


                    procedure S;
                       begin
                          Read(T_y);
                          Write(S -> y);
                          while Next_Token = T_z do
                             begin
                               B;
                               Write(S -> S B)
                             end
                       end;
                                
                    procedure B;
                       begin
                          A;
                          Read(T_x);
                          Write(B -> A x);
                          while Next_Token = T_x do
                            begin
                              Read(T_x);
                              Write(B -> B x)
                            end
                       end;
                    
                    procedure A;
                       begin
                          read(T_z);
                          if Next_Token = T_y then
                            begin
                              S;
                              Read(T_y);
                              Write (A -> z S y)
                            end
                          else Write(A -> z)
                       end;
                    
                    begin  { main }
                       S
                    end;