Assignment #4

Pengajar : Tri Djoko Wahjono

Review Question :

11. Describe the parsing problem for a bottom-up parser.

         =>

         The process of bottom-up parsing produces the reverse of a 
         rightmost derivation. So, in the example derivation, a bottom-up
         parser starts with the last sentential form (the input sentence) and
         produces the sequence of sentential forms from there until all that
         remains is the start symbol, which in this grammar is E. In each step,
         the task of the bottom-up parser is to find the specific RHS, the
         handle, in the sentential form that must be rewritten to get the next
         (previous) sentential form. As mentioned earlier, a right sentential
         form may include more than one RHS. For example, the right
         sentential form.

        

12. Explain why compilers use parsing algorithms that work on only a 
      subset of all grammars.

         =>

         Because  O(n3) algorithms are normally not useful for 
         practical processes, such as syntax    analysis for a compiler, because
         they are far too slow. In situations such as this, computer scientists
         often search for algorithms that are faster, though less general.
         Generality is traded for efficiency. In terms of parsing, faster
         algorithms have been found that work for only a subset of the set of
         all possible grammars. These algorithms are acceptable as long as the
         subset includes grammars that describe programming languages.

13.Why are named constants used, rather than numbers, for token codes?

      =>

      Because it’s for the sake of readability of lexical and syntax analyzers.

14.Describe how a recursive-descent parsing subprogram is written for a 

     rule with a single RHS.

      =>

      A recursive-descent subprogram for a rule with a single RHS is relative
      simple. For each terminal symbol in the RHS, that terminal symbol is
      compared with next Token. If they do not match, it is a syntax error. If
      they match, the lexical analyzer is called to get the next input token.
      For each non terminal, the parsing subprogram for that non terminal
      is called.

15. Explain the two grammar characteristics that prohibit them from being

      used as the basis for a top-down parser.

        =>  Direct or indirect Left Recursion.

Problem Set :

1. Perform the pairwise disjointness test for the following grammar rules.

    a. A → aB | b | cBB
    b. B → aB | bA | aBb
    c. C→ aaA | b | caB

    =>
   (a) FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test
   (b) FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test
   (c) FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test

2. Perform the pairwise disjointness test for the following grammar rules.
     a. S→ aSb | bAA
     b. A → b{aB} | a
     c. B → aB | a

     =>
      S→ aSb | bAA

     first(aSb) = a

     first(bAA) = b

     are not intersected, the rule passes

     A → b{aB} | a

     first(b{aB}) = b

     first(a) = a

     are not intersected, the rule passes

     B → aB | a

     first(aB) = a

     first(a) = a

     They are intersected the rule fails the test.



3. Show a trace of the recursive descent parser given in Section 4.4.1 for
     the string a + b * c.
     Consider the following EBNF description of simple arithmetic 

     expressions:
     <expr> → <term> {(+ | -) <term>}
     <term> → <factor> {(* | /) <factor>}
     <factor> → id | int_constant | ( <expr> )
      =>

     Next token is: 10 Next lexeme is a
     Enter <expr>
     Enter <term>
     Enter <factor>

     Next token is: 21 Next lexeme is +
     Exit <factor>
     Exit <term>

     Next token is: 10 Next lexeme is b
     Enter <term>
     Enter <factor>

     Next token is: 10 Next lexeme is *
     Exit <factor>

     Next token is: 26 Next lexeme is c
     Enter<factor>

     Next token is: -1 Next lexeme is EOF
     Exit <term>
     Exit <expr>


4. Show a trace of the recursive descent parser given in Section 4.4.1 for
     the string a * (b + c).

     => 

     Next token is: 10 Next lexeme is a
     Enter <expr>
     Enter <term>
     Enter <factor>

     Next token is: 21 Next lexeme is *
     Exit <factor>

     Next token is: 25 Next lexeme is (
     Enter <factor>

     Next token is: 10 Next lexeme is b
     Enter <expr>
     Enter <term>
     Enter <factor>

     Next token is: 21 Next lexeme is +
     Exit <factor>

     Next token is: 26 Next lexeme is c
     Enter <factor>

     Next token is: 26 Next lexeme is )
     Exit <term>
     Exit <expr>

     Next token is: -1 Next lexeme is EOF
     Exit <factor>
     Exit <term>
     Exit <expr>

5.  Given the following grammar and the right sentential form, draw a parse
      tree and show the phrases and simple phrases, as well as the handle.
      S → aAb [1] bBA A → ab [1] aAB B → aB [1] b
      a. aaAbb

      b. bBab

      c. aaAbBb

      => 

      

         and for c. it's  doesn't have a answer.