Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!peer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From: Kaz Kylheku <kaz@kylheku.com>
Newsgroups: comp.compilers
Subject: Re: Grammar with low-precedence postfix operator?
Date: Thu, 5 Feb 2015 21:10:47 +0000 (UTC)
Organization: Aioe.org NNTP Server
Lines: 61
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <15-02-010@comp.compilers>
References: <15-02-006@comp.compilers>
NNTP-Posting-Host: news.iecc.com
X-Trace: miucha.iecc.com 1423278728 52219 2001:470:1f07:1126:0:676f:7373:6970 (7 Feb 2015 03:12:08 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Sat, 7 Feb 2015 03:12:08 +0000 (UTC)
Keywords: parse
Posted-Date: 06 Feb 2015 22:12:08 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
X-Received-Bytes: 2908
X-Received-Body-CRC: 452428771
Xref: csiph.com comp.compilers:1512

On 2015-02-05, Robert Jacobson <rljacobson@gmail.com> wrote:
> 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.

I suspect this is not nicely solvable by LALR type tools. Only with hacks.

The problem is that the low precedence postfix operator has no starting
marker to look back to.

When this operator occurs in an expression, it means "everything which comes
before me in the expression is my argument".

The problem with this is that it leaves no room for the onstruct to be
*embedded* in another one. Since the operator says "everything is mine!" it
means, by the same token (pun intended) that "I am not a subexpression; I am
the top-level constituent!". And since that is the case, because
it is a postfix operator, it means that the expression ends right there.

If you want 2+2++^3 to mean (2+2)++^3, that means that you need
a special low-precedence versions of ^ (and other operators) for that
case, so the ++ expression can be a constituent of something.

Try something along these lines. This Yacc grammar only gives me one
shift-reduce conflicts, on account of the empty production rule for
pp_factor_continue.  I didn't test it; I only skimmed through the state
transitions in y.output:

%token INT PLUSPLUS

%%

expr : mul_expr
     | expr '+' mul_expr
     | expr PLUSPLUS pp_add_continue
     ;

mul_expr : factor
         | primary '*' factor
         ;

factor : primary
       | factor '^' primary
       ;

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

pp_add_continue : '+' mul_expr
                | pp_mul_continue
                ;

pp_mul_continue : '*' factor
                | pp_factor_continue
                ;

pp_factor_continue : '^' primary
                   | /* NOTHING */
                   ;