Advance Compiler Test: Master in 1 Hour, Score 60% to Pass

1) Consider the following statements:

STATEMENT1: The grammar:

S -> 0|12|345

is LL(1).

STATEMENT2: The grammar

S -> 0|T1

T -> 1|S0

is LL(1).

STATEMENT3: The grammar

S -> 0|11|01

is LL(1).

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

2) Consider the following statements.

STATEMENT1: LL(k) parsing uses all of the left context of the string being parsed.

STATEMENT2: Strong LL(k) parsing does not use any of the left context of the parse.

STATEMENT3: LL(k) parsing is more stronger than strong LL(k) parsing.

STATEMENT4: Strong LL(k) parsing is more stronger than LL(k) parsing.

SELECT THE CORRECT OPTION.

3) Consider the following grammar G.

S -> ABC

A -> Aa | aB

B -> Bb | ε

C -> Cc | ε

PART1:

Consider the following two statements:

STATEMENT1: G can be used to specify an LL(1) parser.

STATEMENT2: ‘a’ is in FIRST(S).

Which of the following statements is correct?

(a) Statement1 and Statement 2 are both TRUE

(b) Statement1 is TRUE, Statement2 is FALSE

(c) Statement1 is FALSE, Statement2 is TRUE

(d) Statement1 and Statement2 are both FALSE

PART2:

Consider the following two statements:

STATEMENT3: ‘c’ is in FIRST(Aa).

STATEMENT4: ‘c’ is in FOLLOW(A).

Which of the following statements is correct?

(a) Statement3 and Statement4 are both TRUE

(b) Statement3 is TRUE, Statement4 is FALSE

(c) Statement3 is FALSE, Statement4 is TRUE

(d) Statement3 and Statement4 are both FALSE

SELECT THE CORRECT OPTION.

4) Consider the following grammar:

E -> A | B

A -> a | c

B -> b | c

Consider the following statements:

STATEMENT1: Given grammar is LL(1) but not SLR(1).

STATEMENT2: Given grammar is LR(1) but not LL(1).

WHICH OF THE FOLLOWING STATEMENTS IS CORRECT?

5) Consider the following statements.

STATEMENT1: We cannot use regular expression to define MICRO programming language.

STATEMENT1: LA stands for “Look Ahead Merged” in LALR(1) parsing.

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

6) Take a look at the following grammar:

A -> Bx | yC | ε

B -> CzA

C -> xB

PART1: NULLABLE non-terminals?

(a) A                (b) B               

(c) C                (d) A and B

PART2: FIRST(A)?

(a) { y }            (b) { x, y }       

(c) { y, z }        (d) { x, y, z }

PART3: FIRST(B)?

(a) { x }            (b) { y }                       

(c) { z }            (d) { x, y }

PART4: FIRST(C)?

(a) { x }            (b) { y }                       

(c) { z }            (d) { x, y }

PART5: FOLLOW(A)?

(a) { x }            (b) { y }                       

(c) { z }            (d) { x, z }

PART6: FOLLOW(B)?

(a) { x }            (b) { y }                       

(c) { z }            (d) { x, z }

PART7: FOLLOW(C)?

(a) { x }            (b) { y }                       

(c) { z }            (d) { x, z }

PART8: Is this grammar LL(1)?

(a) Yes             (b) No                                                                                                 

(c) Cannot be answered with information provided.

(d) The LL(1) checker would go into an infinite loop.

SELECT THE CORRECT OPTION.

7) Consider the following three grammars.

GRAMMAR1:                      

A -> BC

B -> Ax | x

C -> yC | y     

GRAMMAR2:

A -> BC

B -> Ax | x | ε

C -> yC | y    

GRAMMAR3:           

A -> BC

B -> Ax | x | ε

C -> yC | y | ε  

For each of the following statements about FIRST and FOLLOW sets, indicate for which grammar(s) (1, 2, or 3) the statement is TRUE.

(1) FIRST(A) = {x, y} =

(2) FOLLOW(A) = {$, x} =

(3) FOLLOW(B) = {$, x, y} =

(4) FIRST(C) = {y} =

(5) FOLLOW(C) = {$, x} =

SELECT THE CORRECT OPTION.

8) Consider the following statements.

STATEMENT1: LL(k) parsing uses the next ‘k’ input tokens.

STATEMENT2: LL(k) parsing is more powerful than LL(1) parsing.

STATEMENT3: LL(k) languages are proper subset of LL(k-1) languages.

STATEMENT4: C Programming language is LL(1).

STATEMENT5: LL(1) grammar does not exists for the programming language.

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

9) Consider the following grammar:

E -> A | B

A -> a | c

B -> b | c

Consider the following statements:

STATEMENT1: Given grammar is LL(1).

STATEMENT2: Given grammar is SLR(1).

WHICH OF THE FOLLOWING STATEMENTS IS CORRECT?

10) Consider the following statements.

STATEMENT1: Hand-written parser is much more powerful than that is generated by a parser generator.

STATEMENT2: LL(inf) is a form of top-down parsing.

STATEMENT3: An LL parser is a deterministic, canonical top-down parser for context-free grammars.

STATEMENT4: An LR parser is a deterministic, canonical bottom-up parser for context-free grammars.

STATEMENT5: LL(*) parsing only backtracks over repeating constructs to resolve conflicts.

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

11) Consider the following grammar:

S -> Aa | b

A -> a

WHICH PARSING METHOD WORKS MORE EFFICIENT FOR IT?

12) Consider a bottom-up parser for a grammar with no ε production and no single production (i.e., productions with a single symbol on the right-hand side). For an input string with n tokens, what is the maximum number of reduce moves the parser can take?

13) Consider the following grammar:

S -> aS | aSbS | c

PART1:

Consider the following two statements:

STATEMENT1: Given grammar is left recursive.

STATEMENT2: Given grammar is suitable for predictive parsing.

Which of the following statements is correct?

(a) Statement1 and Statement2 are both true

(b) Statement1 is true, Statement2 is false

(c) Statement1 is false, Statement2 is true

(d) Statement1 and Statement2 are both false

PART2:

Consider the following two statements:

STATEMENT1: Given grammar is ambiguous.

STATEMENT2: Given grammar is regular.

Which of the following statements is correct?

(a) Statement1 and Statement2 are both true

(b) Statement1 is true, Statement2 is false

(c) Statement1 is false, Statement2 is true

(d) Statement1 and Statement2 are both false

SELECT THE CORRECT OPTION.

14) Consider the following FIRSTs and FOLLOWs:

FIRST(X) = { b, d, f }

FIRST(Y) = { b, d }

FIRST(Z) = { c, e }

FOLLOW(d) = { c, e }

FOLLOW(e) = { a }

FOLLOW(f) = { $ }

FOLLOW(X) = { $ }

FOLLOW(Y) = { c, e }

FOLLOW(Z) = { a }

FOLLOW(a) = { $ }

FOLLOW(b) = { b, d }

FOLLOW(c) = { c, e }

Which of the following grammars satisfies the given FIRST and FOLLOW sets?

(a)        X -> Ya | f

            Y -> bY | d

            Z -> cZ | e

(b)        X -> YZa | f

            Y -> bY | d

            Z -> cZ | e

(c)        X -> bY | d

            Y -> Ya | f

            Z -> cZ | e

(d)       X -> bY | e

            Y -> cZ | d

            Z -> Ya | f

SELECT THE CORRECT OPTION.

15) Consider the following grammar with 2 missing productions.

S -> aS | (1st Missing Production of Grammar)

A -> (2nd Missing Production Of Grammar) | ε

X -> cS | ε

Y -> dS | ε

Z -> eS

We have the FIRST and FOLLOW sets for this grammar.

FIRST(S) = { a, b, c, d, e }

FIRST(A) = { c, d, e, ε }

FIRST(X) = { c, ε }

FIRST(Y) = { d, ε }

FIRST(Z) = { e }

FIRST(a) = { a }

FIRST(b) = { b }

FIRST(c) = { c }

FIRST(d) = { d }

FIRST(e) = { e }

FOLLOW(S) = { $ } U FOLLOW(X) U FOLLOW(Y) U FOLLOW(Z)

FOLLOW(A) = { b }

FOLLOW(X) = FIRST(Y) / ε U FIRST(Z)

FOLLOW(Y) = FIRST(Z)

FOLLOW(Z) = FOLLOW(A)

FOLLOW(a) = FIRST(S)

FOLLOW(b) = FOLLOW(S)

FOLLOW(c) = FIRST(S)

FOLLOW(d) = FIRST(S)

FOLLOW(e) = FIRST(S)

WHAT ARE THESE TWO MISSING PRODUCTIONS OF GRAMMAR IN QUESTION?

(Note: We can only define two productions and recall that X -> A|B is two productions.)

16) A context-free grammar over 0 and 1 has three non-terminals S, A, and B. We know the following about the FIRST and FOLLOW sets of these non-terminals.

FIRST(S) = { 0, 1 }      

FOLLOW(S) = { 0, $ }         

FIRST(A) = { ε }         

FOLLOW(A) = { 0, 1 }

FIRST(B) = { ε }             

FOLLOW(B) = { 0, 1 }

PART1:

Which of the following context-free grammar satisfies the given FIRST and FOLLOW sets?

(a)       S -> 0 | 1 | AS0 | BS0

            A -> ε

            B -> ε

(b)        S -> 0 | 1 | BS0

            A -> AS0 | 1

            B -> ε

(c)        S -> 0 | 1 | BS0

            A -> ε

            B -> AS0 | 1

(d)       S -> 0 | 1 | AS0 | BS0

            A -> 0 | 1

            B -> 0

PART2:

Is the resultant grammar is LL(1)?

(a)        TRUE        

(b)        FALSE

SELECT THE CORRECT OPTION.

17) Consider the following grammar:

E -> A | B

A -> a | c

B -> b | c

Consider the following statements:

STATEMENT1: Given grammar is LR(1).

STATEMENT2: Given grammar is LL(1) and SLR(1).

WHICH OF THE FOLLOWING STATEMENTS IS CORRECT?

18) Consider the following grammar.

exp′ -> exp $

exp -> id

exp -> ( exp )

exp -> ( id ) exp                          ($ is end marker)

Consider the following statements.

STATEMENT1: This grammar is SLR

STATEMENT2: This grammar is not SLR

STATEMENT3: This grammar is LR(0)

STATEMENT4: This grammar is not LR(0)

WHICH OF THE STATEMENTS ARE TRUE?

19) For each of the following tasks, indicate the earliest stage of the compiler that can always perform that task or detect the situation. Assume the compiler is a conventional one that generates native code (x86, MIPS, etc.) for a language like C++ or JAVA. Use the following abbreviations to identify the stages:

SCAN: Scanner

PARSE: Parser

SEM: Semantics / Type-check

OPT: Optimization

INSTR: Instruction selection & scheduling

REG: Register allocation

RUN: Runtime, that is, when the compiled code is executed

CANNOT: Cannot be done during compilation or execution

(1) Detect that there is an extra “else stmt” clause in the program that is not associated with a previous “if”.  

(2) Detect that in an array reference a[k], the subscript k is out of bounds (i.e., in JAVA where bounds must be checked).  

(3) Guarantee that a particular pointer reference variable p will never be NULL.  

(4) Guarantee that in a pointer reference p.x (p ® x in C/C++) that the value referenced by p will have a field x, assuming that p is not NULL.  

(5) Use x86 addressing modes to calculate x*5 with leal (%eax, %eax, 4), %eax.         

SELECT THE CORRECT OPTION.

20) Give any context-free grammar in answer to the questions in this part, i.e., it does not matter if the grammar is LL(1), unambiguous, or any other subclass of all context-free grammars.

PART1:  

Consider the following FIRST and FOLLOW sets.

FIRST(S) = {b, ε}

FIRST(T) = {b, ε}

FOLLOW(S) = {a, $}

FOLLOW(T) = {a, b, $}

Give the simplest grammar (fewest productions and shortest right-hand side) that produces these sets, where S is the start symbol.

(a)        S -> Tb | T

            T -> bSa| ε

(b)        S -> Ta | b

            T -> T | bSa | ε

(c)        S -> Tb | ε

            T -> bSa | ε

(d)       S -> Ta | bSa

            T -> a | b | ε

PART2:

Select a grammar with single non-terminal S such that FIRST(S) = Phi.

(a)        S -> S         

(b)        S -> ε          

(c)        S -> T           

(d)       S -> a

PART3:

Select a grammar with single non-terminal S such that FIRST(S) = (FOLLOW(S)–{$}) = Phi.

(a)        S -> aSa        

(b)        S -> aSb      

(c)        S -> aTa       

(d)       S -> aS

PART4:

Select a grammar with a shift-reduce conflict.

(a)        S -> Ta | a

            T -> ε

(b)        S -> Tb | b

            T -> a

(c)        S -> Sa | ε

(d)       S -> S|T|a

            T -> ε

SELECT THE CORRECT OPTION.

21) Consider the following grammar:

S' -> S$

S -> xSS

S -> y

Consider the following statements:

STATEMENT1: The grammar is SLR.

STATEMENT2: This grammar is not SLR.

STATEMENT3: The grammar is LR(0).

STATEMENT4: This grammar is not LR(0).

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

22) Consider the following statements.

STATEMENT1: Hand-written parser is much more powerful than that is generated by a parser generator.

STATEMENT2: LL(inf) is a form of top-down parsing.

STATEMENT3: An LL parser is a deterministic, canonical top-down parser for context-free grammars.

STATEMENT4: An LR parser is a deterministic, canonical bottom-up parser for context-free grammars.

STATEMENT5: LL(*) parsing only backtracks over repeating constructs to resolve conflicts.

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

23) Consider the following statements.

STATEMENT1: Parse tree and abstract Syntax Tree (AST) are different terms.

STATEMENT2: A parse tree captures the structure of the program according to its grammar and AST captures the structure of the program independent of the grammar.

STATEMENT3: It is better to generate AST before producing code, rather than producing code directly.

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

24) Let us assume that we have just come up with a new kind of compiler optimization that can improve the run-time of code by a factor of 10, but is very slow. For code that normally takes 10 seconds to run, the compiler takes 1000 seconds to perform the optimization, but the optimize code runs in 1 second.

PART1:

Select the correct preference.

(a) Prefer to implement this optimization using just-in-time compiler.

(b) Prefer to implement this optimization using cross compiler.

(c) Prefer to implement this optimization using standard compiler (that compile code before it runs).

(d) Prefer to implement this optimization using self-compiler.

PART2:

Suppose this optimization requires seeing the high-level structure of code (e.g., the loops in the code). Select the correct option.

(a) This optimization takes place in front-end of compiler.

(b) This optimization takes place in back-end of compiler.

(c) This optimization takes place in both the ends.

(d) Half optimization takes place in front-end and rest half optimization takes place in back-end.

SELECT THE CORRECT OPTION.

25) For each of the following tasks, indicate the earliest stage of the compiler that can always perform that task or detect the situation. Assume the compiler is a conventional one that generates native code (x86, MIPS, et cetera) for a language like C++ or JAVA. Use the following abbreviations to identify the stages:

SCAN: Scanner

PARSE: Parser

SEM: Semantics / Type-check

OPT: Optimization

INSTR: Instruction selection & scheduling

REG: Register allocation

RUN: Runtime, that is, when the compiled code is executed

CANNOT: Cannot be done during compilation or execution

(1) A comment beginning with /* terminates with */ before the end of the file.

(2) A variable is declared at most once in a scope (function, class, etc.)

(3) Add code to temporarily store a value when there aren’t enough registers to hold all live values at a given point in the program.

(4) Replace array subscripting (a[i] = 0; i+=) and a test (i