第五章 自下而上分析法
自下面上的分析，是从输入符号串出发，试图归约到文法的开始符号。分析过程中，每次选择与某个产生式右部符号串相同的一个子串进行归约。它要解决的关键问题是如何确定一个可归约的子串。
.自下而上分析过程
(1)设置一个存放符号的栈称为符号栈，用于记录分析的过程和确定下一步的动作。
(2)把输入符号按扫描顺序逐个移进栈里(符号栈)，当栈顶的符号组成的符号串形成一个可归约串时(正好是某条产生式的右部)，就进行归约。即把该符号串用与它对应的产生式左部的非终结符号代替，仍然置于栈顶。
(3)接着检查新栈顶，若形成新的可归约串，再进行归约，若没有形成新可归约串，则从符号串中移进新的符号。如此重复，直到整个输入符号串处理完毕为止。
(4)若最终栈底为识别符号，则表明所分析的输入串合法，报告分析成功；否则是不合法的符号串，报告出错信息。
2.1.短语
定义:令G是一个文法，S是文法的开始符号，假定abc是文法G的一个句型
其中α,b,c∈(VN∪VT)*，A∈Vn ，如果有
* +
S = >aAc且A = >b
则b称是句型abc相对于非终结符A的短语。
2.2直接短语：
如果有A=>b,则称b是句型abc相对于规则A->b的直接短语。
2.3一个句型的最左直接短语称为该句型的句柄
思路：
定义算符之间优先关系，借助这种关系来寻找“可归约串”和进行归约
a =.b 表示a的优先性等于b
a >.b 表示a的优先性大于b
a <.b 表示a的优先性小于b
注意：
=. >. <. 不同于数学上的 = < >
a =.b 不一定对应着 b =. a
a >.b 不一定对应着 b <. a
a <.b 不一定对应着 b >. a
4. 算符文法
一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：
…QR…
则我们称该文法为算符文法，也称OG文法 (Operater Grammar) 。
约定：
a、b代表任意终结符；
P、Q、R代表任意非终结符；
‘…’代表由终结符和非终结符组成的任意序列，包括空字
通过检查产生式的每一个候选式可以找出满足a=.b
（即P→…ab…或P→…aQb…的产生式）
(2)为了满足<.和>.，需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：
5.算符优先分析算法和设计
(1)句型的一般表示形式：
#N1a1N2a2…NnanNn+1#
其中，每个ai都是终结符，Ni是可有可无的非终结符
(2)定理：
一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj…NiaiNi+1，
aj-1 <. aj
aj =. aj+1，aj+1 =. aj+2，…，ai-1 =. ai
ai >. ai+1
注意：
出现在左端或右端的非终结符一定属于这个素短语
6.优先函数的构造方法
如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数:
(1)对于每个终结符a，令其对应两个符号fa和ga，画一张以所有符号fa和ga为结点的方向图。如果a>.b，则从fa画一条弧至gb如果a<.b，则从gb画一条弧至fa 。
(2)对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)赋给ga的数作为g(a)。
(3)检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。
7.动作表：
ACTION[s，a]：
当状态s面临输入符号a时，应采取什么动作
状态转换表：
GOTO[s，X]：
状态s面对文法符号X时，下一状态
列表
(1)动作表
ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作
每一项ACTION[s，a]所规定的四种动作:
<1>. 移进
<2>. 归约
<3>. 接受
<4>. 报错
学后感：
随着越往后学，知识的难度，广度，深度也越来越大，在听懂和听不懂的边缘徘徊，可能会徘徊回来吧。