Re: Parsing infix notation

Norman Ramsey <nr@viper.cs.virginia.edu>
12 Sep 1997 21:22:08 -0400

          From comp.compilers

Related articles
Parsing infix notation schairer@dfki.de (Axel Schairer) (1997-09-07)
Re: Parsing infix notation eifrig@acm.org (Jonathan Eifrig) (1997-09-12)
Re: Parsing infix notation nr@viper.cs.virginia.edu (Norman Ramsey) (1997-09-12)
| List of all articles for this month |

From: Norman Ramsey <nr@viper.cs.virginia.edu>
Newsgroups: comp.lang.dylan,comp.lang.lisp,comp.compilers
Date: 12 Sep 1997 21:22:08 -0400
Organization: University of Virginia
References: <comp.lang.dylan.199708151441.PAA09067@gairsay.aiai.ed.ac.uk> <862035xpyn.fsf@g.pet.cam.ac.uk> <5unec0$j8j@tools.bbnplanet.com> 97-09-026
Keywords: parse

Axel Schairer <schairer@dfki.de> wrote:
>This might be true. It is true, of course, if you know all your infix
>operators when you build your parser/parse tables. But I do not know
>how to handle the situation where you
>
> - have user-defined infixes _and_
> - you want/need to use tools like bison/yacc/zebu ...
>
>Is there something I should know and obviously don't?


The thing to do is to use yacc-like tools to parse a sequence of
``atomic expressions'', then use a little operator-precedence parser
to handle the infix operators. My paper `Unparsing Expressions with
Prefix and Postfix Operators' at
http://www.cs.virginia.edu/~nr/pubs/unparse-abstract.html has such a
parser in the appendix. The advantage of this technique is that you
don't have to limit the number of levels of user-defined precedence.
I've found such limits bothersome when I'm trying to embed one
language in another (e.g., defining analogs of C operators in ML is
tedious because you have to cram C's 14 levels of precedence into ML's
10).




Excerpt from an EBNF grammar that uses this trick:


Exp : Atomic {Atomic} ;
Atomic : "(" Exp {"," Exp} ")"
              | "[" Exp {"," Exp} "]"
              | "let" {Decl} "in" Exp "end"
              | "if" Exp "then" Exp "else" Exp "fi"
              | Ident
              | Literal
              ;


If you don't mind ugly ML code, you can see the rest of the grammar at
http://www.cs.virginia.edu/~nr/toolkit/working/sml/rtl/grammar.html
and the post-pass at
http://www.cs.virginia.edu/~nr/toolkit/working/sml/rtl/elab.html.




Norman


--
                                  Norman Ramsey -- moderator, comp.programming.literate
                                  http://www.cs.virginia.edu/~nr
--


Post a followup to this message

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