Consider the following statements.
\[
S_1:\ \text{Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).}
\]
\[
S_2:\ \text{For any context-free grammar, there is a parser that takes at most } O(n^3) \text{ time to parse a string of length } n.
\]
Which one of the following options is correct?
\[ S_1:\ \text{Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).} \] \[ S_2:\ \text{For any context-free grammar, there is a parser that takes at most } O(n^3) \text{ time to parse a string of length } n. \] Which one of the following options is correct?
Show Hint
- $S_1$ is true and $S_2$ is false
- $S_1$ is false and $S_2$ is true
- $S_1$ is true and $S_2$ is true
- $S_1$ is false and $S_2$ is false
The Correct Option is C
Solution and Explanation
Step 1: Analyze Statement S1.
SLR(1) grammars form a proper subclass of LR grammars.
Since LR parsers generate a unique rightmost derivation in reverse,
all LR (and hence SLR(1)) grammars are unambiguous.
However, the converse is not true. There exist grammars that are unambiguous but do not satisfy the stricter FOLLOW-set conditions required for SLR(1) parsing.
Therefore, there exist unambiguous grammars that are not SLR(1), making statement S1 true.
Step 2: Analyze Statement S2.
For arbitrary context-free grammars, general parsing algorithms are available.
Algorithms such as the CYK (Cocke–Younger–Kasami) algorithm and Earley’s parser can parse any context-free grammar in O(n³) time in the worst case, where n is the length of the input string.
Hence, S2 is also true.
Final Conclusion:
Since both statements S1 and S2 are true,
the correct option is:
Final Answer: (C)
Top Questions on Parsing
Consider the augmented grammar with \(\{+,* , (, ), id\}\) as the set of terminals. \[ S' \rightarrow S \] \[ S \rightarrow S + R \mid R \] \[ R \rightarrow R^{\,*} P \mid P \] \[ P \rightarrow (S) \mid id \] If \(I_0\) is the set of two LR(0) items \(\{[S' \rightarrow S.], [S \rightarrow S. + R]\}\), then \(goto(\text{closure}(I_0), +)\) contains exactly \(\underline{\hspace{1cm}}\) items.
- Which one of the following statements is TRUE?
Consider the following context-free grammar where the set of terminals is \(\{a,b,c,d,f\}\):
\[ S \rightarrow daT \mid Rf \] \[ T \rightarrow aS \mid baT \mid \epsilon \] \[ R \rightarrow caTR \mid \epsilon \] The following is a partially-filled LL(1) parsing table.
Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?
Consider the following augmented grammar with terminals {#, @, <, >, a, b, c}.
$S' → S$
$S → S\#cS$
$S → SS$
$S → S@$
$S → <S>$
$S → a$
$S → b$
$S → c$Let I0 = CLOSURE({ S' → • S }). The number of items in the set GOTO(GOTO(I0, <), <) is .
- Want to practice more? Try solving extra ecology questions todayView All Questions
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems