Bison

Question

我正在开发一种使用常量、变量和数组的语法。数组可以像 name[] 或 name。每个语句都使用 expr 或数组等参数。在解析时，没有 [].

的变量名和数组名之间没有区别

array_empty:
                        args_variable '[' ']';

args_array:
                        array_empty {
                            //special command to put array on app stack
                        }
                        | args_variable {
                            //special command to put array on app stack
                        }
args_variable:
                        MYVARIABLE {
                            //Store variable into a variable table
                        }
                        | '(' args_variable ')'
                        ;
args_Ae:
                        expr ',' args_array
            | '(' args_Ae ')';
expr:                   ....

..................

appsomestmt:  APPSOME expr {
                        //do something - one argument
                        }
                        | APPSOME args_Ae {
                        //do something else - two arguments
                        }
                        ;

一条语句可以有多种语法，如：

APPSOME expr
APPSOME array, expr

但是，如果我在我的应用程序 Bison 中使用语句 APPSOME variable，则将 variable 减少到 args_variable，然后再减少到 args_array，即使只有一个参数也是如此。我希望该程序检测到此语句只有一个参数并使用第一个语法 APPSOME expr。只有当语句有 2 个参数时 APPSOME array, expr 我想使用第二种语法 APPSOME array, expr

我该怎么做？请记住，数组在 Mid-Rule 中有一些 操作，用于将数组放入应用程序堆栈。那么，我如何才能强制 Bison 根据语法预期将变量视为 variables/arrays？

编辑

%{ %} %token APPSOME1 APPSOME2 %token <number> APPVARIABLE %left '-' '+' %left '*' '/' %left '^' %% program: programline programnewline program | programline ; programnewline: '\n' { //some code } ; programline: compoundstmt | /* empty */ ; compoundstmt: compoundstmt ':' statement | statement ; array_empty: args_variable '[' ']'; // Array Variable Data args_array: array_empty { //tell interpretor that next is a array } | args_variable { //tell interpretor that next is a array } ; args_variable: APPVARIABLE { //put variable into table } | '(' args_variable ')' ; /* multiple arguments */ args_ee: expr ',' expr | '(' args_ee ')'; args_ae: args_array ',' expr |'(' args_ae ')'; args_aee: args_array ',' expr ',' expr |'(' args_ae ')'; /* list of statements */ statement: app1stmt | app2stmt ; app1stmt: APPSOME1 expr { //code } | APPSOME1 args_ae { //code } ; app2stmt: APPSOME2 args_ee { //code } | APPSOME2 args_aee { //code } ; expr: '(' expr ')' | expr '+' expr { //code } | args_variable { //variable } | expr '-' expr { //code } | expr '*' expr { //code } | expr '/' expr { //code } | expr '^' expr { //code } ; %%

Answer 1

该语法有几个问题。

APPSOME1 并没有什么问题，它需要 expr 或 array, expr。一旦看到逗号，就很清楚选择哪个选项（但请参阅下文有关括号的信息）。但是，APPSOME2 不会起作用：

APPSOME2: expr ',' expr
        | array ',' expr ',' expr

在这里，在遇到 second 逗号之前不可能消除歧义，并且它可能与解析器需要做出决定的点（这是在第一个逗号之前）。

另一个并发症是

之间产生的歧义

args_variable
    : APPVARIABLE
    | '(' args_variable ')'
expr: args_variable
    | '(' expr ')'

当解析器看到 ) 时，它无法知道最后一个产生式是否适用，因为这取决于括号表达式后是否有 ,。

就个人而言，我会通过不允许将数组参数括起来来解决这个问题，但是您也可以通过引入 "parenthesized argument" 非终结符来解决它，它允许将决定推迟到最后一个右括号。那意味着如果你有

APPSOME1 (((ARRAYNAME))), expr

你可以避免在 ARRAYNAME 上执行必要的操作，直到你点击最后一个右括号，这似乎应该是这种情况。

但是 APPSOME2 问题没有这么简单的解决方法。

通常情况下，我建议使用 GLR 解析器来解决这样的问题。由于语法实际上并没有歧义，据我所知，GLR 算法应该能够处理语法不是任何 k 的 LR(k) 的事实。但是你需要仔细考虑解析器动作的处理；在由 bison 构建的 GLR 解析器中，在解析器知道需要哪些操作之前不会处理操作，这意味着在读取了相当多的标记之前可能不会执行操作。通常这无关紧要，但如果你将符号 table 信息反馈回你的词法扫描器，那将不起作用。

当然，总是有可能更改语法以使数组名称的使用不那么含糊。例如，您可以使用如下语法：

APPSOME1 expr
APPSOME1 array expr
APPSOME2 expr, expr
APPSOME2 array expr, expr

其中数组引用根本不使用逗号。这对您的用户来说可能有点微妙，但它也可能使代码更容易阅读，因为它提供了关于命令名称后的第一件事是否用作数组的视觉提示。

Bison - 根据语法期望处理 expr

Bison - treat expr according to syntax expectations

yacc