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	Lasse Hillerøe Petersen <lhp+news@toft-hp.dk>
Newsgroups	comp.compilers
Subject	Can this be proven for LL(1) grammars?
Date	06 Nov 2014 22:16:38 GMT
Organization	SunSITE.dk - Supporting Open source
Lines	26
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<14-11-006@comp.compilers> (permalink)
NNTP-Posting-Host	news.iecc.com
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8
Content-Transfer-Encoding	8bit
X-Trace	miucha.iecc.com 1415384052 32424 2001:470:1f07:1126:0:676f:7373:6970 (7 Nov 2014 18:14:12 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Fri, 7 Nov 2014 18:14:12 +0000 (UTC)
Keywords	parse, theory, question, LL(1)
Posted-Date	07 Nov 2014 13:14:12 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:1414

Show key headers only | View raw

Given a context free grammar G that is LL(1), is the answer to the
following questions "yes"? I intuitively believe it is, except for (2),
but I am not sufficiently confident of my skills in proving this in full
generality, so I would much appreciate expert advice.

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)?

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?

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)?

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

This isn't homework, and I have tried searching for an answer, but found
none - this may of course be because the proof is actually trivial. If
so, I apologize and hope someone will enlighten me anyway.

/Lasse

Back to comp.compilers | Previous | Next — Next 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