Compiler Design - B.Tech. 6th Semester Examination, 2022

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.

1. Leftmost derivation
2. Leftmost derivation traced out in reverse
3. Rightmost derivation
4. Rightmost derivation traced out in reverse

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?

1. \( n/2 \)
2. \( n-1 \)
3. \( 2n-1 \)
4. \( 2^n \)

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

1. always be evaluated
2. be evaluated only if the definition is L-attributed
3. be evaluated only if the definition has synthesized attributes
4. never be evaluated

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

1. LL(1)
2. SLR(1) but not LL(1)
3. LALR(1) but not SLR(1)
4. LR(1) but not LALR(1)

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

1. source program, tokens
2. token, source program
3. Either of the two
4. None of the above

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

1. During the lexical analysis of a program
2. During parsing of the program
3. During the code generation
4. During the data flow analysis

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

1. 4
2. 5
3. 10
4. None of the above

How is the parsing precedence relation defined?

1. To delimit the handle
2. Only for a certain pair of terminal
3. None of the above
4. All of the above

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

1. * has higher precedence than +
2. - has higher precedence than *
3. + and - have same precedence
4. + has higher precedence than *

Shift reduce parsers are

1. top-down parser
2. bottom-up parser
3. may be top-down or bottom-up
4. None of the above

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

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

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 \)

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

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

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

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

Differentiate inherited and synthesized attributes with an example.

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

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

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

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

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

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 \)

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