RE: Backtracking and parsing tools

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.


q.v. http://citeseer.ist.psu.edu/jackson01adaptive.html


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
usefulness.


> 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
http://members.shaw.ca/qjackson/

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