Compiler Construction/Spring 2022 Homework 3
1 Syntax Analysis
Question 1.1 (4 points). Eliminate left recursion in the following grammar:
lVal → id | lVal ( lVal ) | lVal . id Answer. We follow the Dragon Book method, converting:
Copyright By PowCoder代写 加微信 powcoder
For our grammar:
A→Aα1 | … |Aαm |β1 | … |βn
A→β1A′ | … | βnA′ A′→α1A′ | … |αmA′ |ε
lVal → id lVal′
lVal′ →ε|(lVal)lVal′ |.idlVal′
Question 1.2 (4 points). Compute the FIRST and FOLLOW sets of the grammar:
trail → grade | grade , grade grade → letter sign
sign → + | – | ε letter → [A-CF]
Answer. Note that we define the production for letter using a regular expression. It can be rewritten in the usual form without expressive loss.
For the FIRST set, we start by noting that FIRST(terminal_x) = {terminal_x}. With that in mind, we perform each step, one at time. Recall that both FIRST and FOLLOW constructions are “fixed point”, which means we continue adding symbols until nothing changes.
1. Add {A,B,C,F} to FIRST(letter) (comes from FIRST(x) for each possible terminal production for letter).
2. Add {+, -, ε } to FIRST(sign) (similar rationale to above).
Adapted from CSCI-GA.2130-001 assignments by and . Page 1 of 5
3. Add FIRST(letter) to FIRST(grade) (letter is the first non-terminal in the grade production). We do not add FIRST(sign) as ε is not part of FIRST(letter).
4. Add FIRST(grade) to FIRST(trail) (same rationale as before).
The result is as follows:
We now compute the FOLLOW set:
FIRST(letter) = {A, B, C, F} FIRST(sign) = {-, +, ε}
FIRST(grade) = {A, B, C, F} FIRST(trail) = {A, B, C, F}
1. Add $ (the termination marker) to FOLLOW(trail) (adding the terminator to the root’s FOLLOW set is part of the initialization step for this algorithm).
2. Add FOLLOW(trail) to FOLLOW(grade) (grade can be the last non-terminal in a trail production).
3. Add , to FOLLOW(grade) (trail → grade, grade).
4. Add FOLLOW(grade) to FOLLOW(sign) (sign is the last non-terminal in the grade production).
5. Add FIRST(sign), except for ε to FOLLOW(letter) (letter is followed by sign in the grade produc- tion).
6. Add FOLLOW(grade) to FOLLOW(letter) (FIRST(sign) includes ε).
FOLLOW(trail) = {$} FOLLOW(grade) = {$, ,}
FOLLOW(letter) = {$, -, +, ,} FOLLOW(sign) = {$, ,}
Question 1.3 (2 points). What properties should a grammar have to support predictive parsing (in the LL(1) sense) without computing the FOLLOW sets?
Answer. For productions of the form A → α, the FOLLOW sets guide parsing when ε ∈ FIRST(α). Without that possibility, the FIRST sets alone provide sufficient guidance.
Question 1.4 (2 points). LL(k) grammars are defined for k ≥ 0. How would an LL(0) parser work?
Answer. An LL(k) parser uses two pieces of information to choose a production – the current nonter- minal and k tokens of the input text. As an example, consider an LL(1) parsing table on page 225 of the textbook, in which the production to use is found on the intersection of the appropriate row (nonterminal) and column (one token of the input text).
k = 0 means that the parser can determine the right production based on the current nonterminal alone. In other words, there is only one production for each nonterminal. (This constraint also rules out recursive productions, which need at least one non-recursive alternative to terminate.)
Adapted from CSCI-GA.2130-001 assignments by and . Page 2 of 5
Question 1.5 (2 points). We discussed why left recursion is undesirable and how to eliminate it. Yet, the GNU Bison documentation (https://www.gnu.org/software/bison/manual/html_node/Recurs ion.html) recommend to “always use left recursion”. What is different about Bison?
Answer. Left recursion presents a problem for top-down parsing. Bison, like Yacc and CUP, is a bottom- up parser.
2 HTML Grammar
Question 2.1 (8 points). Construct a simple grammar for HTML that identifies the following tags (a
pair of tags makes up an element):
| |
|
|| |
The following constraints must be met in the grammar:
1. An opening tag must always be paired with its closing tag. For example, would be valid, but would not.
2. There must be only one element.
3. An element can contain up to at most one of each of the following, in the given order:
•