Parsing and syntax-directed translation Questions

Introduction

This article will discuss the questions that appeared previously in the gate exam in the compiler design section. Here we will discuss the questions on parsing and syntax-directed translation. Let's get started and discuss some questions.

Parsing and syntax-directed translation questions

1.  The grammar S → aSa | bS | c is

1. LL(1) but not LR(1)
2. LR(1) but not LR(1)
3. Both LL(1) and LR(1)
4. Neither LL(1) nor LR(1)

Answer: C
Explanation: First, we check for LL(1). We see the first of all production rules and see if they are disjoint. Here first of aSa is a, first of bS is b and first of c is c. Since all of these are mutually disjoint, it is LL(1). Now all LL(1) are LR(1) also; hence it is LR(1) also. Therefore, option C is correct.
 

2. Given 2 groups, group1 and group2. Match the following from group1 to group2

Group 1                                                  Group 2

P. Regular expression                     1. Syntax analysis

Q. Pushdown Automata                2. Code generation

R. Dataflow analysis                       3. Lexical analysis

S. Register allocation                      4. Code optimisation

1. P-4. Q-1, R-2, S-3
2. P-3, Q-1, R-4, S-2
3. P-3, Q-4, R-1, S-2
4. P-2, Q-1, R-4, S-3

Answer: B
Explanation: regular expressions are used for Lexical Analysis. Pushdown automata accept context-free grammar, which is related to syntax analysis. Dataflow analysis is related to code optimisation. Register allocation is used in code generation.
 

3. LR parsers use which kind of derivations?

1. Rightmost
2. Leftmost
3. Leftmost in reverse
4. Rightmost in reverse

Answer: D
Explanation: LR parser is a bottom-up approach; it uses the rightmost derivation in reverse.
 

4. Given 2 groups, group1 and group2. Match the following from group1 to group2

Group 1                                                  Group 2

P. Lexical analysis                         1. Leftmost derivation

Q. Top-down parsing                     2. Type checking

R. Semantic analysis                     3. Regular expressions

S. Runtime environments             4. Activation records

1. P-1. Q-2, R-4, S-3
2. P-3, Q-1, R-2, S-4
3. P-2, Q-3, R-1, S-4
4. P-4, Q-1, R-2, S-3

Answer: B
Explanation: Regular expressions are used for lexical analysis. Top-down parsing is done in the leftmost derivation. Type checking is done by semantic analysis.  Runtime environments use activation records.
 

5. Among the following, which is a top-down parser?

1. Recursive descent parser
2. Operator precedence parser
3. An LR(k) parser
4. An LALR(k) parser

Answer: A
Explanation: Recursive descent parser is a top-down parser.
 

6. When converting from infix to postfix expressions, which of the following data structure is most essential?

1. An operator stack
2. An operand stack
3. An operand stack and an operator stack
4. A parse tree

Answer: A 
Explanation: An operator stack stores the operators like +,-,*,/ and is used to convert from infix to postfix. An operand stack that holds the operands like 10,5,9, a,b and is used to convert from postfix to prefix expression.
 

7. Which of the following statements is FALSE?

1. A context-free grammar can specify both lexical and syntax rules.
2. Type checking is done before parsing.
3. Different Intermediate Representations can be generated from high-level language programs.
4. A program stack can be used to pass the arguments to a function.

Answer: B
Explanation: Parsing is done in the syntax analysis phase, and type checking is done in the semantic analysis phase. Syntax analysis is done before semantic analysis; hence, parsing is done before type checking. Therefore, option B is correct.
 

8. Consider the following parse tree involving the two binary operators $ and # for the expression a # b $ c $ d # e # f.

According to the given expression and parse tree, which of the following statements is true?

1. $ has more precedence than #; $ is left-associative, and # is right-associative.
2. # has more precedence than $;  $ is left-associative, and # is right-associative.
3. # has more precedence than $;  $ is right-associative, and # is left-associative.
4. $ has more precedence than #; $ is right-associative, and # is left-associative.

Answer: A 
Explanation: In the given parse tree, it is shown that b $ c is executed first, so $ must have higher precedence than #. Also, b$c is executed first, then (b$c)$d is executed, which shows that $ is left-associative. Whereas in case of #, first e # f is executed and then ((b$c)$d) # (e#f) is executed so # is right-associative.
 

9. The shift-reduce parser includes- (a) input buffer (b) parse table (c) stack. Choose the correct option 

1. (a) and (b) only
2. (a) and (c) only
3. (c) only
4. (a), (b) and (c) 

Answer: D
Explanation: The Shift-reduce parser is a bottom-up parser. It includes all the given three items: an input buffer, a parse table, and a stack. An input buffer is used to store the strings that need to be parsed. A parse table parses the strings, and a stack is used to hold the grammar symbols.
 

10. Let A, B, and C be the variables and a, b and c be the terminals. Which of the following grammar rules violate the requirement of the operator grammar?

1) A → BC

2) A → CcBb

3) A → BaC

4) A →  ϵ

1. 1 only
2. 1 and 2 only
3. 1 and 3 only
4. 1 and 4 only

Answer: D
Explanation: The production rules where more than two variables are present adjacent to each other violate operator grammar. So A → BC violates the operator grammar. Also, the empty production rules are not allowed in operator grammar. So, A → ϵ also violates the operator grammar. Therefore, the correct option is D.
 

11. Yacc stands for

1. yet accept compiler constructs
2. yet accept compiler-compiler
3. yet another compiler construct
4. yet another compiler compiler

Answer: D
Explanation: Yacc is an abbreviation for yet another compiler compiler.
 

12. Shift reduce parsing comes under which category

1. bottom-up parsing
2. top-down parsing
3. recursive parsing
4. predictive parsing

Answer: A
Explanation: Shift-reduce parsing is done using the bottom-up parsing technique. The scanning is done from left to right in SR parsing.
 

13. Stream of atoms is generated by which phase of compiler?

1. Syntax analysis
2. Lexical analysis
3. Code generation
4. Code optimisation

Answer: A
Explanation: Lexical analysis is the first Phases of Compiler responsible for generating a sequence of tokens. Syntax analysis comes next and takes the output of lexical analysis and generates steam of atoms. Code optimisation is the phase where the compiler minimises resources in use by the program. Code generation is the last phase that takes input from the code optimisation phase, and it gives the object code as a result. Therefore, the correct option is A.
 

14. Among the following grammar, which one does not have left recursion?

Answer: B
Explanation: Here, option A has direct left recursion due to the presence of production rule A → Aa. Option C has indirect left recursion because of the production rules S → Aa and A → Sc. Option D also has an indirect left recursion because it has the production rules A → Bd and B → Ae. Only option B has no left recursions; hence, the correct answer is option B.
 

15. The most powerful parsing method among the following is

1. LL(1)
2. Canonical LR
3. SLR
4. LALR

Answer: B
Explanation: The order of powerful parsing LR methods is SLR < LALR < CLR. Also, CLR is more powerful than LL(1) parser. Therefore, the most powerful parsing method is the canonical LR parser. 
 

16. Which one of the following statements is true?

1. SLR parser has more power than the LALR parser
2. The LALR parser has more power than the Canonical LR parser
3. Canonical LR parser has more power than the LALR parser
4. All the three SLR, LALR and canonical LR parsers have the same power.

Answer: C
Explanation: The order of powerful parsing LR methods is SLR < LALR < CLR. Therefore, option C is correct.
 

17. Type checking is done during which phase

1. Lexical analysis
2. Syntax analysis
3. Syntax directed translation
4. Code optimisation

Answer: C
Explanation: Type checking is done during syntax-directed translation.
 

18. Among the three LR methods, SLR, LALR, and Canonical LR, which one is the easiest to implement and which one is the most powerful?

1. SLR is the easiest, and LALR is the most powerful
2. SLR is the easiest, and Canonical LR is the most powerful
3. LALR is the easiest, and Canonical LR is the most powerful
4. Canonical LR is the easiest, and LALR is the most powerful

Answer: B
Explanation: SLR is the easiest to implement because it has a comparatively simple parse table and parser generator algorithm. The power order of parsing LR methods is SLR < LALR < CLR. Therefore Canonical LR or CLR is the most powerful. Hence, the correct option is B.
 

19. Consider the following  grammar expression:

E -> E * F  |  F + E  |  F

F -> F - F |  id

Which of the following is true about the above grammar expression?

1. * has higher precedence than +
2. – has higher precedence than *
3. + and — have the same precedence
4. + has higher precedence than *

Answer: B
Explanation: If we consider an example 8 * 4 - 5, the parse tree using the grammar will be - 

 

It is clear from the parse tree that  F-F is at a lower level than E * F, which means - is executed before *. Therefore, - has more precedence than *.
 

20. Consider the non-terminals {S, A} and terminals {a, b}, also consider the following Syntax Directed Translation Scheme (SDTS)

Using the above SDTS, what will be the output if the input is aab and we use a bottom-up parser?

1. 1 3 2
2. 2 2 3
3. 2 3 1
4. Syntax error

Answer: C
Explanation: Here, we are using a bottom-up parser, and the input string is given aab with the terminals {S, A} and non-terminals {a, b}. We should start with the string aab and reach S. The following steps are taken to reach S from aab.

Input → aab 

→ aSb     [using S → a]  

→ aA       [using A → Sb] 

→ S         [using S → aA]

Now, S → a prints 2, A → Sb prints 3 and S → aA prints 1. Therefore, 2 3 1 is printed. Hence, option C is correct.