Using ANTLR with Left-Recursive Rules

Question

Basically, I've written a parser for a language with just basic arithmetic operators ( +, -, * / ) etc, but for the minus and plus cases, the Abstract Syntax Tree which is generated has parsed them as right associative when they need to be left associative. Having googled for a solution, I found a tutorial that suggests rewriting the rule from:

Expression ::= Expression <operator> Term | Term`

to

Expression ::= Term <operator> Expression*

However, in my head this seems to generate the tree the wrong way round. Any pointers on a way to resolve this issue?

Silly trivia: this question is the seventh hit on Google for "antlr left right associative" seconds after being asked. — sarnold
Could you post your combined- or parser grammar and explain how the AST is formed and how you'd wanted it to be formed instead? Since you say an AST is being created, I presume there's no problem with the grammar you've written, which suggests there's a problem in the rewrite rules in your combined- or parser grammar (which I, or someone else, will then need to see). — Bart Kiers
FYI, here's a small working expression parser: stackoverflow.com/questions/1931307/… — Bart Kiers

Sergey Kalinichenko Sergey Kalinichenko · Accepted Answer · 2011-11-24T02:15:49

First, I think you meant

Expression ::= Term (<operator> Expression)*

Back to your question: You do not need to "resolve the issue", because ANTLR has no problem dealing with tail recursion. I'm nearly certain that it replaces tail recursion with a loop in the code that it generates. This tutorial (search for the chapter called "Expressions" on the page) explains how to arrive at the e1 = e2 (op e2)* structure. In general, though, you define expressions in terms of higher-priority expressions, so the actual recursive call happens only when you process parentheses and function parameters:

expression : relationalExpression (('and'|'or') relationalExpression)*;
relationalExpression : addingExpression ((EQUALS|NOT_EQUALS|GT|GTE|LT|LTE) addingExpression)*;
addingExpression : multiplyingExpression ((PLUS|MINUS) multiplyingExpression)*;
multiplyingExpression : signExpression ((TIMES|DIV|'mod') signExpression)*;
signExpression : (PLUS|MINUS)* primeExpression;
primeExpression : literal | variable | LPAREN expression /* recursion!!! */ RPAREN;

Using ANTLR with Left-Recursive Rules

1 Answers