Enforce hoisting of predicates over actions?

[Harald Timeraider]

Dear all,
I am currently trying to get semantic predicates working under Xtext by manually adding them into the generated InternalDSL.g grammar files (which might later be automated). Xtext uses ANTLR 3.2 to my knowledge.
 
The problem is that according to http://www.antlr.org/papers/LL-star/predicate-hoisting.pdf it is not possible to hoist semantic predicates up if there are actions: ''We cannot hoist predicates over actions because they might be a function of that action''. The problem is that XText generates some actions in between to construct the corresponding model.

Is there any possibility to enforce that the hoisting is done nevertheless, even if there are actions, when we know that the actions will not influence the semantic predicate in anyway?

E.g., imagine the following simple toy example:

grammar test;

test: (foobar)+;

foobar:
    {;/*do nothing relevant*/}
    ({; /*do another irrelevant stuff*/;} foo
    | bar
    )
;

foo: {true/*stupidPredicate*/}? MY;
bar: MY;

MY: 'my';

Is it possible to get the semantic predicates correctly working here?

[Jim Idle]

It is probably better to get rid of the semantic actions. If you post your grammar, then we can try to help. I find XText to be very flakey, and every minor auto upgrade by Eclipse seems to break existing projects. Also a lot of features never seem to be quite finished, such as the new formatting interface. Just an observation of course, However, glad to help you if you show the grammar.

Jim

--
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.

[Harald Timeraider]

Dear Jim, thanks for your helpfulness. I am currently trying to implement C for Xtext. I know that Xtext has its pitfalls and that C is a general-purpose language, and eventually also a hard-one to parse, but a lot of people could profit by having the ability to import existing C code right into Eclipse EMF models without additional effort (including myself).

The syntax/file with which I am currently playing around can be found right here: https://github.com/timeraider4u/xtext-predicates/blob/master/xtext/C.xtext

The original file has been the ANTLRv3 grammar file for C.

The problem is that you need semantic predicates for distingishing between a typedefName and a directDeclarator.

So I do not know if it is possible to re-write the grammar. If not, I do not know how to continue...

[Jim Idle]

V4 needs less of this stuff so that's probably why the grammar has been written that way. The usual answer is to left factor the common tokens of both paths, and distinguish only at point of differnce.

a: A B C '(' args ')' ;

b: A B C ;

Transforms to

a: A B C ( '(' args ')' | /* just b */ ) ;

There is usually a way to refactor things like this. 

Jim

[Harald Timeraider]

Dear Jim, unfortunately I have to correct you that C.g4 (the ANTLRv4 version of C) is pretty much the same as the version for Xtext/version 3. When you run the newer version you get less warnings but the generated parser is still not able to distingish between directDeclarators and typeNames in a correct way. Semantic predicates are still needed!!!

I know that it would be possible to refactor the syntax such that no ambiguties can happen and change the EMF classes later in a post-processing phase after parsing but I would prefer to not change the semantics of the grammar and to be able to use semantic predicates in Xtext instead...

Do you/does anybody know if it is possible to ignore actions when hoisting predicates?

[Jim Idle]

On Wed, Sep 2, 2015 at 6:40 AM, Harald Timeraider <timer...@gmx.at> wrote:

Dear Jim, unfortunately I have to correct you that C.g4 (the ANTLRv4 version of C) is pretty much the same as the version for Xtext/version 3.

Well - I didn't say it would work without predicates, just that v4 was better at such things :)

 

When you run the newer version you get less warnings but the generated parser is still not able to distingish between directDeclarators and typeNames in a correct way. Semantic predicates are still needed!!!

Well - as the grammar is written they are perhaps, but I would think it isn't too difficult to refactor. A lot of times, I will start from scratch and design the grammar such that it serves the purpose. Many grammars try to be close to the written spec instead of efficient; this can be useful in a lot of contexts of course.

 

I know that it would be possible to refactor the syntax such that no ambiguties can happen and change the EMF classes later in a post-processing phase after parsing but I would prefer to not change the semantics of the grammar and to be able to use semantic predicates in Xtext instead...

I pretty much sure that you are not able to do this in Xtext to be honest. Everything I have seen about solving such problems seems to be convoluted and laborious. I think that refactoring is really your only sane choice.

 

Do you/does anybody know if it is possible to ignore actions when hoisting predicates?

I am fairly sure that it isn't possible to hoist and ignore actions. Is there no way to avoid the action? Or move the predicate - manually hoist it? I have not studied the grammar very much, but if you don't want to refactor completely, then perhaps it is possible to tweak thre predicate it and republish the tweaks. 

Jim

PS

The nearest thing I can remember about this in v3 is ANTLR-222 (which took some finding as the v3 JIRA system no longer seems to function or at least has moved).

* Improved nondeterminism warning to have:
  Semantic predicates were present but were hidden by actions.
parser grammar U;
a : (A B)? ;
b : X a {p1}? A B | Y a {a1} {p2}? A B | Z a ;

To create the prediction DFA for the optional sub rule in 'a', ANTLR must find all references to 'a' to determine what can follow. A B can follow 'a' in the first two alts rule 'b'.   To resolve the conflict between matching A B immediately in the sub rule and exiting rule 'a' to match it in 'b', ANTLR looks for predicates. In this case, there are two predicates that indicate the semantic context in which the surrounding alternatives are valid. The problem is that one of the predicates is hidden by an action. It took me 1.5 days, but I've finally have gotten ANTLR to properly track the insufficiently covered alternatives. Further, I have gotten it to tell you precisely where the uncovered predicates are even if they are simply hidden by actions. I have also updated all of the nondeterminism warnings so that it tells you if there was a predicate but one hidden by an action (this could be a separate condition from insufficiently covered predicates). here are your messages from ANTLR:

ANTLR Parser Generator  Version 3.1b1 (??)  1989-2007
warning(203): U.g:2:5: Input such as "A B" is insufficiently covered with predicates at locations: alt 2: line 3:38 at B
Semantic predicates were present but were hidden by actions.
warning(200): U.g:2:5: Decision can match input such as "A B" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
Semantic predicates were present but were hidden by actions.

* Fixed ANTLR-222.  ANTLR now ignores preds after actions.

[Harald Timeraider]

Thank you very much for your response. Yes, I have already tried to move up the predicate manually but it is then still hidden by other actions starting right before the alternative(s). It would then require to remove all AST-node-construction actions :-/.

I will take a closer look on the source code next week when I am back from vacation - thanks to your effort I now know what I have to look out for ;-).

Otherwise there is still the possibility to change the grammar if it is not working out as I would like it to be...

[Jim Idle]

Good luck with it. I would like to see Xtext get better so I'll try to help with the refactoring if nothing else!

[Harald Timeraider]

So I am back home and had time to take a look on the source code yesterday.
I have been successful, at least for the example posted above, to enforce the hoisting.
My changes made so far can be viewed at https://github.com/antlr/antlr3/pull/177