Reporting AttemptingFullContext and ContextSensitivity on an expression inside grammar

[Andres Solenzal]

Hi all. I have the following issue but first I will throw some context. I have created a grammar for a custom DSL for my company using Javascript as the target language. On some queries the parsing happens really fast, but in some cases(large queries) it takes too long, a minute or more. So I have ditched most of the specificity of my grammar and handle the validations and extra stuff in the parsing dictionary. But debugging this grammar with large queries to check where the bottleneck is I have used the -diagnostics flag on grun and the parser complains with contextSensitivity and attemptingFullContext warnings. Those warnings are mostly related to an expression defined in the grammar that is like this one.

binaryBody: expression (AND | OR | AND_NOT) expression (:(AND | OR | AND_NOT) expression)*?

I can parse input in a way that "A" OR "B" OR "C" OR "D" will produce a flat subtree with all elements as leaves but warnings are there. And there is a warning for each instance of OR and OR "term" inside the expression.

line 1:14205 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:14229 reportAttemptingFullContext d=3 (binaryBody), input='OR "google.com"'

My question is, is there a way to rewrite that expression that stops the parser complaints?

This is the output for "amazon" OR "facebook" OR "twitter" OR "youtube" OR "meme" OR "popo" OR "amazon" OR "facebook" OR "twitter" OR "youtube" OR "meme" OR "popo"

line 1:23 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:23 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:36 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:36 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:49 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:49 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:59 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:59 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:69 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:69 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:81 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:81 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:95 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:95 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:108 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:108 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:121 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:121 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:131 reportAttemptingFullContext d=3 (binaryBody), input='OR'

line 1:131 reportContextSensitivity d=3 (binaryBody), input='OR'

[Mike Cargal]

I'm not positive what the source of this particular error is, but do have a question:

the rule: 

  binaryBody: expression (AND | OR | AND_NOT) expression (:(AND | OR | AND_NOT) expression)*?

implies that AND, OR, and AND_NOT all have the same precedence.   That's VERY unusual, are you sure that's what you intend?  Also unusual, making AND_NOT a single token

I had a similar situation where I wanted to flatten the normal expression tree (whenever it was a series of additions, or a series of multiplications for example) and just wrote the grammar to create a standard parse tree, and processed the tree after the fact to "pull up" "siblings" where appropriate.  So, the ruler would have been more like:

  binaryBody: <assoc=right> NOT expressions

      | expression AND  expression 

      | expression  OR  expression 

Then "a OR b AND c AND_NOT d"  would give me a parse tree like

                  OR

              /             \

 a                AND

                          /        \

                        b          AND

                                   /        \      

                                 c           NOT

                                                |

                                               d

after "pulling up" I'd have a structure like

      OR

   /        \

a            AND

            /     |    \

          b    c      NOT

                          |

                         d

I suspect that this same refactoring might fix your problem.  It really looks like you're trying to hard to force a grammar to give you the flattened tree structure you want.  (Possibly at the expense of correctness for precedence)  I also suspect that the parse tree you'd get would be more difficult to deal with than you may expect.

just my two cents...

On Jan 2, 2019, at 1:49 PM, Andres Solenzal <asol...@gmail.com> wrote:

Hi all. I have the following issue but first I will throw some context. I have created a grammar for a custom DSL for my company using Javascript as the target language. On some queries the parsing happens really fast, but in some cases(large queries) it takes too long, a minute or more. So I have ditched most of the specificity of my grammar and handle the validations and extra stuff in the parsing dictionary. But debugging this grammar with large queries to check where the bottleneck is I have used the -diagnostics flag on grun and the parser complains with contextSensitivity and attemptingFullContext warnings. Those warnings are mostly related to an expression defined in the grammar that is like this one.

binaryBody: expression (AND | OR | AND_NOT) expression (:(AND | OR | AND_NOT) expression)*?

I can parse input in a way that "A" OR "B" OR "C" OR "D" will produce a flat subtree with all elements as leaves but warnings are there. And there is a warning for each instance of OR and OR "term" inside the expression.

line 1:14205 reportContextSensitivity d=3 (binaryBody), input='OR'

line 1:14229 reportAttemptingFullContext d=3 (binaryBody), input='OR "google.com"'

My question is, is there a way to rewrite that expression that stops the parser complaints?

-- 
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/d/optout.

[Andres Solenzal]

Hi Mike. Thanks for your two cents, really appreciate them. The thing with my grammar without operator precedence is that I handle it on a dictionary code, I convert the whole expression to a reverse polish notation stack and when doing that I take operator precedence into account but 'expression' can change that precedence on particular cases.

Thanks again. 

Andres

You received this message because you are subscribed to a topic in the Google Groups "antlr-discussion" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/antlr-discussion/Avz8eumt4TU/unsubscribe.
To unsubscribe from this group and all its topics, send an email to antlr-discussi...@googlegroups.com.