1、优点：(1)直观、简单、可读性好；（2)便于扩充。 2、缺点
(1)递归算法速度慢、占用空间多，其实现效率低；
(2)处理能力相对有限，要求文法必须为LL(1)文法，所以通用性差； (3)难以自动生成。
5.4.2 预测分析法
对于LL(1)型文法，可用预测分析法。在使用预测分析法时，必须先将文法化为LL(1)型文法。
一、预测分析器的构造
预测分析器由三部份组成： (1)预测分析表(矩阵)；
(2)先进后出栈：用来存放分析过程的语法符号； (3)预测分析程序。
二、预测分析表
1、预测分析表为一个二维矩阵，其形式为M[A，a]，其中A∈VN ，a∈VT或#。 2、若有产生式A→α，使得a∈SELECT(A→α)，则将A→α填入M[A，a]中。(书写时，通常省略规则左部，只填→α)。
3、对所有没有值的M[A，a]标记为出错。
例：文法G[E]：E→T E? E?→+T E?|ε T→ F T? T?→* F T?｜ε F→ ( E )｜i
解：计算G[E]的SELECT集：
SELECT(E→ T E?)={(，i} SELECT(E?→ + T E?)={+} SELECT(E?→ε)={#，)} SELECT(T→ F T?)={(，i} SELECT(T?→* F T?)={*} SELECT(T?→ε)={+，#，)} SELECT(F→( E ))={(} SELECT(F→i)={i}
根据SELECT集构造G[E]的预测分析矩阵M[X，a]如下：
四、预测分析程序
1、一些符号的约定
#：句子结束符；S：文法开始符；a：当前输入符号a，输入指针指向的符号；X：工作栈栈顶符号。 2、算法描述
#，S进栈 ; //初始化工作 do{
X=当前栈顶符号;a=当前输入符号； if (X∈ＶT∪{#}) {if (X==a)
{if (X ! =#) {将X弹出，且前移输入指针}} else error() }
else {
if (M[X，a]==Y1Y2…Yk )
{将X弹出;依次Yk…Y2Y1将压入栈;} else error()}; }while( X ! =#);
3、例：根据上例中G[E]的预测分析矩阵M[X，a]，对串w=i+i*i进行分析。
解：对输入串w=i+i*i#的分析过程如下表所示（注意：规则右部以逆序入栈）：
课堂作业：对输入串w=i*i+i*i#作分析。
作业：教材P99-101的1、2、4题，6题的（1）（2）（3）小题。
授课顺序：9
教学目的：让学生了解自底向上优先分析的基本思想，掌握优先关系、简单优
先文法的定义、简单优先分析法、直观算符优先分析法、算符优先文法的定义。
教学重点：优先关系表的构造、直观算符优先分析法的应用、算符优先文法的
定义
教学难点：优先关系表的构造、直观算符优先分析法的应用 授课学时：2学时
教学方式：多媒体讲授 教学内容：
第六章 自底向上优先分析法
6.1概述
一、知识回顾
1、最左推导(Left-most Derive)：每次推导都施加在句型的最左边的语法变量上。与最右归约对应。
2、最右推导(Right-most Derive)：每次推导都施加在句型的最右边的语法变量上。与最左归约（规范归约）对应，得规范句型。
3、令G[S]是一文法，αβδ是文法G的一个句型，如果有：S =*> αAδ，且A =+>β，则称β是句型αβδ相对于非终结符A的短语，如有A?β，则称β是αβδ相对于非终结符A或相对于规则A→β的直接短语(也叫简单短语) 。
4、一个句型的最左直接短语称为该句型的句柄。
注意： 作为短语的β必须是需要分析的句型αβδ的一部分。 5、规范归约：设α为文法 G的句子，如果： (1) α=αn<=αn-1<=…<=α2<=α1=Ｓ；
(2)对每个i(1≤i≤n)，αi-1是将句型αi中的句柄归约后得到的句型； 则称由规范归约组成的序列 αn，…，α1为α的规范归约序列。 例子：一个简单的归约过程示例。设文法为G[S]： S→aAcBe A→Ab|b B→d 解：对句子abbcde的分析：
二、自底向上分析
1、思想：从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。
2、核心：寻找句型中的“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法。
6.2 简单优先分析法
简单优先分析法的实现思想：按所有文法符号(包括非终结符和终结符)之间的优先关系来确定句柄。 一、优先关系
X≡Y：表示X和Y的优先关系相等； X≮Y：表示X比Y的优先性小； X≯Y：表示X比Y的优先性大。 1、优先关系的定义
X≡Y：当且仅当G中存在规则A→XY…。即XY并列出现。 X≮Y：当且仅当G中存在规则A→…XB…且B=+>Y…。即X与非终结符B并列（位于最前的Y经过至少一步归约后得到的B）。
X≯Y：当且仅当G中存在规则A→…BD…且B=+>…X和D=*>Y…。即非终结符B与D并列（位于最后的X经过至少一步归约后得到B，位于最前的Y经过0步或多步归约后得到D）。
2、例：G[S]：S→bAb A→(B|a B→Aa) 文法符号间优先关系如下：
≡： 由bA有b≡A，由Ab有A≡b，由(B有(≡B，由Aa有A≡a，由a)有a≡)； ≮： 因为 A?(B?(Aa)?(Ba)?…，A?(B?(Aa)?(aa)?…，A?a， 故由bA有b≮(，b≮a；因为 B?Aa)?(Ba)?(Aa) a)?…，B? Aa)?aa)，故由(B有(≮A，(≮(，(≮a；
≯： 因为 A?(B?(Aa)?(Ba)?…，A?(B?(Aa)?(aa)?…，A?a，故由Ab有B≯b，)≯b, a≯b；故由Aa有B≯a，a≯a，)≯a。
注意：对于符号S和#作特殊处理，定义#优先级≮所有与之相邻符号。所有与之相邻符号优先级≯#。
引入产生式S?→#S#来判断与#相邻符号与#的优先关系，且约定#≡#。
对前例：由#S有#≮S；由S?bAb和#S有#≮b；由S#有S≯#；由S?bAb和S#有b≯# 综上所述得如下优先关系矩阵：
二、简单优先文法的定义
(1)任意两符号间最多只有一种优先关系成立； (2)在文法中任意两产生式没有相同的右部。
三、简单优先分析法步骤
(1)将输入符号串a1a2a3…an#依次入栈，直到栈顶符号优先级高于下一个待输入符。 (2)以栈顶符号ai为句柄尾，往下找句柄头ak（当ak-1≮ak时，终止查找）， 并将句柄归约为一个非终结符，将句柄出栈，非终结符入栈；若无句柄可归约则报错。 (3)重复（1）和（2）。
(4)当栈中只剩S时，分析成功，否则报错。
课堂练习：根据前例对输入串b（aa）b#和b（aa）#用简单优先分析法进行分析。
四、简单优先分析法优缺点
准确、规范，分析效率低，实用价值不大。
6.3 算符优先分析法
6.3.1直观算符优先分析法
一、直观算符优先分析法中优先级和结合性的确定
1、算符优先文法只考虑算符(广义为终结符)之间的优先关系。 2、例G[E]：E→E+E|E*E|i， 对3+4*5#分析的过程如下：
3+4*5?E+4*5?E+E*5?E+E*E?E+E?E
思考：为何不将E+E归约成E?
关键：在于如何确定算符间的优先级和结合性。
3、直观算符优先分析法中优先级和结合性的确定方法：人为指定。
例：对文法E→E+E|E-E|E*E|E/E|E^E|(E) |i，我们可指定优先级和结合性如下： (1) 作运算对象的终结符i优先性最高； (2) ^右结合，且高于其它运算符(2^3^(2)，有：^≮^ , ^≯其它运算符，其它运算符≮^ ; (3) *，/高于+,-且左结合,有*≯*,*≯/,*≯+,*≯-, /≯*,/≯/,/≯+,/≯-,，+≯-,+≯+,-≯+,-≯-…
(4)括号的优先性大于括号外运算符，小于括号内运算符，内括号优先性大于外括号； (5) 对于#可#≮所有与之相邻符号；所有与之相邻符号优先级≯#。引入产生式E?→#E#来判断与之相邻符号。
对G[E?]：E?→#E# E→E+E|E-E|E*E|E/E|E^E|(E) |i有：