Introduction to Compiling

INTRODUCTION TO COMPILING

1. Define a compiler?

2. Describe the AnalysisSynthesis Model of compilation.

3. Define a symbol table.

4. What are the functions of preprocessors?

5. Define Assembly Code.

6. Define tokens, Patterns and lexemes.

7. What are the possible errorrecovery actions in lexical Analyzer?

8. What are the three general approaches to the implementation of a Lexical Analyzer?

9. Define a Sentinel.

10. Describe briefly rational preprocessors with an example.

11. What are the reasons for separating the analysis phase of compiling into Lexical

analysis and parsing?

12. What is the function of a loader?

13. Give the diagrammatic representation of a language processing system.

14. Explain briefly the producer consumer pair of a lexical analyzer and parser.

15. Mention the issues in a lexical analyzer.

16. Mention some of the cousins of the compiler.

17. What are rational preprocessors?

18.Differentiate Parse tree and Syntax tree.

LEXICAL ANALYZER

1. Explain in detail about the role of Lexical analyzer with the possible error

Recovery actions.

2. (a)Describe the following software tools

i. Structure Editors ii. Pretty printers iii. Interpreters

(b)Write in detail about the cousins of the compiler.

3. Describe in detail about input buffering. What are the tools used for constructing a

compiler?

4. (a)Explain the functions of the Lexical Analyzer with its implementation.

(b)Elaborate specification of tokens.

5. (a)What is a compiler? Explain the various phases of compiler in detail, with a neat

sketch.

(b) Elaborate on grouping of phases in a compiler.

6. (a) Explain the various phases of a compiler in detail. Also write down the output for

the following expression after each phase a: =b*cd. (8)

(b) What are the phases of the compiler? Explain the phases in detail. Write down the

output of each phase for the expression a: = b +c * 50.

7. Define a token, pattern ,lexeme

8.Describe language denoted by the following regular expression:0(0/1)*0
9. Describe language denoted by the following regular expression:(0/1)*0(0/1)(0/1)
10. Describe language denoted by the following regular expression:
(00/11)*((01/10)(00/11)*(01/10)(01/10)(00/11)*)*
11. Describe language denoted by the following regular expression: 0*a0*a0*a0*
12. Write the regular definition for the following language: "All strings of digits with no repeated

digits"
13. Give an example for ambiguous grammar and justify it.
14. Write regular definition for a number which can have fraction or exponent part as optional.
15. For the following grammar:
list --> list+digit / list-digit / digit
digit --> 0/1/...... /9
Derive the sentence (9+5-4) using left-most derivation.

16. What is the use of sentinels?
17. Write the algorithm for moving forward pointer in "input buffering" scheme using sentinels.

18. What is the use of lexeme- beginning pointer and forward pointer?
19. What is the need for input buffering?
20. What is the need for input buffering?

SYNTAX ANALYSIS

1. Draw a NFA for a*|b*.

2. What do you mean by Handle Pruning?

3. Define LR (0) items.

4. What do you mean by viable prefixes?

5. Define handle.

6 What are the algebraic properties of regular expressions?

7 What is finite automata?

8 What are the goals of error handler in a parser?

9 What is an ambiguous grammar? Give an example.

10.What is phrase level error recovery?

11.What are the disadvantages of operator precedence parsing?

12.What is a predictive parser?

13.Eliminate left recursion from the following grammar A->Ac/Aad/bd/c.

14.What is LL (1) grammar? Give the properties of LL (1) grammar.

15.Give the algorithm for Left Factoring a Grammar.

16.What is Left Recursion? Give an example for eliminating the same.

17 What is FIRST and FOLLOW? Explain in detail with an example.

18 Construct Predictive Parsing table for the following grammar:

the necessary algorithm.

S -> (L)/ a

L -> L, S/S

and check whether the following sentences belong to that grammar or not.

(i) (a,a)

(ii) (a, (a , a))

(iii) (a,((a,a),(a,a)))

19 (a) Construct the predictive parser for the following grammar:

S -> (L)|a L -> L,S|S.

(b) Construct the behaviour of the parser on sentence (a, a) using the grammar:

S -> (L)|a L -> L,S|S.

20. (a) Check whether the following grammar is SLR (1) or not. Explain your answer with

reasons.

S-> L+R S->R L->*R L->id R->L (8)

(b) For the grammar given below, calculate the operator precedence relation and the

precedence functions.

E-E+E|E –E|E*E|E/E|E^E|(E)| E|id

21. Check whether the following grammar is a LL(1) grammar

S -> iEtS | iEtSeS | a E-> b Also define the FIRST and FOLLOW procedures

22. (a) Consider the grammar given below.

E->E+T E->T T->T*F T->F F->(E) F->id. Construct an LR Parsing table for the above

grammar. Give the moves of LR parser on id*id+id.

(b) What is a shift reduce parser? Explain in detail the conflicts that may occur during

shift reduce parsing.

23. Explain the process of constructing an NFA from the regular expression.
Find the NFA for the expression (a/b)*abb.

24. Mention the error recovery strategies of parser

25. What is a handle?
26. What is handle pruning?

27. What is the need for separating the parser from scanner?
28. Translate the arithmetic expression a*-(b+c) into a syntax tree.

29. Explain LALR parsing, justify how it is efficient over SLR parsing .

INTERMEDIATE CODE GENERATION

0.How would you represent the following equation using the DAG,

a: =b*c + b*c. What is the purpose of DAG?

1 What is the intermediate code representation for the expression a or b and not c ?

2 How would you map names to Values?

3 What are the various methods of implementing three address statements?

4 Suggest a Suitable approach for completing hash function.

5 What are the methods of representing a syntax tree?

6 Give the Syntax directed definition of ifelse statement.

7 What is back patching?

8 What are the applications of DAG?

10. Define marker nonterminals with an example.

11. Why are quadruples preferred over triples in an optimizing Complier?

12. Give the triple representation of a ternary operation x:= y[i]

13. Give the Semantic rules for the production S _ while E do S1.

14. Let A be a 10x20 array with low1=low2=1. Therefore n1=10 and n2=20. Take w to be 4.

Give the annotated parse tree for the assignment x:=A[y,z]

15. What is short-circuit or jumping code?

16 How would you generate the intermediate code for the flow of control

statements? Explain with examples.

17(a) What are the various ways of calling procedures? Explain in detail.

(b)What is a three address code? Mention its types. How would you implement the

three address statements? Explain with examples.

18. How would you generate intermediate code for the flow of control statements? Explain

With examples.

19. (a)Describe the method of generating syntax directed definition for Control statements

(b)Give the semantic rules for declarations in a procedure.

20. (a) How Back patching can be used the generate code for Boolean expressions and

flow of control statements.

(b)Explain how the types and relative addresses of declared names are computed and

how scope information is dealt with.

21. (a) Describe in detail the syntax directed translation of case statements.

(b) Explain in detail the translation of assignment statements.

22. Define a Quadruple.How it is different from Triples.
23.Convert the exp into three address code & Quadruple.
S=(a+b)/(c-d)*(e+f)
24.Write the prefix & postfix exp foe the following
A=(20+(-5)*6+12)

25. Translate the exp –(a+b)*(c+d)+(a+b+c) into
a) Quadruple
b) Triples
c) Indirect triples

QUESTIONS:

1. Write regular expressions for the following languages over the alphabet _ = {a, b}:

(a) All strings that do not end with aa.

(b) All strings that contain an even number of b’s.

2. Draw DFAs for each of the languages from question 1. None of your DFAs may contain more than 4states.

3. Consider the following non-deterministic finite automaton (NFA) over the alphabet ∑ = {0, 1}.

Give a one-sentence description of the language recognized by the NFA. Write a regular expression for this language.

4. Consider the string

abaabaabababbaaabaab

and its tokenization

abaa ba ababa bba aa ba a b

Give a flex specification with the minimum number of rules that produces this tokenization. Each flex rule should be as simple as possible as well. You may not use regular expression union (i.e., R1+R2 )in your solution. Do not give any actions; just assume that the rule returns the string that it matches.

5. Give a context-free grammar (CFG) for each of the following languages over the alphabet ∑ = {a,b}:

(a) All strings in the language L : {anbma2n|n,m ≥0}

(b) All nonempty strings that start and end with the same symbol.

(d) All palindromes (a palindrome is a string that reads the same forwards and backwards).

6. Consider the grammar below, with terminals fc; l; x; v; ig. c = 100; l = 50; x = 10; v = 5; i = 1.

Notice that we use lowercase characters here to represent the numerals, to distinguish them from non-terminals.

S -> xTU |lX | X

T -> c | l

X ->xX | U

U ->iY |vI | I

Y ->x | v

I -> iI |€

(a) Draw a parse tree for “xlvii".

(b) Is this grammar ambiguous?

for X ->A and X-> B) to calculate the decimal value of the input string. You can associate a

synthesized attribute val to each of the non-terminals to store their value. The final value should

be returned in S.val

6. (a) Left factor the following grammar:

E-> int | int + E | int - E | E -(E)

(b) Eliminate left-recursion from the following grammar:

A -> A + B | B

B ->int | (A)

7. Consider the following LL(1) grammar, which has the set of terminals T = {a,b, ep,+,*, (,)}. This grammar generates regular expressions over {a, b}, with + meaning the RegExp OR operator, and ep meaning the € symbol. (Yes, this is a context free grammar for generating regular expressions)

E -> TE’

E’-> +E |€

T -> FT’

T’-> T |€

F -> PF’

F’ -> * F’ | €

P -> (E) |a | b | ep

(a) Give the first and follow sets for each non-terminal.

(b) Construct an LL(1) parsing table for the left-factored grammar.

8. Consider the following CFG, which has the set of terminals T = {stmt, {, },;}. This grammar describes the organization of statements in blocks for a fictitious programming language. Blocks can have zero or more statements as well as other nested blocks, separated by semicolons, where the last semicolon is optional. (P is the start symbol here.)

P -> S

S ->stmt | {B

B -> } | S} | S;B

(a) Construct a DFA for viable prefixes of this grammar using LR(0) items.

(b) Identify any shift-reduce and reduce-reduce conflicts in this grammar under the SLR(1) rules.

operation of such a parser on the input string {stmt;}.