Re: Parsing infix notation

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

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