CODEWITHSUNDEEP
recursionantlr
CNevin561
CNevin561

Reputation: 143

Using ANTLR with Left-Recursive Rules

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?

Upvotes: 2

Views: 1935

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

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;

Upvotes: 2

Related Questions