Re: Can this be proven for LL(1) grammars?

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From	"SLK Mail" <slkpg4@gmail.com>
Newsgroups	comp.compilers
Subject	Re: Can this be proven for LL(1) grammars?
Date	Sat, 08 Nov 2014 14:51:05 -0800
Organization	SLK Systems
Lines	40
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<14-11-019@comp.compilers> (permalink)
References	<14-11-006@comp.compilers>
NNTP-Posting-Host	news.iecc.com
Mime-Version	1.0
Content-Type	text/plain; charset=iso-8859-15; format=flowed; delsp=yes
Content-Transfer-Encoding	8bit
X-Trace	miucha.iecc.com 1415607095 27677 2001:470:1f07:1126:0:676f:7373:6970 (10 Nov 2014 08:11:35 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Mon, 10 Nov 2014 08:11:35 +0000 (UTC)
Keywords	parse, theory
Posted-Date	10 Nov 2014 03:11:35 EST
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	csiph.com comp.compilers:1427

Show key headers only | View raw

1. From G, for each nonterminal symbol R define a grammar GR, where the
start rule is changed to R. Rules that are no longer reachable are of
course useless and discarded. Is each GR also LL(1)?

Yes. SLK lets you do this at runtime by optionally specifying any
start symbol when invoking the parser. Internally it does something
similar when doing nondeterministic parsing by calling the predict
routine with the questionable nonterminal as the start symbol.

2. From all the GR grammars from (1), define G' with a new start rule S:
GR1 | GR2 ... |GRn. Is G' also LL(1)? Given that there could be rules Gi
and Gj such that their FIRST sets intersect, I suppose the answer is no.
What if instead, S is defined only from a selection of rules with
disjoint FIRST sets?

Think of this from the perspective of ambiguity. Seems like you would have
almost a power set of different ways to derive GRn. A variation of this
actually occurs in many modern reference grammars. They contain
redundancies
for clarity mostly, but probably also because they seem to target recursive
descent parsing.

If any nonterminals are nullable, you need to also consider FOLLOW sets.

3. From G, define a new grammar G', such that for each nonterminal R, a
rule R: "R" is added, where "R" is a new terminal symbol. Is G' also LL
(1)?

Yes. Hard to imagine how this would do anything but make the grammar
larger.

4. Do (1) and (3) hold for other types of CFG?

Probably all context free grammars.

I get the impression that you are trying to figure out how to do grammar
composition. You should be able to find many proofs that this generally
does not work.

SLK Parser Generator:  http://slkpg.1eko.com

Back to comp.compilers | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Can this be proven for LL(1) grammars? Lasse Hillerøe Petersen <lhp+news@toft-hp.dk> - 2014-11-06 22:16 +0000
  Re: Can this be proven for LL(1) grammars? Kaz Kylheku <kaz@kylheku.com> - 2014-11-07 19:43 +0000
  Re: Can this be proven for LL(1) grammars? "SLK Mail" <slkpg4@gmail.com> - 2014-11-08 14:51 -0800

csiph-web