2023 105601

B.Tech. 6th Semester Examination, 2023

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.
Symbols used (if any) have their usual meanings.

Q.1 Answer any seven questions of the following:

Q1.1

Which of the following is the most powerful parser?

a)

SLR

b)

LALR

c)

Canonical LR

d)

Operator precedence

Q1.2

A top down parser generates

a)

Rightmost derivation

b)

Rightmost derivation in reverse

c)

Left most Derivation

d)

Left most derivation in reverse

Q1.3

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar: $ S \rightarrow xxW $ {print "1"}, $ S \rightarrow y $ {print "2"}, $ S \rightarrow Sz $ {print "3"}. What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

a)

23131

b)

11233

c)

11231

d)

33211

Q1.4

Three-address code involves

a)

Exactly 3 address

b)

At most 3 addresses

c)

No unary operator

d)

None

Q1.5

Handle pruning forms the basis of

a)

Bottom up parsing

b)

Top down parsing

c)

Predictive parsing

d)

Recursive descent parsing

Q1.6

Left factoring guarantees

a)

Not occurring of backtracking

b)

Cycle free parse tree

c)

Error free target code

d)

Correct LL(1) parsing table

Q1.7

Consider a grammar $ A \rightarrow aS_1 | aS_2 $. The left factored grammar produced from the grammar is

a)

$A' \rightarrow aA, A \rightarrow S_1 | S_2$

b)

$A' \rightarrow aA, A \rightarrow aS_1 | aS_2$

c)

$A' \rightarrow S_1 | S_2, A \rightarrow S_1 | S_2$

d)

None of these

Q1.8

Synthesized attributes are calculated

a)

From the values of attributes of the children of the node

b)

From the values of attributes of the parent of the node

c)

From the values of attributes of the siblings of the node

d)

None of these

Q1.9

The method which merges the bodies of two loops is

a)

Loop rolling

b)

Loop Jamming

c)

Constant folding

d)

None of the above

Q1.10

For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if

a)

The LALR (1) parser for G has S-R conflicts

b)

The LR(0) parser for G has S-R conflicts

c)

The SLR(1) parser for G has S-R conflicts

d)

The SLR(0) parser for G has S-R conflicts

Q.2 Solve both questions :

Q2.1

Explain the working of each phase of compiler in detail with an example.

Q2.2

What is an activation record? Explain how they are used to access various local and global variables.

Q.3 Solve all questions :

Q3.1

What are the advantages of LALR parsing over SLR and CLR methods?

Q3.2

Write the algorithm to compute FIRST and FOLLOW for a given grammar.

Q3.3

What is shift-reduce conflict?

Q.4 Solve both questions :

Q4.1

Given the Syntax-Directed Definition below with the synthesized attribute val. Draw the annotated parse tree for the expression $ (3+4)*(5+6) $:
$ L \rightarrow E $ ; $ L.val = E.val $
$ E \rightarrow T $ ; $ E.val = T.val $
$ E \rightarrow E_1 + T $ ; $ E.val = E_1.val + T.val $
$ T \rightarrow F $ ; $ T.val = F.val $
$ T \rightarrow T_1 * F $ ; $ T.val = T_1.val * F.val $
$ F \rightarrow (E) $ ; $ F.val = E.val $
$ F \rightarrow digit $ ; $ F.val = digit.lexval $

Q4.2

Find the FIRST and FOLLOW from the following production:
$ S \rightarrow aBDh $
$ B \rightarrow cC $
$ C \rightarrow bC | \epsilon $
$ D \rightarrow EF $
$ E \rightarrow g | \epsilon $
$ F \rightarrow f | \epsilon $

Q.5 Solve both questions :

Q5.1

Construct the predictive parsing table for the following grammar:
$ S \rightarrow A $
$ A \rightarrow aB | Ad $
$ B \rightarrow bBC | f $
$ C \rightarrow cg $

Q5.2

Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement: $ a = (a*b+c)\wedge(b+c)*b+c $

Q.6 Solve all questions :

Q6.1

What is handle? Consider the grammar: $ E \rightarrow E+E | E*E | id $. Find the handles of the right sentential forms of the reduction for the string $ id_1 + id_2 * id_3 $.

Q6.2

When a grammar is called ambiguous? Is there any technique to remove ambiguity? Justify whether the grammar is ambiguous or not: $ A \rightarrow AA | (A) | a $

Q6.3

Discuss about operator precedence parser.

Q.7 Solve both questions :

Q7.1

Differentiate between S-attribute SDT and L-attribute SDT with suitable examples.

Q7.2

Consider the following grammar: $ E \rightarrow E+T | T $, $ T \rightarrow T*F | F $, $ F \rightarrow id $. Draw a SLR state transition diagram for the above grammar. Also draw the SLR parse table.

Q.8 Solve both questions :

Q8.1

Consider the following grammar: $ S \rightarrow CC $, $ C \rightarrow cC | d $. Find the LR(1) set of items.

Q8.2

Translate the expression $ a=(a+b)*(c+d)+(a+b+c) $ into (i) Quadruple (ii) Triple (iii) Indirect triple.

Q.9 Write short notes on any two of the following:

Q9.1

a)

LEX and YACC

b)

Peephole Optimization

c)

Symbol Table

d)

Predictive parser

2023 V2 105601

B.Tech. 6th Semester Examination, 2023

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.
Symbols used (if any) have their usual meanings.

Q.1 Answer any seven questions of the following:

Q1.1

Which of the following is the most powerful parser?

a)

SLR

b)

LALR

c)

Canonical LR

d)

Operator precedence

Q1.2

A top down parser generates

a)

Rightmost derivation

b)

Rightmost derivation in reverse

c)

Left most Derivation

d)

Left most derivation in reverse

Q1.3

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar: $S \rightarrow xxW$ {print "1"}, $ S \rightarrow y ${print "2"},$ S \rightarrow Sz $ {print "3"}. What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

a)

23131

b)

11233

c)

11231

d)

33211

Q1.4

Three-address code involves

a)

Exactly 3 address

b)

At most 3 addresses

c)

No unary operator

d)

None

Q1.5

Handle pruning forms the basis of

a)

Bottom up parsing

b)

Top down parsing

c)

Predictive parsing

d)

Recursive descent parsing

Q1.6

Left factoring guarantees

a)

Not occurring of backtracking

b)

Cycle free parse tree

c)

Error free target code

d)

Correct LL(1) parsing table

Q1.7

Consider a grammar $A \rightarrow aS_1 | aS_2$ . The left factored grammar produced from the grammar is

a)

$A' \rightarrow aA, A \rightarrow S_1 | S_2$

b)

$A' \rightarrow aA, A \rightarrow aS_1 | aS_2$

c)

$A' \rightarrow S_1 | S_2, A \rightarrow S_1 | S_2$

d)

None of these

Q1.8

Synthesized attributes are calculated

a)

From the values of attributes of the children of the node

b)

From the values of attributes of the parent of the node

c)

From the values of attributes of the siblings of the node

d)

None of these

Q1.9

The method which merges the bodies of two loops is

a)

Loop rolling

b)

Loop Jamming

c)

Constant folding

d)

None of the above

Q1.10

For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if

a)

The LALR (1) parser for G has S-R conflicts

b)

The LR(0) parser for G has S-R conflicts

c)

The SLR(1) parser for G has S-R conflicts

d)

The SLR(0) parser for G has S-R conflicts

Q.2 Solve both questions :

Q2.1

Explain the working of each phase of compiler in detail with an example.

Q2.2

What is an activation record? Explain how they are used to access various local and global variables.

Q.3 Solve all questions :

Q3.1

What are the advantages of LALR parsing over SLR and CLR methods?

Q3.2

Write the algorithm to compute FIRST and FOLLOW for a given grammar.

Q3.3

What is shift-reduce conflict?

Q.4 Solve both questions :

Q4.1

Given the Syntax-Directed Definition below with the synthesized attribute val. Draw the annotated parse tree for the expression $(3+4)*(5+6)$ :
$L \rightarrow E$ ; $ L.val = E.val $
$E \rightarrow T$ ; $ E.val = T.val $
$E \rightarrow E_1 + T$ ; $ E.val = E_1.val + T.val $
$T \rightarrow F$ ; $ T.val = F.val $
$T \rightarrow T_1 * F$ ; $ T.val = T_1.val * F.val $
$F \rightarrow (E)$ ; $ F.val = E.val $
$F \rightarrow digit$ ; $F.val = digit.lexval$

Q4.2

Find the FIRST and FOLLOW from the following production:
$ S \rightarrow aBDh $
$ B \rightarrow cC $
$ C \rightarrow bC | \epsilon $
$ D \rightarrow EF $
$ E \rightarrow g | \epsilon $
$F \rightarrow f | \epsilon$

Q.5 Solve both questions :

Q5.1

Construct the predictive parsing table for the following grammar:
$ S \rightarrow A $
$ A \rightarrow aB | Ad $
$ B \rightarrow bBC | f $
$C \rightarrow cg$

Q5.2

Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement: $a = (a*b+c)\wedge(b+c)*b+c$

Q.6 Solve all questions :

Q6.1

What is handle? Consider the grammar: $E \rightarrow E+E | E*E | id$ . Find the handles of the right sentential forms of the reduction for the string $id_1 + id_2 * id_3$ .

Q6.2

When a grammar is called ambiguous? Is there any technique to remove ambiguity? Justify whether the grammar is ambiguous or not: $A \rightarrow AA | (A) | a$

Q6.3

Discuss about operator precedence parser.

Q.7 Solve both questions :

Q7.1

Differentiate between S-attribute SDT and L-attribute SDT with suitable examples.

Q7.2

Consider the following grammar: $E \rightarrow E+T | T$ , $T \rightarrow T*F | F$ , $F \rightarrow id$ . Draw a SLR state transition diagram for the above grammar. Also draw the SLR parse table.

Q.8 Solve both questions :

Q8.1

Consider the following grammar: $S \rightarrow CC$ , $C \rightarrow cC | d$ . Find the LR(1) set of items.

Q8.2

Translate the expression $a=(a+b)*(c+d)+(a+b+c)$ into (i) Quadruple (ii) Triple (iii) Indirect triple.

Q.9 Write short notes on any two of the following:

Q9.1

LEX and YACC
Peephole Optimization
Symbol Table
Predictive parser

a)

LEX and YACC

b)

Peephole Optimization

c)

Symbol Table

d)

Predictive parser

2022 105601

B.Tech. 6th Semester Examination, 2022

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer for any seven of the following :

Q1.1

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

a)

Leftmost derivation

b)

Leftmost derivation traced out in reverse

c)

Rightmost derivation

d)

Rightmost derivation traced out in reverse

Q1.2

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type $ A \rightarrow \epsilon $ and $ A \rightarrow a $) to parse a string with n tokens?

a)

$n/2$

b)

$n-1$

c)

$2n-1$

d)

$2^n$

Q1.3

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

a)

always be evaluated

b)

be evaluated only if the definition is L-attributed

c)

be evaluated only if the definition has synthesized attributes

d)

never be evaluated

Q1.4

Consider the grammar shown below : $ S \rightarrow CC $, $ C \rightarrow cC | d $. The grammar is

a)

LL(1)

b)

SLR(1) but not LL(1)

c)

LALR(1) but not SLR(1)

d)

LR(1) but not LALR(1)

Q1.5

The lexical analyzer takes _____ as input and produces a stream of _____ as output.

a)

source program, tokens

b)

token, source program

c)

Either of the two

d)

None of the above

Q1.6

In a compiler, when is the keywords of a language are recognized?

a)

During the lexical analysis of a program

b)

During parsing of the program

c)

During the code generation

d)

During the data flow analysis

Q1.7

How many tokens are there in the following C statement?
printf("j=%d, & j=%x", j, & j)

a)

4

b)

5

c)

10

d)

None of the above

Q1.8

How is the parsing precedence relation defined?

a)

To delimit the handle

b)

Only for a certain pair of terminal

c)

None of the above

d)

All of the above

Q1.9

Given the following expression grammar : $ E \rightarrow E*F | F+E | F $, $ F \rightarrow F-F | id $. Which of the following is true?

a)

has higher precedence than +

b)

has higher precedence than *

c)

and - have same precedence

d)

has higher precedence than *

Q1.10

Shift reduce parsers are

a)

top-down parser

b)

bottom-up parser

c)

may be top-down or bottom-up

d)

None of the above

Q.2 Solve both questions :

Q2.1

Write a lexical analyzer program to identify strings, sequences, comments, reserved words and identifiers.

Q2.2

Explain about the sources and criterions of code optimization as machine dependent and independent types.

Q.3 Solve both questions :

Q3.1

Construct the non-recursive predictive parse table for the given grammar and check the acceptance of input string "abfcg":
$ S \rightarrow A $
$ A \rightarrow aB | Ad $
$ B \rightarrow bBC | f $
$ C \rightarrow cg $

Q3.2

What is the relationship with lexical analyzer, regular expressions and transition diagram? Give an example.

Q.4 Solve both questions :

Q4.1

Explain the type system in type checker. Write the syntax directed definition for type checker.

Q4.2

What is activation record? Explain its usage in stack allocation strategy. How is it different from heap allocation?

Q.5 Solve both questions :

Q5.1

Draw and explain the runtime memory organization static storage allocation strategy with pros and cons.

Q5.2

Differentiate inherited and synthesized attributes with an example.

Q.6 Solve both questions :

Q6.1

Define dataflow analysis. List out the procedures to analyze the data flow of structured programs.

Q6.2

Draw a block diagram of phases of a compiler and indicate the main functions of each phase.

Q.7 Solve both questions :

Q7.1

What is intermediate code? Translate the expression $ (a+b)/(c+d)*(a+b/c)-d $ into quadruples, triples and indirect triples.

Q7.2

Explain reducible and non-reducible flow graphs with an example each.

Q.8 Solve both questions :

Q8.1

What is machine-dependent optimization? Explain how peephole techniques function in this.

Q8.2

Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement: $ a=(a*b+c)\wedge(b+c)*b+c $

Q.9 Explain the following with suitable example :

Q9.1

a)

Function preserving optimization techniques

b)

Reference counting garbage collectors

c)

Elimination of loop invariant variable

d)

Strength reduction

2022 V2 105601

B.Tech. 6th Semester Examination, 2022

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer for any seven of the following :

Q1.1

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

a)

Leftmost derivation

b)

Leftmost derivation traced out in reverse

c)

Rightmost derivation

d)

Rightmost derivation traced out in reverse

Q1.2

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type $A \rightarrow \epsilon$ and $ A \rightarrow a $) to parse a string with n tokens?

a)

$n/2$

b)

$n-1$

c)

$2n-1$

d)

$2^n$

Q1.3

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

a)

always be evaluated

b)

be evaluated only if the definition is L-attributed

c)

be evaluated only if the definition has synthesized attributes

d)

never be evaluated

Q1.4

Consider the grammar shown below : $S \rightarrow CC$ , $C \rightarrow cC | d$ . The grammar is

a)

LL(1)

b)

SLR(1) but not LL(1)

c)

LALR(1) but not SLR(1)

d)

LR(1) but not LALR(1)

Q1.5

The lexical analyzer takes _____ as input and produces a stream of _____ as output.

a)

source program, tokens

b)

token, source program

c)

Either of the two

d)

None of the above

Q1.6

In a compiler, when is the keywords of a language are recognized?

a)

During the lexical analysis of a program

b)

During parsing of the program

c)

During the code generation

d)

During the data flow analysis

Q1.7

How many tokens are there in the following C statement?
printf("j=%d, & j=%x", j, & j)

a)

4

b)

5

c)

10

d)

None of the above

Q1.8

How is the parsing precedence relation defined?

a)

To delimit the handle

b)

Only for a certain pair of terminal

c)

None of the above

d)

All of the above

Q1.9

Given the following expression grammar : $E \rightarrow E*F | F+E | F$ , $ F \rightarrow F-F | id $. Which of the following is true?

a)

has higher precedence than +

b)

has higher precedence than *

c)

and - have same precedence

d)

has higher precedence than *

Q1.10

Shift reduce parsers are

a)

top-down parser

b)

bottom-up parser

c)

may be top-down or bottom-up

d)

None of the above

Q.2 Solve both questions :

Q2.1

Write a lexical analyzer program to identify strings, sequences, comments, reserved words and identifiers.

Q2.2

Explain about the sources and criterions of code optimization as machine dependent and independent types.

Q.3 Solve both questions :

Q3.1

Construct the non-recursive predictive parse table for the given grammar and check the acceptance of input string "abfcg":
$ S \rightarrow A $
$ A \rightarrow aB | Ad $
$ B \rightarrow bBC | f $
$C \rightarrow cg$

Q3.2

What is the relationship with lexical analyzer, regular expressions and transition diagram? Give an example.

Q.4 Solve both questions :

Q4.1

Explain the type system in type checker. Write the syntax directed definition for type checker.

Q4.2

What is activation record? Explain its usage in stack allocation strategy. How is it different from heap allocation?

Q.5 Solve both questions :

Q5.1

Draw and explain the runtime memory organization static storage allocation strategy with pros and cons.

Q5.2

Differentiate inherited and synthesized attributes with an example.

Q.6 Solve both questions :

Q6.1

Define dataflow analysis. List out the procedures to analyze the data flow of structured programs.

Q6.2

Draw a block diagram of phases of a compiler and indicate the main functions of each phase.

Q.7 Solve both questions :

Q7.1

What is intermediate code? Translate the expression $(a+b)/(c+d)*(a+b/c)-d$ into quadruples, triples and indirect triples.

Q7.2

Explain reducible and non-reducible flow graphs with an example each.

Q.8 Solve both questions :

Q8.1

What is machine-dependent optimization? Explain how peephole techniques function in this.

Q8.2

Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement: $a=(a*b+c)\wedge(b+c)*b+c$

Q.9 Explain the following with suitable example :

Q9.1

Function preserving optimization techniques
Reference counting garbage collectors
Elimination of loop invariant variable
Strength reduction

a)

Function preserving optimization techniques

b)

Reference counting garbage collectors

c)

Elimination of loop invariant variable

d)

Strength reduction

2019 051516

B.Tech. 5th Semester Examination, 2019

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

When is the type checking usually done?

a)

During syntax directed translation

b)

During lexical analysis

c)

During code optimization

d)

During syntax analysis

Q1.2

Which one of the following statements is true?

a)

Canonical LR parser is more powerful than LALR parser.

b)

SLR parser is more powerful than LALR.

c)

LALR parser is more powerful than canonical LR parser.

d)

SLR parser, canonical LR parser and LALR parser all have the same power.

Q1.3

In a compiler, _____ checks every character of the source text.

a)

the lexical analyzer

b)

the syntax analyzer

c)

the code generator

d)

the code optimizer

Q1.4

For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if

a)

the LR(1) parser for G has S-R conflicts

b)

the LR(0) parser for G has S-R conflicts

c)

the SLR(1) parser for G has S-R conflicts

d)

the SLR(0) parser for G has S-R conflicts

Q1.5

In an absolute loading scheme, which loader function is accomplished by programmer?

a)

Allocation

b)

Linking

c)

Reallocation

d)

Both (i) and (ii)

Q1.6

_____ is a top-down parser.

a)

Operator precedence parser

b)

An LALR (k) parser

c)

An LR (k) parser

d)

Recursive descent parser

Q1.7

The languages that need heap allocation in the runtime environment are those that

a)

use global variables

b)

use dynamic scoping

c)

support recursion

d)

allow dynamic data structure

Q1.8

In compilers, generation of intermediate code based on an abstract machine model is useful because

a)

syntax-directed translations can be written for intermediate code generation

b)

to generate code for real machines directly from high-level language program is not possible

c)

portability of the front end of the compiler is enhanced

d)

implementation of lexical and syntax analyses is easier

Q1.9

To convert an arbitrary CFG to an LL(1) grammar

a)

factor the grammar alone

b)

remove left recursion alone

c)

remove left recursion and factor the grammar

d)

None of the above

Q1.10

The method which merges the bodies of two loops is

a)

loop rolling

b)

loop jamming

c)

constant folding

d)

None of the above

Q.2 Solve both questions :

Q2.1

What is an activation record? Explain how they are used to access various local and global variables.

Q2.2

What is bottom-up parsing? Discuss shift reduce parsing technique in brief. What is a handle?

Q.3 Solve both questions :

Q3.1

What is left recursion? Eliminate the left recursion from the following grammar:
$ E \rightarrow E+T | T $
$ T \rightarrow T*F | F $
$ F \rightarrow (E) | id $

Q3.2

What is the use of a symbol table? How are the identifiers stored in the symbol table?

Q.4 Solve both questions :

Q4.1

What is the pass of a compiler? Explain how the single- and multi-pass compilers work.

Q4.2

Explain architecture and algorithm for the non-recursive predictive parser.

Q.5 Solve both questions :

Q5.1

Check whether the following grammar is CLR or not:
$ S \rightarrow Aa | bBa | Ba | bAc $
$ A \rightarrow c $
$ B \rightarrow d $

Q5.2

What is the syntax directed translation and why are they important?

Q.6 Solve both questions :

Q6.1

Explain different phases of compiler.

Q6.2

Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement:
$ a=(a*b+c)\wedge(b+c)*b+c $

Q.7 Solve both questions :

Q7.1

Explain various targets for code optimization with examples.

Q7.2

How are CPU registers allocated while creating machine code?

Q.8 Solve both questions :

Q8.1

Check whether the following grammar is LL(1) grammar or not:
$ S \rightarrow iEtSA | a $
$ A \rightarrow eS | \epsilon $
$ E \rightarrow b $

Q8.2

Design the FIRST SET and FOLLOW SET for the grammar.

Q.9 Solve both questions :

Q9.1

Differentiate between S-attribute SDT and L-attribute SDT with suitable examples.

Q9.2

Explain any two of the following:

a)

Lexical phase error

b)

Code generation using dynamic programming

c)

Syntax tree

2019 V4 051516

B.Tech. 5th Semester Examination, 2019

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer of the following (any seven):

Q1.1

When is the type checking usually done?

a)

During syntax directed translation

b)

During lexical analysis

c)

During code optimization

d)

During syntax analysis

Q1.2

Which one of the following statements is true?

a)

Canonical LR parser is more powerful than LALR parser.

b)

SLR parser is more powerful than LALR.

c)

LALR parser is more powerful than canonical LR parser.

d)

SLR parser, canonical LR parser and LALR parser all have the same power.

Q1.3

In a compiler, _____ checks every character of the source text.

a)

the lexical analyzer

b)

the syntax analyzer

c)

the code generator

d)

the code optimizer

Q1.4

For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if

a)

the LR(1) parser for G has S-R conflicts

b)

the LR(0) parser for G has S-R conflicts

c)

the SLR(1) parser for G has S-R conflicts

d)

the SLR(0) parser for G has S-R conflicts

Q1.5

In an absolute loading scheme, which loader function is accomplished by programmer?

a)

Allocation

b)

Linking

c)

Reallocation

d)

Both (i) and (ii)

Q1.6

_____ is a top-down parser.

a)

Operator precedence parser

b)

An LALR (k) parser

c)

An LR (k) parser

d)

Recursive descent parser

Q1.7

The languages that need heap allocation in the runtime environment are those that

a)

use global variables

b)

use dynamic scoping

c)

support recursion

d)

allow dynamic data structure

Q1.8

In compilers, generation of intermediate code based on an abstract machine model is useful because

a)

syntax-directed translations can be written for intermediate code generation

b)

to generate code for real machines directly from high-level language program is not possible

c)

portability of the front end of the compiler is enhanced

d)

implementation of lexical and syntax analyses is easier

Q1.9

To convert an arbitrary CFG to an LL(1) grammar

a)

factor the grammar alone

b)

remove left recursion alone

c)

remove left recursion and factor the grammar

d)

None of the above

Q1.10

The method which merges the bodies of two loops is

a)

loop rolling

b)

loop jamming

c)

constant folding

d)

None of the above

Q.2 Solve both questions :

Q2.1

What is an activation record? Explain how they are used to access various local and global variables.

Q2.2

What is bottom-up parsing? Discuss shift reduce parsing technique in brief. What is a handle?

Q.3 Solve both questions :

Q3.1

What is left recursion? Eliminate the left recursion from the following grammar:
$ E \rightarrow E+T | T $
$ T \rightarrow T*F | F $
$ F \rightarrow (E) | id $

Q3.2

What is the use of a symbol table? How are the identifiers stored in the symbol table?

Q.4 Solve both questions :

Q4.1

What is the pass of a compiler? Explain how the single- and multi-pass compilers work.

Q4.2

Explain architecture and algorithm for the non-recursive predictive parser.

Q.5 Solve both questions :

Q5.1

Check whether the following grammar is CLR or not:
$ S \rightarrow Aa | bBa | Ba | bAc $
$ A \rightarrow c $
$ B \rightarrow d $

Q5.2

What is the syntax directed translation and why are they important?

Q.6 Solve both questions :

Q6.1

Explain different phases of compiler.

Q6.2

Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement:
$ a=(a*b+c)\wedge(b+c)*b+c $

Q.7 Solve both questions :

Q7.1

Explain various targets for code optimization with examples.

Q7.2

How are CPU registers allocated while creating machine code?

Q.8 Solve both questions :

Q8.1

Check whether the following grammar is LL(1) grammar or not:
$ S \rightarrow iEtSA | a $
$ A \rightarrow eS | \epsilon $
$ E \rightarrow b $

Q8.2

Design the FIRST SET and FOLLOW SET for the grammar.

Q.9 Solve both questions :

Q9.1

Differentiate between S-attribute SDT and L-attribute SDT with suitable examples.

Q9.2

Explain any two of the following:

a)

Lexical phase error

b)

Code generation using dynamic programming

c)

Syntax tree

2018 051616

B.Tech. 6th Semester Examination, 2018

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer for any seven of the following:

Q1.1

What is the number of tokens in the following C statement? printf("I=%d and I=%x",I and I)

a)

3

b)

26

c)

10

d)

21

Q1.2

Consider the following two statements: P: Every regular grammar is LL(1). Q: Every regular set has LR(1) grammar. Which of the following is true?

a)

Both P and Q are true

b)

P is true and Q is false

c)

P is false and Q is true

d)

Both P and Q are false

Q1.3

What is the similarity between LR, LALR and SLR?

a)

Use of same algorithm, but different parsing table

b)

Same parsing table, but different algorithm

c)

Their parsing tables and algorithms are similar but use top-down approach

d)

Both parsing tables and algorithms are different

Q1.4

Consider the following grammar: $ S \rightarrow aSbS | bSaS | \epsilon $. How many different parse trees are possible for string ababab?

a)

2

b)

3

c)

4

d)

5

Q1.5

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar: $ S \rightarrow xxW $ {PRINT "1"}, $ S \rightarrow y $ {print "2"}, $ S \rightarrow Sz $ {print "3"}. What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

a)

23131

b)

11233

c)

11231

d)

33211

Q1.6

The most powerful parser is

a)

SLR

b)

LALR

c)

Canonical LR

d)

Operator-precedence

Q1.7

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

a)

$(L \cup D)^*$

b)

$L(L \cup D)^*$

c)

$(L.D)^*$

d)

$L.(L.D)^*$

Q1.8

In operator precedence parsing, precedence relations are defined

a)

for all pairs of non-terminals

b)

for all pairs of terminals

c)

to delimit the handle

d)

None of the above

Q1.9

A bottom-up parser generates

a)

right-most derivation

b)

right-most derivation in reverse

c)

left-most derivation

d)

left-most derivation in reverse

Q1.10

A grammar that produces more than one parse tree for some sentence is called

a)

ambiguous

b)

unambiguous

c)

regular

d)

None of the above

Q.2 Solve both questions :

Q2.1

What do you understand by left recursion and left factoring? How are these eliminated? Explain with the help of suitable example.

Q2.2

What do you understand by bootstrapping? Explain with the help of suitable example.

Q.3 Solve all questions :

Q3.1

How can addressing modes be used for reducing the memory access time?

Q3.2

What are activation records? Explain its purpose in compilers.

Q3.3

What are the optimization techniques applied on procedures calls? Explain with an example.

Q.4 Solve both questions :

Q4.1

Given the Syntax-Directed Definition below with the synthesized attribute val. Draw the annotated parse tree for the expression $ (3+4)*(5+6) $:
$ L \rightarrow E $ ; $ L.val = E.val $
$ E \rightarrow T $ ; $ E.val = T.val $
$ E \rightarrow E_1+T $ ; $ E.val = E_1.val+T.val $
$ T \rightarrow F $ ; $ T.val = F.val $
$ T \rightarrow T_1*F $ ; $ T.val = T_1.val*F.val $
$ F \rightarrow (E) $ ; $ F.val = E.val $
$ F \rightarrow digit $ ; $ F.val = digit.lexval $

Q4.2

Construct a Syntax-Directed Translation scheme that translates arithmetic expressions from infix into postfix notation. Your solution should include the context-free grammar, the semantic attributes for each of the grammar symbols, and semantic rules. Show the application of your scheme to the input "3*4+5*2".

Q.5 Solve all questions :

Q5.1

What is the advantage of using machine independent intermediate representation during translation process?

Q5.2

Explain, with example, what three address codes are. Give some common three address statements.

Q5.3

Find the three address codes of the following program. There are four bytes per word:
Sum = 0
For(i = 1; i <= 20; i++)
Sum = Sum + a[i] + b[i];

Q.6 Solve all questions :

Q6.1

Find the CNF (Chomsky Normal Form) for the following CFG:
$ S \rightarrow ABA $
$ A \rightarrow aA | \epsilon $
$ B \rightarrow bB | \epsilon $

Q6.2

Eliminate null productions from the following CFG:
$ S \rightarrow Xa $
$ X \rightarrow aX | bX | \epsilon $

Q6.3

Convert the following grammar to GNF :
$ A_1 \rightarrow A_2A_3 $
$ A_2 \rightarrow A_3A_1 | b $
$ A_3 \rightarrow A_1A_2 | a $

Q.7 Solve all questions :

Q7.1

What are the advantages of LALR parsing over SLR and CLR methods?

Q7.2

Write the algorithm to compute FIRST and FOLLOW for a given grammar.

Q7.3

What is shift-reduce conflict?

Q.8 Solve this question :

Q8.1

What are intermediate codes in compilers? Why is it needed in compiler design? Discuss different types of intermediate codes generated by intermediate code generation phase.

Q.9 Solve both questions :

Q9.1

What is parsing? What is the difference between Top-down parsing, Bottom-up parsing and Predictive parsing?

Q9.2

Explain the working of each phase of compiler in detail with an example.

2018 V4 051616

B.Tech. 6th Semester Examination, 2018

Time 03 Hours

Full Marks 70

Instructions:

The marks are indicated in the right-hand margin.
There are NINE questions in this paper.
Attempt FIVE questions in all.
Question No. 1 is compulsory.

Q.1 Choose the correct answer for any seven of the following:

Q1.1

What is the number of tokens in the following C statement? printf("I=%d and I=%x",I and I)

a)

3

b)

26

c)

10

d)

21

Q1.2

Consider the following two statements: P: Every regular grammar is LL(1). Q: Every regular set has LR(1) grammar. Which of the following is true?

a)

Both P and Q are true

b)

P is true and Q is false

c)

P is false and Q is true

d)

Both P and Q are false

Q1.3

What is the similarity between LR, LALR and SLR?

a)

Use of same algorithm, but different parsing table

b)

Same parsing table, but different algorithm

c)

Their parsing tables and algorithms are similar but use top-down approach

d)

Both parsing tables and algorithms are different

Q1.4

Consider the following grammar: $ S \rightarrow aSbS | bSaS | \epsilon $. How many different parse trees are possible for string ababab?

a)

2

b)

3

c)

4

d)

5

Q1.5

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar: $ S \rightarrow xxW $ {PRINT "1"}, $ S \rightarrow y $ {print "2"}, $ S \rightarrow Sz $ {print "3"}. What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

a)

23131

b)

11233

c)

11231

d)

33211

Q1.6

The most powerful parser is

a)

SLR

b)

LALR

c)

Canonical LR

d)

Operator-precedence

Q1.7

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

a)

$(L \cup D)^*$

b)

$L(L \cup D)^*$

c)

$(L.D)^*$

d)

$L.(L.D)^*$

Q1.8

In operator precedence parsing, precedence relations are defined

a)

for all pairs of non-terminals

b)

for all pairs of terminals

c)

to delimit the handle

d)

None of the above

Q1.9

A bottom-up parser generates

a)

right-most derivation

b)

right-most derivation in reverse

c)

left-most derivation

d)

left-most derivation in reverse

Q1.10

A grammar that produces more than one parse tree for some sentence is called

a)

ambiguous

b)

unambiguous

c)

regular

d)

None of the above

Q.2 Solve both questions :

Q2.1

What do you understand by left recursion and left factoring? How are these eliminated? Explain with the help of suitable example.

Q2.2

What do you understand by bootstrapping? Explain with the help of suitable example.

Q.3 Solve all questions :

Q3.1

How can addressing modes be used for reducing the memory access time?

Q3.2

What are activation records? Explain its purpose in compilers.

Q3.3

What are the optimization techniques applied on procedures calls? Explain with an example.

Q.4 Solve both questions :

Q4.1

Given the Syntax-Directed Definition below with the synthesized attribute val. Draw the annotated parse tree for the expression $ (3+4)*(5+6) $:
$ L \rightarrow E $ ; $ L.val = E.val $
$ E \rightarrow T $ ; $ E.val = T.val $
$ E \rightarrow E_1+T $ ; $ E.val = E_1.val+T.val $
$ T \rightarrow F $ ; $ T.val = F.val $
$ T \rightarrow T_1*F $ ; $ T.val = T_1.val*F.val $
$ F \rightarrow (E) $ ; $ F.val = E.val $
$ F \rightarrow digit $ ; $ F.val = digit.lexval $

Q4.2

Construct a Syntax-Directed Translation scheme that translates arithmetic expressions from infix into postfix notation. Your solution should include the context-free grammar, the semantic attributes for each of the grammar symbols, and semantic rules. Show the application of your scheme to the input "3*4+5*2".

Q.5 Solve all questions :

Q5.1

What is the advantage of using machine independent intermediate representation during translation process?

Q5.2

Explain, with example, what three address codes are. Give some common three address statements.

Q5.3

Find the three address codes of the following program. There are four bytes per word:
Sum = 0
For(i = 1; i <= 20; i++)
Sum = Sum + a[i] + b[i];

Q.6 Solve all questions :

Q6.1

Find the CNF (Chomsky Normal Form) for the following CFG:
$ S \rightarrow ABA $
$ A \rightarrow aA | \epsilon $
$ B \rightarrow bB | \epsilon $

Q6.2

Eliminate null productions from the following CFG:
$ S \rightarrow Xa $
$ X \rightarrow aX | bX | \epsilon $

Q6.3

Convert the following grammar to GNF :
$ A_1 \rightarrow A_2A_3 $
$ A_2 \rightarrow A_3A_1 | b $
$ A_3 \rightarrow A_1A_2 | a $

Q.7 Solve all questions :

Q7.1

What are the advantages of LALR parsing over SLR and CLR methods?

Q7.2

Write the algorithm to compute FIRST and FOLLOW for a given grammar.

Q7.3

What is shift-reduce conflict?

Q.8 Solve this question :

Q8.1

What are intermediate codes in compilers? Why is it needed in compiler design? Discuss different types of intermediate codes generated by intermediate code generation phase.

Q.9 Solve both questions :

Q9.1

What is parsing? What is the difference between Top-down parsing, Bottom-up parsing and Predictive parsing?

Q9.2

Explain the working of each phase of compiler in detail with an example.

2017 051616

B.Tech. 6th Semester Examination, 2017

Time 03 Hours

Full Marks 70

Instructions:

There are Nine Questions in this Paper.
Attempt Five questions in all.
Question No. 1 is Compulsory.
The marks are indicated in the right-hand margin.

Q.1 Answer any seven questions:

Q1.1

A grammar that produces more than one parse tree for some sentence is said to be

a)

Ambiguous

b)

context free

c)

disambiguous

d)

regular

Q1.2

What is not the phase of a compiler?

a)

Syntax analyzer

b)

code generator

c)

code optimizer

d)

code linker

Q1.3

Given a grammar $ G=(\{E\}, \{id, +\}, P, E) $; where P is given by $ E \rightarrow E+E | id $. Then FOLLOW(E) will contain

a)

{ $ }

b)

{ + }

c)

{ $, + }

d)

{ $, id, + }

Q1.4

Which of the following expressions has no l-value?

a)

a[i+1]

b)

a

c)

3

d)

*a

Q1.5

Consider the statement "fi (x>=10)", where 'if' has been misspelled. The error is detected by the compiler in the phase

a)

lexical analysis

b)

syntax analysis

c)

semantic analysis

d)

syntactic analysis

Q1.6

Which of the following is not a loop optimization?

a)

Induction variable elimination

b)

Loop unrolling

c)

Loop jamming

d)

Loop heading

Q1.7

If x is a terminal then FIRST(x) is

a)

$\epsilon$

b)

{ x }

c)

$x^*$

d)

$xx^*$

Q1.8

Consider following grammar $ S \rightarrow cAd $, $ A \rightarrow ab | a $. For input string cad, how many times the recursive descent parser will backtrack?

a)

2

b)

3

c)

4

d)

5

Q1.9

The optional access link in the activation record is used for

a)

Pointing to the activation record of the caller

b)

Referring the non-local data held in other activation records

c)

Temporary values, such as those arising in the evaluation of expressions

d)

Pointing to the activation record of the calling procedure.

Q1.10

Suppose two productions are there: $ A \rightarrow \alpha $ and $ A \rightarrow \beta $. The recursive descent parsing without backtracking requires:

a)

first($ \alpha $) and first($ \beta $) must be in same set

b)

first($ \alpha $) and first($ \beta $) to be disjoint

c)

first($ \alpha $) and first($ \beta $) must be equal

d)

Data insufficient

Q.2 Solve this question :

Q2.1

Construct DFA for $ (ab^* | ba^*) $ and minimize the number of states of the above constructed DFA.

Q.3 Solve both questions :

Q3.1

A grammar is given below:
$ S \rightarrow A $
$ A \rightarrow aB | Ad $
$ B \rightarrow bBC | f $
$ C \rightarrow g $
Find the FIRST and FOLLOW set.

Q3.2

Construct a predictive parsing table for the grammar given above.

Q.4 Solve this question :

Q4.1

What is a symbol table? Why is it needed in compiler design? Explain different components of a symbol table with an example.

Q.5 Solve both questions :

Q5.1

Consider the following program fragment:
prod = 0;
i = 1;
do {
prod = prod + a[i] * b[i];
i = i + 1;
} while (i <= 20);
Generate the three-address code for the above program fragment.

Q5.2

Determine the basic blocks for the computed three-address code.

Q.6 Solve this question :

Q6.1

What is DAG? What is the use of DAG in compiler construction? Construct a DAG for the following statements:
$ Z = X - Y + X * Y $
$ U = V / W + X + V $

Q.7 Solve both questions :

Q7.1

Explain peephole optimization in detail.

Q7.2

Suppose a basic block is formed from the C assignment statements:
$ x = a + b + c + d + e + f; $
$ y = a + c + e; $
(a) Give the three-address statements (only one addition per statement) for this block.
(b) Use the associative and commutative laws to modify the block to use the fewest possible number of instructions, assuming both $ x $ and $ y $ are live on exit from the block.

Q.8 Solve all questions :

Q8.1

Given the grammar $ G = (S, \{S, A, B\}, \{a, b, c, d\}, P) $ with set of productions $ P $ below compute;

                </p><p>a. LR(1) sets of items.</p>

b. Compute the corresponding parsing table for the corresponding shift-reduce parse engine.

c. Show the actions of the parsing engine as well as the contents of the symbol and state stacks for the input string $ w = \text{"bdac"} $.

d. Is this grammar LALR(1)? Justify.

$ S \rightarrow Aa | bAc | Bc | bBa $
$ A \rightarrow d $
$ B \rightarrow d $
Do not forget to augment the grammar with the production $ S' \rightarrow S $.

Q.9 Write short note on (any two) of the following:

Q9.1

a)

Syntax-directed definition and translation schemes

b)

Handling Reserved Keywords

c)

Bottom Up Parsing

2017 V4 051616

B.Tech. 6th Semester Examination, 2017

Time 03 Hours

Full Marks 70

Instructions:

There are Nine Questions in this Paper.
Attempt Five questions in all.
Question No. 1 is Compulsory.
The marks are indicated in the right-hand margin.

Q.1 Answer any seven questions:

Q1.1

A grammar that produces more than one parse tree for some sentence is said to be

a)

Ambiguous

b)

context free

c)

disambiguous

d)

regular

Q1.2

What is not the phase of a compiler?

a)

Syntax analyzer

b)

code generator

c)

code optimizer

d)

code linker

Q1.3

Given a grammar $ G=(\\{E\\}, \\{id, +\\}, P, E) $; where P is given by $ E \rightarrow E+E | id $. Then FOLLOW(E) will contain

a)

{ $ }

b)

{ + }

c)

{ $, + }

d)

{ $, id, + }

Q1.4

Which of the following expressions has no l-value?

a)

a[i+1]

b)

a

c)

3

d)

*a

Q1.5

Consider the statement "fi (x>=10)", where 'if' has been misspelled. The error is detected by the compiler in the phase

a)

lexical analysis

b)

syntax analysis

c)

semantic analysis

d)

syntactic analysis

Q1.6

Which of the following is not a loop optimization?

a)

Induction variable elimination

b)

Loop unrolling

c)

Loop jamming

d)

Loop heading

Q1.7

If x is a terminal then FIRST(x) is

a)

$\epsilon$

b)

{ x }

c)

$x^*$

d)

$xx^*$

Q1.8

Consider following grammar $ S \rightarrow cAd $, $ A \rightarrow ab | a $. For input string cad, how many times the recursive descent parser will backtrack?

a)

2

b)

3

c)

4

d)

5

Q1.9

The optional access link in the activation record is used for

a)

Pointing to the activation record of the caller

b)

Referring the non-local data held in other activation records

c)

Temporary values, such as those arising in the evaluation of expressions

d)

Pointing to the activation record of the calling procedure.

Q1.10

Suppose two productions are there: $ A \rightarrow \alpha $ and $ A \rightarrow \beta $. The recursive descent parsing without backtracking requires:

a)

first($ \alpha $) and first($ \beta $) must be in same set

b)

first($ \alpha $) and first($ \beta $) to be disjoint

c)

first($ \alpha $) and first($ \beta $) must be equal

d)

Data insufficient

Q.2 Solve this question :

Q2.1

Construct DFA for $ (ab^* | ba^*) $ and minimize the number of states of the above constructed DFA.

Q.3 Solve both questions :

Q3.1

A grammar is given below:
$ S \rightarrow A $
$ A \rightarrow aB | Ad $
$ B \rightarrow bBC | f $
$ C \rightarrow g $
Find the FIRST and FOLLOW set.

Q3.2

Construct a predictive parsing table for the grammar given above.

Q.4 Solve this question :

Q4.1

What is a symbol table? Why is it needed in compiler design? Explain different components of a symbol table with an example.

Q.5 Solve both questions :

Q5.1

Consider the following program fragment:
prod = 0;
i = 1;
do {
prod = prod + a[i] * b[i];
i = i + 1;
} while (i <= 20);
Generate the three-address code for the above program fragment.

Q5.2

Determine the basic blocks for the computed three-address code.

Q.6 Solve this question :

Q6.1

What is DAG? What is the use of DAG in compiler construction? Construct a DAG for the following statements:
$ Z = X - Y + X * Y $
$ U = V / W + X + V $

Q.7 Solve both questions :

Q7.1

Explain peephole optimization in detail.

Q7.2

Suppose a basic block is formed from the C assignment statements:
$ x = a + b + c + d + e + f; $
$ y = a + c + e; $
(a) Give the three-address statements (only one addition per statement) for this block.
(b) Use the associative and commutative laws to modify the block to use the fewest possible number of instructions, assuming both $ x $ and $ y $ are live on exit from the block.

Q.8 Solve all questions :

Q8.1

Given the grammar $ G = (S, \\{S, A, B\\}, \\{a, b, c, d\\}, P) $ with set of productions $ P $ below compute;

                </p><p>a. LR(1) sets of items.</p>

b. Compute the corresponding parsing table for the corresponding shift-reduce parse engine.

c. Show the actions of the parsing engine as well as the contents of the symbol and state stacks for the input string $ w = \text{"bdac"} $.

d. Is this grammar LALR(1)? Justify.

$ S \rightarrow Aa | bAc | Bc | bBa $
$ A \rightarrow d $
$ B \rightarrow d $
Do not forget to augment the grammar with the production $ S' \rightarrow S $.