[译] 自顶向下解析和自底向上解析的区别
原文
The difference between top-down parsing and bottom-up parsing
http://qntm.org/top
给定一套形式化文法和这套文法生成的字符串
parsing (解析)就是分析出字符串产生的过程
对于上下文无关文法, 生成过程以 parse tree 的形式出现
我买开始前, 先要知道 parse tree 的两件事:
根节点, 字符衍生出来的初始的符号
叶节点, 字符串按照顺序的所有字符
我们所不知道的是两者之间的节点和分支
比如对于字符串 acddf, 我们已经知道的是
S /|\ ???| | | | |a c d d f这篇文章作为例子的文法:
S → xyz | aBC
B → c | cd
C → eg | df
自底向上解析
这个方案和拼图没有本质差别
我们从 parse tree 的底部开始, 从单个的字符开始
随后是有规则将字符尽自己所能拼接成更大的 token
字符串最终的结果, 一切都应该被结合到一个单个巨大的 S
而且 S 应该是我们剩下的唯一的内容
如果不是, 那么就需要回溯尝试用别的办法尝试合并出 token
在自底向上解析中,一般会维护一个 stack
也就是已经读取的所有的字符和 token
每一个步骤, 一个新的字符会被插图到 stack 顶部
然后尽可能地结合字符并归纳为更大的 token
例子
字符串是 acddf
步骤
ε无法归纳a无法归纳ac可以被归纳, 如下:归纳
ac为aBaB无法归纳
aBd无法归纳
aBdd无法归纳
aBddf可以被归纳, 如下:
归纳
aBddf为aBdC
aBdC无法归纳
字符串完. Stack 为
aBdC, 非S. 失败! 需要回溯.
aBddf无法归纳
ac无法归纳acd可以被归纳, 如下:归纳
acd为aBaB无法归纳
aBd无法归纳
aBdf可以被归纳, 如下:
归纳
aBdf为aBC
aBC可以被归纳, 如下:
归纳
aBC为S
字符串完. Stack 为
S. 成功!
Parse trees
|a| |a c B| |a c B| | |a c d B| | | |a c d d B| | | | |a c d d f B C| | | |\a c d d f| |a c| | |a c d B| /|a c d B| /| |a c d d B| /| | |a c d d f B C| /| |\a c d d f S /|\ / | | / B C| /| |\a c d d f例子 2
如果所有符合都失败, 那么字符串无法被解析
字符串为 acdg
步骤
ε无法归纳a无法归纳ac可以被归纳, 如下:归纳
ac为aBaB无法归纳
aBd无法归纳
aBdg无法归纳
字符串完. Stack 为
aBdg, 非S. 失败! 需要回溯.
ac无法归纳acd可以被归纳, 如下:归纳
acd为aBaB无法归纳
aBg无法归纳
字符串完. Stack 为
aBg, 非S. 失败! 需要回溯.
acd无法归纳acdg无法归纳字符串完. Stack 为
acdg, 非S. 没有可用的回溯. 失败!
Parse trees
|a| |a c B| |a c B| | |a c d B| | | |a c d g| |a c| | |a c d B| /|a c d B| /| |a c d g| | |a c d| | | |a c d g自顶向下解析
这套方案中设想字符串匹配 S 并查看这个假设的内部逻辑提示
比如当字符串匹配 S 逻辑上按时或者
(1) 字符串匹配 xyz 或 (2) 字符串匹配 aBC
当知道 (1) 不对, 那么 (2) 必须是对的, 而 (2) 内部有更深的逻辑提示
这些必须逐个检查以验证基本的假设
例子
字符串是 acddf
步骤
断言 1:
acddf匹配S断言 2:
acddf匹配xyz:
断言 为否. 尝试其他.
断言 2:
acddf匹配aBC, 即cddf匹配BC:
断言 3:
cddf匹配cC, 即ddf匹配C:
断言 4:
ddf匹配eg:
否.
断言 4:
ddf匹配df:
否.
断言 3 为否. 尝试其他.
断言 3:
cddf匹配cdC, 即df匹配C:
断言 4:
df匹配eg:
否.
断言 4:
df匹配df:
断言 4 为真.
断言 3 为真.
断言 2 为真.
断言 1 为真. 成功!
Parse trees
S | S /|\ a B C | | S /|\ a B C | | c S /|\ a B C /| | c d S /|\ a B C /| |\ c d d f例子 2
如果, 试验了所有逻辑线索, 依然无法验证基本假设("字符串匹配 S")
那么字符串无法被解析
字符串为 acdg
步骤
断言 1:
acdg匹配S:断言 2:
acdg匹配xyz:
否.
断言 2:
acdg匹配aBC, 即cdg匹配BC:
断言 3:
cdg匹配cC, 即dg匹配C:
断言 4:
dg匹配eg:
否.
断言 4:
dg匹配df:
否.
否.
断言 3:
cdg匹配cdC, 即g匹配C:
断言 4:
g匹配eg:
否.
断言 4:
g匹配df:
否.
否.
否.
断言 1 为否. 失败!
Parse trees
S | S /|\ a B C | | S /|\ a B C | | c S /|\ a B C /| | c d为什么做递归是自顶向下解析器的一个问题
如果规则是做递归, 比如这样的内容
S → Sb
可以注意到算法的行为是:
步骤
断言 1:
acddf匹配S:断言 2:
acddf匹配Sb:
断言 3:
acddf匹配Sbb:
断言 4:
acddf匹配Sbbb:
...无穷无尽
Parse trees
S | S |\ S b | S |\ S b |\ S b | S |\ S b |\ S b |\ S b |...