野牛转变/减少冲突

Question

我试图描述野牛输入文件的语法： https://courses.engr.illinois.edu/cs421/sp2011/mps/mp2/minijavasyntax.pdf

这是我输入：

%start Program 
%token KW_CLASS KW_EXTENDS KW_PUBLIC KW_STATIC KW_BOOLEAN KW_STRING KW_FLOAT KW_INT EOF 
%token KW_IF KW_WHILE KW_BREAK KW_CONTINUE KW_SWITCH KW_CASE KW_DEFAULT KW_RETURN 
%token KW_NEW KW_THIS KW_NULL KW_TRUE KW_FALSE KW_PRINTLN 
%token IDENT INT_LITERAL FLOAT_LITERAL STRING_LITERAL 

%nonassoc "THEN" 
%nonassoc KW_ELSE 

%right "STATEMENTS" 

%right OP_ASSIGN 
%left OP_OR 
%left OP_AND 
%nonassoc CMP_EQ CMP_NEQ 
%nonassoc CMP_GT CMP_LT CMP_GTE CMP_LTE 
%left OP_ADD OP_MINUS 
%left OP_MULT OP_DIV OP_MOD 
%right OP_NOT OP_UNARY "NEW" 
%left "FUNCALL" "SUBSCRIPT" '.' 
%nonassoc '(' 
%nonassoc ')' 
%% 
Program:  ClassDeclp EOF 
      ; 

ClassDeclp:  ClassDecl 
      | ClassDeclp ClassDecl 
      ; 
ClassDecl:  KW_CLASS IDENT ExtendsFrom 
      '{' VarDecls MethodDecls '}' 
      ; 
ExtendsFrom:  /*empty*/ 
       | KW_EXTENDS IDENT 
      ; 

VarDecls:  /*empty*/ 
      | VarDecls VarDecl 
      ; 
VarDecl:  Type IDENT ';' 
      | KW_STATIC Type IDENT ';' /*Co the sua thanh AcessModifier Type IDENT*/ 
      ; 

MethodDecls:  /*empty*/ 
      | MethodDecls MethodDecl 
      ; 
MethodDecl:  KW_PUBLIC Type IDENT 
      '('MethodParams')' 
      '{'VarDecls Statements KW_RETURN Expression ';' '}' 
      ; 

MethodParams:  /*empty*/ 
      | MethodParams ',' MethodParam 
      ;  
MethodParam:  Type IDENT; 

Type :   Type '['']' 
       | KW_BOOLEAN 
      | KW_STRING 
      | KW_FLOAT 
      | KW_INT 
      | IDENT 
      ; 
Statements:  Statements Statement %prec "STATEMENTS" 
      | /*empty*/ %prec "STATEMENT" 
      ; 
Statementp:  Statements Statement %prec "STATEMENTS" 
      ; 
Statement:  '{'Statements'}' 
      | KW_IF '(' Expression ')' Statement %prec "THEN" 
      | KW_IF '(' Expression ')' Statement KW_ELSE Statement 
      | KW_WHILE '(' Expression ')'Statement 
      | KW_PRINTLN '(' Expression ')' ';' 
      | IDENT OP_ASSIGN Expression ';' 
      | KW_BREAK ';' 
      | KW_CONTINUE ';' 
      | IDENT %prec "SUBSCRIPT" '['Expression']' '=' Expression ';' 
      | KW_SWITCH '(' Expression ')' '{' 
       Cases 
       KW_DEFAULT ':' Statementp '}' 
      ; 

Cases:   Cases Case 
      | /*empty*/ 
      ; 
Case:   KW_CASE INT_LITERAL ':' Statementp 
      ; 


Expression:  Expression OP_OR Expression 
      | Expression OP_AND Expression 
      | Expression CMP_EQ Expression 
      | Expression CMP_NEQ Expression 
      | Expression CMP_GT Expression 
      | Expression CMP_GTE Expression 
      | Expression CMP_LT Expression 
      | Expression CMP_LTE Expression 
      | Expression OP_ADD Expression 
      | Expression OP_MINUS Expression 
      | Expression OP_MULT Expression 
      | Expression OP_DIV Expression 
      | Expression OP_MOD Expression 
      | '-' Expression %prec OP_UNARY 
      | OP_NOT Expression 
      | Expression %prec "SUBSCRIPT" '['Expression']' 
      | Expression '.'"length" 
      | Expression '.' IDENT %prec "FUNCALL" '(' ParamList ')' 
      | INT_LITERAL 
      | FLOAT_LITERAL 
      | STRING_LITERAL 
      | KW_NULL 
      | KW_TRUE 
      | KW_FALSE 
      | IDENT 
      | KW_THIS 
      | KW_NEW Type '[' Expression ']' %prec "NEW" 
      | KW_NEW IDENT '('')'  %prec "NEW" 
      | '(' Expression ')' 
      ; 


ParamList:  /*empty*/ 
      | ParamList ',' Expression 
      | Expression 
      ; 
%% 
main(int argc, char** argv[]) 
{ 
    extern FILE *yyin; 
    ++argv; --argc; 
    yyin = fopen(argv[0], "r"); 
    yydebug = 1; 
    errors = 0; 
    yyparse(); 
} 

yyerror(char *s) 
{ 
    printf("%s\n", s); 
} 

/* Co 3 conflict RR can xu ly khi bien thuoc kieu bool 
    giua BoolExpr va Expresstion */ 

我有两个16时发生冲突编译。 一个矛盾，我跑野牛与--report =前瞻：

OP_NOT Expression . [OP_OR, OP_AND, CMP_EQ, CMP_NEQ, CMP_GT, CMP_LT, CMP_GTE, CMP_LTE, OP_ADD, OP_MINUS, OP_MULT, OP_DIV, OP_MOD, ')', ';', ',', '[', ']']

我的预期是什么“[”不是OP_NOT超前记号，因为SUBSCRIPT优先级比要高操作！ 其他冲突是这样的。我该如何解决它。 Tks

Answer 1

这不是优先顺序的工作原理。

编辑：如果发现下面的描述混淆或你不想经历了这么多英文文本涉水，你可以把我通常建议：不要使用优先。你几乎总是可以写出一个不需要优先声明的明确语法。如果你这样做，你不需要了解优先级。 （虽然，说实话，它并不复杂，如果你了解LR分析工作。）/EDIT

优先级总是比较一个可能减少（即生产，其rightt手侧电流的顶级赛事解析器堆栈）和lookahead符号。

在点：

Expression : Expression · '[' Expression ']' 

唯一可能的动作分析器是移位，因为当点是在右手侧的端部只能发生的降低。

然而，在该点发生状态中的一种，还有另一种生产：

Expression : OP_NOT Expression · 

这一个可以被减小，因为点是在末端。

由于这两个点都处于相同的状态，它们必须都是有效的。这意味着我们正在寻找：

OP_NOT Expression · '[' Expression ']' 

而我们正试图弄清楚该怎么做。我们可以减少OP_NOT Expression到Expression，在这一点上，我们将有：

Expression · '[' Expression ']' 

，或者我们可以转变的“[”，留给我们

OP_NOT Expression '[' · Expression ']' 

因为这两个都是可能的，有是转换/减少冲突。 Yacc/Bison将尝试使用优先规则来解决冲突（如果存在的话）。特别是，它需要比较生产这可能会减少的优先级：

Expression : OP_NOT Expression 

和符号可能被转移：'['。

但是，彻底查看优先声明表明没有优先级分配给'['。所以，如果你想后缀下标运算符（[表达YACC /野牛无法测试其对生产（其优先级由在右侧，OP_NOT最后的终端定义，因为没有%prec声明。

“ ]'）具有比前缀运营商OP_NOT更高的优先级，你必须声明为优先[比OP_NOT更高。

顺便说一句，我没有看到这里的矛盾点。你可以有对于OP_NOT使用!（对于OP_MINUS等，使用-等），这将更容易阅读且更少工作。

你似乎认为，%prec申报

Expression %prec "SUBSCRIPT" '['Expression']' 

是相关的。不是这样。它只适用于解析器可能会减少Expression '[' Expression ']'。但它也没有意义，因为你不需要建立一个假终端来保持生产的优先顺序;它的优先级由右侧的最后一个终端']'定义，因此您可以只声明该终端的优先级。

在声明Expression : OP_MINUS Expression %prec OP_UNARY假令牌需要的，因为'-'具有两个不同的优先级，或者更准确，因为OP_MINUS Expression具有不同的优先级从Expresson OP_MINUS Expression。不过，你实际上并不需要发明一个虚假的代币。您可以使用具有正确优先级的任何标记，例如OP_NOT或OP_NEW。

如果没有足够的单词，我试图在几个不同的SO答案中解释这一点。 Here's one和here's another one和here's another one。另外，here's one by Chris Dodd和这里的文档the bison manual。如果你幸运的话，你可能会用你自己的语言找到一个描述，使用任何最适合你的互联网搜索引擎，或者如果你有教授，与你的教授交谈。

顺便提一下，超前报告告诉你哪些符号可能跟随给定的生产。优先级对此没有影响。 [绝对可以遵循!a。优先级告诉解析器是否减少或移位，但是可能触发减少或移位的令牌肯定在预见集中。