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

"SLK Mail" <>
Sat, 08 Nov 2014 14:51:05 -0800

          From comp.compilers

Related articles
Can this be proven for LL(1) grammars? (Lasse =?iso-8859-1?q?Hiller=F8e?= Petersen) (2014-11-06)
Re: Can this be proven for LL(1) grammars? (Kaz Kylheku) (2014-11-07)
Re: Can this be proven for LL(1) grammars? (SLK Mail) (2014-11-08)
| List of all articles for this month |

From: "SLK Mail" <>
Newsgroups: comp.compilers
Date: Sat, 08 Nov 2014 14:51:05 -0800
Organization: SLK Systems
References: 14-11-006
Keywords: parse, theory
Posted-Date: 10 Nov 2014 03:11:35 EST

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

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

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:

Post a followup to this message

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