Ayacc/Aflex "entropy" (P2Ada)

Ayacc/Aflex "entropy" (P2Ada)

[Gautier]

Hi all.

I've observed the phenomenon that most
enhancements brought to Pascal.Y in my attempts
to extend P2Ada for the Borland-ish Pascal language
"nebula" increases the "Reduce/Reduce conflicts"
(what does it mean? nothing good surely...)
and can confuse the translator in unexpected way.

- Is there a strategy to avoid it (I'm completely
  amateur in ayacc) ?

- Should one "migrate" to a replacement of ayacc ?

- If so, is there an automatic way to translate
  Pascal.Y ?...

Volunteers are welcome to contribute a bit to
this work.
There seems to be some demand for porting
the monoculture, proprietary Delphi
(or Borland Pascal, Turbo Pascal) to portable,
standardized Ada. Present state of P2Ada is @
http://members.xoom.com/gdemont/logiciel/newp2ada.zip

Note that there is a PasTran tool by RR software
http://www.rrsoftware.com/ but which sort of Pascal
does it translate?...

-- 
Gautier

_____\\________________\_______\_________
http://members.xoom.com/gdemont/gsoft.htm

Re: Ayacc/Aflex "entropy" (P2Ada)

[Ray Blaak]

Gautier <Gautier.deMontmollin@Maths.UniNe.CH> writes:
> I've observed the phenomenon that most enhancements brought to Pascal.Y in my
> attempts to extend P2Ada for the Borland-ish Pascal language "nebula"
> increases the "Reduce/Reduce conflicts" (what does it mean? nothing good
> surely...)  and can confuse the translator in unexpected way.
> 
> - Is there a strategy to avoid it (I'm completely amateur in ayacc) ?

I have worked on a Delphi reverse engineering tool* for Rational Rose, and have
implemented a Delphi (Object Pascal) parser. Let's just say I feel your pain.

Delphi has many strange quirks that cause ambiguities in a straight forward
yacc-like grammar. Single token look ahead is very often not enough to decide
how to resolve to a rule.

The problems are related to the fact than many "keywords" are not in fact
reserved. All of the procedure directives, for example, are not (e.g. the
"virtual" in "procedure Method; virtual;". Semicolons are often optional, which
really makes life difficult for a parser (e.g. "procedure Method virtual;" is
also fine).

The Delphi compiler tolerates a fair bit of divergence from its official
description, which also makes life interesting.

The ways to resolve this are as follows:

- Use a better tool. Visual Parse, for example, supports n-token look ahead (at
  the cost of probable exponential explosion). This is not useful for a
  publicly available grammar file however (VP is a Windows proprietary parsing
  system).

- Use a completely different tool. Recursive descent? I don't know what freely
  available tools are out there.

- Bite the bullet and deal with each ambiguity explicitly by constructing
  precise descriptions of how things can be resolved. Avoid null rules at all
  costs. For example, a record type looks like:

  <record> = "record" <record_body> "end"
  <record_body> = | <field> | <record_body> <field>

  Note the empty choice that makes a record body optional. This kind of thing,
  however, tends to screw up parsers. Instead, make things explicit:

  <record> = "record" "end" | "record" <record_body> "end"
  <record_body> = <field> | <record_body> <field>

For what its worth, ayacc is probably as good as any other yacc tool. The real
work is to make the grammar rules unambiguous.


* See http://www.ensemble-systems.com if you are interested. It is called the
  Rose Delphi Link
-- 
Cheers,                                        The Rhythm is around me,
                                               The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,
blaak@infomatch.com                            The Rhythm has my soul.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Gautier]

Thank you for your precisions! Effectively I'll
(in a not so near future) re-work from the 97 version
by Carlisle & Gasser and add slowly the new features.

Effectively even the TP6 features are ambiguous:
the new keywords can be also used as identifiers
for variables!!

  function tasm:word; far; assembler;
    var near: byte; far:word;
    assembler: integer;
     asm
      cli
     end;

(Example from newp2ada)

-- 
Gautier

_____\\________________\_______\_________
http://members.xoom.com/gdemont/gsoft.htm

Re: Ayacc/Aflex "entropy" (P2Ada)

[Ted Dennison]

In article <3813716C.52655126@Maths.UniNe.CH>,
  Gautier <Gautier.deMontmollin@Maths.UniNe.CH> wrote:
> to extend P2Ada for the Borland-ish Pascal language
> "nebula" increases the "Reduce/Reduce conflicts"
> (what does it mean? nothing good surely...)
> and can confuse the translator in unexpected way.
>
> - Is there a strategy to avoid it (I'm completely
>   amateur in ayacc) ?

You ought to consider getting a good yacc book. I use the O'Reilly
Lex/Yacc nutshell book, and it seems quite good. It has a whole chapter
on Yacc conflicts that you might find most helpful. (Reduce/Reduce
roughly means a series of tokens matches 2 rules and it can't decide
which to use).

> - Should one "migrate" to a replacement of ayacc ?
>
> - If so, is there an automatic way to translate
>   Pascal.Y ?...

Within a couple of months I hope to get OpenToken to a point where it
would be a useful alternative for such projects. As it stands now, you'd
have to do you own parsing, though.

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Ted Dennison]

In article <3813716C.52655126@Maths.UniNe.CH>,
  Gautier <Gautier.deMontmollin@Maths.UniNe.CH> wrote:
> to extend P2Ada for the Borland-ish Pascal language
> "nebula" increases the "Reduce/Reduce conflicts"
> (what does it mean? nothing good surely...)
> and can confuse the translator in unexpected way.
>
> - Is there a strategy to avoid it (I'm completely
>   amateur in ayacc) ?

You ought to consider getting a good yacc book. I use the O'Reilly
Lex/Yacc nutshell book, and it seems quite good. It has a whole chapter
on Yacc conflicts that you might find most helpful. (Reduce/Reduce
roughly means a series of tokens matches 2 rules and it can't decide
which to use).

> - Should one "migrate" to a replacement of ayacc ?
>
> - If so, is there an automatic way to translate
>   Pascal.Y ?...

Within a couple of months I hope to get OpenToken (
http://www.telepath.com/dennison/Ted/OpenToken/OpenToken.html ) to a
point where it would be a useful alternative for such projects. As it
stands now, you'd have to do you own parsing, though.

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[David Starner]

On Tue, 26 Oct 1999 01:36:45 GMT, Robert Dewar <robert_dewar@my-deja.com> wrote:
>I find it appalling that people use such rusty tools as YACC
>and AYACC, these are very limited tools which seem to completely
>ignore the considerable advances in this area in the last 25
>years!

A better recommendation is . . .

>Automatic lexical analyzers are almost completely useless
>in a compiler context.

Blanket claims without evidence or explanation are also almost
completely useless.

--
David Starner - dstarner98@aasaa.ofe.org

Re: Ayacc/Aflex "entropy" (P2Ada)

[Gautier]

Robert Dewar:

> I find it appalling that people use such rusty tools as YACC
> and AYACC, these are very limited tools which seem to completely
> ignore the considerable advances in this area in the last 25
> years!

The problem is that these tools are not time-bombed.
They don't tell simple users: "Sorry, but now I refuse
to run. Please download XYZ". E.g. I know almost nothing
about yacc / grounf / whatever, whether it's old or not etc.

Imagine a Fortran compiler saying after each compilation:
"You know what: you could save months of debugging if
 you were programming in a language called Ada. Please
 upgrade me !"

But I'm sure that ACT will at last react as tens of thousands
people migrate from Borland Pascal dialects to C++ and
provide a translator made with the modernest tools!

-- 
Gautier

--------
http://members.xoom.com/gdemont/

Re: Ayacc/Aflex "entropy" (P2Ada)

[bourguet]

In article <7v30jd$3i6$1@nnrp1.deja.com>,
  Robert Dewar <robert_dewar@my-deja.com> wrote:
> In article <7v2400$e02$1@nnrp1.deja.com>,
>   Ted Dennison <dennison@telepath.com> wrote:
> > You ought to consider getting a good yacc book. I use the
> O'Reilly
> > Lex/Yacc nutshell book, and it seems quite good. It has a
> whole chapter
> > on Yacc conflicts that you might find most helpful.
> (Reduce/Reduce
> > roughly means a series of tokens matches 2 rules and it can't
> decide
> > which to use).
>
> I find it appalling that people use such rusty tools as YACC
> and AYACC, these are very limited tools which seem to completely
> ignore the considerable advances in this area in the last 25
> years!

Could you post some references to books or web pages or good keywords
to reduce the space search on the web. All books that I know off which
speak about parser generators are at the level of LL(1) or simplified
LR(1) (LALR(1) or other way of reducing the LR tables) except T.J. Parr
book on PCCTS which describe more how to use PCCTS than its
"redefinition" of LL(k) and how to use it to build a parser generator.
Web pages I've found with my naive keyword approaches have not be of
more use; some buzzwords like OO where added but if they were more than
buzzwords, it was not clear for me.

Thanks,

-- Jean-Marc


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Ted Dennison]

In article <7v3u0f$nn6$1@nnrp1.deja.com>,
  bourguet@my-deja.com wrote:
> In article <7v30jd$3i6$1@nnrp1.deja.com>,
>   Robert Dewar <robert_dewar@my-deja.com> wrote:
> > In article <7v2400$e02$1@nnrp1.deja.com>,
> > I find it appalling that people use such rusty tools as YACC
> > and AYACC, these are very limited tools which seem to completely
> > ignore the considerable advances in this area in the last 25
> > years!
>
> Could you post some references to books or web pages or good keywords
> to reduce the space search on the web. All books that I know off which

I'd like to third that request for references. I'm doing my thesis in
this area, so I'd like to be at least nominally informed on the subject.
:-)

But a web search on my part lead to only *one* alternative to lex/yacc.
I'd particularly like to know about what parts of lex and or yacc are
considered inadaquate or outdated.

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Robert Dewar]

In article <7v32oe$9ic1@news.cis.okstate.edu>,
  dstarner98@aasaa.ofe.org wrote:
> On Tue, 26 Oct 1999 01:36:45 GMT, Robert Dewar
<robert_dewar@my-deja.com> wrote:
> >I find it appalling that people use such rusty tools as YACC
> >and AYACC, these are very limited tools which seem to
completely
> >ignore the considerable advances in this area in the last 25
> >years!
>
> A better recommendation is . . .
>
> >Automatic lexical analyzers are almost completely useless
> >in a compiler context.
>
> Blanket claims without evidence or explanation are also almost
> completely useless.


A reference is the tutorial I gave at the compiler construction
conference some years ago. The point is that efficient lexical
analyzers are very easy to write, it is pretty much as easy to
write such as to generate the tables for an automatic tool, and
most of the automatic tools are horribly slow (they are one of
many tools in our relatively recently developed technology of
horribly slow compilers :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Robert Dewar]

In article <7v2400$e02$1@nnrp1.deja.com>,
  Ted Dennison <dennison@telepath.com> wrote:
> You ought to consider getting a good yacc book. I use the
O'Reilly
> Lex/Yacc nutshell book, and it seems quite good. It has a
whole chapter
> on Yacc conflicts that you might find most helpful.
(Reduce/Reduce
> roughly means a series of tokens matches 2 rules and it can't
decide
> which to use).

I find it appalling that people use such rusty tools as YACC
and AYACC, these are very limited tools which seem to completely
ignore the considerable advances in this area in the last 25
years!

> > - Should one "migrate" to a replacement of ayacc ?
> >
> > - If so, is there an automatic way to translate
> >   Pascal.Y ?...
>
> Within a couple of months I hope to get OpenToken to a point
where it
> would be a useful alternative for such projects. As it stands
now, you'd
> have to do you own parsing, though.


Automatic lexical analyzers are almost completely useless
in a compiler context.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[William B. Clodius]

Ted Dennison wrote:
> <snip>
> I'd like to third that request for references. I'm doing my thesis in
> this area, so I'd like to be at least nominally informed on the subject.
> :-)
> 
> But a web search on my part lead to only *one* alternative to lex/yacc.
> I'd particularly like to know about what parts of lex and or yacc are
> considered inadaquate or outdated.
> <snip>

It must have been an unimaginative search, ( are you restricting
yourself only to generators that output Ada?, of which I know two
(AYACC/AFLEX and Cocktail)). There are tons of alternatives (with output
in C, C++, Java, Ada, Eiffel, Forth, Icon, Smalltalk, SML, Haskell,
Pearl, Python, (TCL?), Basic, Pascal, Modula 2, Oberon, even Fortran
(though LR no longer seems to be available in its original form)), which
is part of the problem. If there were one alternative it would stand out
and be recognized, but with many alternatives many people simply go with
the best known rather than spending the several days necessary to
evaluate several alternatives. For starting points try

http://www.first.gmd.de/cogent/catalog/
http://iecc.com/compilers/tools.html
http://www.cs.rhbnc.ac.uk/research/languages/lookahead_backtrack.shtml
and while it requirees some searching http://www.idiom.com/free-compilers/

for opinions you might search in the comp.compilers newsgroup archives http://www.iecc.com/compilers/

Two have their own newsgroups

compilers.tools.pccts
compilers.tools.javacc

Re: Ayacc/Aflex "entropy" (P2Ada)

[Robert I. Eachus]

bourguet@my-deja.com wrote:
> Could you post some references to books or web pages or good keywords
> to reduce the space search on the web. All books that I know off which
> speak about parser generators are at the level of LL(1) or simplified
> LR(1) (LALR(1) or other way of reducing the LR tables) except T.J. Parr
> book on PCCTS which describe more how to use PCCTS than its
> "redefinition" of LL(k) and how to use it to build a parser generator.
> Web pages I've found with my naive keyword approaches have not be of
> more use; some buzzwords like OO where added but if they were more than
> buzzwords, it was not clear for me.

    One alternative would be to use a parser generator which uses
Early's algorithm.  Early's algorithm will cheerfully accept any LR(k)
grammar, and parse it quite fast, but it can also accept and recognize
ambiguous grammars, but the performance degrades to O(n**3).
-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Ayacc/Aflex "entropy" (P2Ada)

[Robert Dewar]

In article <3816331A.99C596D2@mitre.org>,
  "Robert I. Eachus" <eachus@mitre.org> wrote:
>     One alternative would be to use a parser generator which
uses
> Early's algorithm.  Early's algorithm will cheerfully accept
any LR(k)
> grammar, and parse it quite fast, but it can also accept and
recognize
> ambiguous grammars, but the performance degrades to O(n**3).



I think the parsing algorithm is less of an issue than error
recovery, the error recovery of YACC is pathetic. It is
surprising what can be done with automatic generators in
this area. See some of the papers from Fisher and Charles from
the early days of the NYU Ada/Ed project. Many commercial Ada/83
compilers made use of this work, and the syntactic error
recovery of Ada/Ed was really quite good (not as good as GNAT,
but GNAT has a lot of careful hand coded heuristic stuff that
I doubt any automatic system could fully match).

Robert Dewar


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Ted Dennison]

In article <7v5ns8$2h1$1@nnrp1.deja.com>,
  Robert Dewar <robert_dewar@my-deja.com> wrote:

> I think the parsing algorithm is less of an issue than error
> recovery, the error recovery of YACC is pathetic. It is

Ahh, well *that* I knew. How could I not? I've used yacc. :-)

> surprising what can be done with automatic generators in
> this area. See some of the papers from Fisher and Charles from
> the early days of the NYU Ada/Ed project. Many commercial Ada/83
> compilers made use of this work, and the syntactic error
> recovery of Ada/Ed was really quite good (not as good as GNAT,

Hmm. I'll have to go hunting for that.

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[bourguet]

In article <7v5ns8$2h1$1@nnrp1.deja.com>,
  Robert Dewar <robert_dewar@my-deja.com> wrote:
> In article <3816331A.99C596D2@mitre.org>,
>   "Robert I. Eachus" <eachus@mitre.org> wrote:
> >     One alternative would be to use a parser generator which
> uses
> > Early's algorithm.  Early's algorithm will cheerfully accept
> any LR(k)
> > grammar, and parse it quite fast, but it can also accept and
> recognize
> > ambiguous grammars, but the performance degrades to O(n**3).

I did knew about Early's algorithm, but thanks for reminding me about
it.

> I think the parsing algorithm is less of an issue than error
> recovery, the error recovery of YACC is pathetic. It is
> surprising what can be done with automatic generators in
> this area.

If you were speaking about error recovery, I knew that there where
better than the non existant automatic and crude manual one of YACC.

-- Jean-Marc


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Tarjei Jensen]

Gautier wrote in message <3815650F.A1D4BCD6@maths.unine.ch>...
>Robert Dewar:
>
>> I find it appalling that people use such rusty tools as YACC
>> and AYACC, these are very limited tools which seem to completely
>> ignore the considerable advances in this area in the last 25
>> years!
>
>The problem is that these tools are not time-bombed.
>They don't tell simple users: "Sorry, but now I refuse
>to run. Please download XYZ". E.g. I know almost nothing
>about yacc / grounf / whatever, whether it's old or not etc.


Perhaps the Cocktail kit (the Ada version) is better? It is available
somewhere. I don't have the URL nearby.

Greetings,

Re: Ayacc/Aflex "entropy" (P2Ada)

[David Botton]

> Perhaps the Cocktail kit (the Ada version) is better? It is available
> somewhere. I don't have the URL nearby.

http://www.informatik.uni-stuttgart.de/ifi/ps/cocktail/

Re: Ayacc/Aflex "entropy" (P2Ada)

[Robert I. Eachus]

Robert Dewar wrote:
> 
  
> I think the parsing algorithm is less of an issue than error
> recovery,...

   Ageed.

> ...the error recovery of YACC is pathetic.

   Worse than that.  Since YACC does not even correctly implement
LALR(1),
you sometimes have to work hard to get it to compile correct programs.

> It is
> surprising what can be done with automatic generators in
> this area. See some of the papers from Fisher and Charles from
> the early days of the NYU Ada/Ed project.

  Yep, very good, and as you may remember Pat Prange and I extended LALR
on Multics in this direction.

> Many commercial Ada/83
> compilers made use of this work, and the syntactic error
> recovery of Ada/Ed was really quite good (not as good as GNAT,
> but GNAT has a lot of careful hand coded heuristic stuff that
> I doubt any automatic system could fully match).
 
   Agreed.  Again when using LALR, the automatic error messages and
error recovery was acceptable, but adding just a few 'extra' productions
to the grammar can (and did) vastly improve error diagnosis.  In fact,
one of the hardest problems of generating meaningful error messages is
knowing what the user intended to do, or for that matter what users do
wrong.  One of the biggest advantages of the Open Source approach is
that it is easier to get feedback on unacceptable error diagnostics. 
For example:

   ...
   package body Foobar is
   ...
   procedure Foo(X: in out Bar);
     I: Integer :=3;
   begin ...

   Is syntactically correct in Ada, but cannot be correct semantically.
However there is no semantic rule that says it is illegal either. 
Putting in a special case rule to recognize that the semicolon should be
an "is" helps a lot, but you also want to look further to deliver the
right error message.  This error commonly happens when someone uses the
package specification as a template for creating the package body.  But
does that begin belong to Foo or Foobar?  Looking at the package 
specification helps, but you really need to look ahead to see the "end"
that matches it.  (And of course insert a dummy body or change the
semicolon to "is" as appropriate.)

-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Ayacc/Aflex "entropy" (P2Ada)

[Brian Rogoff]

On Tue, 26 Oct 1999, Robert Dewar wrote:
> In article <7v32oe$9ic1@news.cis.okstate.edu>,
>   dstarner98@aasaa.ofe.org wrote:
> > On Tue, 26 Oct 1999 01:36:45 GMT, Robert Dewar
> <robert_dewar@my-deja.com> wrote:
> > >I find it appalling that people use such rusty tools as YACC
> > >and AYACC, these are very limited tools which seem to
> completely
> > >ignore the considerable advances in this area in the last 25
> > >years!
> >
> > A better recommendation is . . .
> >
> > >Automatic lexical analyzers are almost completely useless
> > >in a compiler context.
> >
> > Blanket claims without evidence or explanation are also almost
> > completely useless.
> 
> 
> A reference is the tutorial I gave at the compiler construction
> conference some years ago.

I know you hate this, but is there any way this tutorial can be made
available on the web? Or, barring that, a precise reference to which 
compiler construction conference, etc., etc. Not everyone has easy access 
to a good university library!

> The point is that efficient lexical
> analyzers are very easy to write, it is pretty much as easy to
> write such as to generate the tables for an automatic tool, and
> most of the automatic tools are horribly slow (they are one of
> many tools in our relatively recently developed technology of
> horribly slow compilers :-)

More "quotable Dewar"! I'm slowly coming around to agreeing with this, 
though yacc still has the advantage (like C) of being widely known and
used. 

-- Brian

Re: Ayacc/Aflex "entropy" (P2Ada)

[Robert Dewar]

In article
<Pine.BSF.4.10.9910301717450.21024-100000@shell5.ba.best.com>,
  Brian Rogoff <bpr@shell5.ba.best.com> wrote:
> I know you hate this, but is there any way this tutorial can
> be made available on the web?

hate? I really don't know what you are talking about, a most
odd interpretation of anything I have said. I think it would
be nice if everything was on the Web. As to whether this
particular item can be put on the Web, I guess you would
have to ask the copyright holder, which is not me!



Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Robert Dewar]

In article <3819CBDA.E801A064@mitre.org>,
  "Robert I. Eachus" <eachus@mitre.org> wrote:
>    package body Foobar is
>    ...
>    procedure Foo(X: in out Bar);
>      I: Integer :=3;
>    begin ...
>
>    Is syntactically correct in Ada, but cannot be correct
>    semantically. However there is no semantic rule that says
>    it  is illegal either.

Remember to check that the set of declarations (where I is
in the above) does not include a pragma Import for Foo, which
renders this example semantically legal (have a look in the
GNAT code for the rather complex details in handling this
case correctly :-)

> Putting in a special case rule to recognize that the semicolon
> should be an "is" helps a lot, but you also want to look
> further to deliver the right error message.

If Robert Eachus is saying that it is easy to add rules to
a typical table driver parser to handle this case, all I can
say is (a) I never saw it done and (b) I think it would be
tricky, and (c) the only thing that would convince me is an
actual working example.

The trouble in this kind of error detection and recovery is
very much that the devil is in the engineering details.

For example, people have suggested for years the idea of using
indentation to help error recovery, but I have not seen this
systematically implemented till GNAT, and it is really quite
tricky (have a look at par-endh.adb in the GNAT sources for
example!)

Robert Dewar


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ayacc/Aflex "entropy" (P2Ada)

[Robert I. Eachus]

Robert Dewar wrote:
  
> Remember to check that the set of declarations (where I is
> in the above) does not include a pragma Import for Foo, which
> renders this example semantically legal (have a look in the
> GNAT code for the rather complex details in handling this
> case correctly :-)

  Actually, that's why I put in a following declaration but no ellipsis.
 
> > Putting in a special case rule to recognize that the semicolon
> > should be an "is" helps a lot, but you also want to look
> > further to deliver the right error message.
 
> If Robert Eachus is saying that it is easy to add rules to
> a typical table driver parser to handle this case, all I can
> say is (a) I never saw it done and (b) I think it would be
> tricky, and (c) the only thing that would convince me is an
> actual working example.

   Somewhere I have a source listing for LALR for Multics, and a paper
showing how it is done.  But it really isn't so hard.  What you want is
to have productions which are only used in error situations.  Once
errors start spewing out, sometimes the "right" correction is
arbitrarily far back.  But since I am doing LR not LL parsing, it is
possible to add a production such as:

   <subprogram body> ::= <subprogram declaration> ; <begin block>
[<name>] ;

    (There is a standard production:

   <begin block> ::= begin <sequence of statements> end

    This simplifies other error correction...) 

  Now what happens is the compiler notices that it is in "panic mode." 
Lots of errors and no obvious way to continue the parse.  Instead of
just trying to match whatever is on the stack to tokens in the forward
direction, you basically flip a switch and then try to restart from the
(lexical) beginning of
each production in the parse stack with these additional rules switched
in.

  The Ada/SIL compiler grammer had six such productions, including the
one above, and between them they reduced the number of error messages
produced by the ACVC B-tests by seventy something percent.  Things like
= or : or even : = for assignment were detected and fixed by a different
process.  These rules were only used for these "arbitrary lookahead"
errors, where the error could not be detected until many tokens had been
read and processed. 

> The trouble in this kind of error detection and recovery is
> very much that the devil is in the engineering details.

    Amen!
 
> For example, people have suggested for years the idea of using
> indentation to help error recovery, but I have not seen this
> systematically implemented till GNAT, and it is really quite
> tricky (have a look at par-endh.adb in the GNAT sources for
> example!)
 
   Yes, that is pretty hairy because you also have to infer what the
user's indentation style is, and you can't reject anything for bad
indentation (absent -gnatg ;-) but you need to go arbitrarily far back
once you do hit the error to find the right fix.
 
-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...