Sat, 07 Feb 2015 11:27:06 GMT

Related articles |
---|

Grammar with low-precedence postfix operator? rljacobson@gmail.com (Robert Jacobson) (2015-02-05) |

Re: Grammar with low-precedence postfix operator? kaz@kylheku.com (Kaz Kylheku) (2015-02-05) |

Re: Grammar with low-precedence postfix operator? anton@mips.complang.tuwien.ac.at (2015-02-07) |

Re: Grammar with low-precedence postfix operator? rljacobson@gmail.com (Robert Jacobson) (2015-02-07) |

Re: Grammar with low-precedence postfix operator? monnier@iro.umontreal.ca (Stefan Monnier) (2015-02-08) |

Re: Grammar with low-precedence postfix operator? kaz@kylheku.com (Kaz Kylheku) (2015-02-09) |

Re: Grammar with low-precedence postfix operator? DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2015-02-09) |

Re: Grammar with low-precedence postfix operator? jgk@panix.com (2015-02-10) |

Re: Grammar with low-precedence postfix operator? kaz@kylheku.com (Kaz Kylheku) (2015-02-11) |

[1 later articles] |

From: | anton@mips.complang.tuwien.ac.at (Anton Ertl) |

Newsgroups: | comp.compilers |

Date: | Sat, 07 Feb 2015 11:27:06 GMT |

Organization: | Institut fuer Computersprachen, Technische Universitaet Wien |

References: | 15-02-006 |

Keywords: | parse, design |

Posted-Date: | 08 Feb 2015 03:50:08 EST |

X-Auth-Sender: | U2FsdGVkX1/kEiE2kHla5U+htLcXiT2i3mrGWowuoqg= |

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/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.