The Gateway to Computer Science Excellence
+2 votes
290 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 | 290 views
+5
$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.

2 Answers

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
0 votes

A viable prefix is a legitimate prefix that could lead to a handle.

Since handle will always be found on top of the stack, all the viable prefixes of it can appear below it in the stack. If handle is not found yet, the stack would contain just viable prefixes.

I is true.


Viable prefix can't extend past the handle. That's why it's a prefix!

II is true.


The set of all viable prefixes of a language is a Regular Language, so it can be recognised by a DFA.

III is true.


Option D

by
Answer:

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
52,314 questions
60,435 answers
201,773 comments
95,251 users