程序代写 Compiler Construction/Spring 2022 Homework 3

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:

4.

elements can be nested in any element but cannot exist outside of elements.
5. Alphanumericcharactersandwhitespacecharacterscanexistinanynumberbetweentheopening
and closing tags of any element. For example:
2ab
Answer. One possible grammar follows:
P → D H D B D F D H → D
B → D
F →

D

D → D

D

D
C → [a−zA−Z0−9\t\n]+
Adapted from CSCI-GA.2130-001 assignments by and .
Page 3 of 5

Question 2.2 (8 points). With your constructed grammar, verify each of the following snippets of HTML, and explain why each snippet is either correct or incorrect by using your grammar.
Your answers must adhere to the standard described in the question above; if your grammar con- flicts with that standard, this will be considered incorrect if you justify your explanations with your conflicting grammar.
1.
Header text

Body div

Footer text

2.


3.

Innermost div


4.

Inner div

Answer. 1. This snippet is valid and parses as follows:
Adapted from CSCI-GA.2130-001 assignments by and .
Page 4 of 5

ε D ε D ε

D

ε
C D

D

D C Header text ε C ε Footer text
2. This snippet is invalid: guides the parsing to B → D , which fails to match the closing tag.
3. This snippet is invalid: after P → D H D B D F D, there is no production to follow to produce the inner tag.
4. This snippet is valid and parses as follows:
D H D B D F D
ε ε ε ε ε ε D

D

D εCε
D H D B
D F D
Adapted from CSCI-GA.2130-001 assignments by and .
Page 5 of 5

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com