Page 199
Review Question
1. What are three reasons why syntax analyzers are based on grammars?
First, using BNF descriptions of the syntax of programs are clear and concise. Second, can be used as the direct basis for the syntax analyzer. Third, implementations based on BNF are relatively easy to maintain because of their modularity.
2. Explain three reasons why lexical analysis is separated from syntax analysis.
- Simplicity (Techniques for lexical analysis are less complex than those required for syntax analysis)
- Efficiency (Although it pays to optimize the lexical analyzer, because lexical analysis requires a significant portion of total compilation time)
- Portability (Because the lexical analyzer reads input program files and often includes buffering of that input, it is somewhat platform dependent)
3. Define lexeme and token.
Lexeme is the logical groupings that the lexical analyzer collects characters into and Token is the internal codes for categories of these groupings.
5. Describe briefly the three approaches to building a lexical analyzer.
- Write a formal description of the token patterns of the language using a descriptive language related to regular expression.
- Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram.
- Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram.
6. What is a state transition diagram?
A state transition diagram is a directed graph which the representations of a class of mathematical machine that used for lexical analyzers.
8. What are the two distinct goals of syntax analysis?
Two distinct goals of syntax analysis are to detect syntax errors in a given program and to produce a parse tree or possibly the information required to build such a tree for a given program.
17. Describe the pairwise disjointness test.
The pairwise test try to test whether a parsing subprogram can determine which RHS is being parsed on the basis of the next token of input.
18. What is left factoring?
Left factoring is the action taken when a grammar leads backtracking while marking parsing or syntax tree.
23. Describe three advantages of LR parsers.
Three advantages of LR parsers are:
- They can be built for all programming languages.
- They can detect syntax errors as soon as it possible in a left-to-right scan.
- The LR class of grammars is a proper superset of the class parsable by LL parsers.
Page 200
Problem Set
1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
b. B → aB | bA | aBb
c. A → 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
3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string a + b * c.
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>
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
7. Show a complete parse, including the parse stack contents, input string, and action for the string id * (id + id) , using the grammar and parse table in Section 4.5.3.
Stack
|
Input
|
Action
|
0
|
id * (id + id) $
|
Shift 5
|
0id5
|
* (id + id) $
|
Reduce 6 (Use GOTO[0, F])
|
0F3
|
* (id + id) $
|
Reduce 4 (Use GOTO[0, T])
|
0T2
|
* (id + id) $
|
Reduce 2 (Use GOTO[0, E])
|
0T2*7
|
(id + id) $
|
Shift 7
|
0T2*7(4
|
id + id ) $
|
Shift 4
|
0T2*7(4id5
|
+ id ) $
|
Shift 5
|
0T2*7(4F3
|
+ id ) $
|
Reduce 6 (Use GOTO[4, F])
|
0T2*7(4T2
|
+ id ) $
|
Reduce 4 (Use GOTO[4, T])
|
0T2*7(4E8
|
+ id ) $
|
Reduce 2 (Use GOTO[4, E])
|
0T2*7(4E8+6
|
id ) $
|
Shift 6
|
0T2*7(4E8+6id5
|
) $
|
Shift 5
|
0T2*7(4E8+6F3
|
) $
|
Reduce 6 (Use GOTO[6, F])
|
0T2*7(4E8+6T9
|
) $
|
Reduce 4 (Use GOTO[6, T])
|
0T2*7(4E8
|
) $
|
Reduce 1 (Use GOTO[4, E])
|
0T2*7(4E8)11
|
$
|
Shift 11
|
0T2*7F10
|
$
|
Reduce 5 (Use GOTO[7, F])
|
0T2
|
$
|
Reduce 5 (Use GOTO[0, T])
|
0E1
|
$
|
Reduce 2 (Use GOTO[0, E])
|
