TTTK2163 - COMPILERS Pass Year some Solution

Section 1

1. Write a brief description for the following terms:

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.

b. Bottom-up parsing

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).

c. Predictive Parser

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 + (1)

S ->S S * (2)

S ->a (3)

Production (3) allows you to generate a string S0 which consists of a.Using S0 as a starting point, production (1) allows you to generate a string S1 which consists of aa+.Production (3) again allows you to generate a string S2 which consists of a.Then production (2) allows you to generate a string S3 = S1S2* = aa+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.

stm! -> if exprthen stmt

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 grammar:

	First	Follow
S	[ , a	+ ,- ,c ,b ,],$
X	+ , - , E	] , c
Y	- , E	b

*the FOLLOW answer i not sure

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' ->e	T’->*F
F	F->id			F->(E)