Re: language twiddling, was Infinite look ahead required by C++?

"bartc" <bartc@freeuk.com> writes:


> In my design (derived from Algol-68 at one point), an if-statement looks
> like:
>
> if s then s else s fi


Yes, this was a brilliant innovation and well worth following.


> (where s is any sequence of statements/expressions). I guess that might be
> LL(1). But an if-statement can also look like:
>
> ( s | s | s )
>
> In this case it doesn't know it's an if-statement until the second "|"
> (because ( s | s, s | s ) is another kind of statement). Is this still
> LL(1)? I wouldn't have thought so now.


And, this is a mess. C's syntax of e ? e : e is better.


Whether it is still LL(1) depends on whether one can actually left
factor it, to something like:


    if-then-else-as-parens : start-part "|" s ")" ;
    other-stmt: start-part "," s "|" s ")" ;
    start-part: "(" s "|" s


However, doing this kind of left-factoring tends to really mess up the
design of the parser and semantics. You can't hook the semantics
where you want them because the parse tree has a bizarre shape due to
trying to make it LL(1).


And, to my mind, this is indicative of a problem. The question isn't
so much whether you can twist and contort your grammar into being
LL(1), but whether the "natural" grammar you would write is LL(1).


And, I'll readily admit some exceptions. For example, I find it
unnatural to write the kind of rules one needs to write to express
precedence and associativativity in LL(1) fashion. That doesn't mean
that a good grammar can't have precedences and associativities that
match naturally to one's subject area, and one doesn't necessarily
have to write the correct LL(1) rules to enforce that. You can
actually read up on the precedence parsing systems and see that there
are obvious ways to deal with many expression precedence problems.
That's perfectly ok. There is a formalism to solve the problem and
one can apply it and get predictable and understandable results that
match human intuition. Thus, if you want to do your precedences and
associativities with highest to lowest binding schemes, that is
perfectly fine.


> [I thought Algol-68 used a two-level VW grammar. -John]


Algol-68 was. I still have my copy of the report. However, much of
the two level grammar was to enforce certain semantic restrictions.
In particular, Algol-68 had a scheme where either you could implicitly
dereference pointers or you could implicitly take addresses or maybe
it was both, and the grammar would tell one how many levels of
addresses and dereferences that one needed to take. The two-level
grammar made that possible, because only by implicitly inserting the
right amount would the sentences actually parse.


Hope this helps,
-Chris


******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

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