[sv-ec] Grammar ambiguity for empty_queue vs. empty constraint_set

From: Ryan, Ray <Ray_Ryan_at_.....>
Date: Wed Feb 23 2005 - 13:37:34 PST
There appears to be an grammar ambiguity in the rule for
'constraint_set'.

The LRM defines:
        constraint_set ::=
                constraint_expression
                | { { constraint_expression } }

        constraint_expression ::=
                expression_or_dist ;
                | if ( expression ) constraint_set [ else constraint_set
]
                | ...

        expression_or_dist ::= expression [ dist { dist_list } ]

        expression ::=
                primary
                | ...

        primary ::=
                ...
                | empty_queue
                | ...

        empty_queue ::= { } 

Take for example:

    constraint C1 {
         if (cond) {
             // x > y;
         }
    }
    constraint C2 {
        if (cond) {};
    }

In the constraint_expression of 'C1', the constraint_set of the 'if'
constraint is an empty set of constraint_expression's. Whereas in 'C2',
the 'constraint_set' of the 'if' constraint is a 'primary' that is an
'empty_queue'. However, the only difference between the two constraints
is the ';' following the closing brace of the empty_queue. This causes a
grammar ambiguity since the decision between the two must be made prior
to parsing the ';'. 

There are a couple way to resolve the ambiguity.
a) Don't allow an empty list of constraints. IE:
        constraint_set ::=
                constraint_expression
                | { constraint_expression { constraint_expression } }

b) Require a constraint set to be encoded in braces. IE:
        constraint_set ::= { { constraint_expression } }


As illustrated by the example, the case for an empty list can easily
occur when a constraint is temporarily commented out. For this reason,
I'd prefer b).

 

- Ray Ryan

 

 

 
Received on Wed Feb 23 13:37:39 2005

This archive was generated by hypermail 2.1.8 : Wed Feb 23 2005 - 13:37:45 PST