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
@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 — user4259109
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
@GRosenberg Thank you for your answer. Is there any thing can I do with the grammar to make both f and sum roots. — user4259109

GRosenberg GRosenberg · Accepted Answer · 2015-05-19T20:49:54

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.

ANTLR 4 Parser Grammar

1 Answers