How to do this simple semantic check?

[Carl Smotricz]

Dear fellow ANTLR 4 fans,

The language I'm trying to write a grammar for has a similar kind of ambiguity to the one about C++ that Terrence mentions in his book:

A macro definition is syntactically identical to an assignment to a subscripted variable. To wit, here's a grammar excerpt:

topNode: defLines execLines ;

  defLines: defLine* ;
    defLine: macroDef | otherDef ;
      macroDef: id formals '=' expr ;


  execLines: execLine* ;
    execLine: assignment | otherExec ;
      assignment: scalarAssignment | arrayAssignment ;
        arrayAssignment: id formals '=' expr ;

formals: '(' id ( ',' id )* ')' ;

...so occasionally an assignment will wrongly end up in the macro definitions, which messes up my parse tree structure.

There is a simple test that eliminates most of the questionable cases: A legitimate macro will use all of its formal arguments (the 'id's to the left of the '=') in the expression to the right.

'expr' can be an arbitrarily complex tree, but the variables in it are of course all of type 'id'.

Ideally, I would like to access my formal args and my expr before they get cast into the rule 'macroDef' or 'arrayAssignment' and veto the macro def unless all formal args appear in the expr.

I've done the Java coding (it's simple enough) but how can I incorporate the test into my grammar? It looks to me like semantic predicates can only be applied _before_ you know what you're looking at.

[Eric Vergnaud]

Hi,

the parsing phase doesn't sound like the right timz to resolve such ambiguities.

Think of a C program where the macro is defined in an include file, then the parser does not even see it!

I would recommend doing this in a post parsing phase, once all the definitions are collected, and the ambiguity can be resolved by a simple lookup rather than a semantic predicate

Eric

[Carl Smotricz]

I hear you, Eric, and if I don't find a better solution I will end up fiddling with the parse tree in a later step.

But your objection doesn't hold water, for 2 reasons:

1. I'm talking specifically about a case where all the information required to resolve the ambiguity (purely semantically!) is right there, only a few tokens ahead; and
   
2. It's not unusual for a parser to do a little more than pure semantic analysis where this makes sense to allow it to arrive at a correct parse as early as possible. Terrence specifically mentions this kind of situation in his book as a use case for a semantic predicate, and gives an example of using a semantic predicate that controls a parsing decision via a symbol table lookup.
   

[Terence Parr]

On Apr 22, 2015, at 4:27 PM, Eric Vergnaud <eric.v...@wanadoo.fr> wrote:

There is a simple test that eliminates most of the questionable cases: A legitimate macro will use all of its formal arguments (the 'id's to the left of the '=') in the expression to the right.

'expr' can be an arbitrarily complex tree, but the variables in it are of course all of type 'id'.

Ideally, I would like to access my formal args and my expr before they get cast into the rule 'macroDef' or 'arrayAssignment' and veto the macro def unless all formal args appear in the expr.

I've done the Java coding (it's simple enough) but how can I incorporate the test into my grammar? It looks to me like semantic predicates can only be applied _before_ you know what you're looking at.

yep, gotta use input.LT(i) to look ahead in your preds I’m afraid. if it requires parsing in the predicate, that makes it painful. might be time to unify the two possible parses into a single tree and disambiguate after parsing.

Ter

[Carl Smotricz]

That's what I was afraid of! OK, then I'm off to the semantic salt mines. Thanks for the quick replies!