轮班减少冲突

Question

我在修复语法中的 shift reduce 冲突时遇到了问题。我尝试添加 -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;)。这对我来说似乎有点奇怪。如果我想同时定义函数和变量怎么办？我是否必须编写两个程序并以某种方式 link 将它们放在一起？

这不是您的问题的原因，但修复它可能也会解决问题。直接原因是 function_definitions 是一个或多个函数定义，而 variable_definitions 是零个或多个变量定义。换句话说，function_definitions 递归的基本情况是函数定义，而 variable_definitions 的基本情况是空序列。所以变量定义列表以空序列开始。

但是函数定义和变量定义都以type开头。因此，如果程序的第一个标记是 int，它可能是 return 类型 int 的函数定义的开始或 int 类型的变量定义。在前一种情况下，解析器应该移动 int 以产生 function_definitions 基本情况：;在后一种情况下，它应该立即减少一个空的 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)]行的解释是"if the lookahead is INT, immediately reduce using production 9"。产生式 9 产生空序列，因此归约将解析器堆栈顶部的零标记减少为 variable_definitions。归约不使用lookahead token，所以归约后lookahead token还是INT.

然而，解析器实际上并没有这样做，因为它对 INT 有不同的操作，即移动它并进入状态 1。如第一行开始 [=30= 所示].方括号 [...] 表示未执行此操作，因为它是冲突，而冲突的解决是其他操作。所以对该行更准确的解释是 "if it weren't for the preceding action on INT, the lookahead INT would cause a reduction using rule 9."

轮班减少冲突

Shift Reduce Conflict

bison

flex-lexer

yacc

lex