Review Question
3. Define lexemes and token!
answer: Lexemes is the logical groupings that the lexical analyzer collects characters into while tokens is the internal codes for categories of these groupings
6. What is a state transition diagram?
answer: a directed graph that used for lexical analyzers are representations of a class of mathematical machine.
8.What are two distinct goals of syntax analysis?
answer: to detect syntax errors in a given program and to produce a parse tree
11. Describe the parsing problem for a bottom-up parser
answer: to find the substring of the current sentential form that must be reduced to its associated.
17. Why Describe the pairwise disjointness test
answer: tests whether a parsing subprogram can determine which RHS is being parsed on the basis of the next token of input.
24. What was Knuth’s insight in developing the LR parsing technique?
answer: uses the algorithm which is sometimes called Canonical LR
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
3 . Show a trace of the recursive descent parser given in Section 4.4.1 for the tring a + b * c.
answer:
Call lex /* returns a */
Enter
Enter
Enter
Call lex /* returns + */
Exit
Exit
Call lex /* returns b */
Enter
Enter
Call lex /* returns * */
Exit
Call lex /* returns c */
Enter
Call lex /* returns end-of-input */
Exit
Exit
Exit
Felix's Blog 