ComputerNetworks
February 12, 2024ComputerNetworks
February 12, 2024CompilerDesign
Question 15

Consider the following statements.
S_{1}:Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S_{2}: For any contextfree grammar, there is a parser that takes at most O(n^{3} )
Which one of the following options is correct?
S_{1}:Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S_{2}: For any contextfree grammar, there is a parser that takes at most O(n^{3} )
Which one of the following options is correct?
S_{1}is true and S_{2}is true


S_{1}is true and S_{2}is false


S_{1}is false and S_{2}is true


S_{1}is false and S_{2}is false

Question 15 Explanation:
Every unambiguous grammar need not be SLR(1). As we know some unambiguous grammar which is CLR(1) but not SLR(1). So S1 is true.
Any CFG (which is in CNF form) can be parsed by CYK algorithm in O(n^{3}) where n is length of string. Although it is not given that CFG is in CNF form but since we can convert any CFG in CNF form so S2 is true
Correct Answer: A
Question 15 Explanation:
Every unambiguous grammar need not be SLR(1). As we know some unambiguous grammar which is CLR(1) but not SLR(1). So S1 is true.
Any CFG (which is in CNF form) can be parsed by CYK algorithm in O(n^{3}) where n is length of string. Although it is not given that CFG is in CNF form but since we can convert any CFG in CNF form so S2 is true
Subscribe
Login
0 Comments