Q: How to find out which are the next possible terminals for a CFG?

Uday Khedkar <uday@cs.unipune.ernet.in>
5 Apr 2000 22:24:48 -0400

          From comp.compilers
Related articles
Q: How to find out which are the next possible terminals for a CFG? stoimenov@dock.net (Kirill Stoimenov) (2000-04-01)
Q: How to find out which are the next possible terminals for a CFG? uday@cs.unipune.ernet.in (Uday Khedkar) (2000-04-05)
| List of all articles for this month |
From: Uday Khedkar <uday@cs.unipune.ernet.in>
Newsgroups: comp.compilers
Date: 5 Apr 2000 22:24:48 -0400
Organization: Compilers Central
References: 00-04-018
Keywords: parse

"Kirill Stoimenov" <stoimenov@dock.net> wants to know


>I have the following problem: I have a CFG and I need to know for a given
>partial phrase, which are the all next possible terminals.
>
>Example:
>
>L := L I
>L := I
>I := a
>I := b


>For the phrase ab the possible new phrases are: aba and abb, so the next
>possible terminals are {a, b}.


If your grammar is LR(1) and the partial phrase (also called a "viable
prefix") corresponds to an itemset I, then the next possible terminals
are (a subset of) the set of lookahead symbols in the itemset I. The
method of construction is such that you will be able to know which
viable prefix does an itemset correspond to.


(Any text on compilers should explain the construction of LR(1) sets of items.)


Hope it helps.


Uday Khedker.
-------------
uday@cs.unipune.ernet.in
http://cs.unipune.ernet.in/~uday

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.