Re: Semantic predicates into grammar specifications

I thank xorian@solomon.technet.sg (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
simply:


        [1] If it looks like a \fIdeclaration\fP, it is; otherwise
        [2] if it looks like an \fIexpression\fP, it is; otherwise
        [3] it is a syntax error."


PCCTS notation for Stroustrup's solution is simply:


stat: (declaration)?
        | expression
        ;


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:


        (syntactic_predicate)? conditional_production


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


        (grammar_fragment)?


which is really


        (grammar_fragment)? grammar_fragment


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
pccts@ecn.purdue.edu with a blank "Subject:" line.


Terence Parr
Purdue University Electrical Engineering
--

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