Path: csiph.com!usenet.pasdenom.info!news.lightlink.com!news.iecc.com!.POSTED!nerds-end
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Subject: Re: Grammar with low-precedence postfix operator?
Date: Sat, 07 Feb 2015 11:27:06 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 66
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <15-02-014@comp.compilers>
References: <15-02-006@comp.compilers>
NNTP-Posting-Host: news.iecc.com
X-Trace: miucha.iecc.com 1423385408 66392 2001:470:1f07:1126:0:676f:7373:6970 (8 Feb 2015 08:50:08 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Sun, 8 Feb 2015 08:50:08 +0000 (UTC)
Keywords: parse, design
Posted-Date: 08 Feb 2015 03:50:08 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
X-Auth-Sender: U2FsdGVkX1/kEiE2kHla5U+htLcXiT2i3mrGWowuoqg=
Xref: csiph.com comp.compilers:1516

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/