知识卡片
移进归约的工作方式
移进把新 token 连同状态压栈,归约把匹配某条产生式右侧的内容替换为左侧非终结符。重复这两个动作,最终把完整输入归约为起始结构;运算符优先级和结合性影响何时归约。
关联:[[产生式动作构建AST]]从相邻机制说明这一边界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现 · 查看原书依据
第一部分定义了 token 类型和运算符的结合性。四种运算符都是左结合,同一行的运算符优先级相同,不同行的运算符,后定义的行具有更高的优先级。
- TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现 · 查看原书依据
解析表达式是生成表达式的逆向操作,我们需要归约表达式到一个非终结符。Yacc 生成的语法分析器使用自底向上的归约(*shift-reduce*)方式进行语法解析,同时使用堆栈保存中间状态。还是看例子,表达式 x + y * z 的解析过程:
- TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现 · 查看原书依据
点(.)表示当前的读取位置,随着 . 从左向右移动,我们将读取的 token 压入堆栈,当发现堆栈中的内容匹配了某个产生式的右侧,则将匹配的项从堆栈中弹出,将该产生式左侧的非终结符压入堆栈。这个过程持续进行,直到读取完所有的 tokens,并且只有启始非终结符(本例为 program)保留
参考来源
- 位置:《TiDB源码阅读系列文章》第05章《TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现》(来源项目:book-sources;源文件:extracted/TiDB源码阅读系列文章/_epub-src/OEBPS/Text/TiDB 源码阅读系列文章(五)TiDB SQL Parser 的实现.html;阅读段落 22,25,27;均为书中版本)
- 结论依据:原文对移进归约的工作方式给出上述机制或边界;本卡把已读说明整理为可独立理解的解释。
- 原始内容:第一部分定义了 token 类型和运算符的结合性。四种运算符都是左结合,同一行的运算符优先级相同,不同行的运算符,后定义的行具有更高的优先级。 …… 解析表达式是生成表达式的逆向操作,我们需要归约表达式到一个非终结符。Yacc 生成的语法分析器使用自底向上的归约(*shift-reduce*)方式进行语法解析,同时使用堆栈保存中间状态。还是看例子,表达式 x + y * z 的解析过程: …… 点(.)表示当前的读取位置,随着 . 从左向右移动,我们将读取的 token 压入堆栈,当发现堆栈中的内容匹配了某个产生式的右侧,则将匹配的项从堆栈中弹出,将该产生式左侧的非终结符压入堆栈。这个过程持续进行,直到读取完所有的 tokens,并且只有启始非终结符(本例为 program)保留