top-down和bottom-up解析的关键区别在于,top-down解析执行从起始符号到输入字符串的解析,而bottom-down解析执行从输入字符串到起始符号的解析。此外,自顶向下和自底向上解析的另一个重要区别是,自顶向下的解析使用最左边的派生,而自下而上的解析使用最右边的派生。
高级语言有助于编写计算机程序。程序员更容易理解它们,但计算机不容易理解。因此,将程序转换为高级程序。编译器的任务是将人类可读的源代码转换为机器可读的机器代码。一个程序要经过几个步骤才能转换成机器码。整个过程称为语言处理系统。其中之一是汇编。语法分析器或解析器在编译器中,它执行解析任务。
目录
1. 概述和主要区别
2. 什么是自顶向下的解析
3. 什么是自下而上的解析
4. 并排比较-表格形式的自顶向下与自下而上分析
5. 摘要
什么是自顶向下分析(top down parsing)?
每种编程语言都有一组表示语言的规则。语法分析器或语法分析器获取输入字符串,并根据语法结果检查它是否正确。换句话说,语法应该使用解析树生成该字符串。
在自顶向下的解析中,解析从起始符号开始,并将到达给定的输入字符串。考虑以下语法产生式规则。输入字符串(w)为cad。
S->cAd
A->ab/A
执行自顶向下解析后的解析树如下所示。
S产生c A d,A产生b。弦是cabd。它不是必需的字符串。因此,有必要进行回溯,即使用其他替代方法。
类似地,S产生c A d。对A应用另一个选项将得到A。现在它给出了所需的字符串。因此,解析器接受这个输入字符串。执行自顶向下解析后的解析树如下所示。
当输入字符串(w)为abcde时
考虑以下语法产生式规则。
S->aABe公司
A->Abc/b
B->d
在自顶向下的分析中,
S->aABe(代替A->Abc)
S->aAbcBe(替换A->b)
S->Abcbe(代替B->d)
圣母院
替换首先从最左边的变量开始,然后到下一个右边的位置,依此类推。因此,它遵循最左边的求导方法。此外,当存在变量时,决定选择什么样的产生式规则是很重要的。
什么是自下而上分析(bottom up parsing)?
在自下而上中,解析是以另一种方式进行的。解析从输入字符串到起始符号。考虑以下语法产生式规则,并让输入字符串为wɛcad
S->cAd
A->ab/A
执行自底向上解析后的解析树如下所示。
给定的字符串是cad。a由a生成。c、a和d组合得到起始符号S。
当输入字符串(w)为abcde时
考虑以下语法产生式规则。
S->aABe公司
A->Abc/b
B->d
在自下而上的分析中,
S->aABe(代替B->d)
S->aAde(替换A->Abc)
S->aAbcde(子例程A->b)
圣母院
替换首先从最右边的变量开始,然后移到下一个左边的位置,依此类推。因此,它遵循左mot求导方法。
自上而下(top down)和自下而上分析(bottom up parsing)的区别
自顶向下解析是一种解析策略,它首先查看解析树的最高级别,然后使用形式语法的规则沿着解析树向下展开。自底向上解析是一种解析策略,它首先查看解析树的最低层,然后使用形式语法的规则向上搜索解析树。在自顶向下的解析中,解析从起始符号到输入字符串。另一方面,在自下而上的解析中,解析从输入字符串到起始符号。
此外,自顶向下分析的主要决策是选择使用什么产生式规则来构造字符串,而自下而上分析的主要决策是选择何时使用产生式规则来减少字符串以获得起始符号。此外,自顶向下的解析使用最左边的派生,而自下而上的解析使用最右边的派生。
总结 - 自上而下(top down) vs. 自下而上分析(bottom up parsing)
top-down和bottom-up解析的区别在于,top-down解析执行从起始符号到输入字符串的解析,而bottom-down解析执行从输入字符串到起始符号的解析。