Tcs 502 Assignment

COMPILER CONSTRUCTION (TCS502) ASSIGMENT NO. 1 OBJECTIVE :- Design & Implementation of Lexical Analyzer. MAIN ISSUE :- To develop a Lexical Analyzer one should possess the basic knowledge of the followings. (1) Lexical Analyzer’s Basic Mechanism. Source : by Aho,Ullman . (2) Basic Token Forming Technique. Source : by Aho,Ullman . (3) Specification of Tokens. Source : by Aho,Ullman . LANGUAGE FOR IMPLEMENTATION:- C (Block Structured ). INTERFACE OF LEXICAL ANALYZER:(1) push tokens & its attributes Read Character Input

Lexical Analyzer

Parser

Push back character (2) Input /Output

Lexeme( ) Lexical Analyzer

Returns tokens to Caller

Token Val MAIN FILES:- To develop the modules. (1) Lex.h To develop a Header File. (2) Lex.c To develop a module. (3) Plain.c To develop a module. (4) Improved.c To develop a module. (5) Improved1.c To develop a module. LINKING:- After developing all modules we need to link all them modules properly. Use link option Given by ‘C’ language.

COMPILER CONSTRUCTION (TCS502) Problems :Que1. Write a grammar that recognize c variable declaration made up of following keywords. Int, char, long, float, signed, unsigned Que2. Write a grammar that recognize c variable declaration made up only of following legal combinations of following keywords. Int, char, long, float, signed, unsigned Que3. Write a grammar (and a recursive-decent compiler for that grammer) that translate an English description of a c variable in to c style variable declaration. For example the input: X is a pointer to an array of 10 pointers to functions that returns int Y is an array of 10 floats Z is a pointer to struct of type a_struct Should be translated as Int (*(*x) [10] ) (); Float y[10]; Struct a_struct *z;

REFERENCES:(1) Aho,Ullman, Sethi ------ Compiler Construction. (2) Allen I.Holub-------------Compiler Construction.

COMPILER CONSTRUCTION (TCS502) ASSIGMENT NO. 2 OBJECTIVE :- Implementation of Context Free Grammar with ambiguity and without ambiguity using ‘C’. EXPLANATION:- The Syntax of a language may be specified using a notification called Context Free Grammar(CFG) consists of terminal, nonterminals, a start symbol and prediction rules. FOR Eg.:- Consider the following rules to describe a possible syntax for the block in a Pascal like languageCFG as follows: G=(T, N, S, P) Where T(G) is a finite, new empty set of terminals and tokens. Where N(G) is a finite, new empty set of non terminals and tokens. Where S(G) is a set containing non terminals. Where P(G) is a finite set of prediction rules. Problems :Que1. Show a step-by-step left most derivation of the following expressions 1+2* ((3+4) +5) +6 Que2. The following regular expressions recognizes a series of binary digits with pattern 000. use to terminate the series. (0/1)*000 Que3. Write a regular expressions that can recognize all possible integer constant in c all of the following should be recognized : 0x89ab 0123 45 ‘z’ ‘\t’ ‘\012’ LANGUAGE FOR IMPLEMENTATION:- C (Block Structured ).

COMPILER CONSTRUCTION (TCS502) ASSIGMENT NO. 3 OBJECTIVE :- Realization and Implementation of LL(1)Grammar and to complete the first and follow. EXPLANATION:- A Grammar whose parsing table has no multiple defined entities is said to be LL(1). The first “L” in LL(1) stands for scanning the input from the left to right the second “L” for producing a leftmost derivation and “1” for using one input symbol of look ahead at each step to make parsing action decision. FOR Eg.:-

For Grammar :E-> TE1 E1->+TE1/E T->FT1 T1->FT1/E F->(E)/id First (E) =First (T) =First(F)={c,id} First (E1)={+,E} First(T1)={*,E} Follow (E)=Follow (E1)=(,$} Follow(T)=Follow(T1)={+,,,$} Follow(F)={+,*,,,$}

Problems :Que1. Is the following grammar in LL(1)? why or why not? Or if it is not convert it in to LL(1) . E=E+T/ T T=T*F/ F F=(E)/ id Que2. Generate the LL(1) parsing table for the following grammar: S=iCtSS’/ a S’=eS/ e(null) C=b Que3. Find out the First and Follows of both Que1 and Que2. LANGUAGE FOR IMPLEMENTATION:- C (Block Structured ).

COMPILER CONSTRUCTION (TCS502) ASSIGMENT NO. 4 OBJECTIVE :- Implementation of Stack, Implementation of shift –reduce parsing using ‘C’. EXPLANATION:- A Convenient way to implement a shift reduce parser is to use a stack to held grammar symbols and an input buffer to held the string ‘W’ to be parsed.We use the $ to mark the bottom of the stack and also the right end of the input initially the stack is empty and the string ‘W’ is on the input as follows. STACK / $ IMPUT / W$ Right – Sentetial Form

Handle

Ruducing Production

id1+id2+id3

id1

$->id

$+id2*id3

id2

$->id

$+$*id3

id3

$->id

$+$*$

$*$

$->$*$

$+$

$+$

$->$+$

Problems :Que1. Consider the following grammar S=AS/ b A=SA/ a a) List all the LR(0) items for the above grammar. b) Construct an NFA whose states are LR(0) items from (a). show that the canonical collection of the LR(0) items for the grammar is same as the states of the equivalent DFA. c) Is the grammar SLR, is so construct the SLR parsing table. d) Is the grammar LALR? LL(1)? Que2. We might prefer to generate regular expressions using ambiguous grammar E=E+E/ EE/ E*/ (E)/ a/ b/ e(null) a) Give the ambiguity resolving declarations of the grammar. b) Construct the LALR parser for the following grammar. LANGUAGE FOR IMPLEMENTATION:- C (Block Structured ).

COMPILER CONSTRUCTION (TCS502) ASSIGMENT NO. 5 OBJECTIVE :- Implementations of three address code in C using quadruples. EXPLANATION:- A three address statement is an abstract form of intermediate code. In compiler there statements can be implemented as records with fields for the operators and operands. Quadruples Consider the four fields op,arg1,arg2 and result. Ex : a:=b*-c + b*-c op uniminus * uniminus * + :=

(0) (1) (2) (3) (4) (5)

arg1 c b c b t2 t5

arg2 t1 t3 t4

result t1 t2 t3 t4 t5 a

Problems :Que1. Implement the following expressions into quadruples using C language. (a) a+b+c*d/e+f (b) p+q*r+s*t (c) a*r+u*n+I+m*a Que2. Implement the following expressions in quadruples using C language. T1:= -B T2:= C+D T3:= T1*T2 A:= T1 Que3. Implement the following expressions in quadruples using C language. -(a+b)*(c+d)-(a+b+c)

COMPILER CONSTRUCTION (TCS502) ASSIGMENT NO. 6 OBJECTIVE :- Implementation of three address code using triples in C. EXPLANATION:-To avoid the entering temporary names into symbol table be might refer to a temporary value by the position of statement that computes it. It consist three fields op ,arg1,arg2. a:=b*-c + b*-c (0) (1) (2) (3) (4) (5)

op uniminus * uniminus * + assign

arg1 c b c b (1) a

arg2 (0) (2) (3) (4)

Problems :Que1. Implement the following expressions into quadruples using C language. (d) a+b+c*d/e+f (e) p+q*r+s*t (f) a*r+u*n+I+m*a Que2. Implement the following expressions in quadruples using C language. T1:= -B T2:= C+D T3:= T1*T2 A:= T1 Que3. Implement the following expressions in quadruples using C language. -(a+b)*(c+d)-(a+b+c)

COMPILER CONSTRUCTION (TCS502) ASSIGMENT NO. 7 OBJECTIVE :- Implement the following problems using C. EXPLANATION: using the facilities given by the block structured language C and using the mechanisms provided by c like parameter gassings through several methods, implement the following problems and justify your answers . The language may be Pascal also. Also use the scope rules provided by the C/PASCAL language. Using the following program segment answer the following problems: program a(input/output); procedure b(u,v,x,y:integer); var a: record a,b:integer end; b: record b,a:integer end; Begin With a do begin a:=u;b:=v end; with b do begin a:=x;b:=y end; writeln(a.a,a.b,b.a,b.b) end; begin b(1,2,3,4) end. Problems :Que1. What is printed by the program assuming

call-by-value,

Que2. What is printed by the program assuming

call-by-reference,

Que3. What is printed by the program assuming

copy-restore linkage,

Que4. What is printed by the program assuming

call-by-name.

Que5. Discuss the above parameters passing methods in detail in your answer sheet using at least 5 examples of each one. Que6. Discuss these methods in the following languages: ADA C++ C LISP FORTRAN

COMPILER CONSTRUCTION (TCS502)

ASSIGMENT NO. 8 OBJECTIVE: - Implement the following problems using C. EXPLANATION: using the facilities given by the block structured language C and using the mechanisms provided by c like parameter gassings through several methods, implement the following problems and justify your answers . The language may be Pascal also. Also use the scope rules provided by the C/PASCAL language. Using the following program segment answer the following problems: program main(input,output); procedure p(x,y,z); begin y:=y+1; z:=z+x; end; begin a:=2; b:=3; p(a+b,a,a); print a end. Problems :Que1. When a procedure is passed as a parameter in a lexically scoped language, its non-local environment can be passed using an access link. Give an algorithm to determine this link. Que2. The three kinds of environments that could be associated with a procedure passed as a parameter are illustrated by the Pascal program in Fig. given below.The lexical, passing and activation environments of such a procedure consists of the bindings of identifiers at the point at which the procedure is defined, passed as a parameter, and activated; respectively. Consider function f, passed as a parameter on line 11. (1) (2) (3) (4) (5) (6) (7) (8) (9)

program param(input, output); procedure b( function h)n: integer): integer); var m : integer: begin m := 3; writeln(h(2)) end {b}; procedure c; var m : integer: function f(n: integer): integer; begin f := m+n end {f}; procedure r;

COMPILER CONSTRUCTION (TCS502) (10) (11) (12) (13) (14) (15)

var m : integer: begin m := 7; b(f) end {r}; begin m := 0; r end {c}; begin c end

Using the lexical, parsing, and activation environments for f, non-local m on line 8 is in the scope of the declarations of m on lines 6, 10, and 3, respectively. a) Draw the activation tree for this program. b) What is the output of the program, using the lexical, passing , and activation environments for f? c) Modify the display implementation of a lexically scoped language to set up the lexical environment correctly when a procedure passed as a parameter is activated. Que3. Discuss about the Dangling References along with appropriate example. Que4. Discuss about the -- Call by value. -- Call by reference -- Call by value result -- Call by copy store

COMPILER CONSTRUCTION (TCS502) ASSIGMENT NO. 9 OBJECTIVE: - Using the facilities provided by the C Language Justify Your answers. EXPLANATION:Using the Knowledge of the compilation process and its all phases try to find out the best optimal solutions for the given problems .it includes the Syntax Directed Translation Schemes ,Run time Storage Administration and Basic Parsing Techniques as Discussed in the Aho,Ullman of compiler construction book. Try to implement these modules in C language IF Possible Problems :Q1: Translate the arithmetic expression a*-( b+c) into a) a syntax tree b) postfix notation c) three-address code Q2: Translate the expression -( a+b) * (c+d) +( a+b+c) into a) quadruples b) triples c) Indirect triples Q3: translate the executable statements of the following C program main() { int i ; int a[10]; i = 1; while (i<=10) { a[i] = 0; i = i+1; } } into a) a syntax tree b) postfix notation c) three-address code. Q4: The syntax directed definition in fig 8.24(Ullman Sethi) translates E-> id1 < id2 into pair of statements If id1 < id2 goto…… goto……. We could translate instead into the single statement If id1>= id2 goto_ & fall through the code when E is true. Modify the definition in fig 8.24 to generate code of this nature. Q5: Translate the following assignment statement into three-address code Using the translation scheme in section 8.3 (Ullman Sethi). A[i , j] :=B[i ,j] + C[A[k ,l]] + D[i+j]

COMPILER CONSTRUCTION (TCS502) Q6: In C, the for statement has the following form: for (e1 ; e2 ;e3 ) stmt Taking its meaning to be e1; while (e2) { stmt; e3; } Construct a syntax-directed definition to translate C-style for statements into three-address code. Q7: Consider the statement while a < b do if c < d then x := y + z else x := y – z obtain the code using control-flow translation of Boolean expressions. Q8: Using control-flow translation of Boolean expressions obtain the code of the following expression a < b or c < d and e < f