Consider the following LL(1) grammar for a simplified subset of Lisp: P E $$ E
Question:
Consider the following LL(1) grammar for a simplified subset of Lisp:
P → E $$
E → atom
→ ’ E
→ ( E Es )
Es → E Es
→
(a) What is FIRST(Es)? FOLLOW(E)? PREDICT(Es → ∈)?
(b) Give a parse tree for the string (cdr ‚(a b c)) $$.
(c) Show the left-most derivation of (cdr ‚(a b c)) $$.
(d) Show a trace, in the style of Figure 2.21, of a table-driven top-down parse of this same input.
(e) Now consider a recursive descent parser running on the same input.
At the point where the quote token (’) is matched, which recursive descent routines will be active (i.e., what routines will have a frame on the parser’s run-time stack)?
Figure 2.21:
Transcribed Image Text:
Parse stack Input stream Comment program read A read B ... initial stack contents predict program stmt list $$ predict stmtJist stmt stmt list stmt list $$ read A read B stmt stmt list $$ read A read B read id stmnt Jist $$ read A read B predict stmt + read id id stmt-list $$ A read B... match read stmt list $$ read B sum : match id stmt stmt Jist $$ predict stmt Jist – stmt stmt Jist read B sum: read id stmtlist $$ read B sum : predict stmt + read id id stmtlist $$ B sum :=... match read stmtlist $$ sum := A + B match id ... stmt stmt list $$ id := expr stmt_list $$ predict stmt Jist → stmt stmtlist predict stmt - id := expr sum := A + B sum := A + B := expr stmtlist $$ expr stmt list $$ term term_tail stmt list $$ factor factor_tail term.tail stmt.list $$ id factor_tail term_tail stmtlist $$ factor_tail term tail stmt list $$ := A + B... match id A + B... match := A + B predict expr + term term_tail predict term factor factor.tail predict factor id ... A + B A + B + B write sum match id + B write sum + B write sum + B write sum predict factor_tail € predict term tail + add_op term term tail predict add_op -+ term tail stmt list $$ add_op term term.tail stmt list $$ + term term tail stmtlist $$ term term_tail stmt.list $$ B write sum match + factor factor_tail term tail stmt.list $$ id factor_tail term_tail stmtlist $$ factor_tail term tail stmtlist $$ term tail stmt list $$ predict term + factor factor.tail predict factor +id B write sum B write sum write sum. write sum write .. predict factor_tail € match id predict term tail € predict stmtJist stmt stmt list predict stmt write expr stmtlist $$ write sum write ... write sum write... write sum write... stmt stmtlist $$ write expr stmt Jist $$ expr stmt list $$ term term_tail stmt.list $$ factor factor_tail term_tail stmt list $$ id factor_tail term tail stmt list $$ factor_tail term tail stmtlist $$ termtail stmt.list $$ sum write sum / 2 match write predict expr - term term tail predict term factor factor.tail predict factor id sum write sum / 2 sum write sum / 2 sum write sum / 2 write sum / 2 write sum / 2 write sum / 2 match id predict factor_tail € predict term tail € stmt list $$
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 60% (10 reviews)
a atom atom b c P E E Es cdr Es cdr E Es cdr E Es cdr E Es Es cdr ...View the full answer
Answered By
Gaurav Soni
Teaching was always an area where I can pursue my passion. I used to teach my friends and junior during my school and college life. After completing my professional qualification (chartered accountancy) and before joining my job, I also joined an organization for teaching and guidance to my juniors. I had also written some articles during my internship which later got published. apart from that, I have also given some presentations on certain amendments/complex issues in various forms.
Linkedin profile link:
https://www.linkedin.com/in/gaurav-soni-38067110a
5.00+
7+ Reviews
13+ Question Solved
Related Book For
Question Posted:
Students also viewed these Computer science questions
-
Consider the grammar S-ABCI DcA A a AdlEIc E ele C- cle D-dDlE 1. Show that the grammar has a predictive recursive descent parser. You should show that the conditions of predictive parsing apply for...
-
Consider the case study presented in Section 15.5 involving the Texago Corp. site selection problem. Texago management has tentatively chosen St. Louis as the site of the new refinery. However,...
-
Consider the grammar S A b C| D c A A a A d | E | f E e | C c | D d D | 3.1. Show that the grammar has a predictive recursive descent parser. You should show that the conditions of predictive...
-
9. Let x = (1.11... 111000...) 26, in which the fractional part has 26 1's followed by O's. For the Marc-32, determine x, x+, f(x), x-xx-x, xx, and lx-fl(x)/x.
-
Explain the behavioral and cognitive approaches to learning. Which is most relevant to training? Explain your answer.
-
For the data given in Problem 2: a. Plot the scaled frequency histogram. b. Compute the mean and standard deviation and use them to estimate the lower and upper limits of strength corresponding to 68...
-
An analysis of the accounts of Small Appliances Pty Ltd reveals the following manufacturing cost data for the month ended 30 June 2025. Required (a) Prepare the cost of goods manufactured schedule...
-
Phillips Industries runs a small manufacturing operation. For this fiscal year, it expects real net cash flows of $190,000. Phillips is an ongoing operation, but it expects competitive pressures to...
-
Find f'(x) and find the equation of the line tangent to the graph of f at x = 1. f(x)=(1+4x)(5-4x) f'(x)=
-
1. A Truck is purchased for $200,000 and is planned to have an operating life of 8 years working 5,000 hours per year. What is the hourly owning cost of this machine, assuming the company requires a...
-
Extend the grammar of Figure 2.25 to include if statements and while loops, along the lines suggested by the following examples: abs := n if n < 0 then abs := 0 - abs fi sum := 0 read count while...
-
Write top-down and bottom-up grammars for the language consisting of all well-formed regular expressions. Arrange for all operators to be left associative. Give Kleene closure the highest precedence...
-
An 8-kg plunger is released from rest in the position shown and is stopped by two nested springs; the constant of the outer spring is k1 = 3 kN/m and the constant of the inner spring is k2 = 10 kN/m....
-
Why was the problem of capital flight so serious in some highly indebted countries? What causes capital flight, and what do you think can be done about it?
-
Are rapid economic growth (as measured by either GNI or per capita GNI) and a more equal distribution of personal income necessarily conflicting objectives? Summarize the arguments both for and...
-
What are the main ideas of environmental accounting? If practiced, what effects would you expect to see?
-
There appears to be widespread agreement that in regions where the distribution of land ownership is highly unequal (mainly Latin America but also parts of Asia), land reform is a necessary but not...
-
What steps might governments in less developed countries take to reduce overexploitation of natural resources? What impact do pricing policies have?
-
After calculating the ratios for Smolira Golf, you have uncovered the following industry ratios for 2014: How is Smolira Golf performing based on these ratios? Lower Quartile Median Upper Quartile...
-
Outline a general process applicable to most control situations. Using this, explain how you would develop a system to control home delivery staff at a local pizza shop.
-
One queue implementation discussed in this chapter dedicated an unused cell before the front of the queue to distinguish between a full queue and an empty queue. Write another queue implementation...
-
Implement the following specification for an integer function in the client program that returns the number of items in a queue. The queue is unchanged. int GetLength(QueType queue) Function:...
-
Implement the following specification for a Boolean function in the client program that returns true if two queues are identical and false otherwise. You may use any of the member functions of...
-
A European call option for a share costs $5.00. The exercise price of the call option is $100.00. An investor buys one call and holds it until maturity: a. Under what circumstances will the holder of...
-
You have been asked to estimate the cost of capital for the UTX corporation. The company has 7 million shares and 150,000 bonds outstanding at par value $10,000. In addition, it has $300 million in...
-
MM Corp. has 50,000 shares outstanding with share price of $18. It has debt with market value of $300,000. The equity beta is 1.2 and debt beta is 0.1. The risk-free rate is 2% and the market risk...
Study smarter with the SolutionInn App