CODEWITHSUNDEEP
time-complexityantlrll-grammar
OrenIshShalom
OrenIshShalom

Reputation: 7162

antlr parsing of java 8 file (python binding) - slow running time

I'm trying to scan a java 8 file with antlr4, based on this java 8 grammar. Everything goes fine, except the running time:

input_stream = FileStream("/main.java")
lexer = Java8Lexer(input_stream)
stream = CommonTokenStream(lexer)
parser = Java8Parser(stream)
tree = parser.compilationUnit()

class GadgetIfStmtListener(Java8Listener):
    # Enter a parse tree produced by Java8Parser#ifThenStatement.
    def enterIfThenStatement(self, ctx:Java8Parser.IfThenStatementContext):
        print(ctx.getText())

gadget = GadgetIfStmtListener()
walker = ParseTreeWalker()
walker.walk(gadget, tree)

The main.java file is pasted at the end (a simple nested loop to compute primes in [2,100]). When I time it I get:

$ time python3.6 main.py
if(i*j==p){returnfalse;}
if(isPrime(p)){System.out.format("%d\n",p);}

real    0m14.611s

Is this reasonable? The original pldi paper mentions (one of the examples is Java 1.5)

average parsing speed is about 26,000 lines / second for [...] examples

Here is the main.java file for completeness:

class main {
    private static boolean isPrime(int p)
    {
        for (int i=0;i<p;i++) {
            for (int j=0;j<p;j++) {
                if (i*j == p) {
                    return false; }}}
        return true;
    }
    private static void printPrimes(int start, int end)
    {
        for (int p=start;p<=end;p++) {
            if (isPrime(p)) {
                System.out.format("%d\n", p);
            }}
    }
    public static void main(String[] args)
    {
        int start = 2;
        int end = 100;
        printPrimes(start, end);
        System.out.println("Hello, World!");
    }
}

Upvotes: 1

Views: 231

Answers (1)

Bart Kiers
Bart Kiers

Reputation: 170278

Is this reasonable?

That is subjective, I've not studied the grammar and it also all depends on what you think is reasonable :)

The original pldi paper mentions (one of the examples is Java 1.5)

It is a well known fact that there are huge (and I mean really huge) differences between ANTLR targets. Python is, AFAIK, one of the slowest out there. For sure you can squeeze some ms. by reordering parser rules more efficiently, but to gain significant speed improvement, go for the Java or C# target (or probably the C++ or C target as well, but I have no experience with them).

Note that the paper you mentioned talks about the (officially supported) Java target. All other targets than Java are (again AFAIK) community created/supported.

Upvotes: 1

Related Questions