The Gateway to Computer Science Excellence
+1 vote
147 views

Which of the following sentences regarding Viable prefixes is/are CORRECT?

  1. Viable prefixes is the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser
  2. Viable prefixes is the set of prefixes of right-sentential forms that do not extend past the end of the right-most handle
  3. Viable prefixes can be recognized using a DFA
     
    1. Only (i)
    2. Only (ii)
    3. Only (i) and (ii)
    4. (i), (ii) and (iii)
in Compiler Design by Veteran (425k points) | 147 views
+4
$D$.

$I$ and $II$ is the definition of viable prefixes.

The set of viable prefixes for any grammar is a regular language so can be recognized by a $DFA$
0
Please provide some references for above statements.

1 Answer

0 votes

Answer is D.

I : Definition of viable prefix -

Viable prefixes are the prefixes of right sentential forms that do not extend beyond the end of its handle.

i.e. a viable prefix either has no handle or just one possible handle on the extreme RIGHT which can be reduced.

II :  Definition of viable prefix -

viable prefixes are the set of prefixes of right sentential forms that can appear on the stack of a shift­reduce parser

III :The set of all viable prefixes of a context-free language is a REGULAR LANGUAGE. i.e., viable prefixes can be recognized by using a FINITE AUTOMATA.

So I, II & III are true.

References:

  1. https://gatecse.in/viable-prefixes-and-handle-in-lr-parsing/
  2. https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/100%20Bottom-Up%20Parsing.pdf
by Junior (895 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,530 answers
195,622 comments
101,337 users