Shift Reduce Conflict

Question

私は文法の中でshift reduceの競合を解決できません。私は問題の出力を読むために-vを追加しようとしましたが、それはState 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;）のリストのいずれかであるということです。それは私にとって少し奇妙なようです。関数と変数の両方を定義したいのですが？私は2つのプログラムを書いて、何らかの形でそれらをリンクしなければなりませんか？

これは問題の原因ではありませんが、それを修正すると問題が解決する可能性があります。直接の原因はfunction_definitionsが1つ以上の関数定義であり、variable_definitionsが0以上の変数定義であることです。換言すれば、function_definitionsの再帰の基底は関数定義であり、基底の場合はvariable_definitionsは空のシーケンスである。したがって、変数定義のリストは空のシーケンスから始まります。

しかし、関数定義と変数定義の両方はtypeで始まります。したがって、プログラムの最初のトークンがintの場合は、戻り型がintの関数定義の開始、またはタイプがintの変数定義の開始になります。前者の場合、パーサーはfunction_definitionsベースケースを生成するためにintをシフトする必要があります。後者の場合は、すぐに空のvariable_definitionsベースケースを減らす必要があります。

プログラムが関数定義か変数定義のどちらかになりたいのであれば、ベースケースを空からtype identifier_list ';'に変更して、variable_definitionsをfunction_definitionsと同じ形式にする必要があります。次に空のプロダクションを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になります。削減額は先読みトークンを使用しないため、引き落とし後の先読みトークンはまだINTです。

しかし、INTのアクションが異なるためパーサは実際には実行しません。これは、最初の行の開始INTに示すように、シフトして状態1になります。角括弧[...]は、競合であり、競合の解決が何らかの他のアクションであったため、このアクションがとられていないことを示しています。したがって、その行のより正確な解釈は、 "先行するアクションのためにINTでなかった場合、先読みINTはルール9を使用して削減を引き起こします。