第06章 自底向上优先分析法

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

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

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

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

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

构造LRSM的思想： 如果在状态项目集ISi 中有项目A→B， 且B→是B的产生式，则在ISi 中增加项目 B→；对于ISi 这个过程继续到不可再扩 充为止。
构造LR(0)活前缀状态机LRSM的算法要点
构造初始状态 IS0：IS0=CLOSURE({Z→S})，并给 IS0标
Stack
LR分析模型
LR分析表
Action矩阵：行代表状态，列代表输入 符，而矩阵元素则表示相应的分析动作： Shift / Reduce / Accept / Error 。 GoTo矩阵：行代表状态，而列则代表语 法符号（非终极符，终极符），而矩阵 元素则表示移入或归约后的转向状态。 定义 若IS是一个LR(0)项目集，X是一个 文法符号，函数GO（IS, X）定义为 GO（IS, X）=CLOSURE（IS(X)），其中 IS(X)为LR(0)项目集IS的投影。
id
E→E+ T T→ id T→ (E)
E
7
S→E $ E→E +T
+
T→(E ) E→E +T
$
2 4
T
8
)
T→(E)
S→E $
E→E+T
GE的LRSM
LRSM给出了所有的可归活前缀
LRSM中的每个状态将对应一个饱和项目集： （1）其中一部分是由先驱状态分出来 (称为基本项目)； （2）一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“”出现在 产 生式右部的最左侧。

识别规约活前缀的LRSM的构造
派生定理


开始符产生式的右部是归约活前缀。 如果A是归约活前缀，且A→是产生式， 则也是归约活前缀。 任何归约活前缀，都可按上述方式被派生。 设文法开始符的产生式是： S →1|2|…|n RPSG={1,…,n}{|ARPSG,A→P}

自底向下和自顶向上的设计方法及流程下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。

文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢!本店铺为大家提供各种类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you! In addition, this shop provides you with various types of practical materials, such as educational essays, diary appreciation, sentence excerpts, ancient poems, classic articles, topic composition, work summary, word parsing, copy excerpts, other materials and so on, want to know different data formats and writing methods, please pay attention!自底向上和自顶向下的设计方法及流程概述软件设计是软件工程中至关重要的一环，而设计方法的选择直接影响了软件系统的质量和效率。

X >Y X…A Y …
当且仅当存在一个产生式A→…XB…
XB
并有B+Y…
…… BC …
X ⊲Y ：
…
当且仅当存在一个产生式A→…BC… .
并有B+…X，C*Y…
.
. ..… Y.
X
Y
文法G为简单优先文法如果满足： • 对于任意两个语法符号X和Y，至多成立一种 优先关系； • 任意两个产生式都具有不同的右部.
EE1 E1E1+ T1 | T1 T1T TT * F | F F(E) | i
)
i 实例
#
E FIRST E1 ,T1
E1 E1,T1
T1 T ,F ,( ,i
T T ,F ,( ,i
ห้องสมุดไป่ตู้F ( ,i
LAST E1 ,T1 ,T ,F ,),i T1 ,T ,F ,),i T ,F ,),i F ,),i
7
文法优先关系的确定
FIRST(W) ={S | W + S…，S(VNVT)} LAST(W) ={S | W + …S，S(VN VT)}
若有U…SiSj…: 则有Si Sj ; 若Sj有U…SiW…:任SjFIRST(W),有Si ⊲ Sj 若有U…VW…:任SiLAST(V), Sj(FIRST(W) {W})
Shift 3. M (L
Shift Shift
4. L Ma) 分析字符串：b(aa)b
Reduce[2]
Shift
#b(Ma
#b(Ma) ⊳
#b(L
⊳
#bM
#bMb
⊳
#Z
) b # Shift b # Reduce[4]