Compiler Design

Consider the statement: int total = 25; Which of the following represents a lexeme?

1. int
2. 25
3. total
4. All of the Above

The regular expression (a|b)* represents:

1. Strings containing only a
2. Strings containing only b
3. All strings over {a,b}, including ε
4. Strings beginning with ab

Which of the following is a problem for a top-down parser?

1. Left recursion
2. Right recursion
3. Ambiguity only
4. Bottom-up derivation

In bottom-up parsing, the parser constructs:

1. Leftmost derivation
2. Rightmost derivation
3. Reverse of a rightmost derivation
4. Leftmost derivation in reverse

Consider a symbol table implemented using hashing with table size 10. For key 27, using h(k) = k mod 10, the initial position is:

1. 5
2. 7
3. 6
4. 8

Under static scoping, the meaning of a variable reference is determined primarily by:

1. Runtime call sequence
2. CPU register contents
3. Heap location
4. Lexical program structure

Which optimization eliminates repeated computation of the same expression?

1. Loop interchange
2. Dead-code elimination only
3. Common subexpression elimination
4. Register allocation

Which pipeline hazard occurs when an instruction depends on the result of a previous instruction?

1. Structural hazard
2. Data hazard
3. Syntax hazard
4. Memory hazard

Dynamic method dispatch is primarily used to implement:

1. Lexical analysis
2. Constant folding
3. Runtime polymorphism
4. Register allocation

Which statement is true regarding DFA and NFA?

1. NFA is strictly more powerful than DFA
2. DFA and NFA recognize the same class of languages
3. DFA is strictly more powerful than NFA
4. Every NFA requires more states than every equivalent DFA

Explain the different phases of compilation with a suitable example. Show the input and output produced at each phase.

Construct a DFA over {0,1} that accepts all strings containing an even number of 0s and an odd number of 1s. Verify the constructed DFA using suitable accepted and rejected input strings.

For a lexical analyzer, design regular expressions to recognize the following token classes:
(i) Identifiers beginning with a letter and containing letters and digits thereafter.
(ii) Unsigned integer constants.
(iii) Relational operators <, <=, >, >=, ==, and !=.

Consider the grammar:
S→ABC
A→aA | ε
B→bB | ε
C→cC | d
Compute the FIRST and FOLLOW sets for all non-terminals. Using these, construct the LL(1) parsing table. Use the parsing table to show the parsing steps for the input string “aabd”.

Explain ambiguity in context-free grammars. Illustrate how ambiguity can lead to shift-reduce or reduce-reduce conflicts during LR parsing.

Construct a transition diagram for the Pushdown Automaton for the language:
L = {wcw^R | w ∈ {a,b}*}

Explain the structure of an activation record and its role during procedure execution.

Discuss the structure of a symbol table and the information stored for each identifier.

Generate the three-address code for the following expression. Then represent the generated code using quadruple, triple, and indirect-triple representations.
x=a*(b+c)−d/e

Explain the construction of basic blocks and control-flow graphs (CFGs) in compiler design using a suitable three-address code example.

Explain cache locality and its importance in loop optimization.

Explain the major stages involved in target code generation in a compiler. Discuss instruction selection, register allocation, and instruction scheduling, and explain how each stage contributes to generating efficient target machine code.

Discuss the major challenges involved in compiling object-oriented features such as classes, inheritance, and polymorphism.

Consider the following grammar:
E → E + T | T
T → T * F | F
F → digit
Define suitable synthesized attributes to evaluate an arithmetic expression. Construct the annotated syntax tree and evaluate the following expression:
3 + 5 * 2

SLR(1) parser

Syntax Directed Definition

peep-hole optimization

Attribute grammar