1.自底向上分析方法的概述(Ɡàishù)一、规范归约-归约G=(VT,VN,S,P),α,β∈(VT∪VN)*,A→β∈P,αAwαβw。归约的过程是:已知αβw和产生式A→β，用产生式A→β左部A替换(tìhuàn)αβw中的β，得到符号串αAw。规范推导(最右推导)右句型(最右推导可得的句型，规范句型)。-规范归约规范归约是最右推导的逆过程。如果文法G是无二义的，那么，规范推导(最右推导)的逆过程必是规范归约(最左归约)。规范句型(jùxínꞬ)的特点：句柄后不会出现非终结符号。二、自底向上分析方法-自底向上分析方法——移进—归约“移进一归约”分析器使用一个栈和一个存放(cúnfàng)输入符号串w的缓冲器。-分析器的初始状态为:栈剩余输入符号串#w#-工作过程：自左至右把串w的符号一一移进栈里，边移进边归约。一旦栈顶形成句柄时，就进行归约。这种归约可能持续(chíxù)多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至分析器的终止状态为:栈剩余输入符号串#S#工作模型：堆栈的初始状态与终止状态；移进／归约／接受／出错(chūcuò)，一共四种动作（暂不理会什么是可归约串）直观理解：栈中符号串加上未扫描的输入串即是一个（右）句型；可归约串：最左素短语（算符优先分析法）句柄（LR分析法）模型要点：可归约串总是在栈顶出现，绝不会出现在栈内部(一旦形成可归约串则必须立即归约)实现目标：自左向右扫描一次输入串且在每一时刻仅需要看到一个单词。二.算符优先(yōuxiān)分析法一、简单算符优先分析方法按照文法符号(fúhào)(终结符或非终结符)的优先关系确定句柄的。1.优先关系1)X≡Y表示X和Y的优先关系相等1)X≡Y当且仅当文法中存在产生式A…XY...P例若文法(wénfǎ)G[S]:SbAbA(B|aBAa)例若文法(wénfǎ)G[S]:SbAbA(B|aBAa)例若文法(wénfǎ)G[S]:SbAbA(B|aBAa)这三种关系(guānxì)也可以有语法树来得到这三种关系也可以有语法(yǔfǎ)树来得到这三种关系也可以(kěyǐ)有语法树来得到从矩阵表可以看出:(1).矩阵元素要么只有一种关系，要么为空，元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系，在分析中若遇到(yùdào)这种相邻关系出现，则为错，也可以肯定输入符号串不是该文法的句子。(2).#的优先级<所有符号，所有符号>#(符号与#相邻时)简单优先文法的定义若一个文法是简单优先文法必须满足以下条件:(1).在文法符号集V中，任意两个符号之间最多只有一种优先关系成立(chénglì)。(2).在文法中任意的两个产生式没有相同的右部。简单优先分析法算法:首先构造相应优先关系矩阵(1).将输入符号串a1a2…an#依次逐个存入符号栈S中，直到遇到(yùdào)栈顶符号ai的优先性>下一个待输入符号aj为止。(2).栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak,即找到ak-1<ak为止。(3).由句柄ak…ai在文法的产生式中查找右部为ak…ai的产生式，若找到则用相应左部代替句柄，若找不到则出错，这时可以断定输入符号不是的句子。(4).重复上述(1)、(2)、(3)步骤直到归约完输入符号串，栈中只剩文法开始符号为止。自底向上分析方法是一种移进一归约过程(guòchéng)，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程(guòchéng)中如何确定句柄。LR分析法正是(zhènꞬshì)给出一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K＞0）符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是规范归约过程。1.LR分析的三个组成：1).总控程序:对所有LR分析器都是相同的2).分析表或分析函数（ACTION、GOTO)不同文法分析表是不一样的,同一文法采用(cǎiyòng)的LR分析器不一样,分析表也是不一样的.3).分析栈文法符号栈和相应的状态栈.ACTION［Si,a]规定了栈顶状态为Si时遇到输入符号a应执行的动作(dòngzuò)。动作(dòngzuò)有4种可能：1）移进：把Sj=GOTO［Si,a］移入到状态栈，把a移入到文法符号栈。其中i,j表示状态号。2）归约：当在栈顶形成句柄为β时，则用β归约为相应的非终结符A，即文法