ANTLR 4 Parser Grammar

Question

How can I improve my parser grammar so that instead of creating an AST that contains couple of decFunc rules for my testing code. It will create only one and sum becomes the second root. I tried to solve this problem using multiple different ways but I always get a left recursive error. This is my testing code :

f :: [Int] -> [Int] -> [Int]
f x y = zipWith (sum) x y
sum :: [Int] -> [Int]
sum a = foldr(+) a

This is my grammar: This is the image that has two decFuncin this link http://postimg.org/image/w5goph9b7/

prog        : stat+;

stat        : decFunc  | impFunc ;


decFunc     : ID '::' formalType ( ARROW formalType )* NL impFunc
            ;

anotherFunc : ID+;


formalType  : 'Int' | '[' formalType ']' ;


impFunc     : ID+ '=' hr NL

            ;


hr          : 'map' '(' ID* ')'  ID*
                | 'zipWith' '(' ('*' |'/' |'+' |'-') ')' ID+ | 'zipWith' '(' anotherFunc ')' ID+
                | 'foldr'   '(' ('*' |'/' |'+' |'-') ')' ID+
                | hr  op=('*'| '/' | '.&.' | 'xor' ) hr | DIGIT
                | 'shiftL' hr hr | 'shiftR' hr hr
                | hr  op=('+'| '-') hr | DIGIT
                | '(' hr ')'
                | ID '(' ID* ')'
                | ID
                ;

What is the desired output? It doesn't make much sense to say "creating one instead of two `decFunc`". Try creating an AST similar to what you want. — Mephy, May 18 '15 at 21:24
@Mephy I improved my question. I am basically trying to make sum refer to another stat that can be a declaration or implementation. However sum is only the first word of a declaration or implementation How can I do that? this is what I am asking for. Some suggest lookahead. But I don't know how to do it — , May 18 '15 at 21:50
Still not clear what you are asking. Your test input contains two instances of content that will match the `decFunc` rule. The generated **parse-tree** shows exactly that: two sub-trees, each having a `deFunc` instance as the root. Antlr v4 will not produce a true AST where `f` and `sum` are the roots of separate sub-trees, if that is what you are looking for. — GRosenberg, May 19 '15 at 00:50
@GRosenberg Thank you for your answer. Is there any thing can I do with the grammar to make both f and sum roots. — , May 19 '15 at 07:45

score 5 · Accepted Answer · answered May 19 '15 at 20:49

Your test input contains two instances of content that will match the decFunc rule. The generated parse-tree shows exactly that: two sub-trees, each having a deFunc as the root.

Antlr v4 will not produce a true AST where f and sum are the roots of separate sub-trees.

Is there any thing can I do with the grammar to make both f and sum roots – Jonny Magnam

Not directly in an Antlr v4 grammar. You could:

switch to Antlr v3, or another parser tool, and define the generated AST as you wish.
walk the Antlr v4 parse-tree and create a separate AST of your desired form.
just use the parse-tree directly with the realization that it is informationally equivalent to a classically defined AST and the implementation provides a number practical benefits.

Specifically, the standard academic AST is mutable, meaning that every (or all but the first) visitor is custom, not generated, and that any change in the underlying grammar or an interim structure of the AST will require reconsideration and likely changes to every subsequent visitor and their implemented logic.

The Antlr v4 parse-tree is essentially immutable, allowing decorations to be accumulated against tree nodes without loss of relational integrity. Visitors all use a common base structure, greatly reducing brittleness due to grammar changes and effects of prior executed visitors. As a practical matter, tree-walks are easily constructed, fast, and mutually independent except where expressly desired. They can achieve a greater separation of concerns in design and easier code maintenance in practice.

Choose the right tool for the whole job, in whatever way you define it.

Thank you for your precious time and your answer. It helped me to recognize that if I am going to continue with ANTLR4, I should accept what the AST as it is. I would like to ask you which one do you prefer for implementing a translator a Listener or a Visitor. The translate will generate another code no calculation required. — , May 20 '15 at 02:31
The only practical difference between the visitor and listener is that the visitor passes a return object, the listener nothing. In some cases, the return object can be useful. Really up to you to decide if it helps in your specific design. — GRosenberg, May 20 '15 at 04:51

ANTLR 4 Parser Grammar

1 Answers1

Linked