Register

GATE Overflow Test Series | Compiler Design | Test 1 | Question: 7

401 views
3 votes
3 votes

Which of the following is TRUE regarding the running time of an $LR(1)$ parser? (Mark all the appropriate choices)

  1. It runs in linear time for all inputs
  2. It runs in polynomial time for all inputs
  3. For some inputs it may take exponential time
  4. It runs in $O(n^3)$ but not always $O(n^2)$
User Avatar

1 Answer

Best answer
4 votes
4 votes
LR parsers are deterministic; they produce a single correct parse without guesswork or backtracking, in LINEAR time. Some methods which can parse arbitrary context-free languages (e.g., Cocke–Younger–Kasami, Earley, GLR) have worst-case performance of $O(n^3)$ time.
Reference: https://en.m.wikipedia.org/wiki/LR_parser

So, options A and B are correct.
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
1 answer
3
gatecse asked Dec 14, 2020
166 views
GATE Overflow Test Series | Compiler Design | Test 1 | Question: 1
When we merge states in an $LR(1)$ parser to form an $LALR(1)$ parser, we may introduce shift-reduce conflict reduce-reduce conflict neither shift-reduce nor reduce-reduce conflict both shift-reduce as well as reduce-reduce conflict
When we merge states in an $LR(1)$ parser to form an $LALR(1)$ parser, we may introduceshift-reduce conflictreduce-reduce conflictneither shift-reduce nor reduce-reduce c...
User Avatar
5 votes
5 votes
1 answer
4
gatecse asked Dec 14, 2020
212 views
GATE Overflow Test Series | Compiler Design | Test 1 | Question: 2
Suppose we have a rightmost derivation which proceeds as follows: $\begin{array}{ccc}S &\rightarrow & Aabw\\ & \rightarrow &ABw \end{array}$ ... $\begin{array}{ccc} B &\rightarrow & ab \end{array}$
Suppose we have a rightmost derivation which proceeds as follows:$\begin{array}{ccc}S &\rightarrow & Aabw\\ & \rightarrow &ABw \end{array}$Which of the following is a pos...
User Avatar
Link Copied!