Bison遇到冲突的默认行为用户自定义优先级

news/2024/10/14 14:17:17

Bison遇到冲突的默认行为&用户自定义优先级

在使用 Bison 进行语法分析时，如果在语法规则中存在冲突，Bison 会根据默认的优先级和结合性规则进行决策，选择某个特定的行为来解决冲突。Bison 中常见的冲突主要包括两类：

Bison 对这些冲突的处理有一定的优先策略。以下是详细解释：

移入-规约冲突 是最常见的冲突之一。它发生在某个时刻，语法分析器既可以选择移入（读取更多输入符号），也可以选择规约（使用当前符号规约为某个非终结符）。例如：

stmt: expr ';'| expr '+' expr ';';

在这种情况下，当看到 expr 后，有可能既可以选择规约为 stmt，也可以选择移入以继续处理 + 符号并形成 expr '+' expr 的结构。这就导致了移入-规约冲突。

默认行为：Bison 会优先选择移入（shift），而不是规约（reduce）。Bison 默认认为继续读取输入符号可能会得到更多信息，避免过早规约导致后续无法正确处理输入。

这个策略通常会产生正确的行为，尤其是在像表达式解析这种场景下，移入操作能够捕获更多的输入，并正确地生成更大的表达式。

规约-规约冲突 发生在解析器可以根据多条规则规约当前的符号。也就是说，两个或多个规则都可以适用于当前的输入，但 Bison 无法确定使用哪个规则来规约。

示例：

stmt: expr ';'| var_decl ';';var_decl: TYPE ID;expr: ID;

在这种情况下，如果解析器看到 ID 后，不确定是否要将其规约为 expr 还是 var_decl，则会产生规约-规约冲突。

默认行为：对于规约-规约冲突，Bison 会根据文法的书写顺序来选择使用最早声明的规则进行规约。也就是说，如果两个规约规则产生冲突，Bison 将选择在定义中出现顺序靠前的那个规则。

Bison 提供了一种机制，通过定义运算符的优先级和结合性来解决移入-规约冲突。这通常用于消除表达式解析中的冲突问题。

优先级（precedence）：优先级用于决定两个运算符的顺序问题。如果有两条规则冲突，Bison 会根据优先级来决定是先移入还是先规约。高优先级的运算符会优先执行。
结合性（associativity）：结合性用于处理多个同级运算符的顺序问题。结合性可以是：
- 左结合（left-associative）：从左往右结合，比如 a - b - c 应该解析为 (a - b) - c。
- 右结合（right-associative）：从右往左结合，比如 a = b = c 应该解析为 a = (b = c)。
- 非结合（non-associative）：如果两个同级运算符不能连用，则称为非结合。

定义优先级和结合性示例：

%left '+' '-'
%left '*' '/'
%right '^'    // 右结合的运算符
%nonassoc '<' '>'  // 非结合的运算符

通过这种方式，Bison 会根据优先级和结合性来确定如何处理移入-规约冲突，从而生成正确的解析结果。

Bison 在处理语法规则冲突时，采用以下默认的优先行为：

移入-规约冲突：Bison 默认会选择移入操作（shift），而不是规约。如果定义了运算符的优先级和结合性，Bison 会根据这些信息决定是移入还是规约。
规约-规约冲突：Bison 会选择最早定义的规则进行规约。
优先级和结合性：可以通过 %left、%right 和 %nonassoc 定义运算符的优先级和结合性，进一步控制冲突的处理方式。
自定义优先级：通过%left、%right等语法定义的优先级，写在越后面，优先级越高。