野牛轉變/減少衝突

我試圖描述野牛輸入文件的語法： 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

來源

2016-05-17 Phạm Văn Thông

這不是優先順序的工作原理。

編輯：如果發現下面的描述混淆或你不想經歷了這麼多英文文本涉水，你可以把我通常建議：不要使用優先。你幾乎總是可以寫出一個不需要優先聲明的明確語法。如果你這樣做，你不需要了解優先級。（雖然，說實話，它並不複雜，如果你瞭解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。優先級告訴解析器是否減少或移位，但是可能觸發減少或移位的令牌肯定在預見集中。

來源

2016-05-17 04:05:24 rici

感謝您的幫助。 :) –

@rici優秀的答案。 –

野牛轉變/減少衝突

回答

相關問題