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 2 of 2 — ← Prev page 1 [2]

#1366

On 2014/08/26 12:44, Evangelos Drikos wrote:
> 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?

Since then, development of Flex has ceased - perhaps this might change
if it becomes a GNU project sometime. (There are different developers
for Flex and Bison.)

The Bison GLR parser, is written by Paul Hudak, and we discussed split
tokens, which it cannot currently handle, a bit on one of the Bison
lists (perhaps Bison Help).

But that was also some time ago, and there does not seem anything of
that going on now. The main focus is on computer languages, though it
would be nice to be able to experiment with natural languages.

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

#1367 — Re: split tokens; was LR(1) Parsing : Error Handling & Recovery

On 8/29/14 12:13 PM, Hans Aberg wrote:
> On 2014/08/26 12:44, Evangelos Drikos wrote:
>> ... What the Bison team said about your idea?
>>...
> ... we discussed split tokens, which it cannot currently handle
> ... The main focus is on computer languages, though it
> would be nice to be able to experiment with natural languages.

Split tokens are also useful for computer languages like SQL which have
unreserved keywords; yet, an efficient solution requires enough code.

Bison & Flex are fast and mature tools that can be combined efficiently
in a simple and straightforward manner for some computer languages.

But, Bison's GLR probably cannot parse some context free grammars. One
such epsilon grammar given by Nozohoor-Farshi[NF91] has broken Tomita's
original algorithm; a slightly modified grammar for Bison is given here:

G1: S
  ;
S: A S 'b'
  | 'x'
  ;
A: {printf("Delayed forever!\n");}
  ;

Given the string "xbbb", a Bison (2.3) GLR parser created by the above
grammar goes into an infinitive loop. Perhaps, this well known issue is
either solved with a hack or not perceived as a bug exactly because the
main focus is on computer languages.

Probably, one could find a plethora of other open source tools for NLP.

Regards,
Ev. Drikos

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

#1368

On 2014/08/29 11:13, Hans Aberg wrote:

> The Bison GLR parser, is written by Paul Hudak, and we discussed split
> tokens, which it cannot currently handle, a bit on one of the Bison
> lists (perhaps Bison Help).

Correction: The Bison GLR parser is written by Paul Hilfinger.

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

#1331

On Fri, 18 Jul 2014 13:41:53 -0600, wclodius@earthlink.net (William
Clodius) wrote:

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

LL(k) always can be refactored to single token lookahead, but it
causes an explosion of grammar states.  E.g., given a single LL(3)
rule, an equivalent set of LL(1) rules must match every valid
combination of tokens at +1, +2 and +3.

George

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

#1335

George Neuner <gneuner2@comcast.net> wrote:

> On Fri, 18 Jul 2014 13:41:53 -0600, wclodius@earthlink.net (William
> Clodius) wrote:
>
> >I have memories that an LR(k) grammar can in principle be refactored
> >to LR(1), but that in general an LL(k) grammar cannot be refactored to
> >LL(1).
>
> LL(k) always can be refactored to single token lookahead, but it
> causes an explosion of grammar states.  E.g., given a single LL(3)
> rule, an equivalent set of LL(1) rules must match every valid
> combination of tokens at +1, +2 and +3.

Rosenkerantz and Stearns appeared to show otherwise,
<http://dl.acm.org/citation.cfm?id=805431>
Do you know of a problem with their proof?
See <http://compilers.iecc.com/comparch/article/92-05-052>

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

#1343

> > LL(k) always can be refactored to single token lookahead, but it
> > causes an explosion of grammar states.  E.g., given a single LL(3)
> > rule, an equivalent set of LL(1) rules must match every valid
> > combination of tokens at +1, +2 and +3.
>
> Rosenkrantz and Stearns appeared to show otherwise,
> <http://dl.acm.org/citation.cfm?id=805431>
> Do you know of a problem with their proof?
> See <http://compilers.iecc.com/comparch/article/92-05-052>

This topic has appeared a number of times in this forum, but most of the
time people have had trouble coming up with a specific irreducable LL(k)
grammar. The above link however appears to be such a grammar.

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

#1336

George Neuner <gneuner2@comcast.net> wrote in news:14-07-041@comp.compilers:
> LL(k) always can be refactored to single token lookahead, but it
> causes an explosion of grammar states.  E.g., given a single LL(3)
> rule, an equivalent set of LL(1) rules must match every valid
> combination of tokens at +1, +2 and +3.

Not true -- LL(k+1) languages are a strict superset of LL(k) languages, so
there exist LL(k) grammars that cannot be refactored to a smaller k.

LR(k) languages are equivalent the LR(1), so every LR(k) grammar can be
refactored to LR(1)

A useful summary of the relationships between various types of languages and
grammars can be found at

<http://cs.stackexchange.com/questions/43/language-theoretic-comparison-of-ll-and-lr-grammars>

Chris Dodd
cdodd@acm.org

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

#1350

On Mon, 21 Jul 2014 06:07:55 +0000 (UTC), Chris Dodd <cdodd@acm.org>
wrote:

>George Neuner <gneuner2@comcast.net> wrote in news:14-07-041@comp.compilers:
>> LL(k) always can be refactored to single token lookahead, but it
>> causes an explosion of grammar states.  E.g., given a single LL(3)
>> rule, an equivalent set of LL(1) rules must match every valid
>> combination of tokens at +1, +2 and +3.
>
>Not true -- LL(k+1) languages are a strict superset of LL(k) languages, so
>there exist LL(k) grammars that cannot be refactored to a smaller k.

Yes and no.

For every LL(k) grammar where both k and the set T of tokens is fixed,
there is an equivalent LL(1) grammar.  In the worst case, the
equivalent LL(1) grammar will have k**T rules.

Only where k or T is unbounded, so that the power set of {n:1<=n<=k}
lookahead tokens for some rule is not enumerable, can you not derive
an equivalent in LL(1).

The problem is that an LL({n:1<n<=k}) rule explodes multiplicatively
into an n-level tree of LL(1) rules, with each branch at each level
m<=n having to cover follow(m).

Meaning that it is effectively unworkable for any but small k.

Fortunately, for any reasonable LL(k>1) grammar, k will be bounded and
small, and the grammar will contain just a handful of rules requiring
the maximum k lookahead.  Most rules will be LL({n:1<=n<k}) where n is
very small.

George

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

#1352

George Neuner <gneuner2@comcast.net> wrote
> For every LL(k) grammar where both k and the set T of tokens is fixed,
> there is an equivalent LL(1) grammar.  In the worst case, the
> equivalent LL(1) grammar will have k**T rules.

This is simply not true.  A counter-example from Kurki-Suonio
<ftp://ftp.math.utah.edu/pub/tex/bib/idx/bit/9/3/225-238.html>
<http://www.springerlink.com/openurl.asp?genre=article&issn=0006-
3835&volume=9&issue=3&spage=225>
is:

    S ::= aSA | \epsilon
    A ::= aabS | c

This grammar (and the language) is LL(2), but there does not exist an
equivalent LL(1) grammar.  Here k=2 (fixed) and T = {a, b, c} (also fixed)

Chris Dodd
cdodd@acm.org

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

#1353

Chris Dodd schrieb:

> A counter-example from Kurki-Suonio
> <ftp://ftp.math.utah.edu/pub/tex/bib/idx/bit/9/3/225-238.html>
> <http://www.springerlink.com/openurl.asp?genre=article&issn=0006-
> 3835&volume=9&issue=3&spage=225>

Unfortunately I couldn't get the article, so here's what I don't understand:

> is:
>
>     S ::= aSA | \epsilon
>     A ::= aabS | c
>
> This grammar (and the language) is LL(2), but there does not exist an
> equivalent LL(1) grammar.

IMO this grammar is LL(3), not LL(2). There might be a typo in A, which
might originally read as:
   A ::= abS | c
resulting in an LL(2) grammar.

Can somebody enlighten me?

DoDi

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

#1355

Hans-Peter Diettrich <DrDiettrich1@netscape.net> wrote in
> Unfortunately I couldn't get the article, so here's what I don't understand:
>
>> is:
>>
>>     S ::= aSA | \epsilon
>>     A ::= aabS | c
>>
>> This grammar (and the language) is LL(2), but there does not exist an
>> equivalent LL(1) grammar.
>
> IMO this grammar is LL(3), not LL(2). There might be a typo in A, which
> might originally read as:
>    A ::= abS | c
> resulting in an LL(2) grammar.

Yes, my fault for not carefully checking my post.  As written, it's an
LL(3) grammar for a language that is not LL(2).  Remove one 'a' from
the 'A' rule to get an LL(2) grammar for a language that is not LL(1).
Add 'a's to get an LL(k) grammar for a language that is not LL(k-1)
for any k...

Chris Dodd
cdodd@acm.org

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

#1315

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 ?

I can take a crack at answering some of this. I built my own LALR1
parse generator and parser about 20 years ago.  The parser had both
Error Repair and Error Handler.  I can describe how I implemented
these.

There are two mechanisms:

Error Repair tries to fix the input token stream when a syntax error
is detected. This was popular back when compiling was much more
expensive and done as submitted batch jobs.  The desire was to not
abort a compile job or toss away source just because of some syntax
error.  Error Repair attempts to keep as much of the original input
stream and find as many errors as possible in one pass.

The basic repair mechanism tries to either Keep, Insert or Delete
input stream tokens according to their cost. The "best" repair is the
one with the minimum cost.

Error Handling is a simpler mechanism and essentially works by tossing
away tokens until a recognized state is reached.  It can be used when
Error Repair is not available or has failed.  Error Handling is
conceptually like an exception handler (this is just conceptual, it
has nothing to do with C++ or operating system exceptions).

The LALR1 parser pushes items on the stack.  If it reaches a state
where the next token cannot be consumed because there is no next state
for it (a syntax error), then the parser does the equivalent of
"throwing an exception".  It scans backwards through the parse stack
checking the state for a special terminal called ERROR. If it finds
one it rolls back the parse stack to that point, pushes the ERROR
terminal on the stack and calls the associated reduction routine as
though a match on the input terminal ERROR had been found.  That
reduction action routine is expected to do clean up.

For example

   statement
   :  assignment_statement
   |  if_statement
   |  loop_statement
   |  ERROR { action_error(); };

Say we are parsing "foo = a * b / / c;".
At the second '/' token a syntax error is detected.
The parse stack is scanned backwards until we find a state
that can shift the ERROR token. That matches a production
for "assignment" so the action_error() routine is called
which reads input token stream until it consumes a ';'.
(I'm glossing over grotty details like who cleans up
the parse stack and how is memory recovered.)
Finally the assignment production is pushed on the
parse stack and we continue as if nothing had gone wrong.

Anyway, that is the basic idea.
I found Error Repair more interesting but is much more difficult.
Most parsers seem to use Error Handling because it is much easier
to implement and recompiling is cheap.

Eric

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.compilers

csiph-web