2

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?

Steffen
  • 8,033
  • 1
  • 28
  • 34
CNevin561
  • 143
  • 1
  • 3
  • 12
  • 2
    Silly trivia: this question is the seventh hit on Google for "antlr left right associative" seconds after being asked. – sarnold Nov 24 '11 at 01:48
  • 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 Nov 24 '11 at 07:05
  • 1
    FYI, here's a small working expression parser: http://stackoverflow.com/questions/1931307/antlr-is-there-a-simple-example/1932664#1932664 – Bart Kiers Nov 24 '11 at 13:47

1 Answers1

2

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;
Bart Kiers
  • 166,582
  • 36
  • 299
  • 288
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Firstly, there's nothing wrong with you suggestion/answer. However, the OP mentions that the AST being produced is not the "shape" s/he expects. The fact that an AST is created, suggests the parse went okay: so there's no problem with the grammar. – Bart Kiers Nov 24 '11 at 07:04
  • @Bart Kiers My understanding of the OP's question is that the "issue" he would like to resolve is that "in his head" the AST generated with the grammar from the tutorial is wrong because of the left recursion used in the grammar. The fact that a parse went OK does not necessarily imply that the grammar has no problems: naive implementation of tail recursion as a recursive call (as opposed to a loop) in the generator can overflow stack for very long inputs. – Sergey Kalinichenko Nov 24 '11 at 13:34
  • But the grammar _cannot_ be left-recursive since ANTLR is an LL parser generator (the LR at the end of ANTLR stands for Language Recognition). But you have a point: it may be something the OP is wondering about in his head and there isn't a grammar yet (or one that produces errors). In any case, your grammar should put him on the right track! :) (I'll just change the double quotes to single quotes since that is how ANTLR expects literal tokens to look like: the double qoutes in the tutorial you linked to are old ANTLRv2 syntax) – Bart Kiers Nov 24 '11 at 13:45