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

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

8) Consider the following statements.

STATEMENT1: SLL(1) is Deterministic grammar.

STATEMENT2: Deterministic parsers are much faster than non-deterministic parser.

STATEMENT3: LL(k) parsing is suitable for natural languages processing.

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

9) 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?

10) 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?

11) 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.

12) 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.

13) 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.

14) 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?

15) Compilers are almost always doing Parsing and Semantic/Type-checking in separate phases of compiler. So, why this separation into phases is done?

(1) It is better modularity to separate the two jobs so the parser and semantics checker can each do one thing well.

(2) It is easier to get right and easier to maintain.

(3) There are many things we need to check that are not captured by a context-free specification. These either cannot be done in the parser, or require backtracking.

(4) Checking for type compatibility in expression and assignment statements is not a work of parser.

SELECT THE CORRECT OPTION.

16) 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?

17) 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?

18) 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.

19) 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.

20) 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?

21) 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?

22) 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?

23) Consider the following grammar:

S -> Aa | b | bB

A -> a

B -> b

WHICH PARSING METHOD WORKS MORE EFFICIENT FOR IT?

24) 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?

25) Consider the following statements.

STATEMENT1: LL(1) operates from Left to Right and produces Leftmost derivation.

STATEMENT2: In Deterministic parsing, each parse table entry contains at most one element.

WHICH OF THE FOLLOWING STATEMENTS ARE TRUE?

26) 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.

27) Consider the following grammar:

S -> aS | bS | abaA

A -> ε | aA | bA

Consider the following statements.

STATEMENT1: Parse table of given grammar contains two rows and three columns.

STATEMENT2: Parse table can be constructed by using FIRST set only

STATEMENT3: FIRST sets for non-terminals S and A contains 3 elements.

STATEMENT4: FOLLOW(S) = FOLLOW(A) = {$, a}.

STATEMENT5: Given grammar is LL(1).

SELECT THE CORRECT OPTION.

28) 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.

29) 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.

30) 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?

31) Consider the following grammar:

S -> Aa | b

A -> a

WHICH PARSING METHOD WORKS MORE EFFICIENT FOR IT?

32) 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.)

33) 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?