CHAPTER 4

Nama : Aditya Isnugraha
Class   : LM01
NIM    : 1801419606

Assignment from Tri Djoko Wahjono
CHAPTER 4

- REVIEW QUESTION
11. Describe the parsing problem for a bottom-up parser.
      Answer :


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


13. Why are named constants used, rather than numbers, for token codes?
      Answer :
      - 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.
      Answer :
     -A recursive-descent subprogram for a rule with a single RHS is relatively
      simple. For each terminal symbol in the RHS, that terminal symbol is compared
      with nextToken. 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 nonterminal is called.


15. Explain the two grammar characteristics that prohibit them from being used as the basis for a      top-down parser.
      Answer : Two grammar characteristics that prohibit top-down parsing:
                      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
Answer :
 (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
Answer :
 a. FIRST(aSb)=a
    FIRST(bAA)=b
b. FIRST(b{aB}) = b
    FIRST (a) = a
c. FIRST(aB)=a
    FIRST(a) = a



3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c.
Answer :

a + b * c
Call lex /* returns a */
Enter <expr>
Enter <term>
Enter <factor>
Call lex /* returns + */
Exit <factor>
Exit <term>
Call lex /* returns b */
Enter <term>
Enter <factor>
Call lex /* returns * */
Exit <factor>
Call lex /* returns c */
Enter <factor>
Call lex /* returns end-of-input */
Exit <factor>
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).
Answer :
 call lex      // return a
            enter <expr>
            enter <term>
            enter <factor>
          call lex      // return *
            exit <factor>
          call lex      // return (
            enter <factor>
          call lex      // return b
            enter <expr>
            enter <term>
            enter <factor>
          call lex      // return +
            exit <factor>
            exit <term>
          call lex      // return c
            enter <term>
            enter <factor>
          call lex      // return )
            exit <factor>
            exit <term>
            exit <expr>
          call lex      // return 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 bBA    A→ab aAB    B→aB b
a. aaAbb
b. bBab
c. aaAbBb
Answer :