RE: Backtracking and parsing tools

Quinn Tyler Jackson <>
9 Oct 2004 22:29:18 -0400

          From comp.compilers

Related articles
RE: Backtracking and parsing tools (Quinn Tyler Jackson) (2004-10-02)
Re: Backtracking and parsing tools (2004-10-04)
RE: Backtracking and parsing tools (Quinn Tyler Jackson) (2004-10-09)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 9 Oct 2004 22:29:18 -0400
Organization: Compilers Central
References: 04-10-046
Keywords: parse
Posted-Date: 09 Oct 2004 22:29:18 EDT

I wrote:

> >One might say that, in a sense, the parser "looks ahead" for the ")"
> >before invoking the deep parse ... or one might say that the parser
> >(with the benefit of hindsight) "looks back" when it sees that it is
> >worthwhile to do so.

VBDis wrote:

> Isn't that something like stepwise refinement? A simple parser for the
> LL(1) parts of the grammar, and other techniques for the constructs of
> higher degree? Provided that reasonable boundaries for the first
> guess exist, such a parser also can be used with incomplete or
> erroneous code, as occurs during code input.

I guess so. I call the first parse a shallow parse, and the second parse a
deep parse. Of course, there could be a third parse and a fourth parse, too,
but that's neither here nor there. ;-)

A variation on this is the use of adaptive predicates. The first parse,
being more forgiving, gathers enough information during it's shallow pass to
correctly parse the substring during its second parse, using that
information. This was used to great effect in empty-start NLP -- an English
parser that didn't start with a dictionary, gathered its dictionary on the
first parse, and then used that dictionary to properly parse the sentences
in its second pass.


This is closer to selective dual-pass parsing than it is to backtracking and
lookahead, I suppose.

One thing also is that the $-Calculus has "super" casts -- that is,
sub-productions can be told to modify the grammar iff their parent
productions also fully match. Lately, I added the ability to refer to tries
in super-productions, using ^.name and ^{parent}.name type rules. This is
similar to attribute grammars, I assume, and I'm still testing it as to its

> BTW, your paper gave me interesting and useful insight into your
> concepts. Not that I understood all the theory now, but I got a much
> better feeling for MetaS :-)

Thanks. I realize it's a bit long -- and that might limit its chances at
publication where I sent it -- but I hope the referees see past its length.
;-) There's no shortage of ways I could have made it more brief, but I
wanted to capture as many of the findings on context-sensitive parsing
possibilities as I could.

Quinn Tyler Jackson

Post a followup to this message

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