What's the best practice to handle recursive patterns in javascript?

[ML]

We found bad performance issue to parse expressions like abs(abs(abs(abs(abs(abs(abs(abs(abs(1)))))))))  (This is just an example, we are dealing with more complex expressions)

Sample G4:

expression

: 

'(' expression ')' #Scope

| function #FunctionExpr

;

function

: basicName '(' (expression (',' expression)*)? ')'

;

The issue is like https://groups.google.com/forum/#!search/antlr$204$20javascript$20performance/antlr-discussion/Giy2KHEeXgM/6TGuF4nNEAAJ, but I didn't see a solution for that.

How to solve this kind of issue? And to let Javascript parse recursive patterns efficiently, what's the best practice?

Thanks!

[eric vergnaud]

At first glance, your grammar is not able to deal with abs(1)

Maybe this influences the performance significantly 

[刘名扬]

Thanks Eric for your reply! Actually I just pasted part of our definition. We can handle recursive functions, just if there are too many (more than 8), it takes several minutes to parse. We also have a Java version parser, which can deal with this easily.

Do you have any recommendations about how to write a G4 to make JavaScript parser work? We can just use abs for an example. Thanks!

--
You received this message because you are subscribed to the Google Groups "antlr-discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to antlr-discussi...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/antlr-discussion/1f98df13-9da7-449d-a5bf-94b854332b70%40googlegroups.com.

[eric vergnaud]

All official antlr runtimes use the exact same algorithm, and thus have the same complexity.

That doesn't translate into same speed because each target language comes with its own strengths and weaknesses.

And the environment matters. It's possible that the slowness you observe has nothing to do with recursion

Le vendredi 27 septembre 2019 18:41:46 UTC+8, ML a écrit :

Thanks Eric for your reply! Actually I just pasted part of our definition. We can handle recursive functions, just if there are too many (more than 8), it takes several minutes to parse. We also have a Java version parser, which can deal with this easily.

Do you have any recommendations about how to write a G4 to make JavaScript parser work? We can just use abs for an example. Thanks!

On Fri, Sep 27, 2019, 1:58 AM eric vergnaud <ad...@prompto.cloud> wrote:

At first glance, your grammar is not able to deal with abs(1)

Maybe this influences the performance significantly 

Le vendredi 27 septembre 2019 08:38:04 UTC+8, ML a écrit :

We found bad performance issue to parse expressions like abs(abs(abs(abs(abs(abs(abs(abs(abs(1)))))))))  (This is just an example, we are dealing with more complex expressions)

Sample G4:

expression

: 

'(' expression ')' #Scope

| function #FunctionExpr

;

function

: basicName '(' (expression (',' expression)*)? ')'

;

The issue is like https://groups.google.com/forum/#!search/antlr$204$20javascript$20performance/antlr-discussion/Giy2KHEeXgM/6TGuF4nNEAAJ, but I didn't see a solution for that.

How to solve this kind of issue? And to let Javascript parse recursive patterns efficiently, what's the best practice?

Thanks!

--
You received this message because you are subscribed to the Google Groups "antlr-discussion" group.

To unsubscribe from this group and stop receiving emails from it, send an email to antlr-di...@googlegroups.com.

[刘名扬]

Thanks Eric. Our system has been running for several months. Overall the performance of JavaScript is OK. We are pretty sure for this kind of pattern, it takes time.

I saw there were similiar discussions in the internet about this. The root cause seems to be around the toString function. But I didn't find any solution.

If you don't mind, can you give us some guidance, like how to optimize. I think you can repro the issue with a simple G4. If it works for you, can you share your G4 definition? Thanks!

To unsubscribe from this group and stop receiving emails from it, send an email to antlr-discussi...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/antlr-discussion/f3fe98be-6815-478d-9cce-3f5a696d2c6d%40googlegroups.com.

[Michael C. Starkie]

Is it possible for you to profile the code and try to pinpoint where the slowness is located?  

To view this discussion on the web visit https://groups.google.com/d/msgid/antlr-discussion/CAOnVP8ydV%3D3ZGG_vEjN%3D_v1wZ_6zGgJg249nZzPasiYO6E801Q%40mail.gmail.com.

[eric vergnaud]

JavaScript has no support for hashCode and equals, therefore the original runtime made heavy use of toString

since then, it has been refactored to use murmur3

toString should no longer be called during parsing

if it is called, it's a bug (such a bug was recently fixed, but maybe not released yet)

To view this discussion on the web visit https://groups.google.com/d/msgid/antlr-discussion/f3fe98be-6815-478d-9cce-3f5a696d2c6d%40googlegroups.com.

[刘名扬]

We are using 4.7.1. Does it include this change? And for that bug you mentioned, when do you plan to release the new version?

To unsubscribe from this group and stop receiving emails from it, send an email to antlr-discussi...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/antlr-discussion/76d2b8b1-fe39-40ed-8a9d-d7139fa4f254%40googlegroups.com.

[eric vergnaud]

Release schedule is manage by Terence.

Suggest you try using the latest source code to see of it addresses your problem.

To view this discussion on the web visit https://groups.google.com/d/msgid/antlr-discussion/76d2b8b1-fe39-40ed-8a9d-d7139fa4f254%40googlegroups.com.

[刘名扬]

Thanks, I'll try 4.7.2 tomorrow and update the result here.

To unsubscribe from this group and stop receiving emails from it, send an email to antlr-discussi...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/antlr-discussion/b6ca5813-da01-41f7-8b82-b6340057ba87%40googlegroups.com.

[刘名扬]

Hi all,

4.7.2 doesn't work. But I found the root cause. It's due to the toString() used in cache key. I sent out a PR to fix it, please take a look. https://github.com/antlr/antlr4/pull/2657

More details are in the description of the PR.

Thanks