Review Question:
1. What are three reasons why syntax analyzers are based on grammars?
- Grammars are clear and concise.
- The grammar description can be use as a direct basis for the analyzer.
- Grammar are modular or easy to maintain.
2. Explain the 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: altough 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 loxical analyzer collects characters into, and token is the internal codes for categories of these groupings.
4. What are the primary task of lexical analyzer?
A lexical analyzer has to perform syntax analysis at the lowest level of program structure.
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.
Problem Set:
1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, passes the test.
b. B → aB | bA | aBb
FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, failed the test
c. C→ aaA | b | caB
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
FIRST(aSb) = {a}, FIRST(bAA) = {b}, passes the test
b. A → b{aB} | a
FIRST (b{aB}) = {b}, FIRST (a) = {a}, passes the test
c. B → aB | a
FIRST(aB) = {a}, FIRST(a) = {a}, failed the test
3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string 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).
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.
a. A → aB | b | cBB
FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, passes the test.
b. B → aB | bA | aBb
FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, failed the test
c. C→ aaA | b | caB
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
FIRST(aSb) = {a}, FIRST(bAA) = {b}, passes the test
b. A → b{aB} | a
FIRST (b{aB}) = {b}, FIRST (a) = {a}, passes the test
c. B → aB | a
FIRST(aB) = {a}, FIRST(a) = {a}, failed the test
3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string 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).
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
Parse Tree:
S
/ | \
a A b
/ | \
a A B
|
b
Phrases: aaAbb, aAb, b
Simple phrase: b, aAb
Handle: b
b. bBab
Parse Tree:
S
/ | \
b B A
/ \
a b
Phrases: bBab, bBA
Simple phrase: ab
Handle : ab
c. aaAbBb
aaAbBb = aSBb = aSBB = x
The last string cannot be derived from the given grammar.
Tidak ada komentar:
Posting Komentar