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

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

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