200 Chapter 4 Lexical and Syntax Analysis
- What is a phrase of a sentential form?
- What is a simple phrase of a sentential form?
- What is the handle of a sentential form?
- What is the mathematical machine on which both top-down and
bottom-up parsers are based? - Describe three advantages of LR parsers.
- What was Knuth’s insight in developing the LR parsing technique?
- Describe the purpose of the ACTION table of an LR parser.
- Describe the purpose of the GOTO table of an LR parser.
- Is left recursion a problem for LR parsers?
PROBLEM SET
- 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
- Perform the pairwise disjointness test for the following grammar rules.
a. S→aSb bAA
b. A→b{aB} a
c. B→aB a
- Show a trace of the recursive descent parser given in Section 4.4.1 for
the string a + b * c. - Show a trace of the recursive descent parser given in Section 4.4.1 for
the string a * (b + c). - 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
- 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→AbB bAc A→Ab aBB B→Ac cBb c
a. aAcccbbc
b. AbcaBccb
c. baBcBbbc