Re: Call by pattern parsing (Richard A. O'Keefe)
Fri, 5 Aug 1994 07:12:59 GMT

          From comp.compilers

Related articles
Call by pattern parsing (1994-08-03)
Re: Call by pattern parsing (1994-08-04)
Re: Call by pattern parsing (1994-08-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Richard A. O'Keefe)
Keywords: parse, design
Organization: Comp Sci, RMIT, Melbourne, Australia
References: 94-08-039 94-08-047
Date: Fri, 5 Aug 1994 07:12:59 GMT
Status: RO (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, $).
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.

Post a followup to this message

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