searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

移进规约冲突

2024-09-05 09:26:39
4
0
为了避免 Bison 发出有关可预测的、合法的移位/归约冲突的警告,可以使用 %expect n 声明。但不建议
如何解决移进规约冲突?比如下面的文法就有冲突:
 
expr: expr - expr | expr * expr | - expr
 
对于输入:-1 * 2
解析完1后,可以继续移进 * ,或者根据规则 expr:-expr 规约为 -1。也就是说,解析方式有两种:
 
-1 * 2 = (-1)*2 或者 -1 * 2 =- (1*2)
 
虽然结果一样,但是程序不知道该选择哪种方式。
之所以冲突,是因为移进和 归约的优先级没有确定,即符号 * 和规则 expr: -expr 的优先级没有确定,出现了 * 就不知道该移进 * 还是利用规则来归约了。
那么只要定义了它们的优先级,就可以解决冲突了。怎么定义呢?
(其实规则有默认的优先级,为该规则中最后一个符号的优先级,比如 IF expr THEN stmt 的优先级就是THEN的优先级)
  1. 使用%prec定义规则对应的符号(即定义此规则和哪个符号的优先级相同)。
  2. 使用%left/%right/%noassoc/%precedence来定义符号的优先级和结合性(分别是左结合、右结合、没有结合性、未定义的结合性)。
所以需要先定义规则对应的虚拟符号,再定义这个虚拟符号和 * 的优先级关系,这样就定义了此规则和 * 的优先级了。
于是定义符号的优先级。这里UMINUS在 * 的下方,表示优先级比 * 更高:
 
// 优先级从下往上递减 %left - %left * %left UMINUS
 
当然了,这里的UMINUS只是一个虚拟符号,所以结合性无所谓,就用%left来定义吧(或者用%noassoc来定义)。
再定义规则对应的符号:
 
expr: expr - expr | expr * expr | - expr %prec UMINUS
 
这样,UMINUS的优先级比 * 高了,就表示规则 expr:-expr 的优先级比 * 高了。这样移进/规约冲突就解决了。
0条评论
作者已关闭评论
zzzzgj
9文章数
1粉丝数
zzzzgj
9 文章 | 1 粉丝
原创

移进规约冲突

2024-09-05 09:26:39
4
0
为了避免 Bison 发出有关可预测的、合法的移位/归约冲突的警告,可以使用 %expect n 声明。但不建议
如何解决移进规约冲突?比如下面的文法就有冲突:
 
expr: expr - expr | expr * expr | - expr
 
对于输入:-1 * 2
解析完1后,可以继续移进 * ,或者根据规则 expr:-expr 规约为 -1。也就是说,解析方式有两种:
 
-1 * 2 = (-1)*2 或者 -1 * 2 =- (1*2)
 
虽然结果一样,但是程序不知道该选择哪种方式。
之所以冲突,是因为移进和 归约的优先级没有确定,即符号 * 和规则 expr: -expr 的优先级没有确定,出现了 * 就不知道该移进 * 还是利用规则来归约了。
那么只要定义了它们的优先级,就可以解决冲突了。怎么定义呢?
(其实规则有默认的优先级,为该规则中最后一个符号的优先级,比如 IF expr THEN stmt 的优先级就是THEN的优先级)
  1. 使用%prec定义规则对应的符号(即定义此规则和哪个符号的优先级相同)。
  2. 使用%left/%right/%noassoc/%precedence来定义符号的优先级和结合性(分别是左结合、右结合、没有结合性、未定义的结合性)。
所以需要先定义规则对应的虚拟符号,再定义这个虚拟符号和 * 的优先级关系,这样就定义了此规则和 * 的优先级了。
于是定义符号的优先级。这里UMINUS在 * 的下方,表示优先级比 * 更高:
 
// 优先级从下往上递减 %left - %left * %left UMINUS
 
当然了,这里的UMINUS只是一个虚拟符号,所以结合性无所谓,就用%left来定义吧(或者用%noassoc来定义)。
再定义规则对应的符号:
 
expr: expr - expr | expr * expr | - expr %prec UMINUS
 
这样,UMINUS的优先级比 * 高了,就表示规则 expr:-expr 的优先级比 * 高了。这样移进/规约冲突就解决了。
文章来自个人专栏
zzz
9 文章 | 1 订阅
0条评论
作者已关闭评论
作者已关闭评论
0
0