首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

为什么这会在yacc / bison中提供1个shift/reduce冲突

在yacc/bison中,shift/reduce冲突是指在语法分析过程中,存在一种情况,即解析器既可以进行移进操作(shift),也可以进行规约操作(reduce),但无法确定应该选择哪种操作。这种冲突通常是由于文法规则的模糊性或二义性引起的。

shift/reduce冲突的出现可能会导致解析器无法正确地解析输入的语法,从而产生错误的语法树或解析结果。为了解决这个冲突,可以采取以下几种方法:

  1. 优先级规则:通过为文法规则和终结符设置优先级,明确指定在冲突情况下应该进行的操作。可以使用yacc/bison提供的优先级声明来实现。例如,可以通过设置运算符的优先级和结合性来解决表达式中的冲突。
  2. 关联规则:通过为文法规则设置关联性,明确指定在冲突情况下应该进行的操作。可以使用yacc/bison提供的关联声明来实现。例如,可以通过设置赋值操作符的右结合性来解决赋值表达式中的冲突。
  3. 修改文法:通过修改文法规则,消除或减少冲突的发生。可以通过重新设计文法规则,引入额外的非终结符或调整产生式的顺序来解决冲突。这需要对语言的语法进行深入理解和分析。
  4. 解决冲突:在某些情况下,可以通过在yacc/bison中提供解决冲突的指令来明确选择移进或规约操作。可以使用yacc/bison提供的解决冲突的命令,如%prec和%expect等来实现。

总之,解决yacc/bison中的shift/reduce冲突需要对语法规则和解析器的行为有深入的理解和分析。通过设置优先级、关联性,修改文法或使用解决冲突的指令,可以有效地解决这种冲突,确保解析器能够正确地解析输入的语法。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

Postgresqlyacc语法树冲突解决方法(shiftreduce conflicts)

gram.y -Wno-deprecated 正常执行后会产生gram.c文件,一旦发生冲突bison会报错,例如: 但没有进一步的信息不好定位问题,这里提供两种方式打印更详细的错误帮助定位...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向右移进 还是 向上规约?发生冲突

1.9K30

bison解析lookahead前瞻工作原理

https://www.gnu.org/software/bison/manual/bison.html#Algorithm 1 lookahead token 学习yacc后一直有一个疑问,reduce...遇到匹配的规则立即执行reduce吗?还是在等一等看看后面的token,可能匹配上其他的规则? bison行为: bison解析器并不是遇到栈顶的一组token匹配上规则后,立即执行recude。...stmt ; 假设当前"if"、“then"都已经在解析栈,lookahead是"then”。...选择2:lookahead继续shift入栈,按规则2规约。 现在发生了shift/reduce冲突Bison会通过选择shift来解决这些冲突(除非运算符优先级声明)。...3.1 悬挂冲突 为了解其中的原因,下面与其他选择进行对比: 正例:如果bison更偏向于shift “else”,下面语句1就等价与语句2,符合预期。

1.5K70

YACC移进规约冲突案例分析

总结 总结: bison给出的用例是发现冲突的最便捷方法。 第一种用例:明确用例(一个Example),直接反应问题。 第二种用例:混淆用例(两个Example),解析器无法区分两条语句。...也可以看output输出的状态机给出的两条冲突规则,可读性比较差。 方括号括起来的是冲突的路径。 总结: bison给出用例的第二种情况,有时会比较难以理解。为什么呢?...: warning: 2 reduce/reduce conflicts [-Wconflicts-rr] 共有三条冲突,下面是用例: 【冲突一】 注意看用例Example,提供的是一个 "空 word...最上面会有告警和冲突的汇总。 Grammar开始是规则区,y文件的每一行规则在这里编号,后面使用时会使用编号代替。...State 0开始是状态区,状态转移如果不唯一的话,会在State区列出例子和冲突选项。 状态机转移请看下一个例子。

1.3K30

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

2 案例:%prec UMINUS解决shift/recude冲突 gram.y处理select语句的语法规则,发生语法冲突。...当前没有定义select_with_parens的优先级,所以发生了shift/recude冲突。如果加上%prec UMINUS为什么就没有冲突了,bison选择了shift还是recude?...处理上述情况bison的规则: 如果rule的优先级更高,bison选择reduce。 如果lookahead token的优先级更高,bison选择shift。...所以,在上述两条路径,select_with_parens比')'的优先级低,bison执行shift操作,将右括号和更内层、更近的左括号结合,避免了语法错误。.../recude错误,且错误发生的原因是lookahead token和同一条规则的冲突,可以尝试为规则配置优先级,达到帮助bison选择shiftreduce的效果。

77910

【Python】Ply 简介

你可以在单独的模块定义规则,以此保证分析器主代码干净,需要你在创建 lexer 时显式地指定 module: lexer = lex.lex(module=tokrules) 面向对象:有时面向对象不失是一个封装的好办法...的语法规则解析后面的内容知道遇到 "```" 如果遇到 "```c" 就开始按 C 的语法规则解析后面的内容知道遇到 "```" 其余时候按 MarkDown 的规则解析 要处理这样的需求最好是给分析器提供不同的状态和指定在某种状态下的解析规则...* expr,默认情况下,解析器会选择移入,即弹入 PLUS,显然错了,因此我们需要指定规则的优先级: precedence = ( ('left', 'PLUS', 'MINUS'),...当出现这种冲突时,yacc 会打印一下警告信息: WARNING: 1 reduce/reduce conflict WARNING: reduce/reduce conflict in state 15...标注出了冲突的地方,虽然这些冲突不见得都是不好的。

2.5K30

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增加即可。

75530

javacc功能一览

javacc特征 •JavaCC生成自上而下的(递归下降[1])解析器,而不是类似YACC[2]的工具生成的自下而上的解析器。尽管不允许左递归[3],允许使用更通用的语法。...JavaCC提供了语法和语义超前功能,可以在这些点上本地解决shift-shift歧义。例如,解析器LL(k)仅在这样的点上,但仍保留LL(1)在其他地方以获得更好的性能。...对于自上而下的解析器而言,Shift-reducereduce-reduce冲突不是问题。...•JavaCC提供类似Lex[7]的词法状态和词法动作功能。在JavaCC是优于其他工具的具体方面是它提供的概念,如一流的状态TOKEN,MORE,SKIP和状态的变化。...这样可以提供更整洁的规范以及来自JavaCC的更好的错误和警告消息。•在解析过程,在词汇规范定义为特殊标记的标记将被忽略,但是这些标记可供工具处理。的一个有用的应用是在评论的处理

1.9K10

Python 之父撰文回忆:为什么要创造 pgen 解析器?

据我所知,他有自己的博客,为什么还会跑去 Medium 上写文呢?好奇之下,我就打开了他的老博客。...之所以我要写自己的语法分析生成器,原因是当时玩意(我熟悉的)相当稀少——基本上就是用 Yacc(有个 GNU 的重写版,叫作 Bison(译注:美洲野牛),但我不确定那时的自己是否知道);或者是自己手写一个...我曾在大学里用过 Yacc,从“龙书”熟悉了它的工作原理,但是出于某些原因,我并不喜欢它;IIRC 关于 LALR(1) 语法的局限性,我很难解释清楚。...(对我而言)不通过添加帮助性的规则而解决冲突的方式。...如果让我重做一遍,我可能会选择一个更强大的解析引擎,可能是 LALR(1) 的某个版本(例如 Yacc/Bison)。

1.3K30

如何愉快地写个小parser

(一) 在前几日的文章『软件随想录』里,我随性写了一句:「现在似乎已经不是lex/yaccbison/flex的时代了。...后来lex/yacc进化成flex/bison,在工作我也无意中翻看了一本orelley叫『Flex & Bison』的书,书的副标题赫然写着:text processing tools。...bison使用的描述规则的语法是BNF的变体。 以下是编译和执行的结果,作为展示,我仅仅把语法树我感兴趣的内容打印出来了: ?...(二) 可惜,如今大部分文艺青年都已经不用C了 —— 虽说很多语言都提供了对C的FFI(Foreign Function Interface),比如Python,你可以用flex/bison生成一个parser...我想你应该猜到了,货是javascript bisonbison在javascript上的变态。先来个解析SQL里的 create table 的例子。我们想实现这样的效果: ?

3.1K100

(1)PHP内核 - 玩转php的编译与执行

你会发现这里面没有讲到opline里面handler字段,关于opline handler的具体细节会在后面详细介绍。...PHP内词法分析和语法分析分别使用的是re2c和yacc来完成的。其实准确来说一个应该是re2c和bison。...如果你真的想看看yacc内部扫描语法的,不要去看经过bison预处理之后的.c文件,同级目录下有一个.output后缀相同文件名的文件,里面描述了yacc里面的状态机是如何工作的。...具体的值,需要自己提供接口,yacc也一个宏YYPRINT,在这里可以不用为它这个宏提供个函数。...你可以先不看下面的解答,先自己想想为什么会这样? 其实这个问题需要在语法分析这个阶段来看,可以先去yacc里面关于print的语法结构。

1.8K10

Postgresql源码(44)server端语法解析流程分析

框架 3、yacc框架调用base_yylex进入lex拿一个token(正常用框架是每次拿一个,PG通过对lex函数的封装可以拿后面多个,有些语法需要看到后面多个一块解析) 4、拿回来token...5、从语法树底层节点向上reduce,识别收集文本的目标信息,创建对应的stmt结构体,填入数据,返回上层。...(2)如果有预读的token就直接用了,不再重新解析 (3)如果没有预读的token,调core_yylex从lex拿一个token出来,如果是普通token直接返回yacc继续reduce (4).../reduce语法树的过程,调用base_yylex获取token 4、base_yylex的第三个参数就是初始化的scanner,里面可以取出extra 5、base_yylex的前两个参数是lex...框架定义的,保存了解析所需 6、core_yylex是scan.l生成scan.c中提供的函数,功能就是scan.l编写的匹配规则 7、core_yylex可以自己在scan.l自定义其他同参函数

52650

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

我们的议题重点关注Lex&YACC和LEMON Parser Generator。 在Lex YACC解析器,生成解析器的流程如右图所示。...我们希望能够给大家提供一个新的攻击面和思路,以此抛砖引玉。 接下来,我们来看一下Lex和YACC的攻击模型。...正如右图所示,黄色部分表示可能被攻击的攻击面,分别对应四个处理程序(Lex,YACC,yylex,yyparse)。但在实际攻击场景,规则其实早已定义好,规则在程序相当于常量。...但为什么有符号数的情况下不会触发呢?...SQLite使用了Lemon Parser,它和Yacc&Lex很像,但是又不互相兼容,不过在右边Call Stack中大家一样能看到中间有个yy_reduce,最后它还是用了yy_这个标准开头。

96040

分享 20 个 Javascript 的数组方法,收藏

array.forEach(callback[, thisObject]);forEach()按索引升序为数组的每个元素调用一次提供的callbackFn函数。...Array.prototype.shift()的行为与pop()类似,但应用于数组的第一个元素。...shift()函数直接修改您正在使用的JavaScript数组。shift()返回从数组移除的项。函数的作用是:删除索引位置0处的项,并将未来索引号处的值下移一位。...array1.at(index)}`);// expected output: "Using an index of -2 item returned is 130"19.findfind()方法返回所提供的数组满足所提供的测试函数的第一个元素...如果你正在学习JS或者已经在我们的三十天计划完成了4个综合项目实战,那不妨可以听下这个课程体系,三十天计划群里还提供了算法、数组等知识体系!

54220

Yacc 与 Lex 快速入门(词法分析和语法分析)

在 高级 Lex 这一节我们将讨论 Lex 提供的函数,这样你就能编写更加复杂的程序了。 将它们全部结合起来 .lex文件是 Lex 的扫描器。...它在 Lex 程序如下表示: $ lex 生成了 lex.yy.c 文件,它可以用 C 编译器来进行编译。...-v提供一个两行的统计汇总。 -n不打印 -v 的汇总。 高级 Lex Lex 有几个函数和变量提供了不同的信息,可以用来编译实现复杂函数的程序。 下表列出了一些变量和函数,以及它们的使用。...yytext 匹配模式的文本存储在这一变量(char*)。 yyleng 给出匹配模式的长度。 yylineno 提供当前的行数信息。 (lexer不一定支持。)...下面我们来讨论 Yacc... Yacc Yacc 代表 Yet Another Compiler Compiler。 Yacc 的 GNU 版叫做 Bison

5.1K20
领券