Programming Language Principles

Solution to Homework for Week 02.

1. 

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

  b) Modified grammar:

               S -> k Z
               Z -> B Z
                 -> 
               B -> A x Y
               Y -> x Y
                 ->
               A -> v Q
               Q -> S k
                 -> 

   c) LL(1) Parse Table:

       Stack Top       x            k            v          <eof>
    +---------------------------------------------------+------------+
    |     S      |            | S -> k X   |            |            |
    +------------+------------+------------+------------+------------+
    |     Z      |            | Z ->       | Z -> B Z   |  Z ->      |
    +------------+------------+------------+------------+------------+
    |     Y      | Y -> x Y   | Y ->       | Y ->       |  Y ->      |
    +------------+------------+------------+------------+------------+
    |     Q      | Q ->       | Q -> S k   |            |            |
    +------------+------------+------------+------------+------------+
    |     A      |            |            | A -> v Q   |            |
    +------------+------------+------------+------------+------------+
    |     B      |            |            | B -> A x Y |            |
    +------------+------------+------------+------------+------------+

   d) 
       Stack               Input                    OPF
    -----------------------------------------------------------
        S                  kvxvkkxx<eof>            S->kZ
        kZ                 kvxvkkxx<eof>
        Z                   vxvkkxx<eof>            Z->BZ
        BZ                  vxvkkxx<eof>            B->AxY
        AxYZ                vxvkkxx<eof>            A->vQ
        vZxYZ               vxvkkxx<eof>
        ZxYZ                 xvkkxx<eof>            Q->
        xYZ                  xvkkxx<eof>
        YZ                    vkkxx<eof>            Y->
        Z                     vkkxx<eof>            Z->BZ
        BZ                    vkkxx<eof>            B->AxY
        AxYZ                  vkkxx<eof>            A->vQ
        vQxYZ                 vkkxx<eof>
        QxYZ                   kkxx<eof>            Q->Sk
        SkxYZ                  kkxx<eof>            S->kZ
        yZkxYZ                 kkxx<eof>
        XkxYZ                   kxx<eof>            Z->
        kxYZ                    kxx<eof>
        xYZ                      xx<eof>
        YZ                        x<eof>            Y->xY
        xYZ                       x<eof>
        YZ                        <eof>             Y->
        Z                         <eof>             Z->
        ---                         ---
 
   Derivation of input:
 
         S
      => kZ                       using S->yZ
      => kBZ                      using Z->BZ
      => kAxYZ                    using B->AxY
      => kvQxYZ                   using A->vQ
      => kvxYz                    using Q->
      => kvxZ                     using Y->
      => kvxBZ                    using Z->BZ
      => kvxAxYZ                  using B->AxY
      => kvxvQxYZ                 using A->vQ
      => kvxvSkxYZ                using Q->Sy
      => kvxvkXkxYZ               using S->yX
      => kvxvkkxYZ                using Z->
      => kvxvkkxxYZ               using Y->xY
      => kvxvkkxxZ                using Y->
      => kvxvkkxx                 using Z->
      => kvxvkkxx<eof> 
 
   e) Skeleton of recursive descent parser:

                    procedure S;
                       begin
                          Read(T_k);
                          Z;
                       end;
                                
                    procedure Z;
                       begin
                          if Next_Token = T_v then
                            begin
                              B;
                              Z
                            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_v);
                          Q
                       end;
                    
                    procedure Q;
                       begin
                          if Next_Token = k then
                             begin
                               S;
                               Read(T_k);
                             end;
                       end;
                    
                    begin  { main }
                       S
                    end;
                    
   f)  Code with output statements added:


                    procedure S;
                       begin
                          Read(T_k);
                          Write(S -> k);
                          while Next_Token = T_v 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_v);
                          if Next_Token = T_k then
                            begin
                              S;
                              Read(T_k);
                              Write (A -> v S k)
                            end
                          else Write(A -> v)
                       end;
                    
                    begin  { main }
                       S
                    end;