Antlr 4.1: Right-recursion, parsing time and freezes

[Paweł Kaczyński]

Hi,

I'm using Antlr 4.1 to write a tool for parsing and translating a programming language. I just ran into a strange problem.

I have logical expression parsing written as:

expression

:(...)

|   lhs=expression operator=(

                            AMPERSANDAMPERSAND

                          | PIPEPIPE

                          ) rhs=expression      # LogicalOperationExpression

which basically works quite well. Only I just parsed a bit of code where there were many, many OR's:

if(a || (b || c || d || e || ... || zz))

Antlr (both embed in my app and the Antlrworks one) basically froze. It was eating cpu cycles but with no result. I stated cutting back those ORs. At (a || (b || c)) it works fast. With 5 ORs it's a bit slower. With about 8 it starts to take loong time to parse it and with full load (14 I think) it just doesn't end in reasonable time.

Is that a known behaviour or a bug? And in both cases, what can I do to be able to parse such expressions?

I tried rewriting the rule to

| expression logicalRest+ #...

logicalRest

: operator=(

                            AMPERSANDAMPERSAND

                          | PIPEPIPE

                          ) rhs=expression

;

but it still prefers to go recursive way instead of flattening it as expression -> expression, logicalRest, logicalRest, ..., logicalRest

[gekk...@gmail.com]

After upgrading from c# target 4.01-snapshot to 4.1 snapshot I'm experiencing the same problem.

If I have a statement in the form of
var = a + b +  <generate couple of 100 expressions here> + z;
it will freeze. I traced it back to

        protected internal virtual void Closure(ATNConfigSet sourceConfigs, ATNConfigSet
            configs, bool collectPredicates, bool hasMoreContext, PredictionContextCache
            contextCache)
        {
            if (contextCache == null)
            {
                contextCache = PredictionContextCache.Uncached;
            }
            ATNConfigSet currentConfigs = sourceConfigs;
            HashSet<ATNConfig> closureBusy = new HashSet<ATNConfig>();
            while (currentConfigs.Count > 0)
            {
                ATNConfigSet intermediate = new ATNConfigSet();
                foreach (ATNConfig config in currentConfigs)
                {
                    Closure(config, configs, intermediate, closureBusy, collectPredicates, hasMoreContext
                        , contextCache, 0);
                }
                currentConfigs = intermediate;
            }
        }

It stays in the foreach loop. Looking at the source history, some infinite recursion check was removed. Could this have caused this ?

[Terence Parr]

Hi.  What you are experiencing is possible. Can you try it with the two-stage parsing trick, described in the book?  You can try just setting:

    parser.getInterpreter().setPredictionMode(PredictionMode.SLL);

 to get an idea what the faster but slightly less powerful mechanism can do on your grammar.

--
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.
For more options, visit https://groups.google.com/groups/opt_out.

--

Dictation in use. Please excuse homophones, malapropisms, and nonsense.