自底向上分析

自顶向下和自底向上
评估软件有两种不同的方法:自顶向下的评估和自底向上的评估。

在自顶向下的估算方式中，首先对软件项目某些属性的整体值（如整个项目的规模、工作量和成本）进行估算，然后根据这一估算值，软件项目在不同阶段或者软件开发活动中的属性估算值（如在需求分析阶段的工作量）就可以按照在整体工作量的百分比来确定。

例如，假设通过估算某个软件项目的总工作量是120个人月，而需求分析在整个软件项目大约占25％的比例，那么就可以估算出需求分析阶段的工作量是30个人月。

在自底向上估算方式中，首先对软件项目某些属性的部分值进行估算（如某些阶段或者某个软件开发活动的工作量和成本，或者某个软件子系统的规模），然后在此基础上进行综合和累加，得到关于软件项目某些属性整体值的估算值（比如整个软件项目的工作量、成本和规模）。

例如，如果通过分解可以将一个复杂软件系统分解为五个相对独立的子系统，而每个子系统的规模估算值分别为：10000、5000、6000、8000和12000行代码，那么整个软件项目的规模就是上述值的累加即41000行代码。

第六章自底向上优先分析方法•教学要求：了解简单优先分折法，掌握算符优先分析法的关系表的构造以及分析过程。

•教学重点：算符优先表构造及算符优先分析法。

1自底向上分析法的基本思想•从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。

•工作方式：“移进－归约”方式。

2分析程序模型1）初态时栈内仅有栈底符“＃”，读头指针在最左单词符号上。

2）语法分析程序执行的动作：a）移进读入一个单词并压入栈内，读头后移；b）归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；c）识别成功移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；d）识别失败语法分析程序语法表a+b……#输出带#3例如：有文法如下（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d问：语句abbcde是不是该文法的合法语句？4•例：设文法G(S)：(1) S aAcBe(2) A b(3) A Ab(4) B d 试对abbcde进行“移进－归约”分析。

bbcde bbcde b cde de deabbcde eB cA a SB A a 5成功11接受2,3,4,1＃＃S 10归约＃＃aAcBe 9移进2,3,4e ＃＃aAcB 8归约e ＃＃aAc d 7移进de ＃＃aAc 6移进2,3cde ＃＃aA 5归约cde ＃＃a Ab 4移进2bcde ＃＃aA 3归约bcde ＃＃a b 2移进bbcde ＃＃a 1移进abbcde ＃＃0动作输出带输入串栈步骤移进归约的分析过程G[S]:（1）S →aAcBe（2）A →b（3）A →Ab（4）B →d 6遇到的问题：（1）如何找出进行直接归约的简单短语？（2）找出的简单短语应直接归约到哪一个非终结符？关键：确定句柄.常用的分析方法:（1）优先分析法（2）LR分析法7b db ac eSA B A d b a c e S A B A d a c eSA B a c e A B S 没有语法树如何确定句柄？86.1 自底向上优先分析法概述•基本思想：利用文法符号中相邻符号之间的优先关系（谁先规约的优先关系）找出句柄。

在自底向上的语法一、什么是自底向上的语法自底向上的语法（Bottom-Up Parsing）是一种常用的语法分析方法，用于将一个字符串根据给定语法规则转化为语法分析树。

与之相对的是自顶向下的语法分析方法，自顶向下的语法分析从根节点开始，逐步将输入的字符串分解为非终结符和终结符，直到得到语法分析树。

而自底向上的语法分析则相反，它从叶子节点开始，逐步合并成非终结符，直到得到语法分析树。

自底向上的语法分析方法通常采用的是操作符优先分析法（Operator Precedence Parsing），也称为算符优先文法。

这种分析方法可以通过构造一个算符优先关系表来进行分析，从而判断字符串是否符合给定的语法规则。

自底向上的语法分析方法适用于各种类型的语言和文法，包括正则文法、上下文无关文法等。

这种方法具有较高的灵活性和适应性，并且能够处理大型复杂的文法和语言。

二、自底向上的语法分析步骤自底向上的语法分析过程可以分为以下步骤：1. 词法分析首先，将输入的字符串进行词法分析，将其划分为一个个单词或记号（Token）。

每个单词或记号都具有一个特定的含义，表示了输入字符串中的一个基本语义单元。

2. 初始化构建一个栈（Stack）用于保存已识别的单词或记号，并初始化一个语法分析表（Parsing Table）用于记录语法规则和操作符的优先级关系。

3. 移入操作从输入的字符串中读取一个未处理的单词或记号，并将其压入栈中。

4. 归约操作不断检查栈中的记号序列是否满足某一语法规则，如果满足，则将该记号序列替换为相应的非终结符，并执行相应的语义动作。

重复这个过程，直到不能再进行归约操作。

5. 接受或错误处理如果最终栈中只剩下一个元素，且该元素为起始符号，则语法分析成功，接受输入的字符串。

如果栈中无法进行归约操作，或者最终栈中还有多余的元素，或者无法匹配到输入字符串的所有部分，则语法分析失败，进行错误处理。

三、算符优先文法算符优先文法是自底向上分析方法的代表，它以操作符的优先级和关联性为基础，构造一个优先关系表来进行分析。

第6章⾃底向上优先分析法⾃底向上分析⽅法，也称移进－归约分析法，粗略地说它的实现思想是对输⼊符号串⾃左向右进⾏扫描，并将输⼊符逐个移⼊⼀个后进先出栈中，边移⼊边分析，⼀旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产⽣式的右部），就⽤该产⽣式的左部⾮终结符代替相应右部的⽂法符号串，这称为归约。

重复这⼀过程直到归约到栈顶中只剩⽂法的开始符号时则为分析成功，也就确认输⼊串是⽂法的句⼦。

本章将在介绍⾃底向上分析思想基础上，着重介绍算符优先分析法。

例6.1，设⽂法G[S]为：（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d对输⼊串abbcde#进⾏分析，检查该符号串是否是G[S]的句⼦。

由于⾃底向上分析的移进－归约过程是⾃顶向下最右推导的逆过程，⽽最右推导为规范推导，⾃左向右的归约过程也称为规范归约。

容易看出对输⼊串abbcde的最右推导为：S aAcBe aAcde aAbcde abbcde由此我们可以构造它的逆过程即归约过程。

先设⼀个后进先出的符号栈，并把句⼦左括号”#”号放⼊栈底。

对上述分析过程也可看成⾃底向上构造语法树的过程，每步归约都是构造⼀棵⼦树，最后当输⼊串结束时刚好构造出整个语法树。

在上述移进－归约或⾃底向上构造语法树的过程中，考虑⼏个问题：u 何时移进？u 何时归约？u 将哪个字符串归约？当⼀个⽂法⽆⼆义性时，那么它对⼀个句⼦的规范推导是唯⼀的，规范规约也必然是唯⼀的。

因⽽每次归约时要找当前句型的句柄，也就是说，任何时候栈中的符号串和剩余的输⼊串组成⼀个句型，当句柄出现在栈顶符号串中时，则可⽤句柄归约，这样⼀直归约到输⼊串只剩结束符，⽂法符号栈中只剩开始符号。

由此可见，⾃底向上分析的关键问题是在分析过程中如何确定句柄，即如何知道何时在栈顶符号串中已形成某句型的句柄。

然⽽⾃底向上的分析算法很多，我们仅在本章和第7章介绍⽬前常⽤的算符优先分析和LR类分析法。

6.1 ⾃底向上优先分析法概述优先分析法⼜可分简单优先法和算符优先分析法。

自底向上和自顶向下的区别
用两个简单的例子说明一下:
某日小明上数学课，他的老师给了很多个不同的直角三角板让小明用尺子去量三角板的三个边，并将长度记录下来。

两个小时过去，小明完成任务，把数据拿给老师。

老师给他说，还有一个任务就是观察三条边之间的数量关系。

又是两个小时，聪明的小明连蹦带跳走进了办公室，说：“老师，我找到了，三条边之中有两条，它们的平方和约等于另外一条的平方。

”老师拍拍小明的头，“你今天学会了一个定理，勾股定理。

它就是说直角三角形有两边平方和等于第三边的平方和”。

另一个故事，某日老师告诉小明“今天要教你一个定理，勾股定理。

”小明说，“什么是勾股定理呢？”“勾股定理是说，直角三角形中有两条边的平方和等于第三边的平方。

”然后老师给了一大堆直角三角板给小明，让他去验证。

两个小时后，小明告诉老师定理是正确的.
两个故事刚好是语法分析里面对应的两个方法：第一个故事说的是自底向上的分析方法，第二个故事说的是自顶而下的分析方法。

在三维建模软件里也存在这个问题:
自底向上就是先建零件图，然后去组装装配图！三维网技术论坛; b2 c2 d( t9 G" k
自顶向下就是先建装配图，再在装配图中建零件图！
或者先建立一个总装配体的零件图，然后切割成各个零件图!
两种分析方法的根本区别是：自底向上的分析，是从具体到抽象；自顶向下的分析，是从抽象到具体。

两种分析思路恰恰又是哲学思考问题的两大方向。

可见计算机科学与哲学也是相通的.。