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

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

18) Consider the following grammar:

S -> Aa | b | bB

A -> a

B -> b

WHICH PARSING METHOD WORKS MORE EFFICIENT FOR IT?

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

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

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

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

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

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

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

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

27) Take the following grammar into consideration:

S -> [SX] | a

X -> ε | +SY | Yb

Y -> ε | -SXc

PART1: NULLABLE non-terminal(s)?

(a) S                             (b) X                           

(c) Y                            (d) X and Y

PART2: FIRST(S)?

(a) { a, [ }                     (b) { a, [, ] }                

(c) { a, ], ε }                 (d) { a, ] }

PART3: FIRST(X)?

(a) { ε, +, b }                (b) { ε, +, - }               

(c) { +, -, b, ε }            (d) { +, -, b }

PART4: FIRST(Y)?

(a) { ε, - }                     (b) { ε, +, - }               

(c) { +, -, a, ε }             (d) { ε, a }

PART5: FOLLOW(S)?

(a) { $, +, -, ] }             (b) { $, +, -, ], c, b }    

(c) { $, ], c }                 (d) { $, + }

PART6: FOLLOW(X)?

(a) { ], c }                     (b) { ], c, b }               

(c) { [, b, c }                 (d) { [, ], c, b }

PART7: FOLLOW(Y)?

(a) { ], c, b }                 (b) { ], [, c, b }            

(c) { [, b, c }                 (d) { [, ], a }

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.

28) Consider the following grammar:

S -> Aa | b

A -> a

WHICH PARSING METHOD WORKS MORE EFFICIENT FOR IT?

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

30) A C identifier consists of zero or more letters, digits, and underscores, in any order, but may not begin with a digit. Which pattern will match one?

31) Let us consider two LL(1) grammars, each with a single non-terminal, and without ε production. The non-terminal for the first grammar is ‘A’; and the non-terminal for the second grammar is ‘B’. Now, let us consider a third grammar obtained by merging the productions of the two grammars and adding the production S -> A | B.

PART1:

Is it possible to derive the empty string from S in the third grammar?

(a) Yes            (b) No             

(c) Sometimes yes, sometimes no.                                                    

(d) None of the above answer is correct.

PART2:

What is (are) the necessary and sufficient condition(s) that the two original grammars must satisfy, in order to ensure that the third grammar is un-ambiguous?

(a) L(A) intersect L(B) is equal to Phi

(b) L(A) intersect L(B) not equal to Phi

(c) L(A) union L(B) is equal to Phi

(d) L(A) is equal to Phi

(e) Both (b) and (d)

PART3:

What is (are) the necessary and sufficient condition(s) that the two original grammars must satisfy, in order to ensure that the third grammar is LL(1)?

(a) FOLLOW(A) intersect FOLLOW(B) is equal to Phi.             

(b) FIRST(A) intersect FIRST(B) is equal to Phi.

(c) Both (a) and (b).                                      

(d) None of the above answers is correct.

SELECT THE CORRECT OPTION.

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

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