Pearson eText for Concepts of Programming Languages -- Instant Access (Pearson+)
12th Edition
ISBN: 9780135102268
Author: Robert Sebesta
Publisher: PEARSON+
expand_more
expand_more
format_list_bulleted
Expert Solution & Answer
Chapter 4, Problem 8PS
Explanation of Solution
Complete parse for the string “(id+id)*id” using the parse table:
The complete trace of the shift reduce parser including stack contents, input string, and action is shown below.
| Stack | Input | Action |
| 0 | (id+id)*id$ | Shift 4 |
| 0(4 | id+id)*id$ | Shift 5 |
| 0(4id5 | +id)*id$ | Reduce 6 (GOTO[4, F]) |
| 0(4F3 | +id)*id$ | Reduce 4 (GOTO[4, T]) |
| 0(4T2 | +id)*id$ | Reduce 2 (GOTO[4, E]) |
| 0(4E8 | +id)*id$ | Shift 6 |
| 0(4E8+6 | id)*id$ | Shift 5 |
| 0(4E8+6id5 |
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
Please use Prolog programming language
Bottom-up Parsing : Show a complete parse, including the parse stack contents, input string, and actions for the string id + (id * id + id) using the grammar and parse table
Design a context free grammar by your own. Construct a LL(1) parsing table using First and Follow and show stack movement for any one input string.
Chapter 4 Solutions
Pearson eText for Concepts of Programming Languages -- Instant Access (Pearson+)
Ch. 4 - Prob. 1RQCh. 4 - Prob. 2RQCh. 4 - Prob. 3RQCh. 4 - Prob. 4RQCh. 4 - Prob. 5RQCh. 4 - Prob. 6RQCh. 4 - Prob. 7RQCh. 4 - Prob. 8RQCh. 4 - Prob. 9RQCh. 4 - Prob. 10RQ
Ch. 4 - Prob. 11RQCh. 4 - Prob. 12RQCh. 4 - Prob. 13RQCh. 4 - Prob. 14RQCh. 4 - Prob. 15RQCh. 4 - Prob. 16RQCh. 4 - Prob. 17RQCh. 4 - Prob. 18RQCh. 4 - Prob. 19RQCh. 4 - Prob. 20RQCh. 4 - Prob. 21RQCh. 4 - Prob. 22RQCh. 4 - Prob. 23RQCh. 4 - What was Knuths insight in developing the LR...Ch. 4 - Prob. 25RQCh. 4 - Prob. 26RQCh. 4 - Is left recursion a problem for LR parsers?Ch. 4 - Prob. 1PSCh. 4 - Prob. 2PSCh. 4 - Prob. 3PSCh. 4 - Prob. 4PSCh. 4 - Prob. 7PSCh. 4 - Prob. 8PS
Knowledge Booster
Similar questions
- Draw the parse tree for expression a = b / (a+c).arrow_forwardBoth interpretation and code generation can be performed by traversal of a syntax tree. Compare these two kinds of traversals. In what ways are they similar/different?arrow_forwardCreate a BNF grammar using a parsimonious Python module. This should consist of a first name, space, and last name. The solution needs to be written in the Python programming language. After running the code it should draw a parse tree. Input examples: John Doe Bob Simonarrow_forward
- Subject: Compiler Design / Computer Science Note: Answer in your own words. copy from internet will not help me. Question: Consider the following grammar and input string,S → S+SS → S-SS → (S)S → a Input string: a1*(a2+a3)Find out the parsing table using shift reduce parsing.arrow_forward1.Given that, L = { start of all strings over a, b }. Construct CFG from this language.2.Determine the FIRST and FOLLOW sets from the production rules you used to construct the parse table. S --> A $ A --> - A B | id C B --> - B | " " C --> " " | idarrow_forward3. Given the following BNF grammar: -> d c | cd -> a la -> b | b Use the top-down recursive descent method which we discussed in the class to implement a parser (i.e. tdrd.parser.py) in python3 for the above BNF grammar. The input data file name is given from the command line. You may assume that there is a space character between two terminals (e.g. a a adc b ) in the data file.arrow_forward
- Answer the given question with a proper explanation and step-by-step solution.arrow_forwardDesign a PDA for the following language: L = {0*1³ | 0 < i < j < 2i}. Hint: remember we showed PDAS both for {a"b"} and {a"b?"}. However, to allow the string to have that range of number of b's, you need to use the nondeterminism: for each 0 push a symbol in the stack and allow the PDA to non-deterministically choose to match 1 or 2 b's to each a.arrow_forwardSubject: Compiler Design Consider the following grammar and input string, S → S+S S → S*S S → (S) S → a Input string: a1*(a2+a3) Find out the parsing table using shift reduce parsing.arrow_forward
- Write Prolog code for the following problems list-set(Lst, N,X,Ans) returns in Ans a list like Lst, except that the n-th element, using zero-based indexing,arrow_forwardGive a description of "Semantic augmentation" for the CFG (Context Free Grammar) rules and an illustration of it.arrow_forwardPlease help with this modification:2. Use the logic in that program to design your own Recursive Descent parser in C for the following grammar:S →aABA →Abc | bB →d3. Make sure that you choose at least two strings that pass the grammar and one string that does not pass the grammar just like I did in the model program4. Submit both the code and a screen shot of your results for the choice of strings that you provided. Below is the C code that can be used to implement a Recursive Descent parser for the above grammar/* Recursive Descent Parser for the Expression Grammar:S → (L) |aL' →,SL'|εL → SL'Valid inputs: (a,(a,a)) and (a,((a,a),(a,a)))Invalid inputs:(aa,a)*/#include <stdio.h>#include <string.h>int S(), Ldash(), L();char *ip;char string[50];int main() {printf("Enter the string\n");scanf("%s", string);ip = string;printf("\n\nInput\t\tAction\n ------------------------------\n");if…arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education