Explanation of Solution
a.
Parse tree for the string foo (a, b):
Explanation of Solution
b.
Canonical (rightmost) derivation:
- Canonical derivation is a leftmost or rightmost derivations that may not be unique but they allow describing a derivation by the sequence of production rules taken.
- In the rightmost derivation, the rightmost nonterminal on the right hand side of a rule is replaced by a suitable rule.
- The complete derivation in this case is processed in the rightmost way.
Explanation of Solution
c.
Proof:
The EPS, FIRST, and FELLOW sets table for the above grammar:
Terminals and non-terminals | EPS | FIRST | FELLOW |
stmt | False | id | empty |
assignment | False | id | empty |
subr_call | False | id | empty |
expr | False | id, ( | ‘,’, ) |
expr_tail | True | +, -, *, / | ‘,’, ) |
primary | False | id, ( | +, -, *, / |
op | False | +, -, *, / | id, ( |
arg_list | False | id, ( | ) |
args_tail | True | ‘,’ | ) |
Now add the predict sets to the grammar above:
Parse table for the above grammar:
Id | := | ( | + | - | * | / | , | ) | |
stmt | 1, 2 | ||||||||
assignment | 3 | ||||||||
subr_call | 4 | ||||||||
expr | 5 | 5 | |||||||
expr_tail | - | 6 | 6 | 6 | 6 | 7 | 7 | ||
primary | 8, 9 | 10 | |||||||
op | - | 11 | 11 | 11 | 11 | ||||
arg_list | 12 | 12 | |||||||
args_tail | - | 13 | 14 |
- The entries in the above table indicates the production of predict. The “-” means an error.
- If the top-of-stack is terminal, the appropriate action is always to match it against an incoming token from the scanner.
The given grammar can’t be LL (1) because of confusion with “stmt” and “id”.
Explanation of Solution
d.
Modified grammar to make it is LL (1):
Factor out “id” from productions with “stmt” and “expr”.
Want to see more full solutions like this?
Chapter 2 Solutions
Programming Language Pragmatics, Fourth Edition
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education