Re: parsing with user defined operators

Torben Mogensen <torbenm@diku.dk>
13 Aug 1999 01:09:12 -0400

          From comp.compilers

Related articles
parsing with user defined operators rwg@exoterica.com (1999-08-12)
Re: parsing with user defined operators torbenm@diku.dk (Torben Mogensen) (1999-08-13)
Re: parsing with user defined operators mfinney@lynchburg.net (1999-08-15)
Re: parsing with user defined operators Andrew.Walker@nottingham.ac.uk (Dr A. N. Walker) (1999-08-27)
Re: parsing with user defined operators rspartan@my-deja.com (rspartan) (1999-08-27)
Re: parsing with user defined operators darcy@moa.CS.Berkeley.EDU (1999-08-28)
| List of all articles for this month |

From: Torben Mogensen <torbenm@diku.dk>
Newsgroups: comp.compilers
Date: 13 Aug 1999 01:09:12 -0400
Organization: Compilers Central
References: 99-08-053
Keywords: parse

Roy Germon wrote:


> I'm looking for parsing techniques to handle expressions that include
> user defined operators and overloaded operators. The precedence
> levels of operators are user definable over a range of several hundred
> values. The associativity is user definable as well. Any pointers to
> books or articles are more than welcome.


There are several ways of doing this.


  1) Parse all operators with the same associativity and
        precedence. The use a second pass over the syntax tree to change
        the structure to reflect the precedences. This means that
        parentheses must be visible in the syntax tree.


  2) Define a lexical token for each possible precedence/associativity
        combination. Give the lexer access to a table that contains the
        precedences of all user-defined operators and use this to assign
        the correct lexical token to the operator (the operator name is
        now an attribute to the token).


  3) Make a modified LR-parser that can resolve conflicts at
        parse-time. The parser will look up the precedences in a table
        when it has to resolve a conflict.


The first is the conceptually simplest method and has a small
parse-table, but requires an extra pass. The second requires a simple
fix in the lexer, something that can usually be done in the lexer
specification without having to fix the generated lexer. The
parse-table will be fairly large as it has to handle a (potentially)
large number of precedence/associativity combinations. The third
alternative requires use of a non-standard parser-generator or else a
modification of the generated parser, which may be complex. But it
uses a small parse-table and no extra pass.


Torben Mogensen (torbenm@diku.dk)


Post a followup to this message

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