RE: Backtracking and parsing tools

> A few years ago I produced a web page on backtracking and lookahead
> parser generator tools
> (http://www.cs.rhul.ac.uk/research/languages/projects/lookahead_ba
> cktrack.shtml). I
> use the terms in the widest possible interpretation: syntactic
> predicates in ANTLR look like user programmed lookahead to me, for
> instance.
>
> I want to update the page, so this is an invitation to anybody with an
> interest to send me an email recommending tools that they think should
> be included.


Adrian:


Normally I would reply to your request directly and privately only, since
it's not of general interest, but the last time I replied directly (when you
asked if there were any BNF systems that allowed for spaces in the symbol
names, I believe the question was) your email address bounced it back saying
it had been decided at some automated level that my response to your query
was spam. ;-)


That said, the Meta-S formalism (and the A-BNF implementation) have
both lookahead and backtracking that can be effected in numerous
ways. In a recently submitted paper, for instance, I discuss a method
of parsing a number of difficult to parse constructs (classical
languages, Collatz sequences, successor sequences, genetic p-knots,
C++ templates, Perl, and a few others, for instance), using many
variations of both.


If you would like, I could send you the paper (now being refereed --
so this is not a general invitation) that shows each of these
languages and the techniques used to parse them, and then you can
decide if you'd like to include a reference on the stuff.


One technique that I'd like to know (and this -- since this message is
also posted to comp.compilers in general -- a general query) is how
much has been done on the idea of "delayed" predication? I note work
by Searls on "String Variable Grammars" that may correlate.


Specifically, the idea is that meta-s grammars can store previously
parsed substrings in a data structure I am calling a name-indexed
trie. One of the properties of my predicates is that they can accept
one argument, and that argument I call an alpha-expression. The
"expansion" of a name-indexed trie when encountered in an
alpha-expression is the most recently added substring. With the
delayed predicate, the predicate check can be done in this fashion:


X ::= "(" $x(some_shallow_parse) ")" <x=some_deep_parse>;


In a sense, I see this as a kind of "look-ahead" even though in fact
it is really more like "hindsight is 20-20 parsing". The shallow
parse between the parentheses may be some inexpensive parse that
accepts the "general form" of the input between those parentheses. Iff
the terminating ")" is encountered, a deeper "re-parse" of that
substring is then done -- since it is known that the form of that
substring is at least accepted by the more-forgiving shallow parse.


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.


Anyone have any thoughts on this idiom? (Used quite often in my
$-grammars to what I think is useful effect.)


Cheers.


--
Quinn Tyler Jackson
http://members.shaw.ca/qjackson/

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