COMPILER

By Aditi Mam
Paper II June 2014

A grammar G is LL(1) if and only if the following conditions hold for

two distinct productions A → α | β
I. First (α) ∩ First (β) ≠ {a} where a is some terminal symbol of the
grammar.
II. First (α) ∩ First (β) ≠ λ
III. First (α) ∩ Follow(A) = φ if λ є First (β)
(A) I and II (B) I and III
(C) II and III (D) I, II and III
Paper II June 2014

A grammar G is LL(1) if and only if the following conditions hold for

two distinct productions A → α | β
I. First (α) ∩ First (β) ≠ {a} where a is some terminal symbol of the
grammar.
II. First (α) ∩ First (β) ≠ λ
III. First (α) ∩ Follow(A) = φ if λ є First (β)
(A) I and II (B) I and III
(C) II and III (D) I, II and III
Paper II June 2014

Which of the following suffices to convert an arbitrary CFG to an

LL(1) grammar ?

(A) Removing left recursion alone.

(B) Removing the grammar alone
(C) Removing left recursion and factoring the grammar
(D) None of the above
(D) None of the above

An ambiguous grammar can't be LL(1). Removing left recursion and

factoring the grammar not always guarantees the unambiguity of
grammar.
Paper II June 2014

A shift reduce parser suffers from

(A) shift reduce conflict only
(B) reduce reduce conflict only
(C) both shift reduce conflict and reduce reduce conflict
(D) shift handle and reduce handle conflicts
(C) both shift reduce conflict and reduce reduce conflict

A shift-reduce parser scans and parses the input text in one forward pass over the text,
without backing up.
A shift/reduce parser has two different actions it can take SHIFTING and REDUCING.
▪ Shift: the shift action is when the parser takes the first unanalyzed word from the
sentence, looks up its dictionary rule, and puts a token of category of the word onto
the stack.
▪ Reduce: the reduce action is when the parser tries to match the topmost category
tokens on the stack to the right hand side of the rule. If this succeeds, the tokens are
removed and a token for the category on the left hand side of the rule is put on the
stack instead.
Paper II June 2015

Which one from the following is false ?

a) LALR parser is Bottom - Up parser

b) A parsing algorithm which performs a left to right scanning and
a right most deviation is RL (1).
c) LR parser is Bottom - Up parser.
d) In LL(1), the 1 indicates that there is a one - symbol look -
ahead.
b) A parsing algorithm which performs a left to right scanning and a right most deviation is RL
(1).

RL(1) is not a parsing algo its LR(1)

Recursive descent
parser
Top down
parser
LL(1)
Parser

LR(0)
Parsers parser

SLR(1)
parser
LR parser
Bottom up LALR(1)
parser Operator parser
precedence
grammar CLR(1)
parser
Paper II June 2015

Which phase of compiler generates stream of atoms ?

(A) Syntax analysis

(B) Lexical Analysis
(C) Code generation
(D) Code optimization
(B) Lexical Analysis
Paper II December 2015

Which of the following statements is false?

(A) Top-down parsers are LL parsers where first L stands for left-to-right scan and
second L stands for a leftmost derivation.
(B) (000)* is a regular expression that matches only strings containing an odd
number of zeroes, including the empty string.
(C) Bottom-up parsers are in the LR family, where L stands for left-to-right scan
and R stands for rightmost derivation
(D) The class of context-free languages is closed under reversal. That is, if L is any
context-free language, then the language LR={WR:wϵL} is context free.
(B) Lexical Analysis
LL Parser LR Parser

First L of LL is for left to right and second L is for leftmost

L of LR is for left to right and R is for rightmost derivation.
derivation.

It follows the left most derivation. It follows reverse of right most derivation.

Using LL parser parser tree is constructed in top down manner. Parser tree is constructed in bottom up manner.

In LL parser, non-terminals are expanded. In LR parser, terminals are compressed.

Starts with the start symbol(S). Ends with start symbol(S).

Ends when stack used becomes empty. Starts with an empty stack.

Pre-order traversal of the parse tree. Post-order traversal of the parser tree.

Terminal is read after popping out of stack. Terminal is read before pushing into the stack.

It may use backtracking or dynamic programming. It uses dynamic programming.

LL is easier to write. LR is difficult to write.

Example: LL(0), LL(1) Example: LR(0), SLR(1), LALR(1), CLR(1)

Paper II January 2017

Consider the following statements related to compiler construction:

I. Lexical Analysis is specified by context-free grammars and implemented by

pushdown automata.
II. Syntax Analysis is specified by regular expressions and implemented by
finite-state machine.

Which of the above statement(s) is/are correct?

(1) Only l (2) Only ll

(3) Both I and II (4) Neither I nor Il
(4) Neither I nor Il
Paper II November 2017
Match the description of several parts of a classic optimizing compiler in List - I, with the names of
those parts in List - II:

Code:
(a) (b) (c) (d) (a) (b) (c) (d)
(1) (iii) (iv) (i) (ii) (2) (iv) (iii) (ii) (i)
(3) (ii) (iv) (i) (iii) (4) (ii) (iv) (iii) (i)
(1) (iii) (iv) (i) (ii)
Phases of Compiler Responsibilities

Lexical Analysis It is accountable for terminating the comments and white spaces from the source program.
It helps in identifying the tokens.
Categorization of lexical units.
Syntax Analysis Note syntax errors.
Helps in building a parse tree.
Acquire tokens from the lexical analyzer.
Scan the syntax errors, if any.
Semantic Analysis Saving collected data to symbol tables or syntax trees.
It notifies semantic errors.
Scanning for semantic errors.

Intermediate Code Helps in maintaining the priority ordering of the source language.
Generation Translate the intermediate code into the machine code.
Having operands of instructions.
Code optimizer Remove the unused variables and unreachable code.
Enhance runtime and execution of the program.
Produce streamlined code from the intermediate expression.

Code Generator Translate the intermediate code to target machine code.

Select and allocate memory spots and registers.
Paper II July 2018

A bottom-up parser generates:

(1) Left-most derivation in reverse

(2) Right-most derivation in reverse
(3) Left-most derivation
(4) Right-most derivation
(2) Right-most derivation in reverse
Top-Down Parsing Bottom-Up Parsing

It is a parsing strategy that first looks at the highest It is a parsing strategy that first looks at the lowest
level of the parse tree and works down the parse tree level of the parse tree and works up the parse tree by
by using the rules of grammar. using the rules of grammar.

Bottom-up parsing can be defined as an attempt to

Top-down parsing attempts to find the left most
reduce the input string to the start symbol of a
derivations for an input string.
grammar.

In this parsing technique we start parsing from the top In this parsing technique we start parsing from the
(start symbol of parse tree) to down (the leaf node of bottom (leaf node of the parse tree) to up (the start
parse tree) in a top-down manner. symbol of the parse tree) in a bottom-up manner.

This parsing technique uses Right Most Derivation in

This parsing technique uses Left Most Derivation.
reverse.

The main decision is to select when to use a

The main leftmost decision is to select what
production rule to reduce the string to get the starting
production rule to use in order to construct the string.
symbol.

Example: Recursive Descent parser. Example: Shift Reduce parser.

Paper II June 2019

Shift-reduce parser consists of

(1) input buffer

(2) stack
(3) parse table

Choose the correct option from those given below:

(a) (1) and (2) only (b) (1) and (3) only
(c) (3) only (d) (1), (2) and (3)
(d) (1), (2) and (3)

SR parser is a bottom up parser. It consists of input buffer, stack, parse table. Where
Input buffer is used for storing strings to be parsed, stack is used for holding
grammar symbols and parse table is used for parsing the string.
Nov 2021

Given below are two statements

Statement I: LL(1) and LR are examples of Bottom-up parsers.

Statement II: Recursive descent parser and SLR are examples of Top-down parsers

In light of the above statements, choose the correct answer from the options given below

a) Both Statement I and Statement II are false

b) Both Statement I and Statement II are true
c) Statement I is false but Statement II is true
d) Statement I is true but Statement II is false
a) Both Statement I and Statement II are false

Parsers

Top
Bottom
down
up parser
parser

Recursive LL(1) LR Operator

descent precedenc
parser Parser parser e grammar

LR(0) SLR(1) LALR(1) CLR(1)

parser parser parser parser
Oct 2022
Consider the following statements:

Statement I: SLR parser is more powerful than LALR .

Statement II: LALR parser is more powerful than canonical LR parse.

Which of the following is correct

a) Statement I true and Statement II false

b) Statement I false and Statement II true
c) Both Statement I and Statement II false
d) Both Statement I and Statement II true
c) Both Statement I and Statement II false

Important Notes
Even though CLR parser does not have RR
conflict but LALR may contain RR conflict.
2. If number of states LR(0) = n1, number
of states SLR = n2, number of states
LALR = n3, number of states CLR = n4
then, n1 = n2 = n3 <= n4
March 2023

The item generated by the production A → ε is:

A. A→.
B. A → ε.
C. A → .ε
D. A→ε
March 2023

The item generated by the production A → ε is:

A. A→.
B. A → ε.
C. A → .ε
D. A→ε
June 2023

Which phase of compiler checks the grammar of programming?

1. Code optimization
2. Semantic analysis
3. Code generators
4. Syntax analysis
June 2023

Which phase of compiler checks the grammar of programming?

1. Code optimization
2. Semantic analysis
3. Code generators
4. Syntax analysis
June 2023

Which of the following parser is most powerful parser?

1. Operator precedence
2. SLR
3. Canonical LR
4. LALR
3. Canonical LR
June 2023

The compiler for high level language that runs on one machine and
produces code for other machine is called-

1. Cross compiler
2. Multipass compiler
3. Optimizing Compiler
4. One pass Compiler
1. Cross compiler

A cross compiler is a compiler capable of creating executable code for a platform

other than the one on which the compiler is running. For example, a compiler that
runs on a PC but generates code that runs on an Android smartphone is a cross
compiler.
DEC 2023
One of the purposes of using intermediate code in compilers is to:

(1) make parsing and semantic analysis simpler

(2) improve error recovery and error reporting
(3) increase the chances of reusing the machine independent code
optimizer in other compilers
(4) improve the register allocation
DEC 2023
One of the purposes of using intermediate code in compilers is to:

(1) make parsing and semantic analysis simpler

(2) improve error recovery and error reporting
(3) increase the chances of reusing the machine independent code
optimizer in other compilers
(4) improve the register allocation
Arrange the following phases of a compiler as per their order of execution
(start to end)

(A) Target code generation

(B) Syntax Analysis
(C) Code optimization
(D) Semantic Analysis
(E) Lexical Analysis

Choose the correct answer from the options given below :

(1) (B), (E), (D), (A), (C) (2) (E), (D), (B), (A), (C)
(3) (E), (B), (D), (C), (A) (4) (B), (D), (Ε), (A), (C)
(3) (E), (B), (D), (C), (A)
Three address codes can be represented in special structures known as:

(A) Quadruples
(B) Triples
(C) Patterns
(D) Indirect Triples

Choose the correct answer from the options given below:

(1) (A) and (B) Only (2) (A), (B) and (D) Only
(3) (B) and (C) Only (4) (B), (C) and (D) Only
(2) (A), (B) and (D) Only
Quadruples: The quadruples structure is
Triples: In triples, the operation is defined in
similar to the triples structure, but it includes
one row by three fields: op (the operation),
an additional field for the result so that each
arg1 and arg2 (the arguments), and result (the
operation does not depend on its physical
place to store the resulting operation). Each
position in the sequence. This makes it easier
row, or instruction, is implicitly defined by its
to carry out transformations on the code
position in the table. So, if there is an
sequence, as this additional field for the result
instruction like 'sub a, b', it means 'subtract b
gives more flexibility, particularly in the
from a’.
process of optimization.

Indirect Triples: Indirect triples use the

concept of triples but give the advantage of
quadruples. It decouples the usage of an
expression from its physical location in the
sequence. It consists of a position-
independent data structure like quadruples,
which can effectively alter the sequence of
expressions without modifying the triples.
Match List - I with List - II according to input to the compiler phase that process it:

List - I List - II
(A) Syntax tree (I) Code generator
(B) Intermediate (II) Semantic analyzer representation
(C) Token stream (III) Lexical analyze
(D) Character stream. (IV) Syntax analyser

Choose the correct answer from the options given below:

(1) (A)-(IV), (B)-(III), (C)-(I), (D)-(II)
(2) (A)-(II), (B)-(I), (C)-(IV), (D)-(III)
(3) (A)-(II), (B)-(IV), (C)-(I), (D)-(III)
(4) (A)-(IV), (B)-(1), (C)-(II), (D)-(III)
(2) (A)-(II), (B)-(I), (C)-(IV), (D)-(III)