Exams › GATE › Technical

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 → ε and A → a) to parse a string with n tokens?

1. n/2
2. n-1
3. 2n-1
4. 2ⁿ

Correct answer: n-1

Solution

In a bottom-up parsing process, each reduce move corresponds to reducing a production rule, and since the parser must eventually reduce the entire input string to the start symbol, the maximum number of reduce moves is one less than the number of tokens, which is n-1.

Related GATE Technical questions

• The truth table X Y f(X,Y) 0 0 0 0 1 0 1 0 1 1 1 1 represents the Boolean function
• The decimal value 0.5 in IEEE single precision floating point representation has
• A process executes the code fork(); fork(); fork(); The total number of child processes created is
• The protocol data unit (PDU) for the application layer in the Internet stack is
• Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L̄ also context-free? 3) If L is a regular language, then is L̄ also regular? 4) If L is a recursive language, then is L̄ also recursive?
• A binary operation ⊕ on a set of integers is defined as x ⊕ y = x² × y². Which one of the following statements is TRUE about ⊕?

⚔️ Practice GATE Technical free + battle 1v1 →