解决解析带有可选参数的AgeSQL子句时的reduce/reduce冲突

Question

我正在开发一个项目，以在 Postgres psql 上添加对 Cypher 子句的支持。我正在尝试提高解析器性能，解决规则之间的冲突。我创建了一个最小的示例来说明实现中的常见问题。该示例位于描述下方。

子句由与选项混合的命令组成。选项是可能包含在子句中也可能不包含在子句中的命令。在下面的例子中，当执行程序时，我们可以触发规则

COMMAND id_opt B str_opt

运行子句

COMMAND country A "Canada"

。同样，我们可以触发规则

COMMAND num_opt ab_opt str_opt

运行子句

COMMAND 1 A "Canada"

或

COMMAND 1 B "Canada"

。由于冲突，第一个子句返回语法错误。

问题是由于

id_opt

、

str_opt

和

num_opt

都是选项并且可以为空，子句

COMMAND A

可以触发这两个规则，导致冲突并在编译项目时返回以下警告：

gram.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]

创建包含所有选项的唯一规则（如下例所示）可以解决警告问题。但我不希望

id_opt

与

num_opt

出现在同一个子句中。在这种虚构的语言中，子句“COMMAND 1 name A“Canada”不存在。在这种情况下，我应该合并所有选项并稍后处理无效选项，还是应该保留冲突并避免无效选项组合？

command: 
    COMMAND num_opt id_opt ab_opt str_opt { printf("Clause parsed successfully.\n"); }
    ;

对于更具体的示例，我正在处理 AgeSQL 存储库 中的 cypher.y 文件。这个问题出现在

return_clause

规则中。我展示一个最小示例的动机是 cypher.y 文件规则有近千行。最小的例子如下：

gram.l 文件：

%{
#include "gram.tab.h"
%}

%%
[ \t\n]          /* ignore whitespace */
"COMMAND"        { return COMMAND; }
"A"              { return A; }
"B"              { return B; }

[0-9]+ { return NUMBER; }
[a-zA-Z][a-zA-Z0-9_.*]* { return IDENTIFIER; }
("\"")[^"]*("\"")|("\'")[^']*("\'") { return STRING; }
%%
int yywrap(void) {
    return 1;
}

gram.y 文件：

%{
#include <stdio.h>
#include <stdlib.h>

int yylex(void);
void yyerror(const char*);

char u;
%}

%token COMMAND A B IDENTIFIER STRING NUMBER

%%

command: 
    COMMAND id_opt A str_opt { printf("Clause A parsed successfully.\n"); }
    | COMMAND num_opt ab_opt str_opt { printf("Clause B parsed successfully.\n"); }
    ;
            
id_opt:
    /* empty */
    | IDENTIFIER;
    ;
     
str_opt:
    /* empty */
    | STRING
    ;

num_opt:
    /* empty */
    | NUMBER
    ;

ab_opt:
    A
    | B
    ;

%%


void yyerror(const char *s) {
    fprintf(stderr, "Parse error: %s\n", s);
    exit(1);
}

int main(void) {
    yyparse();
    printf("Parsed variable: %c\n", u);
    return 0;
}

Makefile：

gram: gram.tab.c lex.yy.c
    gcc -o gram gram.tab.c lex.yy.c

gram.tab.c: gram.y
    bison -d gram.y

lex.yy.c: gram.l
    flex gram.l

Answer 1

您可以简单地将

id_opt

和

num_opt

规则组合在一起，我将其命名为

id_num_opt

。然后，您可以删除

command

中的规则之一以避免重复：

command: 
    COMMAND id_num_opt ab_opt str_opt { printf("Clause parsed successfully.\n"); }
    ;
            
id_num_opt:
    /* empty */
    | IDENTIFIER;
    | NUMBER;
    ;
     
str_opt:
    /* empty */
    | STRING
    ;

ab_opt:
    A
    | B
    ;