Re: LL1 program ???

"Rodney M. Bates" <>
20 Jul 1998 16:55:37 -0400

          From comp.compilers

Related articles
LL1 program ??? (Aulas de =?iso-8859-1?Q?Inform=E1tica?=) (1998-07-01)
Re: LL1 program ??? (Srikanth M) (1998-07-03)
Re: LL1 program ??? (Joachim Durchholz) (1998-07-03)
Re: LL1 program ??? (Janaki S) (1998-07-10)
Re: LL1 program ??? (1998-07-11)
Re: LL1 program ??? (Joachim Durchholz) (1998-07-13)
Re: LL1 program ??? (Rodney M. Bates) (1998-07-20)
Re: LL1 program ??? (Jerry Leichter) (1998-07-21)
Re: LL1 program ??? (1998-07-24)
| List of all articles for this month |

From: "Rodney M. Bates" <>
Newsgroups: comp.compilers
Date: 20 Jul 1998 16:55:37 -0400
Organization: The Boeing Company
References: 98-07-009 98-07-033 98-07-098 98-07-110
Keywords: parse, LL(1)

Joachim Durchholz wrote:

> Of course this doesn't tell you whether the *language* is LL(1) or not.
> (An LL(1) language is a language that has an LL(1) grammar; if you
> grammar happens not to be LL(1), this doesn't mean an LL(1) grammar
> doesn't exist for it.)

This statement is a prime invitation to broach something which has
bothered me for a long time. According to the theory we have, a
language is just a subset of the strings over some alphabet and a
grammar is kind of recursive enumeration scheme to define such a set.
So, if I have a grammar which is not LL(1), I could search for another
grammar which is LL(1), and which defines the same set of strings.

But in practice, this is not nearly strong enough, if I want the
grammar in order to produce a parser. We use grammars in compilers
not just to ascertain syntactic correctness, but to define a syntactic
structure for an input program. So a suitable alternative grammar
will have to preserve not only the language, but some aspects of the
shape of its derivation trees as well.

Exactly what it needs to preserve, I can't fully define in any formal
way, although I think I have a reasonably good intuition for it. It
clearly includes things such as precedence and associativity, or
perhaps more generally, the nesting of syntactic constructs.

But that's not all. In addition to getting the grammar into a given
class while preserving whatever needs to be preserved about the shape
of trees, rewriting grammars for compilers also involves changing the
shape of the derivation trees in certain ways to provide places for
attributes, semantic actions, etc. And it isn't just the shape of the
trees. It often gets into the temporal behavior of the parsing
machine as well.

This also relates to the question of what constitutes an abstract
syntax tree and how does it relate to a derivation tree. Again, I
think I have a good intuition about this, but I don't know how to
describe it formally. I suspect that grammar rewrites which preserve
what we want them to might give the same or similar ASTs, if it were
somehow defined what that meant.

I think the theory of formal languages it missing some things, if it
is to be a basis for writing compilers etc. Or am I missing some

Rodney Bates

Post a followup to this message

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