Section 1
a. Panic-mode error recovery
Panic-mode error recovery is based on the idea of skipping symbols on the the input until a token in a selected set of synchronizing tokens appears.
A bottom-up parse corresponds to the construction of a parse tree for an input string beginning at the leaves (the bottom) and working up towards the root (the top).
Recursive-descent parsing is a top-down method of syntax analysis in which a set of recursive procedures is used to process the input.
2.
a. Give example of 4 different type of strings that are accepted by the transition diagram.
DD, DD.DD ,DD.DE+DDD
b. Write a pseudocode to recognize the string of the transition diagram.
Section 2
1. Consider the following context-free grammar:
S -> SS + l SS* l a
a. Construct a parse tree to show how the string aa+a* can be generated by this grammar.
S ->S S * (2)
S ->a (3)
Production (3) allows you to generate a string S0 which consists of a.
b. Rewrite the grammar to eliminate the left factoring and left recursion in the grammar.
left factoring
S -> SG l a
G -> S+lS*
left recursion
S -> aS’
S -> GS’ l E
G -> S+lS*
c. What language does this grammar generate? Justify your answer.
Assuming a is an identifier for a numeric value, for example, then the grammar generates a language consisting of all possible arithmetic combinations of a using only the operations + and * and postfix notation.
2. Show that the string if E1 t"en ifE2 then SJ else S2 is ambiguous when it is parsed using the
following grammar.
I if expr then stmt else stmt
I other
Section 3
1.Fill in the table below with the First and Follow sets for the non-terminals in this
| First | Follow |
S | [ , a | + ,- ,c ,b ,],$ |
X | + , - , E | ] , c |
Y | - , E | b |
2. Show all the steps in order to produce a predictive parsing table for the following grammar:
NON-TERMINAL | INPUT SYMBOL | |||||
id | + | * | ( | ) | $ | |
E | | | E->T’ | | E->e | E’->e |
E’ | | E’->+TE’ | | | |
|
T | T->FT’ | | | T->FT’ | | |
T’ | | | T’->*F | | |
|
F | F->id | | | F->(E) | | |
3 comments:
Thanks Ray~haha..good luck for ur exam=)
thanks Ray~~~~love you so much...
the follow for T' is {+,),$} and F is {*,+,),$} for section 3 question 2
Post a Comment