在YACC中移位減少衝突

Question

我嘗試了下面的yacc碼和m接收移位/減少錯誤。我敢新的這

The Purpose of the code is to prepare the syntax for if - else with logical operators also incorporated

  %{ 
       #include<stdio.h> 
       #include"lex.yy.c" 
       int syntax_status=0; 
      %} 
      %token IF ELS id EE LE GE closep openp num openb closeb SP logicop 
      %start S 
      %% 
      S : S SP IF SP openp SP EXP SP closep SP openb SP closeb SP ELS SP openb SP closeb SP {syntax_status=1;} 
      | S SP IF SP openp SP EXP SP closep SP openb SP closeb SP {syntax_status = 1;} 
      | 
      ; 
     EXP : EXP CMP logicop CMP 
      | EXP CMP 
      | 
      ; 
     CMP : CMP id EE id 
      | CMP id LE id 
      | CMP id GE id 
      | CMP id EE num 
      | CMP id GE num 
      | CMP id LE num 
      | CMP num EE id 
      | CMP num GE id 
      | CMP num LE id 
      | 
      ; 
     %% 
     int main() 
     { 
       printf("\n\n\n Enter the Syntax : "); 
       yyparse(); 
       if(syntax_status==1) 
       { 
        printf("\n\n\n The Syntax is Correct "); 
       } 
       else 
       { 
        printf("\n\n\n The Syntax is Imcorrect"); 
       } 
       return 0; 
      } 
      yyerror(char *s) 
      { 
       syntax_status=0; 
      } 

lex程序此相應的yacc代碼如下：

  %{ 
       #include<stdio.h> 
       #include"y.tab.h" 
      %} 
      IF (if) 
      ELS (else) 
      iden [a-zA-Z][a-zA-Z0-9]* 
      num [0-9]+ 
      space [ ]* 
      %% 
      {IF} { return IF; } 
      {ELS} {return ELSE;} 
      {iden} {return id;} 
      (==) {return EE;} 
      (<=) { return LE;} 
      (>=) { return GE;} 
      ")" { return closep;} 
      "(" { return openp;} 
      {num} { return num;} 
      {space} { return SP; } 
      "{" { return openb;} 
      "}" { return closeb;} 
      "||"|"&&"|"!=" {return logicop;} 

%%

Answer 1

的CMP和EXP規則都顯得很成問題。例如：

EXP ==> (by EXP -> CMP) 
EXP CMP ==> (by CMP -> CMP id EE id) 
EXP CMP id EE id ==> (by CMP -> CMP id EE id) 
EXP CMP id EE id id EE id ==> (by CMP -> epsilon) 
EXP id EE id id EE id ==> (by EXP -> epsilon) 
id EE id id EE id ==> 
id == id id == id 

我很確定這不是你想要的。它還引入了歧義到語法：終端的相同的字符串可以通過此不同的最右推導得出：

EXP ==> (by EXP -> CMP) 
EXP CMP ==> (by CMP -> CMP id EE id) 
EXP CMP id EE id ==> (by CMP -> epsilon) 
EXP id EE id ==> (by EXP -> CMP) 
EXP CMP id EE id ==> (by CMP -> CMP id EE id) 
EXP CMP id EE id id EE id ==> (by CMP -> epsilon) 
EXP id EE id id EE id ==> (by EXP-> epsilon) 
id EE id id EE id ==> 
id == id id == id 

你看，YACC就沒有辦法知道，如果id == id id == id真的exp exp或exp。另外，exp-> epsilon規則允許表達式如if(){}，這不是很好。

現在，考慮下面的語法：

exp -> exp logicop cmp | cmp 
cmp -> rvalue < rvalue | rvalue > rvalue ... 
rvalue -> id | num 

但它也可以這樣做：

exp -> exp op exp | rvalue 
op -> "||" | "&&" | "<" | ">" ... 

後者是這樣做的傳統方式，但是你需要語義檢查以確保操作數是正確的類型，而前面的語法確保在句法層面。從長遠來看（一旦引入了布爾變量），第二種方法更可取，因爲類型安全性是語義問題，而不是語法。

另一個說明：空格在您的語言中似乎不相關，但lex將它們交給yacc。你可以讓法丟棄在詞彙層面的空間說

{space} //nothing after a pattern discards the matched characters 

這會節省你的yacc寫出所有這些SP的頭痛。

Answer 2

你需要指定您的運營商的優先級和關聯性：請參閱例如。我從教派引用。 6

作爲這些聲明的行爲的一個例子，

%right '=' 
    %left '+' '-' 
    %left '*' '/' 

    %% 

    expr :  expr '=' expr 
      |  expr '+' expr 
      |  expr '-' expr 
      |  expr '*' expr 
      |  expr '/' expr 
      |  NAME 
      ; 

可以用於結構中的輸入

a = b = c*d - e - f*g 

如下的描述：

a = (b = (((c*d)-e) - (f*g))) 

您的CMP運營商必須以類似的方式定義，並且您的logicop應該分開。爲了在布爾表達式中獲得通常的讀數，通常NOT不像一元減法，AND就像*，或者像+一樣。

HTH