移位減少衝突

Question

我在修復語法中的移位減少衝突時遇到問題。我嘗試添加-v來讀取問題的輸出，它引導我進入狀態0，並提到我的INT和FLOAT被規則9簡化爲variable_definitions。我看不到衝突，並且無法找到解決方案。

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

%token INT FLOAT 
%token ADDOP MULOP INCOP 
%token WHILE IF ELSE RETURN 
%token NUM ID 
%token INCLUDE 
%token STREAMIN ENDL STREAMOUT 
%token CIN COUT 
%token NOT 
%token FLT_LITERAL INT_LITERAL STR_LITERAL 


%right ASSIGNOP 
%left AND OR 
%left RELOP 

%% 
program: variable_definitions 
     | function_definitions 
     ; 
function_definitions: function_head block 
     | function_definitions function_head block 
     ; 
identifier_list: ID 
     | ID '[' INT_LITERAL ']' 
     | identifier_list ',' ID 
     | identifier_list ',' ID '[' INT_LITERAL ']' 
     ; 
variable_definitions: 
     | variable_definitions type identifier_list ';' 
     ; 
type:   INT 
     | FLOAT 
     ; 
function_head: type ID arguments 
     ; 
arguments: '('parameter_list')' 
     ; 
parameter_list: 
     |parameters 
     ; 
parameters: type ID 
     | type ID '['']' 
     | parameters ',' type ID 
     | parameters ',' type ID '['']' 
     ; 
block:  '{'variable_definitions statements'}' 
     ; 
statements: 
     | statements statement 
     ; 
statement: expression ';' 
     | compound_statement 
     | RETURN expression ';' 
     | IF '('bool_expression')' statement ELSE statement 
     | WHILE '('bool_expression')' statement 
     | input_statement ';' 
     | output_statement ';' 
     ; 
input_statement: CIN 
     | input_statement STREAMIN variable 
     ; 
output_statement: COUT 
     | output_statement STREAMOUT expression 
     | output_statement STREAMOUT STR_LITERAL 
     | output_statement STREAMOUT ENDL 
     ; 
compound_statement: '{'statements'}' 
     ; 
variable:  ID 
     | ID '['expression']' 
     ; 
expression_list: 
     | expressions 
     ; 
expressions: expression 
     | expressions ',' expression 
     ; 
expression: variable ASSIGNOP expression 
     | variable INCOP expression 
     | simple_expression 
     ; 
simple_expression: term 
     | ADDOP term 
     | simple_expression ADDOP term 
     ; 
term:   factor 
     | term MULOP factor 
     ; 
factor:  ID 
     | ID '('expression_list')' 
     | literal 
     | '('expression')' 
     | ID '['expression']' 
     ; 
literal:  INT_LITERAL 
     | FLT_LITERAL 
     ; 
bool_expression: bool_term 
     | bool_expression OR bool_term 
     ; 
bool_term: bool_factor 
     | bool_term AND bool_factor 
     ; 
bool_factor: NOT bool_factor 
     | '('bool_expression')' 
     | simple_expression RELOP simple_expression 
     ; 
%% 

Answer 1

你一個program的定義是，它可以是一個變量定義的列表或功能定義列表（program: variable_definitions | function_definitions;）。這對我來說似乎有點奇怪。如果我想定義一個函數和一個變量呢？我是否必須編寫兩個程序並以某種方式將它們鏈接在一起？

這不是你的問題的原因，但修復它可能會解決這個問題。直接原因是function_definitions是一個或多個函數定義，而variable_definitions是零個或多個變量定義。換句話說，function_definitions遞歸的基本情況是函數定義，而variable_definitions的基本情況是空序列。所以變量定義列表以空序列開頭。

但是函數定義和變量定義都以type開頭。所以如果程序的第一個標記是int，它可能是函數定義的開始，返回類型爲int或類型爲int的變量定義。在前一種情況下，解析器應該移動int以生成function_definitions基本情況：在後一種情況下，應立即減少空的variable_definitions基本情況。

如果您確實想要一個程序既可以是函數定義也可以是變量定義，但不是兩者都可以。您需要使variable_definitions與function_definitions具有相同的格式，將基本情況從空改爲type identifier_list ';'。然後，您可以將空產品添加到program，以便解析器可以識別空輸入。

但正如我開頭所說，你可能需要一個程序是定義一個序列，每一個要麼可以是一個變量或函數：

program: %empty 
     | program type identifier_list ';' 
     | program function_head block 

---

順便說一句，你誤讀了由-v產生的輸出文件。它顯示了狀態0以下操作：

INT shift, and go to state 1 
FLOAT shift, and go to state 2 

INT  [reduce using rule 9 (variable_definitions)] 
FLOAT  [reduce using rule 9 (variable_definitions)] 

這裏，INT和FLOAT是可能向前看符號。因此，INT [reduce using rule 9 (variable_definitions)]這一行的解釋是「如果向前看是INT，立即減少使用產量9」。生產9生成空序列，所以減少將解析器堆棧頂部的零標記減少到variable_definitions。 Reduce不使用Lookahead標記，因此在縮小之後，Lookahead標記仍然爲INT。

但是，解析器實際上並沒有這樣做，因爲它對INT有不同的操作，即將它移到狀態1，如第一行開始INT所示。括號[...]表示不採取此行動，因爲這是衝突，解決衝突是其他行爲。因此，對該線更準確的解釋是「如果不是針對INT的前面的操作，則使用規則9的前瞻INT會導致減少。」