Re: Grammar with low-precedence postfix operator?

Robert Jacobson <rljacobson@gmail.com> writes:
>I'm trying to write an ANTLR4 grammar for a language with a low precedence
>postfix operator (Wolfram Language with '&', but I use a simple toy grammar
>below). I'm struggling with finding the right pattern to express this
>language.


Precedence is error-prone (both programmers writing expressions that
the computer silently interprets differently, and programmers reading
the expressions differently from what the computuper understands), and
you should be very reluctant to use it IMO.


For your example involving ^ and ++, I think that one should use
parentheses explicitly in most cases, e.g. (a^b)++^c or a^(b++)^c.
You can leave away the parentheses if there is no ambiguity, as in
your 2++^3, but that's not straightforward to express in BNF.


The right solution for accepting 2++^3 and rejecting a^b++^c might be
to use a parsing algorithm that allows ambiguity (Early or GLR), maybe
prune away some solutions through, e.g., type rules, and accept the
result only if it is unambiguous.


Anyway, on to your problem. The grammar you presented is ambiguous
(when interpreted as a BNF, maybe ANTLR resolves the ambiguity for
you) even for simple stuff like 1+1+1, so I have played around with an
even simpler example. It took me some time, but eventually I found a
solution (inspired by the unambiguous solution to the dangling else
problem); in bison syntax:


%start exprp
%token INT PLUSPLUS


%%
postfix: expr PLUSPLUS
              ;


term: INT
        | '(' expr ')'
        ;


termp: postfix
          | term
          ;


expr: termp '^' right
        | term
        ;


right: term
          | term '^' right
          ;


exprp: postfix
          | expr
          ;


Bison produces no warnings for this, and with a little luck it also
parses the language you have in mind for the operators ^ and ++.
Maybe it is useful for your larger problem, but I suspect that this
approach becomes too complicated when involving more operators with
more precedence levels.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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