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

Groups > comp.compilers > #1516

Re: Grammar with low-precedence postfix operator?

Show all headers | View raw

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/

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Grammar with low-precedence postfix operator? Robert Jacobson <rljacobson@gmail.com> - 2015-02-05 13:27 -0500
  Re: Grammar with low-precedence postfix operator? Kaz Kylheku <kaz@kylheku.com> - 2015-02-05 21:10 +0000
    Re: Grammar with low-precedence postfix operator? Robert Jacobson <rljacobson@gmail.com> - 2015-02-07 10:30 -0800
  Re: Grammar with low-precedence postfix operator? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-02-07 11:27 +0000
    Re: Grammar with low-precedence postfix operator? jgk@panix.com (Joe keane) - 2015-02-10 21:03 +0000
      Re: Grammar with low-precedence postfix operator? Kaz Kylheku <kaz@kylheku.com> - 2015-02-11 02:19 +0000
  Re: Grammar with low-precedence postfix operator? Stefan Monnier <monnier@iro.umontreal.ca> - 2015-02-08 12:34 -0500
    Re: Grammar with low-precedence postfix operator? Kaz Kylheku <kaz@kylheku.com> - 2015-02-09 01:24 +0000
      Re: Grammar with low-precedence postfix operator? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2015-02-09 08:05 +0100
  Re: Grammar with low-precedence postfix operator? Robert Jacobson <rljacobson@gmail.com> - 2015-02-21 12:55 -0800

csiph-web