CS代写 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

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:

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
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


Adapted from CSCI-GA.2130-001 assignments by and .
Page 2 of 3

4.

Inner div

Adapted from CSCI-GA.2130-001 assignments by and .
Page 3 of 3

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