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

Groups > comp.compilers > #1313 > unrolled thread

LR(1) Parsing : Error Handling & Recovery

Back to article view | Back to comp.compilers

Contents

  LR(1) Parsing : Error Handling & Recovery Seima Rao <seimarao@gmail.com> - 2014-07-10 05:30 +0530
    Re: LR(1) Parsing : Error Handling & Recovery Ivan Godard <ivan@ootbcomp.com> - 2014-07-16 16:39 -0400
      Re: LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-07-17 20:15 +0300
        Re: LR(1) Parsing : Error Handling & Recovery Ivan Godard <ivan@ootbcomp.com> - 2014-07-17 13:03 -0700
          Re: LR(1) Parsing : Error Handling & Recovery Ivan Godard <ivan@ootbcomp.com> - 2014-07-17 13:57 -0700
            Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (William Clodius) - 2014-07-18 13:41 -0600
              Re: LR(1) Parsing : Error Handling & Recovery Stefan Monnier <monnier@iro.umontreal.ca> - 2014-07-18 21:09 -0400
                Re: LR(1) Parsing : Error Handling & Recovery Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-07-19 12:04 +0200
                  Re: LR(1) Parsing : Error Handling & Recovery Stefan Monnier <monnier@iro.umontreal.ca> - 2014-07-20 10:28 -0400
                    Re: LR(1) Parsing : Error Handling & Recovery Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2014-07-21 10:46 +0200
                      Re: LR(1) Parsing : Error Handling & Recovery Stefan Monnier <monnier@iro.umontreal.ca> - 2014-08-06 21:32 -0400
              Re: LR(1) Parsing : Error Handling & Recovery arnold@skeeve.com (Aharon Robbins) - 2014-07-20 06:05 +0000
      Re: LR(1) Parsing : Error Handling & Recovery George Neuner <gneuner2@comcast.net> - 2014-07-17 18:49 -0400
        Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (William Clodius) - 2014-07-18 13:41 -0600
          Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-07-19 15:29 +0200
            Re: LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-07-20 00:40 +0300
              Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-07-20 01:38 +0200
                Re: LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-07-21 15:20 +0300
                  Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-07-21 18:39 +0200
                    Re: LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-08-26 13:44 +0300
                      Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-08-29 11:13 +0200
                        Re: split tokens; was LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-09-03 16:57 +0300
                        Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-09-03 19:07 +0200
          Re: LR(1) Parsing : Error Handling & Recovery George Neuner <gneuner2@comcast.net> - 2014-07-20 01:19 -0400
            Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (William Clodius) - 2014-07-20 21:43 -0600
              Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (William Clodius) - 2014-07-21 21:44 -0600
            Re: LR(1) Parsing : Error Handling & Recovery Chris Dodd <cdodd@acm.org> - 2014-07-21 06:07 +0000
              Re: LR(1) Parsing : Error Handling & Recovery George Neuner <gneuner2@comcast.net> - 2014-07-25 21:58 -0400
                Re: LR(1) Parsing : Error Handling & Recovery Chris Dodd <cdodd@acm.org> - 2014-07-26 21:16 +0000
                  Re: LR(1) Parsing : Error Handling & Recovery Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2014-07-28 14:43 +0200
                    Re: LR(1) Parsing : Error Handling & Recovery Chris Dodd <cdodd@acm.org> - 2014-07-29 19:38 +0000
    Re: LR(1) Parsing : Error Handling & Recovery Eric <news@fx29.iad.highwinds-media.com> - 2014-07-16 16:40 -0400

Page 1 of 2  [1] 2  Next page →

#1313 — LR(1) Parsing : Error Handling & Recovery

Hi,

    I am a practitioner of bottom up parsing by yacc and similar tools
for some time now.

    However, till date, I am flummoxed by error handling & recovery.

    How far is impressive error handling & recovery possible by LR(1) parsers ?

    What would be good references for the subject?

    As an aside, do the famous compilers use LR(1) parsing ?

Sincerely,
Seima Rao

[toc] | [next] | [standalone]

#1314

On 7/9/2014 5:00 PM, Seima Rao wrote:
> How far is impressive error handling & recovery possible by LR(1)
> parsers ?
>
> What would be good references for the subject?
>
> As an aside, do the famous compilers use LR(1) parsing ?

LR1 was an experiment. The way to get apt error messages out of
one is to add error production rules. Unfortunately that process
explodes the state space, resulting in generally poor quality compilers.

As a practical matter, natural languages are pretty much LL1 (German
verbs excepted) so people are reasonably familiar to quasi-linear
parsing. A recursive descent LL1 parser can be written in less time than
a LR1 grammar for the same language can be debugged, if it ever is. For
those that really really believe in parser-generators, high-quality
generators exist for LL1 too. Nearly all languages yield to LL1
techniques (the formal proofs that a language is not LL1 are
irrelevant), often by introducing a few union-productions into the
lexer; examples have been shown here, such as DOI=1 in Fortran.

The great advantage of a recursive-descent parser is that you can do
most semantic analysis on the fly while you are at it, and can emit apt
and copious error messages at the point where the source first goes off
the rails. You can even do a decent job of recovery: for example, an
unrecognized identifier can be used to search for an approximate match
in the current dictionary (also built on the fly) to fix a typo, thereby
avoiding the cascade of irrelevant diagnostics typical of YACC parsers.

FWIW, I recall hearing that GCC switched from LR1 (LALR?) to
recursive-descent a few years back. You couldn't pay me to work on a
YACC-based front end.

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

#1316

Hello,

On 7/16/14, 11:39 PM, Ivan Godard wrote:
> FWIW, I recall hearing that GCC switched from LR1 (LALR?) to
> recursive-descent a few years back.

Yes, gcc switched to a hand-coded parser; the gcc team claimed that one
of the benefits was diagnostic location improvements (and potentially
other diagnostic improvements);see https://gcc.gnu.org/wiki/New_C_Parser

But, I guess they could say the same thing if they replaced the hand
coded Fortran parser with a LALR parser. Ibve compared recently an
enhanced LALRb parser with gfortran; the former has better error
recovery and in many cases more accurate error messages whereas the
latter sometimes just prints the clichC) bUnclassifiable Statementb.

Anyway, other implementers (e.g. clang team) also confirm that C++ is
best parsed by a recursive descent parser; Ibve not created a C++ parser
and cannot comment on it.

Regards,
Ev. Drikos

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

#1317

On 7/17/2014 10:15 AM, Evangelos Drikos wrote:

> But, I guess they could say the same thing if they replaced the hand
> coded Fortran parser with a LALR parser. I've compared recently an
> enhanced LALR parser with gfortran; the former has better error
> recovery and in many cases more accurate error messages whereas the
> latter sometimes just prints the cliche "Unclassifiable Statement".

It is my understanding (admittedly not based on personal experience)
that adding good error handling to LALR parser generator rules leads to
rule explosion and difficulties in producing a consistent rule set
without odd corner cases. Can you comment? If possible, can you give a
sense of the difference in rule-set size and parser performance between
your improved error set and one for the same language with no error
productions at all?

BTW: the Univac 1108 Fortran II compiler had, as many batch compilers
did, a cut-off so that if the compiler went completely off the rails it
would stop printing errors and append "Not all errors listed" as a final
message.

You guessed it: at SINTEF (NTH, Trondheim) circa 1974 we had a Fortran
program whose *only* diagnostic was: "Not all errors listed".

Ivan
[The problem with LALR error recovery is that the generated parser
combines states that are the same if your program is valid, but they
are from different grammar rules, so you'd want to produce different
error messages.  The size of LR(1) parser tables was an issue on a 64K
PDP-11, but they're trivial now, and I don't know of any reason other
than inertia to use LALR rather than LR(1). -John]

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

#1319

On 7/17/2014 1:03 PM, Ivan Godard wrote:

> [The problem with LALR error recovery is that the generated parser
> combines states that are the same if your program is valid, but they
> are from different grammar rules, so you'd want to produce different
> error messages.  The size of LR(1) parser tables was an issue on a 64K
> PDP-11, but they're trivial now, and I don't know of any reason other
> than inertia to use LALR rather than LR(1). -John]
>

This suggests that LALR with sufficient error handling is of the same
size as LR(1), so I'll rephrase my question in those terms: what is
the ruleset size difference between good and no error handling for the
same language? I am concerned with ruleset size here, not table size.
Ruleset size matters to the language designer, which I have repeatedly
been in my career. Too large a ruleset makes a language intellectually
intractable and impractical to extend; one of the charges against
Algol68 was that it was too big, compared to Algol60; the WG2.1 group
of then should see the C++ spec we have now :-(

In my recursive descent compilers, I have always done semantic analysis
on the fly while doing the parse, which lets me give semantically apt
diagnostics where appropriate rather than "left parenthesis expected",
or, worse, the "right bracket cannot appear here" kind of diagnostic.

Doing semantics on the fly also permits a language to have a
semantic-directed grammar, where what can follow "foo" depends on what
"foo" is. Such grammars have much greater expressiveness than pure
BNF-style syntax, although that beauty may be in the eye of the beholder.

[Error rules in yacc parsers are really for error recovery, not error
reporting.  They let the parser resynchronize at a boundary such as a
semicolon between statements.  LALR can only tell you that the parse
failed, and it can give you a set of tokens that would be valid where
the parse failed, but that set is often too large due to the way the
states are created.  It's certainly easier to produce diagnostics in a
RD parser.  What's hard is to verify that the language it accepts is
the language you want, and that it correctly catches any invalid
input. -John]

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

#1322

Ivan Godard <ivan@ootbcomp.com> wrote:

> <snip>
>
> [Error rules in yacc parsers are really for error recovery, not error
> reporting.  They let the parser resynchronize at a boundary such as a
> semicolon between statements.  LALR can only tell you that the parse
> failed, and it can give you a set of tokens that would be valid where
> the parse failed, but that set is often too large due to the way the
> states are created.  It's certainly easier to produce diagnostics in a
> RD parser.  What's hard is to verify that the language it accepts is
> the language you want, and that it correctly catches any invalid
> input. -John]
This sort of comment has appeared frequently in the past and to some
extent I find it puzzing. A recursive descent translation of an LL(k)
(with k small) grammar is straightforward, and should readilly match the
grammar, and give you the parse you desire. Is the problem that error
recognition generally does not readily map to the desired grammar, or
that the usual "on the fly" semantic anayisis in such implementations
loses context, or something else I haven't recognized?

[The practical problem is that RD parsers are typically written by
hand, and after a couple of tweaks to the grammar and what are
supposed to be matching tweaks to the code, they can get out of sync.
Also, error checking code is boring and one's eyes tend to glaze.  An
RD parser mechanically generated from the grammar should reflect the
grammar as accurately as any other mechanically generated parser.
-John]

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

#1324

> This sort of comment has appeared frequently in the past and to some
> extent I find it puzzing. A recursive descent translation of an LL(k)
> (with k small) grammar is straightforward, and should readilly match the
> grammar, and give you the parse you desire. Is the problem that error

This is misleading.  Take your BNF and pass it to a PEG parser: a PEG
parser can accept pretty much the same input syntax as a BNF parser, and
can be considered as a kind of RD parser, so you'd think the result is
necessarily correct.
Well, not so, because the semantics of the language is not the same:
The PEG/RD parser will "silently resolve ambiguities".


        Stefan

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

#1327

Stefan Monnier schrieb:
>> This sort of comment has appeared frequently in the past and to some
>> extent I find it puzzing. A recursive descent translation of an LL(k)
>> (with k small) grammar is straightforward, and should readilly match the
>> grammar, and give you the parse you desire. Is the problem that error
>
> This is misleading.  Take your BNF and pass it to a PEG parser: a PEG
> parser can accept pretty much the same input syntax as a BNF parser, and
> can be considered as a kind of RD parser, so you'd think the result is
> necessarily correct.

Sorry, that's ambiguous :-]

You miss to define what is "passing a grammar to an parser". Should the
PEG parser
- parse the grammar
- create an parser from the grammar
- interpret the grammar in parsing further input

In general the result cannot be more correct than is your grammar.

If your grammar is unambiguous, the results should be the same
(equivalent at least) in either case. But if your grammar is ambiguous,
what "result" do you consider possibly incorrect?

> Well, not so, because the semantics of the language is not the same:

That's the case with every grammar: who knows whether it really reflects
the semantics of the language? A parser generator only can verify that a
grammar is *valid*, but not that it matches a specific language.

> The PEG/RD parser will "silently resolve ambiguities".

IMO a correct PEG parser generator should warn about ambiguities in the
grammar, just as every other parser generator does. In such cases the
disambiguation is *not* performed by the parser generator, but by the
grammar writer, who arranges the alternatives in the correct (intended)
order.

I only can hope that you know how to use your programming tools, and
don't belong to those coders who say: "it compiles, so let's ship it" ;-)

DoDi

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

#1333

> IMO a correct PEG parser generator should warn about ambiguities in the
> grammar, just as every other parser generator does.

AFAIK, there can't be ambiguities in a PEG grammar, because the PEG
semantics explicitly have a "use the first match" semantics.


        Stefan

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

#1337

Stefan Monnier schrieb:
>> IMO a correct PEG parser generator should warn about ambiguities in the
>> grammar, just as every other parser generator does.
>
> AFAIK, there can't be ambiguities in a PEG grammar, because the PEG
> semantics explicitly have a "use the first match" semantics.

How is a grammar related to an specific parser type?

Remember the origin of my comment:
 >>
Take your BNF and pass it to a PEG parser: a PEG parser can accept
pretty much the same input syntax as a BNF parser, and can be considered
as a kind of RD parser, so you'd think the result is necessarily correct.
<<

A grammar primarily describes a language, not an parser. Almost every
parser generator (including PEG) will accept a correct LL(1) grammar,
and the generated parsers will accept the same language. A PEG parser
*also* may be created from a grammar that is rejected by other parser
generators, for contained ambiguities. That's what I consider an
ambiguous grammar.

DoDi

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

#1363

> How is a grammar related to an specific parser type?

AFAIK PEG parsers don't take a BNF grammar.  Instead they take
a "grammar" whose syntax looks very much like a BNF grammar but whose
semantics is specified by the usual PEG semantics.


        Stefan

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

#1332

In article <14-07-032@comp.compilers>,
Our Esteemed Moderator wrote:
>[The practical problem is that RD parsers are typically written by
>hand, and after a couple of tweaks to the grammar and what are
>supposed to be matching tweaks to the code, they can get out of sync.
>Also, error checking code is boring and one's eyes tend to glaze.  An
>RD parser mechanically generated from the grammar should reflect the
>grammar as accurately as any other mechanically generated parser.
>-John]

A long time ago, in a galaxy far, far away, the guys at the Georgia
Institute of Technology School of Information and Computer Science wrote
STACC (STill Another Compiler Compiler) which was yacc-like but generated
a recursive descent parser written in their enhanced version of RATFOR.

Sometime in the 1984-1985 time frame I translated it into K&R C.
I have it, but it was last touched in 1993. (Probably the modified
dates are from when I copied it around; I suspect it's been even
longer since I looked at the code. The README lists a date of
February 1985!)

I could probably put it up on github, if anyone's interested.
--
Aharon (Arnold) Robbins 			arnold AT skeeve DOT com
P.O. Box 354		Home Phone: +972 8 979-0381
Nof Ayalon
D.N. Shimshon 9978500	ISRAEL

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

#1320

On Wed, 16 Jul 2014 16:39:09 -0400 (EDT), Ivan Godard
<ivan@ootbcomp.com> wrote:

>As a practical matter, natural languages are pretty much LL1 (German
>verbs excepted)

Obviously you haven't read any legal briefs lately  8-)

Natural languages are contextual.  Neither LL(1) nor (LA|S)LR(1) can
parse a contextual language - both are limited to context-free
languages.

GLR and PEG theoretically can parse contextual languages.  It is
thought that LL(*) - LL with unlimited lookahead - may be able to as
well, but AFAIK, there has been no formal proof offered for this.


>so people are reasonably familiar to quasi-linear parsing.

Studies have shown that human parsing of language is both top-town and
bottom-up simultaneously.


>Nearly all languages yield to LL1 techniques (the formal proofs
>that a language is not LL1 are irrelevant) ...

Yes ... most useful context free languages can be contorted into
LL(1).  But it's a lot easier just to use an LL(k) tool.

In theory, any LL(k) language can be refactored to be LL(1), but
refactoring a "greater than small k" language is usually impractical
due to explosive growth of the resulting LL(1) grammar.

George

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

#1321

George Neuner <gneuner2@comcast.net> wrote:

> On Wed, 16 Jul 2014 16:39:09 -0400 (EDT), Ivan Godard
> <ivan@ootbcomp.com> wrote:
> <snip>
> In theory, any LL(k) language can be refactored to be LL(1), but
> refactoring a "greater than small k" language is usually impractical
> due to explosive growth of the resulting LL(1) grammar.
>
> George

I have memories that an LR(k) grammar can in principle be refactore to
LR(1), but that in general an LL(k) gramar cannot be refactored to
LL(1).

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

#1328

On 2014/07/18 21:41, William Clodius wrote:

> I have memories that an LR(k) grammar can in principle be refactore to
> LR(1), but that in general an LL(k) gramar cannot be refactored to
> LL(1).

For every LR(k) grammar there is an LR(1) grammar parsing the same
language [1], but this result does not say what happens with the grammar
rule actions.

A GLR parser splits the parses in face of an ambiguity, which might be
used instead. Bison supports this, but currently the actions during a
parse split are not executed, and so cannot set context variables for
the lexer, until the merge.

Some other results from [1]:

Every LL(k) grammar is LR(k); not all LR(k) grammars are LL(k). If one
knows a grammar is LR(k) for some k, then there it is decidable whether
it is LL(k') for some k'.

1. Waite & Goos, "Compiler Construction", p. 133.

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

#1329

Hello,

On 7/19/14, 4:29 PM, Hans Aberg wrote:
> A GLR parser splits the parses in face of an ambiguity, which might be
> used instead. Bison supports this, but currently the actions during a
> parse split are not executed, and so cannot set context variables for
> the lexer, until the merge.

A GLR parser splits on conflicts and thus needs two different types of
actions. I recall that DParser uses the terms speculative and final.
In my GLR Builder I use the terms semantic checks & actions.

Semantic checks are not delayed when the parser splits but they should
not have side effects. In general, it is unsafe to notify the scanner
that the parser has just reached a particular state.

In contrast, you can query a symbol table to reject an active parser or
just create a node for the AST of the current parse. BTW, its my
impression that Elkhound and Elsa parse C++ with actions that actually
are immediate; but i have not read their code to be sure.

To conclude, in a deterministic LALR parser semantic actions are both
immediate and final but in a GLR parser this principle doesn't hold.

Hope this helps,
Ev. Drikos

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

#1330

On 2014/07/19 23:40, Evangelos Drikos wrote:

> On 7/19/14, 4:29 PM, Hans Aberg wrote:
>> A GLR parser splits the parses in face of an ambiguity, which might be
>> used instead. Bison supports this, but currently the actions during a
>> parse split are not executed, and so cannot set context variables for
>> the lexer, until the merge.
>
> A GLR parser splits on conflicts and thus needs two different types of
> actions.

As for Bison, there have been discussions to admit this, but as far as
I know, it does not have it currently.

> I recall that DParser uses the terms speculative and final.

Or perhaps direct (immediate) and delayed, or something. Bison then only
has the delayed.

> In my GLR Builder I use the terms semantic checks & actions.
>
> Semantic checks are not delayed when the parser splits but they should
> not have side effects. In general, it is unsafe to notify the scanner
> that the parser has just reached a particular state.

The lexer probably need some extensions as well. May be useful for
parsing natural languages.

> In contrast, you can query a symbol table to reject an active parser or
> just create a node for the AST of the current parse. BTW, its my
> impression that Elkhound and Elsa parse C++ with actions that actually
> are immediate; but i have not read their code to be sure.

It is possible to make a LALR(1) parser for C++: one parses a larger
language, and cuts it down in the actions.

> To conclude, in a deterministic LALR parser semantic actions are both
> immediate and final but in a GLR parser this principle doesn't hold.

Right. Only for simultaneous, parallel parses, if some reader here wonders.

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

#1339

On 7/20/14, 2:38 AM, Hans Aberg wrote:
>> A GLR parser splits the parses in face of an ambiguity, which might be
>> used instead. Bison supports this, but currently the actions during a
>> parse split are not executed, and so cannot set context variables for
>> the lexer, until the merge.

In short, your idea can be applied only as a hack; it might work
sometimes, depends on the grammar. If that is what you meant we don't
disagree.
[In my experience, it's a rare parser that is useful and doesn't depend on some hacks. -John]

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

#1341

On 2014/07/21 14:20, Evangelos Drikos wrote:
> On 7/20/14, 2:38 AM, Hans Aberg wrote:
>>> A GLR parser splits the parses in face of an ambiguity, which might be
>>> used instead. Bison supports this, but currently the actions during a
>>> parse split are not executed, and so cannot set context variables for
>>> the lexer, until the merge.
>
> In short, your idea can be applied only as a hack; it might work
> sometimes, depends on the grammar. If that is what you meant we don't
> disagree.
> [In my experience, it's a rare parser that is useful and doesn't depend
> on some hacks. -John]

Indeed, but yet another feature that one might want is being able to
split the lexer as well - may be useful for experimenting with the
processing of natural languages. Such a feature has been discussed a bit
on the Bison mailing lists.

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

#1365

On 7/21/14, 7:39 PM, Hans Aberg wrote:

>> [In my experience, it's a rare parser that is useful and doesn't depend
>> on some hacks. -John]
>
> Indeed, but yet another feature that one might want is being able to
> split the lexer as well - may be useful for experimenting with the
> processing of natural languages. Such a feature has been discussed a bit
> on the Bison mailing lists.

Have read some of your relevant discussions; specifically:
[1] https://lists.gnu.org/archive/html/help-flex/2003-12/msg00008.html
[2] http://lists.gnu.org/archive/html/help-flex/2003-07/msg00067.html
[3] http://sci.tech-archive.net/Archive/sci.lang/2006-10/msg01330.html

But cannot find Bison's todo list or relevant discussions in help-bison
lists. What the Bison team said about your idea? Is it described in any
paper or supported in another tool?

Regards,
Ev. Drikos

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.compilers

csiph-web