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

Gerald Rosenberg gerald at certiv.net
Tue Nov 3 22:28:17 PST 2009


It is AntlrDT: http://www.certiv.net/projects/antlrdt.html

At 07:20 PM 11/3/2009, you wrote:
>Hi Gerald,
>
>What's the program you used to generate those diagrams in the last 
>message? I sometimes have a bit of trouble understanding what the 
>2nd alternatives are in ANTLRWorks, and this might with it.
>
>Chi Ho Kwok
>
>On Tue, Nov 3, 2009 at 7:55 PM, Gerald Rosenberg 
><<mailto:gerald at certiv.net>gerald at certiv.net> wrote:
>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, <mailto:alex.marin at amiq.ro>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>http://www.antlr.org/mailman/listinfo/antlr-interest
>>Unsubscribe: 
>><http://www.antlr.org/mailman/options/antlr-interest/your-email-address>http://www.antlr.org/mailman/options/antlr-interest/your-email-address 
>>
>
>
>List: 
><http://www.antlr.org/mailman/listinfo/antlr-interest>http://www.antlr.org/mailman/listinfo/antlr-interest
>Unsubscribe: 
><http://www.antlr.org/mailman/options/antlr-interest/your-email-address>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/0e1c8161/attachment.html 


More information about the antlr-interest mailing list