bison/yacc grammar disambiguation
I have following bison grammar (as part of more complex grammar):
which describe expressions containing identifiers, constants and lambda-functions with pattern matching, which looks like this:
expression:
IDENTIFIER
| CONST
| LAMBDA match_block
;
match_block:
pattern '=' expression
| match_block '|' pattern '=' expression
;
pattern:
IDENTIFIER
| CONST
;
lambda 0 = 1
| 1 = 2
| x = x
Problem is 1 shift/reduce conflict caused by ambiguity with nested matches, as in following example:
lambda 0 = 1
| x = lambda 1 = 2
| y = 4
Rule开发者_JS百科 is that match block relate to closest function, as shown with indentation in example above.
My questions is - how can I rewrite this grammar to eliminate this ambiguity (without using %left %right yacc directives)?
If you always want the |
to bind to the closest LAMBDA
, that basically just means that you can only have a LAMBDA
in the LAST |
clause of a match_block
:
non_lambda_expression:
IDENTIFIER
| CONST
;
expression:
non_lambda_expression
| LAMBDA match_block
;
non_lambda_match_block:
pattern '=' non_lambda_expression
| non_lambda_match_block '|' pattern '=' non_lambda_expression
;
match_block:
pattern '=' expression
| non_lambda_match_block '|' pattern '=' expression
;
pattern:
IDENTIFIER
| CONST
;
Basically, you split expression
and match_block
into two versions -- one that allows lambdas and one that does not -- and use the appropriate one in each spot to avoid the ambiguity.
精彩评论