Semantic predicates into grammar specifications

parrt@ecn.purdue.edu (Terence J Parr) writes:
>I'm very pleased by the posting of Mayan Moudgill
><moudgill@cs.cornell.EDU>; people are beginning to see that semantic
>predicates are the way to recognize context-sensitive constructs rather
>than having the lexer change the token type (ack!).
>
>We call this a *validation* semantic predicate (we have syntactic
>predicates in the next release of PCCTS). Predicates can also be used to
>distinguish between two syntactically ambiguous productions
>(*disambiguating* semantic predicates).


Terence only begins to scratch the surface of what can be accomplished by
the introduction of semantic predicates into grammar specifications. His
examples concentrated on the lookahead (looking up the next symbol in the
symbol tables) but this is by far the least interesting use of semantic
predicates.


Semantic predicates, as defined in LADE, allow you to attach arbitrary
computations to any production: the production will only be reduced if the
predicate returns true. The predicates have access not only to the
lookahead symbol(s), but to the entire state of lexical, syntactic and
semantic analysis.


Here are two examples of what can be achieved:


The predicate has access to, for example, the synthesized attributes of
the production symbols. You might, for example, restrict a particular
production to only allow expressions of a particular type or type
expressions which indicate a class. This is of particular importance in
sugh languages as C++ where type expression equivalence is not name based.


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.


As a general rule, though, you should only use predicates for the purpose
of disambiguation; if there is no alternative syntactic interpretation of
a string, let the error handling fall to the semantic analysis. But where
syntactic ambiguities occur, whether shift-reduce or reduce-reduce,
semantic predicates are a powerful tool for their resolution and certainly
a much cleaner and simpler approach than hacking the lexer.


A more interesting questions arises wich respect to language design:
should languages be intionally designed to take advantage of semantic
predicates? A purist might be inclined to answer no, but consider that the
typical programmer does not look at a program and see only the syntactic
information; he does not look at it with PDA-eyes. Instead, he not only
sees the semantic information that has passed before but also that which
lies ahead. (My favorite example is the function call/arrary reference
ambiguity in Ada. No rational Ada programmer would see it as an ambiguity
for he would have to practice extreme myopia to fail to notice that the
declarations that preceeded their use.) If anything, semantic predicates
allow for more natural languages to be defined, languages which are not so
syntactically contrived. That, I think, is the best argument for a closer
look at semantic predicates in grammar specifications.




For more info on LADE, fax or send us an email.


Xorian Technologies
email: xorian@solomon.technet.sg
Fax: +65 253-7709
Tel: +65 255-7151
--

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