Bissoy.com
Doctors Medicines MCQs Q&A

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?

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? Correct Answer S<sub>1</sub> is true and S<sub>2</sub> is true

Answer: Option 1

Explanation:

Statement 1:Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).

[ alt="F1 Raju.S 01-04-21 Savita D3" src="//storage.googleapis.com/tb-img/production/21/04/F1_Raju.S_01-04-21_Savita_D3.png" style="width: 463px; height: 243px;">

As you can see in the diagram Not all Unambiguous grammars are SLR(1) but All SLR(1) grammars are Unambiguous.

This Statement is True.

Statement 2:For any context-free grammar, there is a parser that takes at most O(n3) time to parse a string of length n.

This Statement is also True. There exists a standard algorithm for general Context-free grammars known as the CYK algorithm whose time complexity is O(n3).

Note:

  • LR parsers have linear time(O(n)) complexity.

Related Questions

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.
A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example, int a[10] [3] ; The grammars use D as the start symbol, and use six terminal symbols int; id[ ] num Grammar G1 Grammar G2 D → int L; D → int L; L → id[E L → idE E → num] E → E[num] E → num][E E → [num]   Which of the grammars correctly generate the declaration mentioned above?
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
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 problems. L(?) denotes the language generated by a grammar ?. L(?) denotes the language accepted by a machine ?. (I) For an unrestricted grammar ? and a string ?, whether ? ∈ (?) (II) Given a Turing machine M, whether L(M) is regular (III) Given two grammars ?1 and ?2, whether (?1) = (?2) (IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?
Select the correct differences between char and varchar data types? i. varchar is non unicode and char is unicode character data type ii. char is ‘n’ bytes whereas varchar is actual length in bytes of data entered in terms of storage size iii. varchar is variable in length and char is the fixed length string iv. For varchar, if a string is less than the maximum length then it is stored in verbatim without any extra characters while for char if a string is less than the set length it is padded with extra characters to equalize its length to given length
Which of the following statements are FALSE? 1. Ambiguous grammars must have more than one parse tree for every string. 2. Addition (+), subtraction (–), and assignment (=) operators in C are left associative. 3. Python is a weakly typed language.
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. 2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter. Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string? 
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 to parse a string with n tokens?