|Call by pattern parsing email@example.com (1994-08-03)|
|Re: Call by pattern parsing firstname.lastname@example.org (1994-08-04)|
|Re: Call by pattern parsing email@example.com (1994-08-05)|
|From:||firstname.lastname@example.org (Richard A. O'Keefe)|
|Organization:||Comp Sci, RMIT, Melbourne, Australia|
|Date:||Fri, 5 Aug 1994 07:12:59 GMT|
email@example.com (Bryan O'Sullivan) writes:
>Prolog has a far larger number (10,000) of precedences for the programmer
>to choose from, so the above approach is unsuitable. In this case, you
>can just parse expressions with all infix operators treated as if they
>have the same precedence and fixity, and build a parse tree in this
>manner. Once you're done parsing the expression, you go over the tree and
>change its shape using the associativity and fixity information you have
>for each operator. This technique can be applied whenever you have a
>total ordering on the set of possible operator precedences (e.g. where
>precedences are specified numerically), and is used by the Glasgow Haskell
Prolog operations are classified by "strength" (when two operators "fight"
for an operand the one with the bigger number wins) and associativity.
The strengths range from 1 to 1200 (twelve hundred, not 10 000).
expr(N) --> expr(N) op(N, yf) -- postfix
| expr(N-1) op(N, xf) -- postfix
| expr(N-1) op(N, xfy) expr(N) -- infix
| expr(N-1) op(N, xfx) expr(N-1) -- infix
| expr(N) op(N, yfx) expr(N-1) -- infix
| op(N, fx) expr(N-1) -- prefix
| op(N, fy) expr(N) -- prefix
You would have to be *off your head* to "go over the tree and change its
shape" after parsing, as it would be trivially easy to parse Prolog
expressions perfectly in a single very rapid pass but for one thing:
operator overloading. One and the same symbol may *simultaneously* be
readble as a prefix, infix, or postfix operator or even a constant
(context permitting). For example,
:- op(20, yf, $).
:- op(20, xfx, $).
:- op(20, fx, $).
Constant = $,
Prefix = $ b,
Infix = a $ b,
Postfix = a $ .
is syntactically legal. In a left-to-right parse, the only local
ambiguities that actually arise are constant/prefix and infix/postfix.
The Edinburgh Prolog systems "C Prolog" and "DEC-10 Prolog" use a sort
of left corner-cum-operator precedence method; C Prolog adds a rule that
says the following symbol + precedence levels must diambiguate (which in
practice they do) and gets a very fast parse in which the total number of
precedence levels has no effect whatsoever.
It is worth noting that Prolog operators have ***no*** semantics associated
with them. They are simply syntactic sugar for data constructions that
could have been written without them:
f B => f(B)
A f B => f(A, B)
A f => f(A)
and "functional" syntax may be used for all symbols, so
a + b * c => +(a,*(b,c))
is just a data structure made from two records. There is no _semantic_
overloading involved in this parsing process.
Return to the
Search the comp.compilers archives again.