Re: Predicates

Sylvain Schmitz wrote this interesting comment:


> I would not really consider predicates on the same level as the
> operators in boolean grammars: syntactic predicates are additional
> run-time checks written by the user to help disambiguate a conflict. As
> such, they are highly convenient and utterly dangerous, allowing more or
> less arbitrary code to be run during the parsing phase, possibly
              ^^^^^^^^^
> unrelated to the language at hand and possibly introducing an
> exponential overhead.


I'm not sure what you mean by the underlined word. If you mean that
predicates allow running arbitrary "host language" (e.g. C) code in
the process of the parse, then you are talking about SEMANTIC
predicates. SYNTACTIC predicates only allow one to write grammar
fragments (rules, non-terminals, and regular expressions) that are
used as "lookahead".


Now, part of your contention is potentially true for syntactic
predicates. When implemented via backtracking, they do have a
potential exponential cost. However, so does converting an NFA to a
DFA. In practice, I have not seen that as an issue. Moreover, it is
not required that one implement predicates via backtracking. I
believe it is possible to fold the predicates into the normal parsing
process for many instances and to have guaranteed linear time bounds
on performance with a run-time overhead comparable to standard LR
parsing.


So, if your argument is that predicates are not a panacea and one can
write very poorly structured parsers that use predicates to
bail-themselves out, but which as a result are unreliable, slow, and
otherwise bad, I would agree. However, if you are arguing that
boolean grammars resolve all these problems, I'll need more evidence,
especially that we are talking about the same things. What I've read
of boolean grammars, maps loosely onto how I view syntactic
predicates. It is a little more formal. However, that is to be
expected, since it is intended as a formal system more than the ad hoc
way predicates were initially formulated.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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