Sat, 08 Nov 2014 14:51:05 -0800

Related articles |
---|

Can this be proven for LL(1) grammars? lhp+news@toft-hp.dk (Lasse =?iso-8859-1?q?Hiller=F8e?= Petersen) (2014-11-06) |

Re: Can this be proven for LL(1) grammars? kaz@kylheku.com (Kaz Kylheku) (2014-11-07) |

Re: Can this be proven for LL(1) grammars? slkpg4@gmail.com (SLK Mail) (2014-11-08) |

From: | "SLK Mail" <slkpg4@gmail.com> |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.