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 =?iso-8859-1?q?Hiller=F8e?= Petersen 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> 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 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