Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #834

Re: Compiling expressions

Show all headers | View raw

James Harris <james.harris.1@gmail.com> writes:

> The requirements [for parsing expressions] are:
>
> 1. Hand-written, not the output of a parser generator.
> 2. Efficient and without backtracking.
> 3. Precedences (and possibly associativities) defined in tables.
> 4. Output to be a tree structure.
> 5. Parenthesised subexpressions allowed.
> 6. Some operator families are *not* to associate with each other. See
> below.
> 7. Monadic prefix, dyadic infix and monadic postfix operators are all
> allowed.
> 8. Prefix and infix operators can use some same symbols (e.g. minus
> sign).
>
> Infix and postfix operators use distinct symbols. For example, if a
> certain symbol were used as a postfix operator it could not also be
> used as an infix operator.

It sounds like you could use the classic precedence parsing method.
Basically, each infix operator is given two precedence values: One for
its left-hand side and one for its right-hand side.  Left-associative
operators would have a higher left-hand precdence than right-hand
precedence and vice-versa.  Left parens have the highest possible left
precedence and the lowest possible right precedence.  Right parens
have the opposite.

If you only have infix operators, atoms (numbers, variables, etc) and
parentheses, the method is as follows:

Start with an empty stack of treess and an operator stack containing a
left paren.  Then loop the following until explicitly stopped:

 - If the next input symbol is an atom, it is read and pushed on the
   tree stack.

 - If the next input symbol is an operator, compare its left-hand
   precedence to the right-hand precedence of the top-most operator on
   the operator stack.

   If the stacked symbol has higher precedence, pop the two top-most
   trees from the tree stack and the operator from the operator stack
   and push on the tree stack a tree build from the two popped trees and
   the popped symbol.  The input symbol is kept unread.

   If the stacked symbol has lower precedence, read the input symbol and
   push it on the operator stack.

 - If the next input symbol is a left paren, read it and push it on the
   operator stack.

 - If the next input symbol is a right paren and the topmost symbol on
   the operator stack is a left paren, pop this and read the right
   paren.

 - If the next input symbol is a right paren and the topmost symbol on
   the operator stack is not a left paren, pop the two topmost trees and
   the topmost operator and push a tree built from these.  Keep the
   right paren unread.

 - If the end of file is reached and the topmost symbol on the operator
   stack is a left paren, then stop.

 - If the end of file is reached and the topmost symbol on the operator
   stack is not a left paren, pop the two topmost trees and the topmost
   operator and push a tree built from these.

When stopped, the tree stack contains the desired syntax tree.

This needs some modification to catch all syntax errors.  For example, 3
4 + + 5 would parse the same way as 3 + 4 + 5.  The simplest solution is
to add a bit that tells whether the most recently read symbol was an
atom or an operator.

A prefix operator will never follow an atom, so by checking this bit,
you can treat a - as a prefix or infix symbol depending on context.
Prefix operators are pushed on the operator stack (with a bit saying
they are prefix operators) and the above algorithm is modified so a
stacked prefix operator with higher precedence than the input operator
builds a tree with only one child.  A stacked prefix operator with lower
precedence causes the new operator to be read and pushed.

Postfix operators in input with higher predecence than the topmost
operator are read and a tree is built from this and the topmost tree.
Postfix operators with lower precedence causes a tree to be built from
the topmost operator and one or two trees from the tree stack (depending
on whether the topmost operator is prefix or infix).

Note that postfix operators are never pushed on the operator stack and
prefix operators never stay unread.  Neither change the bit that
indicate whether an atom or infix operator was read.

If specific pairs of operators do not associate with each other, you
report an error if one is in the input and the other is at the top of
the operator stack.

	Torben

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Compiling expressions James Harris <james.harris.1@gmail.com> - 2012-12-29 05:11 -0800
  Re: Compiling expressions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-12-29 23:33 +0000
    Re: Compiling expressions James Harris <james.harris.1@gmail.com> - 2013-01-02 09:04 -0800
      Re: Compiling expressions "matzebraun@googlemail.com" <matzebraun@googlemail.com> - 2013-01-03 07:13 -0800
      Re: Compiling expressions Horst von Brand <vonbrand@inf.utfsm.cl> - 2013-01-14 16:31 -0300
  Re: Compiling expressions "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2012-12-30 08:58 +0100
    Re: Compiling expressions James Harris <james.harris.1@gmail.com> - 2013-01-02 09:10 -0800
    Re: Compiling expressions James Harris <james.harris.1@gmail.com> - 2013-01-03 12:01 -0800
      Re: Compiling expressions "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2013-01-04 10:18 +0100
  Re: Compiling expressions torbenm@diku.dk (Torben Ægidius Mogensen) - 2013-01-03 16:49 +0100
  Re: Compiling expressions James Harris <james.harris.1@gmail.com> - 2013-01-03 13:33 -0800
    Re: Compiling expressions James Harris <james.harris.1@gmail.com> - 2013-01-06 00:57 -0800
    Re: Compiling expressions "James Harris \(es\)" <james.harris.1@gmail.com> - 2013-03-07 11:11 +0000

csiph-web