Compiler Construction/Spring 2022 Homework 4
1 Bottom-Up Parsing
Question 1.1 (3 points). LR(0) parsers, while too limiting for practical uses, are still more powerful
than LL(0) ones. Where does the difference in power come from?
Copyright By PowCoder代写 加微信 powcoder
Question 1.2 (6 points). Consider the following grammar:
E→F∗E|F F → (E) | n
The first few moves for parsing the string (n ∗ n) ∗ n bottom-up look as follows:
Stack Input
$ (n*n)*n$
$( n*n)*n$
$(n *n)*n$
$(F *n)*n$
$(F* n)*n$
shift reduceF→n shift
Write down the remaining moves.
Question 1.3 (6 points). Using the grammar from the previous question:
• Compute the ITEMS set for each production. • For each item, compute its CLOSURE set.
2 Recursive Schemes
Consider the following grammar for nested lists over numbers:
L → num L | { L } L | ε
Question 2.1 (5 points). Write a syntax-directed recursive scheme that computes the product of all
numbers in a list.
Question 2.2 (5 points). Write a syntax-directed recursive scheme that generates a flattened copy of a nested list with all the same numbers in the same order but with no curly brackets.
Question 2.3 (5 points). Write a syntax-directed recursive scheme that computes the reverse of a nested list and all the contained nested lists. You can flatten the list in the process.
Adapted from CSCI-GA.2130-001 assignments by and . Page 1 of 1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com