bison/yacc grammar disambiguation_问答_开发者_运维开发者技术经验分享

开发者 https://www.devze.com 2023-03-08 14:43 出处：网络

I have following bison grammar (as part of more complex grammar): expression: IDENTIFIER CONST LAMBDA match_block

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.