Question

Problem 3.

Let G be the grammar we saw in homework 3:

E -> E + T | E - T | T

T -> T * F | F

F -> ( E ) | x | y

Let w be (x + y) * x - y

a) Show the leftmost derivation for w in G. Number the rules for G and show the corresponding rule number under each substitution arrow in the derivation.

Hint: it may be easier to create a parse tree first, as you did in homework 3

b) Convert G to a string-pushing PDA, call it D_G; show a transition diagram for D_G. There will be one reduce transition for each terminal symbol in G and one shift transition for each rule in G.

Label all transitions in D_G as follows:

• T_i and T_f for the initial and final transitions

• R_c for a reduce transition that reads terminal symbol c

• S_k for a shift transition that corresponds to rule numbered k in G

c) Show an accepting computation for w in D_G as a table. This table will one row per transition, and 4 columns: remaining input, current state, stack contents, and next transition. For example, the first row in your table will be (w, q₀, e, T_i)

Hint: use your derivation from part (a) to help you choose the shift transitions

Answer 1

the shift reduce parsing of the given string has been done in the figure above. In that figure initially this content is dollar which represent the bottom of the stack. The input string initially is the given string in the question. In step by step process we first take the imput string contents to the stack and as and when the string in the stack becomes eligible for the reduced operation through the given grammar, we reduce it immediately in a reduced step as shown in the figure above. This procedure goes on until we pass the whole of input string and finally the the string is reduced to a single start symbol. Here we got the start symbol as E. And now the stack is empty and the passing is over and hence we accept the string.

To easily create the table for stack contents and action performed, we will make a purse tree in which we will do left hand derivation starting from the start symbol to get to the given input string in a step by step use of the given grammar.