转变减少冲突 [英] Shift Reduce Conflict
问题描述
我在解决班次减少语法方面的冲突时遇到了麻烦.我试图添加-v以读取问题的输出，它引导我进入状态0，并提到规则9将我的INT和FLOAT简化为variable_definitions.
I'm having trouble fixing a shift reduce conflict in my grammar. I tried to add -v to read the output of the issue and it guides me towards State 0 and mentions that my INT and FLOAT is reduced to variable_definitions by rule 9. I cannot see the conflict and I'm having trouble finding a solution.
%{
#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
;
%%
推荐答案
您对program的定义是它是变量定义列表还是函数定义列表(program: variable_definitions | function_definitions;).我觉得这有点奇怪.如果我想同时定义一个函数和一个变量怎么办?我是否必须编写两个程序并以某种方式将它们链接在一起?
Your definition of a program is that it is either a list of variable definitions or a list of function definitions (program: variable_definitions | function_definitions;). That seems a bit odd to me. What if I want to define both a function and a variable? Do I have to write two programs and somehow link them together?
这不是造成问题的原因，但是修复它也可能会解决问题.直接原因是function_definitions是一个或多个函数定义，而variable_definitions是零或多个变量定义.换句话说，function_definitions递归的基本情况是函数定义，而variable_definitions的基本情况是空序列.因此，变量定义列表以空序列开头.
This is not the cause of your problem, but fixing it would probably fix the problem as well. The immediate cause is that function_definitions is one or more function definition while variable_definitions is zero or more variable definitions. In other words, the base case of the function_definitions recursion is a function definition, while the base case of variable_definitions is the empty sequence. So a list of variable definitions starts with an empty sequence.
但是函数定义和变量定义都以type开头.因此，如果程序的第一个标记为int，则可能是返回类型为int的函数定义的开始或类型为int的变量定义的开始.在前一种情况下，解析器应移动int以产生function_definitions基本情况:在后一种情况下，应立即减少空的variable_definitions基本情况.
But both function definitions and variable definitions start with a type. So if the first token of a program is int, it could be the start of a function definition with return type int or a variable definition of type int. In the former case, the parser should shift the int in order to produce the function_definitions base case:; in the latter case, it should immediately reduce an empty variable_definitions base case.
如果您确实希望程序是函数定义或变量定义，但不能兼而有之.您需要通过将基本大小写从空更改为type identifier_list ';'来使variable_definitions具有与function_definitions相同的形式.然后，您可以在program中添加一个空的生产内容，以便解析器可以识别空的输入.
If you really wanted a program to be either function definitions or variable definitions, but not both. you would need to make variable_definitions have the same form as function_definitions, by changing the base case from empty to type identifier_list ';'. Then you could add an empty production to program so that the parser could recognize empty inputs.
但是正如我在一开始所说的，您可能希望程序是一系列定义，每个定义可以是变量或函数:
But as I said at the beginning, you probably want a program to be a sequence of definitions, each of which could either be a variable or a function:
program: %empty
| program type identifier_list ';'
| program function_head block
顺便说一句，您误读了-v生成的输出文件.它显示了针对状态0的以下操作:
By the way, you are misreading the output file produced by -v. It shows the following actions for State 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.
Here, INT and FLOAT are possible lookaheads. So the interpretation of the line INT [reduce using rule 9 (variable_definitions)] is "if the lookahead is INT, immediately reduce using production 9". Production 9 produces the empty sequence, so the reduction reduces zero tokens at the top of the parser stack into a variable_definitions. Reductions do not use the lookahead token, so after the reduction, the lookahead token is still INT.
但是，解析器实际上并没有这样做，因为它对INT具有不同的操作，即将其移动并进入状态1，如第一行开头INT所示.括号[...]表示未执行此操作，因为它是冲突，并且解决冲突是其他一些操作.因此，对该行的更准确解释是如果不是针对INT的先前操作，则超前INT将使用规则9进行归约."
However, the parser doesn't actually do that because it has a different action for INT, which is to shift it and go to state 1. as indicated by the first line start INT. The brackets [...] indicate that this action is not taken because it is a conflict and the resolution of the conflict was some other action. So the more accurate interpretation of that line is "if it weren't for the preceding action on INT, the lookahead INT would cause a reduction using rule 9."
这篇关于转变减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
