Exams › GATE › Technical

Consider the following statements. S1: Every SLR(1) grammar is unambiguous, but there are certain unambiguous grammars that are not SLR(1). S2: For every grammar, there is a parser that takes at most linear time to parse a string of length $n$. Which of the following is correct?

1. S1 is true and S2 is true
2. S1 is true and S2 is false
3. S1 is false and S2 is true
4. S1 is false and S2 is false

Correct answer: S1 is true and S2 is true

Solution

SLR(1) grammars are indeed unambiguous, and there exist unambiguous grammars that are not SLR(1). Also, for any grammar, parsing can be done in linear time using suitable parser constructions for the fixed grammar. Hence both statements are true.

Related GATE Technical questions

• Which of the following is/are bottom-up parser(s)?
• Which ONE of the following statements is FALSE regarding the symbol table?
• Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
• Which of the following statement(s) is/are TRUE while computing FIRST and FOLLOW during top-down parsing by a compiler?
• Which one of the following is a top-down parser?
• In a simplified computer, the instructions are: - `OP Rj, Ri` — performs `Rj OP Ri` and stores the result in register `Ri`. - `OP m, Ri` — performs `val OP Ri` and stores the result in register `Ri`, where `val` denotes the content of memory location `m`. - `MOV m, Ri` — moves the content of memory location `m` to register `Ri`. - `MOV Ri, m` — moves the content of register `Ri` to memory location `m`. The computer has only two registers, and `OP` is either `ADD` or `SUB`. Consider the following basic block: ```text t1 = a + b t2 = c + d t3 = e - t2 t4 = t1 - t3 ``` Assume that all operands are initially in memory and the final value of the computation should be in memory. What is the minimum number of `MOV` instructions in the code generated for this basic block?

⚔️ Practice GATE Technical free + battle 1v1 →