Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1414 > unrolled thread

Can this be proven for LL(1) grammars?

Back to article view | Back to comp.compilers

Contents

  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

#1414 — Can this be proven for LL(1) grammars?

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

[toc] | [next] | [standalone]

#1419

On 2014-11-06, Lasse HillerC8e Petersen <lhp+news@toft-hp.dk> wrote:
> 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)?

This is true, and the informal proof is to work backwards: you cannot
take some grammar GR which is not LL(1) and embed it in a larger
context free grammar G which fixes the problem.

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

Indeed:

  G1 -> blah blah blah 'x'
  G2 -> blah blah blah 'y'

Oops! Of course, the language is LL(1) parseable, but requires
a refactored grammar in which we merge the similar left parts:

  G1_G2 -> blah blah blah G1_G2'
  G1_G2' -> 'x' | 'y'

If we are building a syntax tree as a semantic action, we can handle this
language by encoding the difference between the 'x' and 'y' variant in the
tree. We don't have G1 and G2 phrase structures, but a G1_G2 that
generates multiple forms.

> What if instead, S is defined only from a selection of rules with
> disjoint FIRST sets?

This might not help because of the threat of FIRST/FOLLOW conflicts.

The problem is that G1 and G2 might share some constituent, call it C.
The G1 and G2 rules contribute different material to FOLLOW(C):

  G1 -> 'x' C Z
  G2 -> 'y' C W

G1 and G2 nicely derive a starting nonterminal, so their FIRST sets are clearly
disjoint (in compliance with your stated constraint on S). But the combintion
of G1 and G2 causes a merging of FOLLOW(C) from G1, and FOLLOW(C) from G2.
Moreover, if C can derive empty (C -> N5), FIRST(C) is also being affected. In
general, conflicts can arise from this.  Even though there is no
FIRST(C)/FOLLOW(C) conflict in the G1 and G2 rules in isolation, possibly the
FIRST(C) from G1 could conflict with FOLLOW(C) in G2 or vice versa,
under the merge of these 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)?

This lets you replace any phrase structure in the language with
a "super token" which represents that phrase structure like
3 + MULTIPLICATIVE_EXPR.

This seems to fit in with sentential form representations that you
would use in generation or derivation of sentences.

This introduction cannot introduce a new FIRST/FOLLOW conflict.
R -> "R" means that the terminal "R" is in FIRST(R). Can it also
appaer in FOLLOW(R)? Only if grammar derives R R somewhere, and R happens to
derive N5. But in that case, there is already an existing FIRST/FOLLOW
conflict, unless perhaps the *only* rule for R was previously R -> N5.

If we have:

 S -> R R
 R -> N5

Then we add:

 R -> 'R'

We have a FIRST/FOLLOW conflict. Given the input 'R' it is ambiguous
whether it is S -> N5 'R'  or  S -> 'R' N5.

What's not clear to me is that the original before the new rule doesn't already
have a conflict. I think not because the symbol N5 only appears in FIRST sets,
not FOLLOW sets. In the original unaugmented grammar, we have FIRST(R) = { N5 }
and FOLLOW(R) = { }.  The grammar clearly matches the input in exactly
one way, by deriving R -> N5 twice.

Suppose that R actually derives something in addition to N5, and is embedded
in a correct grammar with no conflicts. Since there is no FIRST/FOLLOW
conflict that means that either R does not derive N5, or FIRST(R)
and FOLLOW(R) do not intersect. If they do not intersect, that means that
FOLLOW(R) was not derived from R: there is nothing in the grammar of
the form R R or R X R where symbols X potentially disappear by deriving N5.

Then if we add R -> 'R', it is harmless.

Informally, since R already derives *something* non-empty without conflicts,
then making R derive a new nonterminal, unique to R, will not create
a conflict. (R already succesfully derives tokens that are not necessarily
unique to the R rule, so why wouldn't it handle an additional unique one.)

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

I suspect (1) may pop out from what it means for a grammar to be "context
free", but since I already hand-waved through the first comment about it, I'm
going to leave it at that. :) I look forward to other responses.

[toc] | [prev] | [next] | [standalone]

#1427

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web