Chapter 4

Review Questions

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

to find the substring of the current sentential form that must be reduced to its associated.

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

Parsing algorithms that work for any unambiguous grammar are complicated and inefficient. In fact, the complexity of such algorithms is O(n3), which means the amount of time they take is on the order of the cube of the length of the string to be parsed. This relatively large amount of time is required because these algorithms frequently must back up and reparse part of the sentence being analyzed. Reparsing is required when the parser has made a mistake in the parsing process. Backing up the parser also requires that part of the parse tree being constructed (or its trace) must be dismantled and rebuilt. 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.

13.Why are named constants used, rather than numbers, for token codes?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 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 nonterminal, 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.

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

A -> aB | b | CBB

first(aB) = a

first(b) = b

first(CBB) = aaA = a

B -> aB | ba | aBb

first(aB) = a

first(ba) = b

first(aBb) = a

They are intersected & thus the rule fails the test.

C -> aaA | b | caB

first(aaA) = a

first(b) = b

first(caB) = c

are not intersected & thus the rule passes

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) = bare 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.

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 bBA A → ab aAB B → aB b
a. aaAbb
b. bBab
c. aaAbBb

a) aaAbb

Phrases: aaAbb, aAb, b

Simple phrases: b

Handle: b

b) bBab

Phrases: bBab, ab

Simple phrases: ab

Handle: ab

 c) aaAbBb (tidak ada jawaban)