开发者

bison/yacc grammar disambiguation

I have following bison grammar (as part of more complex grammar):

expression:
    IDENTIFIER
    | CONST
    | LAMBDA match_block
;
match_block:
    pattern '=' expression
    | match_block '|' pattern '=' expression
;
pattern:
    IDENTIFIER
    | CONST
;
which describe expressions containing identifiers, constants and lambda-functions with pattern matching, which looks like this:

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜