2

当我在 Ubuntu Linux 中运行此野牛代码时，我收到以下警告：

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

这是一个更清晰的屏幕截图：http: //i.imgur.com/iznzSsn.png

编辑：减少/减少错误在

line 86 : typos_dedomenwn
line 101: typos_synartisis

并且移位/减少错误在：

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;
}
4

1 回答 1

8

A. 冗余非终端

减少/减少冲突是因为您有两个非终端，它们的存在只是为了收集不同的类型：

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;

B. 悬空其他

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;

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

  1. 没做什么。Bison 在这里做了正确的事情，通过设计：它总是更喜欢“shift”而不是“reduce”。这意味着如果 anelse可以匹配一个开放if语句，bison 将始终这样做，而不是坚持else匹配某个外部if语句。在《龙之书》以及其他地方，对此有很好的描述。

    此解决方案的问题在于，您最终仍会收到有关移位/减少冲突的警告，并且很难区分“OK”冲突和新创建的“not OK”冲突。Bison 提供了%expect声明，因此您可以告诉它您期望有多少冲突，如果找到正确的数字，它将抑制警告，但这仍然非常脆弱。

  2. 使用优先声明。这些在野牛手册中有描述。并且它们在解决悬空 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令牌。如果您想保留它，无论出于何种原因，您都需要在使用它%prec T_else的产品末尾添加一个。entoli_if

    该%precedence声明仅适用于 bison 3.0 及更高版本。如果您有较早版本的 bison，则可以改用该%nonassoc声明，但这可能会隐藏一些其他错误。

  3. 修正语法。实际上可以制作一个明确的语法，但这有点工作。

    重要的一点是：

    if (expr) statement1 else statement2

    statement1不能是无与伦比的if陈述。ifstatement1是一个if语句，它必须包含一个else子句；否则，else外部的 inif将匹配内部的if。这递归地适用于 中的任何尾随语句statement1，例如

    if (e2) statement2; 
  else if (e3) statement3
  else /* must be present */ statement;

    我们可以通过将语句分为“匹配”语句（所有if都由 匹配else）和“不匹配”语句来表达这一点：（我没有尝试在这里保留希腊非终端名称；抱歉。你必须使想法适应您的语法）。

    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) 结尾的复合语句。其中每一个也将有一个“匹配”和“不匹配”版本，具体取决于最终语句是匹配还是不匹配：

    while_condition: "while" '(' expression ')' ;
matching_while_statement: while_condition matching_statement ;
non_matching_while_statement: while_condition non_matching_statement ;

    据我所知，这不适用于您的语言，但您可能希望将来扩展它以包含此类语句。

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

  1. Bison 允许您使用单字符标记作为它们本身，并用单引号括起来。因此，与其声明T_openpar然后编写使用它的详细规则，不如编写'('; 你甚至不需要声明它。（在您的 flex - 或其他 - 扫描仪中，您只需要return '(';代替return T_openpar，这就是您不需要声明令牌的原因。）这通常会使语法更具可读性。

  2. Bison 还允许您为令牌指定一个人类可读的名称。（此功能并非在所有yacc派生中，但很常见。），这也可以使语法更具可读性。例如，您可以为if和else标记命名，如下所示：

    %token T_if "if"
%token T_else "else"

    然后您可以在语法规则中使用带引号的字符串。（我在上一个示例中针对 dangling-else 问题这样做了。）在 flex 扫描仪中，您仍然需要使用标记符号T_if和T_else.

  3. 如果您有两个符号的标记，例如&&，扫描器识别它并返回单个标记通常会更好，而不是解析器识别两个连续的&标记。在第二种情况下，解析器将识别：

    boolean_expr1 &  & boolean_expr2

    好像它已经写好了

    boolean_expr1 && boolean_expr2

    尽管第一个很可能是应该报告的错误。

  4. Bison 是一个自底向上的 LALR(1) 解析器生成器。没有必要删除左递归。自下而上的解析器更喜欢左递归，左递归语法通常更准确，更容易阅读。例如，最好全面声明：

    apli_ekfrasi: aplos_oros
    | apli_ekfrasi '+' aplos_oros
    | apli_ekfrasi '-' aplos_oros;

    而不是使用 LL 样式的重复后缀（loop7在您的语法中）。左递归语法可以在不扩展解析器堆栈的情况下进行解析，更准确地表示表达式的句法结构，使解析器动作更容易编写。

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

    （这个建议直接来自野牛手册：“你应该总是使用左递归，因为它可以解析具有有限堆栈空间的任意数量元素的序列。”）

于 2015-09-28T15:32:15.170 回答