Re: Call by pattern parsing

bos@dcs.gla.ac.uk (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
>Compiler.


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, $).
all_four_uses :-
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 comp.compilers page.
Search the comp.compilers archives again.