[antlr-interest] Bug report: Unexplainable "no viable alternative"

[Gerald Rosenberg]

The first version is failing on the associative_dimension_1 not 
having a star or data_type and no other alternative available.

The second version falls through the associative_dimension_2 to 
sized_or_unsized_dimension to recognize the '[]'

Note, both have a bit of backtracking that may be problematic on more 
complex inputs.

HTHs,
Gerald

At 10:22 AM 11/3/2009, alex.marin at amiq.ro wrote:
>Hello,
>
>We have trouble understanding why we get a "no viable alternative" when
>running the attached parser grammar on the following input:
>
>bit bitstream [];
>
>The output is:
>
>line 1:15 no viable alternative at input ']'
>
>However, we have found two (very strange) workarounds for the issue:
>1. Commenting out the 'real' option in the data_type rule
>2. Using associative_dimension_2 rule instead of associative_dimension_1
>(although the two are equivalent)
>
>What is the explanation for this behavior?
>Is there a rigurous solution to avoid such behavior?
>
>Thanks,
>Alex Marin
>
>Notes:
>- the example is not intended to be useful by itself (it is an excerpt from
>a much larger grammar)
>- the latest antlr version has been used for code generation
>(antlr-3.2.jar)
>- you can find the referred grammar inline at the end of this e-mail and
>also in the attached file
>- by comparing the generated parsers, we noticed that the workarounds cause
>the prediction to be done by some complicated if-conditions rather than the
>dfa which throws the NoViableAlt
>
>////////////////// Example.g ////////////////////////
>
>grammar Example;
>
>options {
>         k=1;
>         output=AST;
>         }
>
>entry
>:
>(my_rule)+
>;
>
>my_rule
>         :
>           tf_port_item SEMI
>         ;
>
>tf_port_item
>:
>data_type ID variable_dimension
>;
>
>
>data_type
>:
>'bit'
>| 'byte'
>| 'real' // Comment this to suppress NoViableAlt
>| 'struct'
>| 'union' ( 'tagged' )?
>| 'enum'
>| 'virtual'
>| ps_identifier
>;
>
>ps_identifier
>:
>( ID COLON_COLON ) => ID COLON_COLON ID
>| ID
>;
>
>variable_dimension
>:
>( associative_dimension_1 ) => associative_dimension_1 variable_dimension
>// comment this line
>//        ( associative_dimension_2 ) => associative_dimension_2
>variable_dimension  // and uncomment this one to suppress NoViableAlt (
>with 'real' alt in data_type)
>| ( sized_or_unsized_dimension )*
>;
>
>associative_dimension_1
>:
>LBRACK ( STAR | data_type ) RBRACK
>;
>
>associative_dimension_2
>             :
>( LBRACK STAR ) => LBRACK STAR RBRACK
>| LBRACK data_type RBRACK
>             ;
>
>
>sized_or_unsized_dimension
>:
>LBRACK ( NUMBER )? RBRACK
>;
>
>/********** Lexer *************/
>
>SEMI: ';';
>STAR: '*';
>LBRACK: '[';
>RBRACK: ']';
>COLON_COLON: '::';
>
>WS
>:
>(' '|'\r'|'\t'|'\u000C'|'\n') {$channel=HIDDEN;}
>;
>
>ID
>:
>('a'..'z'|'A'..'Z'|'_') ('0'..'9'|'a'..'z'|'A'..'Z'|'_')*
>;
>
>NUMBER
>:
>('0'..'9')+
>;
>
>
>Content-Type: application/octet-stream; charset="UTF-8";
>  name="Example.g";
>Content-Disposition: attachment;
>  filename="Example.g";
>
>
>List: http://www.antlr.org/mailman/listinfo/antlr-interest
>Unsubscribe: 
>http://www.antlr.org/mailman/options/antlr-interest/your-email-address
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20091103/2ee031ae/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Version1.png
Type: application/octet-stream
Size: 87155 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20091103/2ee031ae/attachment-0002.obj 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Version2.png
Type: application/octet-stream
Size: 87947 bytes
Desc: not available
Url : http://www.antlr.org/pipermail/antlr-interest/attachments/20091103/2ee031ae/attachment-0003.obj