Re: LL1 program ???

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


Rodney Bates
--

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