Bison shift/reduce 冲突/reduce/reduce 冲突警告

Question

当我运行 Ubuntu Linux 中的此野牛代码时，我收到这些警告：

- shift/reduce conflict [-Wconflicts-sr]
- reduce/reduce conflicts [-Wcolficts-sr]

为了更清楚起见，这里有一个屏幕截图： http://i.imgur.com/iznzSsn.png

编辑：reduce/reduce 个错误在

line 86 : typos_dedomenwn
line 101: typos_synartisis

并且 shift/reduce 错误在：

line 129: entoli_if

我找不到解决方法，有人可以帮忙吗？

下面是野牛代码：

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

int totalerrors=0;

extern int yylex();
extern FILE *yyin;
extern int lineno; //Arithmos grammis pou kanei parse

//error handling
void yyerror(const char *msg) {
}
//filling the error array
void printError(char y[],int x){
    //param 1: error string
    //param 2: line number
    char temp[15];
    char temp2[5];
    char final[256];
    sprintf(temp2,"%d: ",x);
    strcpy(temp, "In Line ");
    strcat(temp,temp2);
    strcpy(final,"");
    strcat(final,temp);
    strcat(final,y);
    printf("%d) %s\n",totalerrors+1,final);
    totalerrors++;
}
%}
%start start
%token T_sigkritikos_telestis
%token T_typos_dedomenwn
%token T_typos_synartisis
%token T_stathera
%token T_newline
%token T_kefalida_programmatos
%token T_extern
%token T_void
%token T_return
%token T_if
%token T_else
%token T_plus
%token T_minus
%token T_mult
%token T_div
%token T_percentage
%token T_int
%token T_bool
%token T_string
%token T_true
%token T_false
%token T_id
%token T_semic
%token T_comma
%token T_openpar
%token T_closepar
%token T_ampersand
%token T_begin
%token T_end
%token T_excl
%token T_or
%token T_equals
%token T_semileft
%token T_semiright
%%
start: exwterikes_dilwseis T_kefalida_programmatos tmima_orismwn tmima_entolwn;

exwterikes_dilwseis: exwteriko_prwtotypo exwterikes_dilwseis
    | ;

exwteriko_prwtotypo: T_extern prwtotypo_synartisis;

tmima_orismwn: orismos tmima_orismwn
    | ;

orismos: orismos_metavlitwn
    | orismos_synartisis
    | prwtotypo_synartisis;

orismos_metavlitwn: typos_dedomenwn lista_metavlitwn T_semic;

typos_dedomenwn: T_int
    | T_bool
    | T_string;

loop1: T_comma T_id
    | ;

lista_metavlitwn: T_id loop1;

orismos_synartisis: kefalida_synartisis tmima_orismwn tmima_entolwn;

prwtotypo_synartisis: kefalida_synartisis T_semic;

kefalida_synartisis: typos_synartisis T_id T_openpar lista_typikwn_parametrwn T_closepar
    | typos_synartisis T_id T_openpar T_closepar;

typos_synartisis: T_int
    | T_bool
    | T_void;

lista_typikwn_parametrwn: typikes_parametroi loop2;

loop2: T_comma typikes_parametroi
    | ;

typikes_parametroi: typos_dedomenwn T_ampersand T_id;

tmima_entolwn: T_begin loop3 T_end;

loop3: entoli loop3
    | ;

entoli: apli_entoli T_semic
    | domimeni_entoli
    | sintheti_entoli;

sintheti_entoli: T_semileft loop3 T_semiright;

domimeni_entoli: entoli_if;

apli_entoli: anathesi 
    | klisi_sunartisis
    | entoli_return
    | ;

entoli_if: T_if T_openpar geniki_ekfrasi T_closepar entoli else_clause 
    | T_if T_openpar geniki_ekfrasi T_closepar entoli;

else_clause: T_else entoli;

anathesi: T_id T_equals geniki_ekfrasi;

klisi_sunartisis: T_id T_openpar lista_pragmatikwn_parametrwn T_closepar 
    | T_id T_openpar T_closepar;

lista_pragmatikwn_parametrwn: pragmatiki_parametros loop4;

loop4: T_semic pragmatiki_parametros loop4
    | ;

pragmatiki_parametros: geniki_ekfrasi;

entoli_return: T_return geniki_ekfrasi 
    | T_return;

geniki_ekfrasi: genikos_oros loop5;

loop5: T_or T_or genikos_oros loop5
    | ;

genikos_oros: genikos_paragontas loop6;

loop6: T_ampersand T_ampersand loop6 
    | ;

genikos_paragontas: T_excl genikos_protos_paragontas
    | genikos_protos_paragontas;

genikos_protos_paragontas: apli_ekfrasi tmima_sigrisis
    | apli_ekfrasi;

tmima_sigrisis: T_sigkritikos_telestis apli_ekfrasi;



apli_ekfrasi: aplos_oros loop7;

loop7: T_plus aplos_oros loop7
    | T_minus aplos_oros loop7
    | ;

aplos_oros: aplos_paragontas loop8;

loop8: T_mult aplos_paragontas loop8
    | T_div aplos_paragontas loop8
    | T_percentage aplos_paragontas loop8
    | ;

aplos_paragontas: T_plus aplos_prot_oros
    | T_minus aplos_prot_oros
    | aplos_prot_oros;

aplos_prot_oros: T_id
    | stathera
    | klisi_sunartisis
    | T_openpar geniki_ekfrasi T_closepar;

stathera: T_true
    |T_false;

%%
int main(int argc, char *argv[]){
    ++argv; --argc;  //agnooume to onoma tou exe
    if (argc==1) {
        FILE *fp = fopen(argv[0],"r");
        if (fp!=NULL) {
            printf("Reading input from file: %s\n",argv[0]);
            printf("Output:\n\n");
            yyin = fp;
            yyparse();
        } else {
            printf("File doesn't exist\n");
            return 1;
        }
    } else if (argc>1) {
        printf("Only one file allowed for input...\n");
        return 1;
    } else {
        printf ("Parsing from stdin..\n");
        yyparse();
    }
    if (totalerrors==0) {
        printf("All good!\n");
        printf("===================================\n");
        printf("Parsing complete! No errors found!!\n");
    } else {
        printf("===================================\n");
        printf("Total Errors: %d\n",totalerrors);
    }
    return 0;
}

Answer 1

一个。冗余非终端

reduce/reduce冲突是因为你有两个非终结符，它们的存在只是为了聚集不同的类型：

typos_dedomenwn: T_int
    | T_bool
    | T_string;

typos_synartisis: T_int
    | T_bool
    | T_string;

在使用这些非终结符的地方，解析器不可能知道应用了哪一个；它只能在声明中进一步说明。不过，没关系。您可以只定义一个 typos 非终端，并在整个过程中使用它：

typos: T_int
    | T_bool
    | T_string;

orismos_metavlitwn: typos lista_metavlitwn T_semic;
kefalida_synartisis: typos T_id T_openpar lista_typikwn_parametrwn T_closepar
    | typos T_id T_openpar T_closepar;
typikes_parametroi: typos T_ampersand T_id;

乙。其他悬挂

shift/reduce 冲突 是"C" 样式if 语句的经典问题。这些陈述很难用明确的方式来描述。考虑：

if (expr1) if (expr2) statement1; else statement2;

我们知道else必须匹配秒if，所以上面等价于：

if (expr1) { if (expr2) statement1; else statement2; }

但语法也匹配其他可能的解析，相当于：

if (expr1) { if (expr2) statement1; } else statement2;

这个问题有三种可能的解决方案：

什么都不做。 Bison 在这里做了正确的事情，从设计上讲：它总是更喜欢 "shift" 而不是 "reduce"。这意味着如果 else 可以匹配一个开放的 if 语句，野牛将始终这样做，而不是坚持 else 来匹配一些外部 if 语句。在龙之书和其他地方对此有很好的描述。

此解决方案的问题在于，您仍然会收到有关 shift/reduce 冲突的警告，并且很难区分 "OK" 冲突和新创建的 "not OK"冲突。 Bison 提供了 %expect 声明，所以你可以告诉它你期望有多少冲突，如果找到正确的数字，这将抑制警告，但这仍然很脆弱。
使用优先声明。 这些在 bison manual. 中有描述，它们在解决悬空 else 问题中的用途是运行那一章的例子。在您的情况下，它看起来像这样：
```
%precedence T_then  /* Fake terminal, needed for %prec */
%precedence T_else
 /* ... */
%%
 /* ... */

entoli_if: T_if T_openpar geniki_ekfrasi Tw_closepar entoli T_else entoli
   | T_if T_openpar geniki_ekfrasi T_closepar entoli %prec T_then
```
在这里，我删除了不必要的非终结符 else_clause，因为它隐藏了 else 标记。如果您想保留它，无论出于何种原因，您都需要在使用它的 entoli_if 产品的末尾添加一个 %prec T_else。

%precedence 声明只能从 bison 3.0 开始使用。如果你有较早版本的 bison，你可以使用 %nonassoc 声明来代替，但这可能会隐藏一些其他错误。
修正语法。搞个无歧义的语法其实是可以的，只是有点费工夫

重点在于：
```
if (expr) statement1 else statement2
```
statement1 不能是不匹配的 if 语句。如果 statement1 是一个 if 语句，它必须包含一个 else 子句；否则，外部 if 中的 else 将匹配内部 if。这递归地适用于 statement1 中的任何尾随语句，例如
```
if (e2) statement2; 
  else if (e3) statement3
  else /* must be present */ statement;
```
我们可以通过将语句分为 "matching" 语句（其中所有 if 都与 else 匹配）和 "non-matching" 语句来表达这一点：（我没试过在这里保留希腊语非终端名称；抱歉。您必须根据您的语法调整想法）。
```
statement: matching_statement | non_matching_statement ;
matching_statement: call_statement | assignment_statement | ...
    | matching_if_statement
non_matching_statement: non_matching_if_statement
    /* might be others, see below */

if_condition: "if" '(' expression ')' ;

matching_if_statement:
      if_condition matching_statement "else" matching_statement ;
non_matching_if_statement:
      if_condition statement
    | if_condition matching_statement "else" non_matching_statement
    ; 
```
在C语言中，还有其他复合语句可以以语句(while、for)结束。其中每一个也将有一个 "matching" 和 "non-matching" 版本，具体取决于最终语句是匹配还是不匹配：
```
while_condition: "while" '(' expression ')' ;
matching_while_statement: while_condition matching_statement ;
non_matching_while_statement: while_condition non_matching_statement ;
```
据我所知，这不适用于您的语言，但您可能希望将来对其进行扩展以包含此类语句。

C。关于野牛风格的一些注意事项

Bison 允许您使用单字符标记作为它们自己，用单引号括起来。因此，与其声明 T_openpar 然后编写使用它的冗长规则，不如直接编写 '(';你甚至不需要声明它。（在您的 flex 或其他扫描器中，您只需 return '('; 而不是 return T_openpar，这就是您不需要声明标记的原因。）这通常会使语法更具可读性。
Bison 还允许您为令牌指定一个人类可读的名称。（此功能并非在所有 yacc 派生词中都有，但它很常见。），这也可以使语法更具可读性。例如，您可以为 if 和 else 标记命名，如下所示：
```
%token T_if "if"
%token T_else "else"
```
然后您可以在语法规则中使用带引号的字符串。（我在上一个悬空问题的示例中这样做了。）在 flex 扫描仪中，您仍然需要使用令牌符号 T_if 和 T_else.
如果你有一个像 && 这样的双符号标记，通常情况下扫描器识别它和 returns 单个标记通常更好，而不是解析器识别两个连续 & 个标记。在第二种情况下，解析器将识别：
```
boolean_expr1 &  & boolean_expr2
```
好像已经写好了
```
boolean_expr1 && boolean_expr2
```
虽然第一个很可能是应该报告的错误。
Bison 是一个自下而上的 LALR(1) 解析器生成器。没有必要删除左递归。自下而上的解析器 更喜欢 左递归，而左递归语法通常更准确且更易于阅读。例如，最好全面声明：
```
apli_ekfrasi: aplos_oros
    | apli_ekfrasi '+' aplos_oros
    | apli_ekfrasi '-' aplos_oros;
```
而不是使用 LL 风格的重复后缀（loop7 在你的语法中）。左递归文法可以在不扩展解析器堆栈的情况下进行解析，更准确地表示表达式的句法结构，使解析器动作更容易编写。

您的语法中还有许多其他地方可能需要重新审视。

（此建议直接来自 bison manual："you should always use left recursion, because it can parse a sequence of any number of elements with bounded stack space."）

Bison shift/reduce 冲突/reduce/reduce 冲突警告

Bison shift/reduce conflict / reduce/reduce conflict warnings

warnings

bison

shift-reduce-conflict

一个。冗余非终端

乙。其他悬挂

C。关于野牛风格的一些注意事项