Compiler-2_Bottom-Up_Parsing-自底向上分析

Last updated Oct 30, 2021 Edit Source

• All
• Compiler
• Course

Tags: #Compiler #Course

• 自底向上分析是一种语法分析方法, 它从语法树的下边缘(即一堆终结符)开始, 逐步向上构建这个句子的推导过程

• 一般来说, 自底向上分析比自上而下分析要更强大, 同时也更复杂.

# Shift-reduce parsing1

• 移位-规约分析(Shift-Reduce Parsing)是自底向上分析的主流方法

• 有许多不同的移位规约分析方法: 比如: “算符优先分析”

  Compiler-3_算符优先分析

  Operator-precedence grammar 2021-10-30 Tags: #Compiler #Course #FormalLanguage 算符优先文法 算符优先文法(OPG)是一种有特殊性质的上下文无关文法(CFG) 它的特殊性质表现为: 产生式右部不能为空 (即没有 $P\rightarrow \varepsilon$) 产生式右边不能有两个连续的非终结符 (即没有 $P\rightarrow \cdots AB\cdots$) 上述规则使得我们可以定义终结符之间的"优先级"(Precedence), (为什么?) 算符优先分析不是规范规约, 它的每一步不一定替换句柄 在书里面的定义中, 算符文法是不含两个连续非终结符的文法, 算符优先文法则是终结符之间最多只有一种优先关系的算符文法 Main differences with...

  11/19/2023

  和"LR分析"都属于移位规约分析.

• This is a good illustration ²

• Operator Precedence grammar could be either ambiguous or unambiguous.²

规范规约: 每步都替换句柄的规约 句柄就是 “那个可以直接规约的东西”

• 像table-driven predictive parser一样(比如LL(1)分析里面的那个表), 有的自底向上分析器使用栈来跟踪分析的位置, 使用分析表来决定接下来做什么.