Which one of the following statements is TRUE?
Show Hint
- The LALR(1) parser for a grammar G cannot have reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict.
- Symbol table is accessed only during the lexical analysis phase.
- Data flow analysis is necessary for run-time memory management.
- LR(1) parsing is sufficient for deterministic context-free languages.
The Correct Option is D
Solution and Explanation
Option (A) – False:
Although LR(1) parsers are more powerful than LALR(1) parsers, converting an LR(1) parser to an LALR(1) parser involves merging states with identical LR(0) cores. This merging can introduce reduce–reduce conflicts that were not present in the original LR(1) parser. Hence, it is incorrect to say that LALR(1) will never have such conflicts if LR(1) does not. Therefore, this statement is false.
Option (B) – False:
The symbol table is not used only during lexical analysis. While entries may be created during lexical analysis, the symbol table is extensively accessed and updated during syntax analysis, semantic analysis, and even during code generation. Hence, restricting its use to lexical analysis alone is incorrect.
Option (C) – False:
Data flow analysis is a compile-time technique used to gather information about the possible values of variables at different points in a program. It is mainly used for optimization and error detection. It does not deal with run-time memory management, which is handled by mechanisms such as stack and heap management. Therefore, this statement is false.
Option (D) – True:
Deterministic context-free languages (DCFLs) are exactly the class of languages that can be parsed by deterministic pushdown automata. LR(1) parsers are powerful enough to parse all deterministic context-free languages using one symbol of lookahead. Hence, LR(1) parsing is sufficient for DCFLs, making this statement correct.
Final Answer: (D)
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.
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 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? 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