bison解析中lookahead前瞻工作原理
2023-02-25 18:17:24 时间
https://www.gnu.org/software/bison/manual/bison.html#Algorithm
1 lookahead token
学习yacc后一直有一个疑问,reduce到底什么时候发生? 遇到匹配的规则立即执行reduce吗?还是在等一等看看后面的token,可能匹配上其他的规则?
bison行为:
- bison解析器并不是遇到栈顶的一组token匹配上规则后,立即执行recude。因为这种简单的策略不能满足一些复杂语言的需要。
- bison解析器在发现一次匹配后,会继续向前看一个lookahead,再决定做什么。
具体步骤:
- 当读到一个token时,并不立即shift进入堆栈,而是把他当成lookahead token(不入栈)。
- 然后解析器就可以执行栈上的匹配动作了,匹配上就可以reduce。lookahead token放在一边。
- 当没有token能进行reduce后,再把lookahead token shift入栈。
上面的步骤2并不是匹配上的都能reduce,lookahead token会影响一些规则,使其延迟reduce。
1.1 lookahead token案例分析
- 这是一个有相互依赖关系的语法树。term可以reduce为expr;expr加括号可以reduce为term。
- !是后缀运算符,表示阶乘。
- 语法支持括号分组。
expr:
term '+' expr
| term
;
term:
'(' expr ')'
| term '!'
| "number"
;
当1+2
进入语法树时,如果不向前看一个token,会发生的问题:
1 + 2 )
\ /
1 + 2 reduce为:expr ')'
\ /
expr 和 右括号reduce为term
如果1+2后面跟的是!,上面的1+2已经被reduce为expr,叹号肯定是无法匹配上了。
所以要reduce'1+2'
时,必须向前看一个,再决定1+2要不要reduce。
- 如果
lookahead=)
,可以直接reduce。 - 如果
lookahead=!
,需要延迟reduce,什么也不做。
1.2 lookahead读取方法
- lookahead token
- yychar
- lookahead token值
- yylval
- lookahead token位置
- yylloc
2 Shift/Reduce冲突
实例:其中"if"、“then”、"else"终结符
if_stmt:
"if" expr "then" stmt
| "if" expr "then" stmt "else" stmt
;
假设当前"if"、“then"都已经在解析栈中,lookahead是"then”。
- 选择1:当前解析栈按规则1规约。
- 选择2:lookahead继续shift入栈,按规则2规约。
现在发生了shift/reduce冲突。Bison会通过选择shift来解决这些冲突(除非运算符优先级声明)。
3.1 悬挂冲突
为了解其中的原因,下面与其他选择进行对比:
正例:如果bison更偏向于shift “else”,下面语句1就等价与语句2,符合预期。
-- 语句1
if x then
if y then win;
else lose;
-- 语句2:else和里面的If结合,符合预期
if x then do;
if y then win;
else lose; end;
反例:如果bison更偏向于reduce,下面语句1就等价与语句2,不符合预期。
能shift也能recude得时候,先recude了,
-- 语句1
if x then
if y then win; -- 栈:if then if then(lookahead=else),看到后一个if then直接recude了。
else lose; -- 剩下一个else,只能和外面的if一起recude了。
-- 语句2:else和外面的if结合,不符合预期。
if x then do;
if y then win; end;
else lose; -- 结果就是else给外面的if了,但预期是需要和里面的if结合。
这就是经典的“dangling else”冲突,悬挂的else。
文件
%%
stmt:
expr
| if_stmt
;
if_stmt:
"if" expr "then" stmt
| "if" expr "then" stmt "else" stmt
;
expr:
"identifier"
;
bison --report=counterexamples if.y
output文件
State 9
3 if_stmt: "if" expr "then" stmt •
4 | "if" expr "then" stmt • "else" stmt
"else" shift, and go to state 10
后面挂了一个else,是要等else进来shift,还是
"else" [reduce using rule 3 (if_stmt)]
直接reduce掉前面的if then?
$default reduce using rule 3 (if_stmt)
shift/reduce conflict on t0ken "else":
3 if_stmt: "if" expr "then" stmt •
4 if_stmt: "if" expr "then" stmt • "else" stmt
Example: "if" expr "then" "if" expr "then" stmt • "else" stmt
Shift derivation
if_stmt
↳ 3: "if" expr "then" stmt
↳ 2: if_stmt
↳ 4: "if" expr "then" stmt • "else" stmt
Reduce derivation
if_stmt
↳ 4: "if" expr "then" stmt "else" stmt
↳ 2: if_stmt
↳ 3: "if" expr "then" stmt •
3 解析器状态
- yyparse使用有限状态机实现。
- 推入解析器栈的值不仅仅看做是一个个的token,它们表示的是终结、非终结符组成的序列(栈顶的token序列),token就是状态机的状态。·
- 每次读lookahead时,状态机的状态 和 lookahead一并去 “table”里面查出来一条转移指令。
- 转移指令可能是shift:解析器堆栈入栈。
- 转移指令可能是recude:解析器堆栈出栈状态(token/tolen序列),入栈一个替换的状态(token)。
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023