自顶向下语法学习教案.ppt

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bAb
A(B|a
BAa)例若文法(wénfǎ)G[S]:
SbAb
A(B|a
BAa)例若文法(wénfǎ)G[S]:
SbAb
A(B|a
B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，即文法