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
Copyright By PowCoder代写 加微信 powcoder
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]
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?
Question 1.4 (2 points). LL(k) grammars are defined for k ≥ 0. How would an LL(0) parser work?
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?
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.
Adapted from CSCI-GA.2130-001 assignments by and . Page 1 of 3
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:
•