|Re: A C++ Parser toolkit email@example.com (1993-04-12)|
|Semantic predicates into grammar specifications firstname.lastname@example.org (1993-04-19)|
|Re: Semantic predicates into grammar specifications email@example.com (1993-04-19)|
|From:||firstname.lastname@example.org (Terence J Parr)|
|Date:||Mon, 19 Apr 1993 20:45:31 GMT|
I thank email@example.com (Xorian Technologies) for furthering my
brief introduction to predicates. A couple of comments on his summary:
As will the LADE system, our semantic predicates have access to all
information about the current parse, results of user actions and current
lexical state etc... (although LL(k) parsers know more about their *exact*
position in the parse than LR(k) parsers do).
Of particular interest in Xorian's posting is:
> In C++, there are many pathological ambiguities which are unresolvable for
> lr(k) or ll(k) for any k. They require, instead, an unbounded lookahead.
> This can be accomplished by predicating the reduction of a production on a
> successful recursive parsing of the forward stream. In essence, the
> current parse is suspended and a secondary, simplified, parse is
> initiated. If the forward parse succeeds, then the production is reduced
> and the primary parsing proceeds as usual from the original point. If the
> forward parse fails, another alternative is considered.
Quoting from Ellis and Stroustrup's ARM where they discuss some rather
nasty C++ ambiguities:
"In a parser with backtracking the disambiguating rule can be stated very
 If it looks like a \fIdeclaration\fP, it is; otherwise
 if it looks like an \fIexpression\fP, it is; otherwise
 it is a syntax error."
PCCTS notation for Stroustrup's solution is simply:
PCCTS-generated parsers are completely deterministic, LL(k), until you
enter a (...)? block which can be viewed as a guess block (backtracking).
Note that this guess block is NOT a simplified parse; hence, you will be
doing arbitrary lookahead with full CFG power (not regular expressions,
for example). The full form of our (...)? blocks are:
where syntactic_predicate can be any EBNF grammar construct (except a new
rule definition). If the EBNF grammar fragment is matched on the input
stream, the conditional_production is then applied. The short form, as
employed above, is
which is really
In summary, I strongly advocate the use semantic and syntactic (guessing)
predicates in deterministic parsers and am happy that LADE and others are
of the same mind.
Semantic predicates in PCCTS were released in December 1992 as version
1.06. Version 1.07, which includes the syntactic predicates, will be out
this Summer. Information about PCCTS can be obtained by mailing to
firstname.lastname@example.org with a blank "Subject:" line.
Purdue University Electrical Engineering
Return to the
Search the comp.compilers archives again.