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

Groups > comp.compilers > #819 > unrolled thread

Compiling expressions

Back to article view | Back to comp.compilers

Contents

  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

#819 — Compiling expressions

Compiling expressions is turning out to be more 'interesting' than I
anticipated! My requirements I believe to be fairly generic but they
seem not to be supported by standard algorithms so it's not as simple
as it might be. I thought I would post here as much out of interest as
anything. I'm not after a prebuilt solution but would be interested to
hear from other folks who have had similar issues to address. The
requirements 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.

Point 6 about some operator families not associating is because, at
least in the proposed version of the language, bitwise operators

  and, xor, or, not

are not to have any defined precedence relative to the arithmetic
operators

  plus, minus, times, power, unary minus etc

Operators in these two families are to have precedences relative to
other symbols in the same family and to families below and above them
but there is no defined precedence between, say, plus and bitwise and.
Some examples of operators of lower precedence would be comparisons
(less than, equal to etc) and boolean conjunctions (logical and,
logical or etc). Operators of higher precedence include binding,
dereference, function application etc.

So if the compiler sees

  a + b & c

then it is to complain about + and & being adjacent. One of the sides
must be parenthesised such as either of these two:

  (a + b) & c
  a + (b & c)

By contrast the following are both OK without needing parens because <
can interact with either family.

  a + b < x
  b & c < x

I have considered: recursive calls, shunting yard stacking of
operators, stacking of pairs (symbol, operand), of triples
(precedence, symbol, operand), some bitwise modification of stacked
precedences and some table-driven recognition of exceptions.

I have tried to avoid a two-dimensional grid-based solution but having
concluded it may be the way to go my copy of the dragon book advises
that such a solution does not work with unary minus! It says it should
be separated out in the lexer. That is something I don't want to do.
The parsing should be controlled wholly in the expression parser.

Perhaps strangely prefix operators seem to me easy enough to
distinguish from infix as they are seen in two different contexts.
What is acceptable before an operand is not the same as what is
acceptable after an operand.

Am currently thinking this might need a grid per context - i.e. two
grids - but I've never seen an algorithm with such. Er, fun this,
isn't it!

James

[toc] | [next] | [standalone]

#820

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

> Compiling expressions is turning out to be more 'interesting' than I
> anticipated! My requirements I believe to be fairly generic but they
> seem not to be supported by standard algorithms so it's not as simple
> as it might be. I thought I would post here as much out of interest as
> anything. I'm not after a prebuilt solution but would be interested to
> hear from other folks who have had similar issues to address. The
> requirements are:

> 1. Hand-written, not the output of a parser generator.

An interesting requirement.

I can understand need for speed, size, and such, and maybe one
of those requires a hand-written (hand optimized) parser.

If you are so restricted, do you allow your parser to be written
in a high-level language? To be compiled by a non-handwritten
compiler?

> 2. Efficient and without backtracking.

Seems reasonable to me, though the languages has to allow for it.

> 3. Precedences (and possibly associativities) defined in tables.

Tables most easily generated automatically, by a parser generator?

> 4. Output to be a tree structure.

> 5. Parenthesised subexpressions allowed.

> 6. Some operator families are *not* to associate with each other.
>    See below.

So you generate an error when such occurs. The usual problem is
to make the error message good enough that one can figure out
what happened.

> 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.

(snip)

-- glen

[toc] | [prev] | [next] | [standalone]

#829

On Dec 29 2012, 11:33 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu>
wrote:
> James Harris <james.harri...@gmail.com> wrote:

> > Compiling expressions ...

> > ... I'm not after a prebuilt solution but would be interested to
> > hear from other folks who have had similar issues to address. The
> > requirements are:

> > 1. Hand-written, not the output of a parser generator.
>
> An interesting requirement.
>
> I can understand need for speed, size, and such, and maybe one
> of those requires a hand-written (hand optimized) parser.
>
> If you are so restricted, do you allow your parser to be written
> in a high-level language? To be compiled by a non-handwritten
> compiler?

The parser for the rest of the language is handwritten and top-down.
Therefore it makes sense to parse expressions the same way. I don't
want to have generated code just to recognise expressions. It doesn't
feel like a restriction per se, just a choice.

HLL is fine. How the compiler is compiled doesn't matter.

...

> > 3. Precedences (and possibly associativities) defined in tables.
>
> Tables most easily generated automatically, by a parser generator?

I would rather the result is easy to understand but I don't mind too
much how the tables are generated.

James

[toc] | [prev] | [next] | [standalone]

#833

> > > 3. Precedences (and possibly associativities) defined in tables.
>
> I would rather the result is easy to understand but I don't mind too
> much how the tables are generated.

Search for Shunting-yard algorithm/precedence climbing/precedence
parsing these should fulfill your requirements easily if implemented
properly. You basically have a pair of parsing function callback and
precedence level for each input token, if your ast is perfectly
regular and it's only infix operations, then you can leave out the
parsing function callback.

You may find an implementation in our c compiler (though keep in mind that
this is a complete c parser with semantic so there is a lot more code
"around"), you may find the relevant pieces here:
https://github.com/MatzeB/cparser/blob/master/parser.c (look for
parse_subexpression(), init_expression_parser(), struct
expression_parser_function_t)

Greetings,
    Matthias Braun

[toc] | [prev] | [next] | [standalone]

#844

James Harris said:

> Compiling expressions is turning out to be more 'interesting' than I
> anticipated! My requirements I believe to be fairly generic but they seem
> not to be supported by standard algorithms so it's not as simple as it
> might be.

Your requirements seem to match operator precedence parsing closely.
Look at <http://en.wikipedia.org/wiki/Operator-precedence_parser>.
--
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                    Fono: +56 32 2654431
Universidad Tecnica Federico Santa Maria             +56 32 2654239
Casilla 110-V, Valparaiso, Chile 2340000       Fax:  +56 32 2797513

[toc] | [prev] | [next] | [standalone]

#822

On Sat, 29 Dec 2012 05:11:16 -0800 (PST), James Harris wrote:

> Compiling expressions is turning out to be more 'interesting' than I
> anticipated! My requirements I believe to be fairly generic but they
> seem not to be supported by standard algorithms so it's not as simple
> as it might be. I thought I would post here as much out of interest as
> anything. I'm not after a prebuilt solution but would be interested to
> hear from other folks who have had similar issues to address. The
> requirements 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).

Here is an implementation with an explanation of the technique used:

http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc

I extended the method, which fairly old, towards non-associativity (#6),
advanced parenthesis (#5, keyed parameter associations), and split
association priorities into left-right pairs. But basically it is still the
same twin-stack method. Everything is table-driven, of course.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#830

On Dec 30 2012, 7:58 am, "Dmitry A. Kazakov" <mail...@dmitry-
kazakov.de> wrote:
> On Sat, 29 Dec 2012 05:11:16 -0800 (PST), James Harris wrote:

> > Compiling expressions ...

...

> > requirements 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).
>
> Here is an implementation with an explanation of the technique used:
>
> http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc
>
> I extended the method, which fairly old, towards non-associativity (#6),
> advanced parenthesis (#5, keyed parameter associations), and split
> association priorities into left-right pairs. But basically it is still the
> same twin-stack method. Everything is table-driven, of course.

Thanks, a took a look. As mentioned I'm not looking for a solution as
yet but I'll keep a note of it for guidance if nothing else. If it
covers all the points I was asking about it's impressive.

James

[toc] | [prev] | [next] | [standalone]

#835

On Dec 30 2012, 7:58 am, "Dmitry A. Kazakov" <mail...@dmitry-
kazakov.de> wrote:

...
> Here is an implementation with an explanation of the technique used:
>
> http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc

Thanks Dmitry. As mentioned I am not looking for a solution at the
moment. Maybe I have spent too long with this to give up and import a
solution now. I may well come back to it though, especially the
comments. It seems to be very clearly explained.

> I extended the method, which fairly old, towards non-associativity (#6),
> advanced parenthesis (#5, keyed parameter associations), and split
> association priorities into left-right pairs. But basically it is still the
> same twin-stack method. Everything is table-driven, of course.

Is it based on a Pratt parser? I see your comment and saw left and
right priorities mentioned. I have never spent the time to understand
Pratt parsers or why they need both. To deal with left- and right-
associativity if I ever need to I was thinking to use the lowest bit
of the precedence - something along the lines of clearing the bit on
one side before a comparison. Then each operator would only need a
single precedence. Or, maybe Pratt parsers use left and right
priorities for cleverer purposes such as an operator in multiple
parts...?

At any rate, have come up with some ideas for a parser. Will post
separately.

James

[toc] | [prev] | [next] | [standalone]

#837

On Thu, 3 Jan 2013 12:01:33 -0800 (PST), James Harris wrote:

>> I extended the method, which fairly old, towards non-associativity (#6),
>> advanced parenthesis (#5, keyed parameter associations), and split
>> association priorities into left-right pairs. But basically it is still the
>> same twin-stack method. Everything is table-driven, of course.
>
> Is it based on a Pratt parser? I see your comment and saw left and
> right priorities mentioned. I have never spent the time to understand
> Pratt parsers or why they need both. To deal with left- and right-
> associativity if I ever need to I was thinking to use the lowest bit
> of the precedence - something along the lines of clearing the bit on
> one side before a comparison. Then each operator would only need a
> single precedence.

Priority + direction sufficiently less general. For example it fails to
capture asymmetrically associated operations, e.g. assignment. Provided you
wanted assignment as an operator, you would like to have it rather this
way:

   a + b := c + d  --> a + (b := (c + d))

Priority + direction model cannot handle this. Here the left priority of :=
must be sufficiently higher than the right one.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#834

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

[toc] | [prev] | [next] | [standalone]

#836

On Dec 29 2012, 1:11 pm, James Harris <james.harri...@gmail.com>
wrote:

...

> 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.

...

Here is an idea for an expression parser to try to address the points
mentioned. I am not sure if it covers all the bases yet. For some
reason, although the requirement "parse an expression" is ostensibly
straightforward, when precedence and three types of operators are
thrown in I have been finding it very hard to reduce to easily
understandable concepts.

I should say what concepts the proposal is based on:

* An expression has exactly two key types of elements which I am
calling values and operators. The operators are the normal types of
operator symbols: prefix, infix and postfix. The values are
identifiers and literals. A subexpression in parentheses is also a
value.

* A value can have an arbitrary number of prefix operators to its left
and an arbitrary number of postfix operators to its right.

* A prefix operator applies not just to the value immediately to its
right but to an arbitrary expression to its right as far as an
operator with lower precedence. For example,

  -a.b+c

The unary minus in this case applies not just to the variable, a, but
to the subexpression a.b and terminates at the + sign. The dot here is
a binding operator which has a higher precedence than unary minus.

* Parentheses can appear in two contexts. Before a value (i.e. when
scanning for a value) a left paren is regarded as a grouping
parenthesis and starts the enclosure of a subexpression. Conversely,
after a value a left paren indicates a function call or similar. For
example,

  a + (...)  //a grouped expression
  a(...)     //a function call

So, here is an attempt to produce such an expression parser. This one
is partially recursive and written in fairly low-level pseudocode. Of
the approaches I have tried I think this is the easiest to understand.
It is certainly short (which is cool!) but it may not be completely
right. Just about all the issues I have had have been to do with
applying precedence properly. Discussion and/or corrections would be
welcome.

Parsing of an expression is intended to start with a call to
expression_parse which takes one parameter. On the initial call this
is a dummy start-of-expression symbol which has a lower precedence
than any real operator. Once the parse is complete expression_parse
should return a tree representing the expression.

This function is essentially in two parts: first obtain a value and
then iterate over as many pairs of (infix operator, value) as have
higher precedence than that of the initial symbol.

function expression_parse(op1)
  op2 = token //a copy of the current token
  if op2 is lparen //*grouping* parens
    v1 = expression_parse(lparen)
    consume rparen
  else if op2 is a prefix operator
    v1 = expression_parse(prefix version of op2)
    v1 = node(PREFIX_OP, op2, v1)
  else
    v1 = value_parse(op1)
  op2 = current token (or dummy end of expression)
  while prec(op2) > prec(op1)
    if incompatible(op1, op2)
      raise "incompatible - grouping parens needed"
    v2 = expression_parse(op2)
    v1 = node(INFIX_OP, op2, v1, v2)
    op2 = current token (or dummy end of expression)
  return v1

I won't insult your intelligence by explaining it all but some notes
are in order. Each call to this routine ends leaving the current token
pointer pointing at the next unconsumed operator. The line

   v1 = expression_parse(prefix version of op2)

is intended to deal with such things as a prefix (unary) minus having
a different precedence than an infix minus. When such a symbol is seen
in prefix context the "prefix version" of it (which has the higher
precedence) is used on the recursive call.

When expression_parse gets to a value - an identifier or a literal -
it calls value_parse, below. The value_parse function is intended not
just to read the value but to accumulate all the following operations
- postfix and infix - which bind tighter than the precedence in force
at the time value_parse was called.

function value_parse(op1)
  v1 = value() //identifier or literal
  while true
    op2 = current token or dummy end of expression
    if lparen //parens of a function call or similar
      v1 = args_parse(op2)
      consume rparen
    else if prec(op2) > prec(op1)
      if incompatible(op1, op2)
        raise "incompatible - grouping parens needed"
      v1 = node(POSTFIX_OP, v1)
  return v1

There is a need to accumulate a list of arguments. That is the job of
args_parse, below.

function args_parse()
  v1 = empty list
  while true
    append to v1 expression_parse(lparen)
    if current token is a comma
      consume comma
    else
      break loop
  return v1

I am aware of some little things I would change to render it into a
programming language but the main issue is whether it would handle
precedences generally and correctly (or could be made easier to
understand). As I say, comments and corrections - especially on the
bigger issues - would be very welcome.

James

[toc] | [prev] | [next] | [standalone]

#842

On Jan 3, 9:33 pm, James Harris <james.harri...@gmail.com> wrote:

A small correction was needed, as follows, as I had omitted the loop-
out condition.

> function value_parse(op1)
>   v1 = value() //identifier or literal
>   while true
>     op2 = current token or dummy end of expression
>     if lparen //parens of a function call or similar
>       v1 = args_parse(op2)
>       consume rparen
>     else if prec(op2) > prec(op1)
>       if incompatible(op1, op2)
>         raise "incompatible - grouping parens needed"
>       v1 = node(POSTFIX_OP, v1)
    else
      break
>   return v1

James

[toc] | [prev] | [next] | [standalone]

#866

"James Harris" <james.harris.1@gmail.com> wrote in message
> On Dec 29 2012, 1:11 pm, James Harris <james.harri...@gmail.com> wrote:
> ...
>
>> 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.
>
> ...
>
> Here is an idea for an expression parser to try to address the points
> mentioned. I am not sure if it covers all the bases yet.

<snipped>

In case anyone is later looking for some code to parse expressions I should
say that I have placed an updated copy at

  https://groups.google.com/group/comp.lang.misc/browse_frm/thread/c21bf4f4cd55f345

The most important changes were to allow for low-precedence postfix
operators (the original code here only allowed them to be highest
precedence) and add some detailed documentation.

James

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web