为什么这段yacc代码会生成shift/reduce冲突

在编译原理中，语法分析器（Parser）是将输入的代码序列转换为抽象语法树（AST）的重要组件。而Yacc是一种生成语法分析器的工具，通过定义产生式规则和语法规则，可以自动生成用于语法分析的LALR(1)分析器。

Shift/reduce冲突是指在语法规则中存在一个产生式可以进行移进（Shift）操作，也可以进行归约（Reduce）操作，从而导致分析器无法确定下一步应该选择移进还是归约。这种冲突的产生可能会导致语法分析器无法正确解析输入的代码。

通常，产生Shift/reduce冲突的原因有以下几种情况：

模棱两可的语法规则：在语法规则中存在模棱两可的产生式，导致分析器无法确定应该采取哪种操作。
同级运算符的优先级问题：当存在多个同级运算符时，可能会发生优先级冲突，导致分析器无法确定应该采取移进还是归约操作。
归约-归约冲突：当存在多个产生式可以进行归约操作时，可能会导致分析器无法确定应该使用哪个产生式进行归约。

要解决Shift/reduce冲突，可以采取以下几种方法：

修改语法规则：通过修改语法规则，消除产生冲突的情况，使得分析器能够正确进行移进或归约操作。
指定运算符优先级：通过指定运算符的优先级和结合性，可以告诉分析器在遇到同级运算符时应该如何进行操作。
使用语义动作：在语法规则中添加语义动作，通过在归约过程中进行特定的操作，来消除冲突或指导分析器的决策。

总之，要解决Shift/reduce冲突，需要对语法规则和产生式进行仔细分析，并采取相应的方法来消除冲突，以确保语法分析器能够正确解析输入的代码。

关于Yacc在腾讯云的相关产品和产品介绍，可以参考腾讯云提供的云开发服务（Serverless Cloud Function）：https://cloud.tencent.com/product/scf

相关·内容

为什么这段代码会阻塞？

01、故事开始的地方——这段代码为什么会阻塞？...content log.Infof("audit in after content = %s", strconv.Itoa(content.i)) } } } 让我们来拆解一下这段代码的大致逻辑...这段代码开启了一个 goroutine，这个goroutine会向 in 通道中放入2000个 Content 对象，每个对象的 i 字段从0到1999。每放入一个对象都会记录日志。...主循环在接收到审核失败信号后，会等待一段时间，然后继续处理后续数据。你看出来这段代码为什么会阻塞了吗？...到这里，代码阻塞的原因已经全部提到了，我们来结合代码讲一讲： 1.

2742 1

借助yacc和lex自制计算器——《自制编程语言》一

1.3 yacc： yacc是自动生成语法分析器的工具，输入扩展名为.y的文件，就会输出语法分析器的C语言代码。...解析流程对照语法规则代码 2-0跟踪下解析1 + 2 * 3的执行流程首先，yacc生成的解析器会保存在程序内部的栈。...称为移进/归约冲突即便发生冲突，yacc仍会生成解析器。如果存在归约/归约冲突，则优先匹配前面的语法规则，移进/归约冲突则会优先匹配移进规则。 ...1 shift/reduce // 冲突信息（见下文） State 14 conflicts: 1 shift/reduce State 15 conflicts: 1 shift/reduce Grammar...所以只放这段代码。 3 结束以上结束了一个mycalc计算器的代码流程，编译完之后确实有一个终端计算器。但是实际上代码都是原书提供的，跟着思路走了一遍。

4.6K1 0

Postgresql中yacc语法树冲突解决方法（shiftreduce conflicts）

-Wcounterexamples （如果命令不支持counterexamples请更新bison：https://ftp.gnu.org/gnu/bison/）结果：可以看出这是一个reduce.../recude冲突，位置也给出了。...二、冲突信息输出到文件： bison --report="cex" -d -o gram.c gram.y 会在当前目录下生成gram.output文件。...在文件中搜索conflict on token即可： yacc的两种冲突 reduce/reduce冲突：两条规则都可以规约当前token 实例：VARCHAR改规约哪个？发生冲突。...shift/reduce冲突：两条规则既可以移进也可以规约token 实例：VARCHAR向右移进还是向上规约？发生冲突。

2.1K3 0

bison解析中lookahead前瞻工作原理

https://www.gnu.org/software/bison/manual/bison.html#Algorithm 1 lookahead token 学习yacc后一直有一个疑问，reduce...bison解析器在发现一次匹配后，会继续向前看一个lookahead，再决定做什么。...上面的步骤2并不是匹配上的都能reduce，lookahead token会影响一些规则，使其延迟reduce。 1.1 lookahead token案例分析这是一个有相互依赖关系的语法树。...选择2：lookahead继续shift入栈，按规则2规约。现在发生了shift/reduce冲突。Bison会通过选择shift来解决这些冲突（除非运算符优先级声明）。...3.1 悬挂冲突为了解其中的原因，下面与其他选择进行对比：正例：如果bison更偏向于shift “else”，下面语句1就等价与语句2，符合预期。

1.5K7 0

【Python】Ply 简介

(start="foo") 移入/规约上面给出的语法规则是经过规约的规则，对解析器来说，它更容易处理，因为它几乎不存在歧义，但从编程的角度来说，我们可能会以一种更符合人类直觉的方式定义语法规则，就像下面这样...当出现这种冲突时，yacc 会打印一下警告信息： WARNING: 1 reduce/reduce conflict WARNING: reduce/reduce conflict in state 15...resolved using rule (assignment -> ID EQUALS NUMBER) WARNING: rejected rule (expression -> NUMBER) 上面的信息会告诉你发生了什么冲突...，但并不会告诉你冲突是如何发生的，要了解语法分析的详细流程，你肯呢个需要阅读 parser.out 文件，该文件在语法分析器第一次运行时被生成，描述了语法分析的详细流程,文件内容其实很容易理解，你需要注意下面三点...标注出了冲突的地方，虽然这些冲突不见得都是不好的。

2.7K3 0

Postgresql源码（50）语法解析时关键字判定原理（函数名不能使用的关键字为例）

lex返回522后，yacc语法树没有匹配项了，返回错误。 [lex] NORMALIZE = 522 [yacc] if (!...所有的关键字都在gram.y文件中使用%token表示了，这些关键字应该都不能用于表名、列名等对象名等，可能会造成shift/reduce冲突。...但其实很多也不会触发冲突，为了使用这些关键字，在gram.y文件后面专门定义了几组语法规则： unreserved_keyword：可以用于任意命名场景，如果新增的关键字不会引发shift/reduce...冲突，可以放在这个列表中。...增加方法：先确定新增关键字会不会造成语法冲突歧义等，加到上面5个list中，然后根据能否用于表名、列名、as等场景，在kwlist中增加即可。

7913 0

gcc语法解析如何解决dangling else的问题？

GCC上古版本（3.4）还有yacc，学习GCC如何实现if else 嵌套的问题。...解决关键点：将simple_if非终结符的优先级降低到if，当出现else simple_if时，让simple_if去reduce。...解决关键点：else的优先级比if要高，当else if出现时，发生shift/reduce冲突，根据优先级if会选择reduce。...《使用优先级解决shift/reduce冲突的经典例子（%prec UMINUS）》手册中相关部分 https://www.gnu.org/software/bison/manual/bison.html...#Shift_002fReduce

2176 0

javacc功能一览

javacc特征 •JavaCC生成自上而下的（递归下降[1]）解析器，而不是类似YACC[2]的工具生成的自下而上的解析器。尽管不允许左递归[3]，这允许使用更通用的语法。...•默认情况下，JavaCC生成一个LL(1)解析器。但是，可能有一部分语法不是LL(1)。JavaCC提供了语法和语义超前功能，可以在这些点上本地解决shift-shift歧义。...对于自上而下的解析器而言，Shift-reduce和reduce-reduce冲突不是问题。...> false 第三步，执行命令，生成代码...mvn javacc:javacc 命令执行后会在generated-sources目录下生成对应的java代码，在idea上将代码根目录设置为source目录即可正常加载。

2K1 0

三十分钟成为 Contributor | 提升 TiDB Parser 对 MySQL 8.0 语法的兼容性

TiDB 通过 AST 树生成执行计划，修改 AST 节点可能会影响 TiDB 的行为，因此应尽量保持原有结构，不改变原有的属性，如果确实有修改 AST 树必要，我们会帮助 Contributor 检查...goyacc 所生成的 parser 采用了 LALR(1) 方法进行解析，冲突有两类：一类是两条规则都能被用于归约，称为 reduce-reduce 冲突。...另一类是既能使用一条规则归约，又能按照另一条规则移进下一个 token，称为 shift-reduce 冲突。...可以通过指定优先级的方式消除冲突，具体可以参考 yacc 的 %precedence 和 %prec 指示。...经过比较和分析，我们发现第一个方案会引入新的数据结构，有较大的概率会引起现有的 TiDB 测试不过，为此可能要修改 TiDB 方面的代码，工作量大的同时提高了 parser 的复杂度，因此作为备选方案；

1.3K2 0

Postgresql源码（44）server端语法解析流程分析

5、从语法树底层节点向上reduce，识别收集文本中的目标信息，创建对应的stmt结构体，填入数据，返回上层。...（2）如果有预读的token就直接用了，不再重新解析（3）如果没有预读的token，调core_yylex从lex拿一个token出来，如果是普通token直接返回yacc继续reduce （4）...427 258 708 258 524 588 SELECT * FROM IDENT WHERE IDENT NOT LIKE 3、从524（NOT）开始，会进入函数的...，可以理解为lex的抽象 3、gram.y生成gram.c在shift/reduce语法树的过程中，调用base_yylex获取token 4、base_yylex的第三个参数就是初始化的scanner...这两个变量指明了lex生成的词法分析器从哪里获得输入和输出到哪里。

5665 0

TiDB SQL Parser 的实现

词法分析器读取源代码，根据patterns将源代码转换成tokens输出。Yacc根据用户定义的语法规则生成语法分析器。语法分析器以词法分析器输出的tokens作为输入，根据语法规则创建出语法树。...Yacc 生成的语法分析器使用自底向上的归约（shift-reduce）方式进行语法解析，同时使用堆栈保存中间状态。...对这个语法树进行遍历访问，可以生成机器代码，也可以解释执行。至此，我们大致了解了Lex & Yacc的原理。...从 parser.y 的注释看到，这个文件最初是用工具从 BNF 转化生成的，从头手写这个规则文件，工作量会非常大。...这段代码的运行结果如下，依次输出遍历过程中遇到的节点类型： *ast.SelectStmt *ast.TableOptimizerHint *ast.TableRefsClause *ast.Join

5391 0

LL(1),LR(0),SLR(1),LALR(1),LR(1)

LL(k)文法 LL(1) 为什么需要FIrst和Follow，以及如何根据First与Follow生成预测分析表步骤首先生成First，再结合First生成Follow, 最后根据First...这就是为什么我们要引入SLR解决reduce-shift conflict(尽管不能完全解决该问题)....SLR -> LR(1)的必要性 SLR不能完全解决reduce-shift confict....SLR不能完全解决reduce-shift conflict....构造关键合并同心集合并前合并后构造方法: 见中文第二版P.169下方[算法 4.56] reduce-shift reduce

1.3K3 1

TiDB 源码阅读系列文章（五）TiDB SQL Parser 的实现

词法分析器读取源代码，根据 patterns 将源代码转换成 tokens 输出。Yacc 根据用户定义的语法规则生成语法分析器。...Yacc 生成的语法分析器使用自底向上的归约（shift-reduce）方式进行语法解析，同时使用堆栈保存中间状态。...对这个语法树进行遍历访问，可以生成机器代码，也可以解释执行。至此，我们大致了解了 Lex & Yacc的原理。...从 parser.y 的注释看到，这个文件最初是用工具从 BNF 转化生成的，从头手写这个规则文件，工作量会非常大。...这段代码的运行结果如下，依次输出遍历过程中遇到的节点类型： *ast.SelectStmt *ast.TableOptimizerHint *ast.TableRefsClause *ast.Join

4.6K10 0

CSS大会 | 打破常“规”：挖掘语法解析器规则漏洞

我们的议题重点关注Lex&YACC和LEMON Parser Generator。在Lex YACC解析器中，生成解析器的流程如右图所示。...右边是生成它的具体Fuzzer代码。这样一个PoC有什么玄机呢，让我们继续往后看。 POC在第一张图中。那么为什么会导致这样的问题呢，让我们阅读一下layout相关的语法规则。...Yy就是yacc的那个y，大家可以读一下它的代码，他们写的时候并不是十分规范，大量使用了全局变量，我猜测这个yy是为了避免生成的代码。...和它自己的代码冲突而加上的一个模拟C++namespace的东西，如果觉得看着很碍眼，可以在阅读的时候把yy全部删掉。...SQLite使用了Lemon Parser，它和Yacc&Lex很像，但是又不互相兼容，不过在右边Call Stack中大家一样能看到中间有个yy_reduce，最后它还是用了yy_这个标准开头。

9874 0

Postgresql源码（40）server端语法解析流程分析

5、从语法树底层节点向上reduce，识别收集文本中的目标信息，创建对应的stmt结构体，填入数据，返回上层。...（2）如果有预读的token就直接用了，不再重新解析（3）如果没有预读的token，调core_yylex从lex拿一个token出来，如果是普通token直接返回yacc继续reduce （4）...427 258 708 258 524 588 SELECT * FROM IDENT WHERE IDENT NOT LIKE 3、从524（NOT）开始，会进入函数的...~~", $1, $4, @2); } 工作过程第一步：符号从左到右依次入栈，shift操作符号堆栈值堆栈 | | |...操作，执行{...}代码，并全部出栈，然后将$$重新入值堆栈，a_expr入符号堆栈符号堆栈值堆栈 | | | | |

5042 0

YACC移进规约冲突案例分析

也可以看output输出的状态机中给出的两条冲突规则，可读性比较差。方括号括起来的是冲突的路径。总结： bison给出用例的第二种情况，有时会比较难以理解。为什么呢？...因为他给的用例可能是经过reduce的上层用例，真正冲突的地方在语法树下层。案例一：返回一个Example的场景（简单）冲突报错返回一个明确用例的场景。.../reduce conflict [-Wconflicts-sr] sequence.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr] 共有三条冲突...【冲突二】输入空的时候，有两个规约路径。...ID ',' ID shift, and go to state 6 ID [reduce using rule 2 (a)] shift/reduce conflict

1.4K3 0

使用优先级解决shiftreduce冲突的经典例子（%prec UMINUS）

2 案例：%prec UMINUS解决shift/recude冲突 gram.y中处理select语句的语法规则，发生语法冲突。.../reduce conflicts: 1 found, 0 expected gram.y: warning: shift/reduce conflict on t0ken ')' [-Wcounterexamples...当前没有定义select_with_parens的优先级，所以发生了shift/recude冲突。如果加上%prec UMINUS为什么就没有冲突了，bison选择了shift还是recude？...处理上述情况bison的规则：如果rule的优先级更高，bison选择reduce。如果lookahead token的优先级更高，bison选择shift。.../recude错误，且错误发生的原因是lookahead token和同一条规则的冲突，可以尝试为规则配置优先级，达到帮助bison选择shift、reduce的效果。

8581 0

LR分析中shiftreduce reducereduce冲突解决方案SLR(1)与LR(1)

LR(0)分析法简述 LR分析法从左至右移进输入的终结符（词法分析器的输出实际是token，但在语法分析阶段会代表是一个终结符），并将终结符压入到堆栈，称为shift。...如果当前栈上的符号恰好符合某个非终结符的生成式，则此时进行归约操作：将这些符号弹出栈，然后将规约后的非终结符压入堆栈，这一步就称为reduce。然后继续上面的步骤，直到没有输入。...这种情况称为shift/reduce冲突。...这种情况称为reduce/reduce冲突。因为这两种冲突的存在导致了LR(0)分析法在实际语法分析中基本不可用，必须找到解决这两种冲突的方案才行，那么如何这两种冲突呢？ 3....上面的例1也可以通过此算法解决shift/reduce冲突。

1491 0

YACC嵌入式规则

测试用例在文章末尾嵌入式用法 YACC语法分析只允许动作在规则的末端，例如：（其中{}内部为定义好的规则） expr: T_INT { $$ = $1; } | expr T_PLUS...当前1表示A、3表示B、移进/规约冲突嵌入式规则等于在匹配规则的过程中就执行一些动作（正常动作是在规则整体匹配完了再执行）。...这样会导致规约的动作有可能要比没有嵌入式的规则提前做，例如： thing: abcd | abcz; abcd: ‘A' 'B' 'C' 'D' ; abcz: ‘A' 'B'...'B' 'C' 'Z' 原因是：第一种情况下，yacc在看到4个字符之前不需要决定匹配abcd还是abcz，reduce动作可以在收到4个字符之后再做。...第二种情况下，在收到A、B之后，就必须做出决定了，因为abcd规则有嵌入式规则要执行，但是只收到两个字符无法决定走哪个分支，所以发生冲突。

9681 0

Flex & Bison 开始

例如，如下代码片段： alpha = beta + gamma; 词法分析把这段代码分解为这样一些记号：alpha, =, beta, +, gamma, ;。...起源 bison 来源于 yacc，一个由 Stephen C. Johnson 于 1975 年到 1978 年期间在贝尔实验室完成的语法分析器生成程序。...正如它的名字（yacc 是 yet another compiler compiler 的缩写）所暗示的那样，那时很多人都在编写语法分析器生成程序。Johnson 的工具基于 D. E....来自自由软件基金会（Free Software Foundation）的 Richard Stallman 改写了 Corbett 的版本并把它用于 GNU 项目中，在那里，它被添加了大量的新特性并演化成为当前的...如下编译所有范例： cd books/flex_bison/ # 编译 release make # 编译 debug make debug # 清理 make clean 范例程序会输出进 _build

1.5K2 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云