Fri, 5 Aug 1994 07:12:59 GMT

Related articles |
---|

Call by pattern parsing myg@gate.net (1994-08-03) |

Re: Call by pattern parsing bos@dcs.gla.ac.uk (1994-08-04) |

Re: Call by pattern parsing ok@cs.rmit.oz.au (1994-08-05) |

Newsgroups: | comp.compilers |

From: | ok@cs.rmit.oz.au (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 |

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.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.