ANTLR4: How to find the root rules in a gramar which maybe used to find the start rule

Question

I have been looking at the grammars located at:

Antlr 4 grammars

and I have been using Antlrworks 2 to view them, however I am finding it difficult to locate the start rule for the entire grammar.

I think the definition of a start rule is a node which has no other pointers to it, does anyone have a working solution to find the start rule for these grammars?

Answer 1

To find the root/start rule I have implemented a ANTLR tree listener which creates an adjacency list of all the rules in an ANTLR grammar and check to see if no other grammar rule references it. This would give a hint as to what the start rule might be.

To run this you will need the antlr grammar taken from Antlr 4 grammar

Here is the listener implementation:

(RootFinder.java)

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;


public class RootFinder extends ANTLRv4ParserBaseListener {

    private Set<String> rules = new HashSet<String>( );
    public Map<String, Set<String>> adjacencyList = new LinkedHashMap<String, Set<String>>( );

    public void enterParserRuleSpec(ANTLRv4Parser.ParserRuleSpecContext ctx)
    {
        rules = new HashSet<String>( );     
    }

    public void exitParserRuleSpec(ANTLRv4Parser.ParserRuleSpecContext ctx)
    {
        if(ctx != null)
        {
            adjacencyList.put(ctx.RULE_REF().getText(), rules);
        }
    }

    public void exitRuleref(ANTLRv4Parser.RulerefContext ctx) {
        if(ctx != null)
        {
            rules.add(ctx.getText());
        }
    }

    public List<String> leafNodes( )
    {
        List<String> leafs = new ArrayList<String>( );
        for(Entry<String, Set<String>> entry : adjacencyList.entrySet())
        {
            if( entry.getValue().size() == 0)
            {
                leafs.add(entry.getKey());
            }
        }
        return leafs;
    }

    public Set<String> rootNodes( )
    {
        Set<String> roots = new HashSet<String>( );
        Collection<Set<String>> values = adjacencyList.values();

        for(Entry<String, Set<String>> entry : adjacencyList.entrySet())
        {
            boolean found = false;
            for(Set<String> vals : values)
            {
                if(vals.contains(entry.getKey()))
                {
                    found = true;
                }
            }
            if(found == false)
            {
                roots.add(entry.getKey());
            }
        }
        return roots;
    }
}

and here is the Main program that runs it

(Main.java)

import java.io.IOException;

import org.antlr.v4.runtime.ANTLRFileStream;
import org.antlr.v4.runtime.ANTLRInputStream;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;


public class Main {

    public static void main(String[] args) throws IOException {

        String filename = args[0];
        ANTLRInputStream reader = new ANTLRFileStream(filename);
        ANTLRv4Lexer lexer = new ANTLRv4Lexer(reader);
        CommonTokenStream tokenStream = new CommonTokenStream(lexer);
        ANTLRv4Parser parser = new ANTLRv4Parser(tokenStream);
        RootFinder rootfinder = new RootFinder();
        parser.addParseListener(rootfinder);

        ParseTree tree = parser.grammarSpec();
        System.out.println(rootfinder.leafNodes());
        System.out.println(rootfinder.rootNodes());
    }

}