Bissoy.com
Doctors Medicines MCQs Q&A

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?

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? Correct Answer n – 1

Explanation:

Grammar with no epsilon- and unit-production

S → PQ

P → pp

Q → qq

Derive String: ppqq

S → PQ

S → ppQ

S → pppqq

String length = 4

Production needed = 4 – 1 = 3.

Related Questions

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 to parse a string with n tokens?
Which of the following statements is/are correct? A. SLR parser is more powerful than LALR parser. B. Canonical LR parser is more powerful than LALR parser. C. LALR parser is more powerful than Canonical LR parser.
Consider the following grammar G S → F | H F → p | c H → d | c Where S, F, and H are non-terminal symbols, p, d, and c are terminal symbols. Which of the following statement(s) is/are correct? S1. LL(1) can parse all strings that are generated using grammar G S2. LR(1) can parse all string that are generated using grammar G
A bag contained red, green and pink tokens. The ratio between red and green tokens was 15 : 32 while that between pink and red tokens was 18 : 25. What was the ratio between green and pink tokens?
In a bag containing red, green and pink tokens, the ratio of red to green tokens was 5 : 12 while the ratio of pink to red tokens was 7 : 15. What was the ratio of green to pink tokens?
In a bag containing red, green and pink tokens, the ratio of red to green tokens was 5 : 11 while the ratio of pink to red tokens was 7 : 15. What was the ratio of green to pink tokens?
Consider the following grammar G: P → Q + R | Q – R | Q | R Q → q | r R → r | s where P, Q, and R are non-terminal symbols, and q, r, and s are terminal symbols. Which of the following statement(s) is/are correct? S1. LL(1) can parse all strings that are generated using grammar G S2. LR(1) can parse all strings that are generated using grammar G
Consider the following statements. S1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2 : For any context-free grammar, there is a parser that takes at most O(n3) time to parse a string of length n. Which one of the following option is correct?
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable? I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ϕ? III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑? IV. Given a Turing machine M and a string w, is w ∈ L(M)?  
Which of the following statements is/are TRUE? (a) The grammar S → SS | a is ambiguous. (Where S is the start symbol) (b) The grammar S → 0S1 | 01S |e is ambiguous. (The special symbol e represents the empty string) (Where S is the start symbol) (c) The grammar (Where S is the start symbol) S → T / U T → x S y | xy | ϵ U → yT generates a language consisting of the string yxxyy.