1、1盛威网：专业的计算机学习网站指导教师指导教师:杨建国杨建国二零零七年十一月二零零七年十一月2盛威网：专业的计算机学习网站第6章自底向上优先分析语法分析推导推导p自上而下的语法分析过程p预测分析程序，递归下降分析法（最左推导）p注：要求文法是LL(1)文法归约p自下而上的语法分析过程p简单优先分析法，算符优先分析法，LR分析法3盛威网：专业的计算机学习网站1.1.自底向上优先分析概述自底向上优先分析概述2.2.简单优先分析（简单优先分析（优先关系的理解优先关系的理解）3.3.算符优先分析算符优先分析 确定句型的短语、直接短语、句柄、确定句型的短语、直接短语、句柄、素短语、素短语、最左素短语最左
2、素短语 算符优先关系矩阵的构造及输入串的过程分析算符优先关系矩阵的构造及输入串的过程分析学习目标学习目标4盛威网：专业的计算机学习网站v第一节第一节 自底向上优先分析概述自底向上优先分析概述v第二节第二节 简单优先分析法简单优先分析法v第三节第三节 算符优先分析法算符优先分析法v第四节第四节 典型例题及解答典型例题及解答教学内容教学内容5盛威网：专业的计算机学习网站知识结构知识结构6盛威网：专业的计算机学习网站从输入串开始，逐步进行从输入串开始，逐步进行“归约归约”，直至，直至归约到文法开始符号；或者说，从语法树的末归约到文法开始符号；或者说，从语法树的末端开始，步步向上端开始，步步向上“归约
3、归约”，直到根结点。，直到根结点。7盛威网：专业的计算机学习网站u引言引言 1.1.基本思想基本思想自下而上的语法分析过程是一个自下而上的语法分析过程是一个最左归约最左归约的过程，的过程，从输入串开始，朝着文法的开始符号进行归约，从输入串开始，朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程。直到到达文法的开始符号为止的过程。从语法树角度看从语法树角度看，是以输入符号串作为语法树的，是以输入符号串作为语法树的末端结点符号串，自底向上地构造语法树，使文末端结点符号串，自底向上地构造语法树，使文法开始符号正好是该语法树的根。如果最终根结法开始符号正好是该语法树的根。如果最终根结点是开始
4、符号，则输入符号串是语言的一个句子，点是开始符号，则输入符号串是语言的一个句子，否则不是。否则不是。自底向上分析过程实际上是一个不断进行直接归自底向上分析过程实际上是一个不断进行直接归约的过程。约的过程。注意：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列。 8盛威网：专业的计算机学习网站1、找出当前句型的句柄、找出当前句型的句柄 x （或句柄的变形）（或句柄的变形）2 2、找出以、找出以x x为右部的规则为右部的规则X Xx x 3 3、把、把x x规约为规约为X X，产生语法树的一枝产生语法树的一枝9盛威网：专业的计算机学习网站2.2.实现方式实现方式- -“移进归约移进
5、归约”方式方式 语法分析程序 语法表 a+b#输出带#p 自左至右把输入串的符号逐个自左至右把输入串的符号逐个移进移进栈栈【注注】初态时栈内仅有栈底符初态时栈内仅有栈底符“”，读头指在最左边的单词符号上。读头指在最左边的单词符号上。 p 若栈顶形成某个句型的句柄，就将此句柄用相应的若栈顶形成某个句型的句柄，就将此句柄用相应的产生式左部替换（产生式左部替换（归约归约），若再形成句柄，就继续替），若再形成句柄，就继续替换，直到栈顶不再形成句柄为止。换，直到栈顶不再形成句柄为止。p重复上面的过程直到栈顶只剩下重复上面的过程直到栈顶只剩下# #和文法的和文法的开始符号开始符号，同时输入串读完为止，这样
6、就认为识别了一个句子。同时输入串读完为止，这样就认为识别了一个句子。10盛威网：专业的计算机学习网站3.3.语法分析程序执行的动作语法分析程序执行的动作移进移进 读入下一个输入符号并压入栈内，读头后移；归约归约 检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式；接受接受 移进归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符； 报错报错 当识别程序察觉一个错误，因此输入符号串不是句子而无法继续识别工作时，调用一个出错处理子程序进行处理或停止。11盛威网：专业的计算机学习网站例例1：文法：文法GS：(1) S aAcBe(2) A b(3) A
7、Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进A 5） #aAb cde# 归约归约(AAb) 6） #aA cde# 移进移进 7） #aAc de# 移进移进B 8） #aAcd e# 归约归约(Bd) 9） #aAcB e# 移进移进11） #S # 接受接受S10） #aAcBe # 归约归约(S aAcBe)符号串符号串abbcdeabbcde是否是是否是GSGS的句子的句子对输入串对输入串a
8、bbcde#的移进的移进-归约分析过程归约分析过程SaAcBe aAcde aAbcde abbcde12盛威网：专业的计算机学习网站顺序扫描输入符号并依次移进栈栈顶部的符号串是否构成一句柄？YN进行一次归约输入串扫描完否？noY栈中仅有开始符号？noerror输入串合法，报告分析报告出口移进移进- -归约过程归约过程Y13盛威网：专业的计算机学习网站14盛威网：专业的计算机学习网站15盛威网：专业的计算机学习网站6.1自底向上优先分析概述1.1.优先分析器（优先分析器（Precedence ParserPrecedence Parser）简单优先分析法简单优先分析法算符优先分析法算符优先分析
9、法2.LR2.LR分析器分析器16盛威网：专业的计算机学习网站基本思想基本思想：按一定原则定义文法中所有符号：按一定原则定义文法中所有符号（终结符和非终结符）之间的优先关系，按照（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄并实行归约。这种关系确定归约过程中的句柄并实行归约。是一种规范归约。是一种规范归约。简单优先分析法准确、规范，但效率低，不实简单优先分析法准确、规范，但效率低，不实用，不流行。用，不流行。17盛威网：专业的计算机学习网站基本思想基本思想：只定义文法中终结符之间的优先：只定义文法中终结符之间的优先关系（关系（不考虑非终结符不考虑非终结符），并由这种关系指
10、），并由这种关系指导分析过程导分析过程不是规范归约不是规范归约算符优先分析法分析速度快，特别适用于表算符优先分析法分析速度快，特别适用于表达式的分析。缺点是不规范，常常要采用适达式的分析。缺点是不规范，常常要采用适当措施克服其缺点。当措施克服其缺点。 18盛威网：专业的计算机学习网站6.2简单优先分析法6.2.1 6.2.1 优先关系优先关系.+*.+（1 1） X XY Y当且仅当当且仅当G G中存在产生式规则中存在产生式规则 A AXYXY（2 2） X XY Y当且仅当当且仅当G G中存在产生式规则中存在产生式规则 A A XBXB，且，且B BY Y（3 3） X XY Y当且仅当当且
11、仅当G G中存在产生式规则中存在产生式规则 A ABDBD, ,且且B B X X和和D D Y Y20盛威网：专业的计算机学习网站 设设G G是已化简的文法是已化简的文法, ,s,ts,t V V, ,若若G G中存在规范句型中存在规范句型 = =stst, , 则则s,ts,t与与 的句柄之间的关系必有下述情况的句柄之间的关系必有下述情况之一之一: :1.1.s s在句柄在句柄中中, ,而而t t不不在句柄中在句柄中2.2.s s与与t t均均在句柄中在句柄中3.3.s s不在句柄不在句柄中中, ,而而t t在句在句柄中柄中对于上述情况对于上述情况, ,我们规定：我们规定：情况情况1 1:
12、 :stst; ;情况情况2 2: :s=ts=t; ;情况情况3 3: :ststA s t .A s t .A s t .21盛威网：专业的计算机学习网站 另外另外, ,还有一种情况还有一种情况, ,就是就是s s和和t t均不在句柄中均不在句柄中, ,那那么一定存在某句型使得它们进入上述三种情况之一。么一定存在某句型使得它们进入上述三种情况之一。 若若s s和和t t在任何句型中都不可能相邻出现在任何句型中都不可能相邻出现, ,则我们则我们规定二者规定二者。, ,这种优先关系是这种优先关系是的的! !22盛威网：专业的计算机学习网站在句型中，句柄内各相邻符号之间具有相同的优先级。u结论由
13、于句柄要先归约，所以规定句柄两端符号的优先级 要比位于句柄之外的相邻符号的优先级高。 句型中NiNj是句柄，则 N1Ni-1 N Ni i N Nj j Nj+1Nn .【注】优先分析法基本思想也可以表述为： 若句型中N Ni iN Nj j是句柄，语法分析程序可以 通过寻找Ni-1 Ni和Nj Nj+1 这两个关系来确定句 柄的头尾，从而确定句柄进行归约。 .23盛威网：专业的计算机学习网站p我们可以通过两个相邻符号我们可以通过两个相邻符号S Si iS Si i+1+1之间的关系之间的关系来找到句柄：来找到句柄：S Si iS Si i+1+1在句柄内：必然有规则在句柄内：必然有规则UUS
14、 Si iS Si i+1+1S Si i在句柄内部，但是在句柄内部，但是S Si i+1+1在句柄之后，必然有规则在句柄之后，必然有规则UUS Si i，且存在规范句型，且存在规范句型USUSi+1i+1。如果如果S Si i+1+1在句柄内，而在句柄内，而S Si i在句柄外，那么必然存在在句柄外，那么必然存在规范句型规范句型S Si iU U，且有，且有USUSi i+1+1。24盛威网：专业的计算机学习网站如何确定优先关系？如何确定优先关系？例例2文法文法GS：(1) S bAb(2) A (B|a(3) B Aa)1.1.求求= =关系：关系：由由(1)(1)：b=Ab=A A=b
15、A=b由由(2)(2)：(=B(=B由由(3)(3)：A=aA=a a=) a=)注意：注意：行列与左右，空行列与左右，空4.#4.#3.3.求求 关系：关系：由由(1)(1)：BbBb ab ab )b)b由由(3)(3)：BaBa aa aa )a)a2.2.求求 关系：关系：由由(1)(2)(1)(2)：b bab ba由由(2)(3)(2)(3)：( ( A A ( (a( (.第二步：找句柄头第二步：找句柄头trjkiSk-1 Skkk-1 =SkSk+1Si 是句柄，用它查产生式表是句柄，用它查产生式表 与一产生式右部与一产生式右部相同相同Si=#且且trj=#结束结束ik，Si
16、UU是该产生是该产生式左部符号式左部符号errorii+1Si trjjj+1YNNYYNYYNerrorerrorN30盛威网：专业的计算机学习网站文法文法GS：(1) S bAb(2) A (B|a(3) B Aa)步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # b(aa)b# 2） #b (aa)b# 3） #b( aa)b# 4） #b(a a)b# 5） #b(A a)b# 6） #b(Aa )b# 7） #b(Aa) b# 8） #b(B b# 9） #bA b#10） #bAb #11） #S #对输入串对输入串b(aa)bb(aa)b# #的简单优先分析过程的简单优
17、先分析过程简单优先关系矩阵简单优先关系矩阵注意注意：何时移进，何时归约？：何时移进，何时归约？归约中如何确定句柄？归约中如何确定句柄？#b(a#b, ,移进移进b( , ,移进移进(a, ,用用Aa归约归约A=a , ,移进移进a=) , ,移进移进#b(Aa)b, ,用用BAa) )归约归约#b(BBb, ,用用A(B归约归约A=b, ,移进移进#bAbb#, ,用用SbAbSbAb归约归约接受接受31盛威网：专业的计算机学习网站6.2.4 6.2.4 简单优先分析法的优缺点简单优先分析法的优缺点优点：优点：技术简单 缺点：缺点：适用范围小，分析表尺寸太大。 32盛威网：专业的计算机学习网站
18、6.2.5 6.2.5 简单优先分析法的局限性简单优先分析法的局限性简单优先分析法是有局限性的，它只适应于简单优简单优先分析法是有局限性的，它只适应于简单优先文法，但是程序设计语言的文法一般都不是简单先文法，但是程序设计语言的文法一般都不是简单优先文法，即使是关于表达式的文法也不是简单优优先文法，即使是关于表达式的文法也不是简单优先文法。如果要使用简单优先文法，就必须修改相先文法。如果要使用简单优先文法，就必须修改相应语言的文法，使之成为简单优先文法。应语言的文法，使之成为简单优先文法。例例3 3 设文法设文法G G：E EE+T|TE+T|T T TT T* *F|FF|F E E（E E）
19、|i|i33盛威网：专业的计算机学习网站【解】因为有EE+T，所以有+=T，但由于T T*F，所以有+. + +( ( = = ) )40盛威网：专业的计算机学习网站注意：注意： 是三种有序关系，与数学中的是三种有序关系，与数学中的 不同，所以不同，所以a=ba=b不意味不意味b=ab=a，abab不意不意味味bab +) +，在在(E+T)(E+T)中得中得 + )+ )41盛威网：专业的计算机学习网站a1 a2 a3 ai an# 优先关系表优先关系表总控程序总控程序X1Xn-1Xn#分析器的逻辑结构：分析器的逻辑结构：优先关系表、分析栈、总控程序优先关系表、分析栈、总控程序文法符号文法符
20、号42盛威网：专业的计算机学习网站EE+E|E-E|EEE+E|E-E|E* *E|E/E|EE|E/E|E E|(E)|iE|(E)|i 二义性文法的句子往往有不同的规范推导，句子i+i*i的两种不同的规范归约过程如下：第一个规范归约过程第一个规范归约过程(1) i+i(1) i+i* *i i(2) E+i(2) E+i* *i i(3) E+E(3) E+E* *i i(4) E+E(4) E+E* *E E(5) E+E(5) E+E(6) E(6) E第二个规范归约过程第二个规范归约过程(1) i+i(1) i+i* *i i(2) E+i(2) E+i* *i i(3) E+E(3
21、) E+E* *i i(4) E(4) E* *i i(5) E(5) E* *E E(6) E(6) Ei i是句柄是句柄E+EE+E是句柄是句柄43盛威网：专业的计算机学习网站u按按传统的习惯规定传统的习惯规定优先级从优先级从高到低为高到低为:（0 0）i i的优先级最高的优先级最高（1 1） 优先级次于优先级次于i i，右结合，右结合（2 2）* *和和/ /优先级次之，左结合优先级次之，左结合（3 3）+ +和和- -优先级最低，左结合优先级最低，左结合（4 4）括号）括号( (, ,) )的优先级大的优先级大于括号外的运算符，小于括号于括号外的运算符，小于括号内的运算符，内括号的优先
22、性内的运算符，内括号的优先性大于外括号大于外括号（5 5）# #优先性低于与其相邻的优先性低于与其相邻的算符算符+-*/ ()i#+-*/ (=i#-*/ (=i#P-QRQR 例例GE: EEE|E*E |(E) |i GE: EEAE|(E)|i A|*注：算符文法保证了两个运算符之间只有一个操作数。注：算符文法保证了两个运算符之间只有一个操作数。 47盛威网：专业的计算机学习网站证明：用归纳法证明：用归纳法设设 是句子，是句子，S S，即，即S S 0 01 1.n-1n-1n n 1.1. 推导长度是推导长度是n n，归纳起点，归纳起点n n1 1时，时，S=S= 0 0 1 1 ，即
23、，即S S，必存在一个规则，必存在一个规则S S，而由算符文，而由算符文法的定义，文法的规则中无相邻的非终结符，满足性质法的定义，文法的规则中无相邻的非终结符，满足性质1 1。 2.2. 假设假设n1n1， n-1n-1满足性质满足性质1 1。若若 n-1n-1 A A ，A A为非终结符。由假设的为非终结符。由假设的 的尾符号和的尾符号和 的首符的首符号都不是非终结符，否则与假设矛盾。号都不是非终结符，否则与假设矛盾。又若又若A A是文法的规则，则有是文法的规则，则有 n-1n-1n n= = 而而A A是文法的规则，它不含两个相邻非终结符，所以是文法的规则，它不含两个相邻非终结符，所以 也
24、不含两个相邻的非终结符，满足性质也不含两个相邻的非终结符，满足性质1 1。* *性质性质1 1：在算符文法中，：在算符文法中，任意句型任意句型都不含两个相邻的非终结符。都不含两个相邻的非终结符。48盛威网：专业的计算机学习网站性质性质2 2：若：若AbAb或或bAbA出现在算符文法的句型出现在算符文法的句型 中，其中中，其中A A V VN N , ,b b V VT T, ,则则 中任何中任何含含b b的短语的短语必包含必包含A A。 证明：用反证法。证明：用反证法。由算符文法的性质由算符文法的性质1 1可知。可知。S S bAbA 若存在若存在B Bb b，（ b b是仅含是仅含b b但不
25、含但不含A A的短语）的短语）这时这时b b和和A A不同不同时归约，分属于不同的短语，时归约，分属于不同的短语，则必有则必有S SBABA ，这样在句型，这样在句型BABA 中，存在相邻的非终结符，中，存在相邻的非终结符，所以所以与性质与性质1 1矛盾矛盾。故：故： 中任何含中任何含b b的短语必包含的短语必包含A A，证毕。证毕。* *注意：含注意：含b b的短语必含的短语必含A A，含，含A A的短语不一定含的短语不一定含b b。49盛威网：专业的计算机学习网站优先关系的定义优先关系的定义定义定义6.2 6.2 设设G G是一个不含是一个不含产生式的算符文法，产生式的算符文法，A A、B
26、 B、C C是非终结符，是非终结符，a a、b b是终结符，则算符优先关系定义为：是终结符，则算符优先关系定义为：1)a=b iff文法中有形如文法中有形如 Aab或或A aBb2)ab iff文法中有形如文法中有形如 A Bb, 其中其中B a或或B aV +1)1)当栈顶为当栈顶为a a，预扫描的下一字符为，预扫描的下一字符为b b，应该执行移进操作，因，应该执行移进操作，因为为a a和和b b在同一个产生式在同一个产生式A A中。中。2)2)当栈顶为当栈顶为a a，预扫描的下一字符为，预扫描的下一字符为b b，应该执行移进操作，应该执行移进操作，期望先规约出期望先规约出B B，然后再试图
27、规约出，然后再试图规约出A A。3)3)当栈顶为当栈顶为a a，预扫描的下一字符为，预扫描的下一字符为b b，应该先执行规约操作，应该先执行规约操作，规约出规约出B B，然后再移入，然后再移入b b。50盛威网：专业的计算机学习网站以上三种关系存在语法子树如下图：51盛威网：专业的计算机学习网站算符优先文法的定义算符优先文法的定义定义定义6.3 6.3 设有一设有一OGOG文法文法, ,如果在任意两个终结符之间如果在任意两个终结符之间, ,至多至多只有上述关系中的只有上述关系中的一种一种成立成立, ,则称该文法为算符则称该文法为算符优先文法，也叫优先文法，也叫OPGOPG（operator p
28、recedence grammaroperator precedence grammar）文法。文法。结论结论: :算符优先文法是无二义的。算符优先文法是无二义的。例例GE: EEE|E*E |(E) |i EE+T| E-T|T TT*F| T/F|F F(E)|i52盛威网：专业的计算机学习网站例例8 8 文法文法GEGE：EE+E|EEE+E|E* *E|(E)|iE|(E)|i1.1. 所有规则中都没有相邻的非终结符，所以它所有规则中都没有相邻的非终结符，所以它是算是算符文法符文法OGOG。2.2. 由于由于EE+EE+E E 和和E EE E* *E E，所以有，所以有+ + * *
29、运算符运算符+ +和和* *之间存在两种不同的优先关系，所以之间存在两种不同的优先关系，所以该文法该文法不是算符优先文法不是算符优先文法OPGOPG。+ + +53盛威网：专业的计算机学习网站三三. .算符文法和算符优先文法定义的意义算符文法和算符优先文法定义的意义 这两个定义相当于对文法的句型和可归约的短语这两个定义相当于对文法的句型和可归约的短语做了如下规定：做了如下规定：设A1A2Ai-1AiAi+1An是文法G的一个句型， 1、若AiVN，则Ai-1、Ai+1 VT，即不许出现相继两个非终结符； 2、若B1B2Bm是当前可归约短语，并可归约为Ai，则：54盛威网：专业的计算机学习网站a
30、)B1B2Bm中不能有相继两个非终结符且相邻的终结符优先级别全相等；b)对于B1B2Bm中首终结符b有Ai-1 b；c)对于B1B2Bm中尾终结符b有b Ai+1。 注：实际上，可归约短语是某产生式右部符号串，所以通过检查G的每个产生式的每个候选式，可以查找出任意优先级相同的终结符序偶。要找出所有满足关系 和 的终结符序偶，就要找出各非终结符B的首终结符集和尾终结符集。55盛威网：专业的计算机学习网站6.3.3 6.3.3 算符优先关系表的构造算符优先关系表的构造p 由定义直接构造由定义直接构造p 由算法构造由算法构造p 由关系图形构造由关系图形构造1.1.求各个非终结符的首终结符集和尾终结符
31、集求各个非终结符的首终结符集和尾终结符集 u定义定义 （1 1）首终结符集首终结符集FIRSTVT(B)=FIRSTVT(B)=b|Bb|B b b或或B B CbCb.直观含义直观含义：对于非终结符：对于非终结符B B，其往下推导所可能出现，其往下推导所可能出现的的最左边最左边的终结符集合（允许其左边有一非终结符集）的终结符集合（允许其左边有一非终结符集）56盛威网：专业的计算机学习网站思考：思考：A ABaBaB Be eFIRSTFIRST（A A）？）？FIRSTVTFIRSTVT（A A）？）？FIRSTFIRST（B B）？）？FIRSTVTFIRSTVT（B B）？）？（2 2）
32、尾终结符集尾终结符集LASTVT(B)=LASTVT(B)=a|Ba|B a a或或B . B . aCaC 直观含义直观含义：对于非终结符：对于非终结符B B，其往下推导所可能出现，其往下推导所可能出现的的最右边最右边的终结符集合（允许其右边有一非终结符集）的终结符集合（允许其右边有一非终结符集）思考：思考：A ABaBaB Be eFollowFollow（A A）？）？LASTVTLASTVT（A A）？）？FollowFollow（B B）？）？LASTVTLASTVT（B B）？）？57盛威网：专业的计算机学习网站（1 1）= =关系关系n直接看产生式的右部，若出现了直接看产生式的右
33、部，若出现了AAabab或或AAaBbaBb, ,则则a a= =b b（2 2） 关系关系n求出每个非终结符求出每个非终结符B B的的FIRSTVT(B)FIRSTVT(B)n若若AAaBaB, ,则则 b bFIRSTVT(B),aFIRSTVT(B),a 关系关系n求出每个非终结符求出每个非终结符B B的的LASTVT(B)LASTVT(B)n若若AABbBb, ,则则 a aLASTVT(B),aLASTVT(B),a b b2.2.三种优先关系的计算三种优先关系的计算58盛威网：专业的计算机学习网站例例9 9文法文法GEGE：(0) (0) E#E#E#E#(1) EE+T(1) E
34、E+T(2) ET(2) ET(3) TT(3) TT* *F F(4) TF(4) TF(5)(5) FP FP F|PF|P(6) P(6) P(E)(E)(7) (7) PiPiFIRSTVT(EFIRSTVT(E)=#)=#FIRSTVT(E)=+,FIRSTVT(E)=+,* *, , ,(,i,(,i FIRSTVT(T)=FIRSTVT(T)=* *, , ,(,i,(,i FIRSTVT(F)=FIRSTVT(F)= ,(,i,(,i FIRSTVT(P)=(,iFIRSTVT(P)=(,iLASTVT(ELASTVT(E)=#)=#LASTVT(E)=+,LASTVT(E)=
35、+,* *, , ,),i,),i LASTVT(T)=LASTVT(T)=* *, , ,),i,),i LASTVT(F)= LASTVT(F)= ,),i,),i LASTVT(P)= ),iLASTVT(P)= ),i2)2)= =关系关系 逐条扫描产生式逐条扫描产生式, ,由由产生式产生式(0)(0)和和(6),(6),得得#=#=#，（，（= =）4)4) 关系关系找：找：AABbBb的产生式的产生式E# ,E# ,则则 LASTVT(E)#LASTVT(E)#E+ ,E+ ,则则 LASTVT(E)+ LASTVT(E)+ T T* * , ,则则 LASTVT(T)LASTVT
36、(T)* * P P , ,则则 LASTVT(P)LASTVT(P) E) E) , ,则则 LASTVT(E)LASTVT(E)3 3） 关系关系找：找：AAaBaB产生式产生式#E#E：则：则#FIRSTVT(E)#FIRSTVT(E)+T: +T: 则则+FIRSTVT(T) +FIRSTVT(T) * *F: F: 则则* *FIRSTVT(F)FIRSTVT(F) F: F: 则则 FIRSTVT(F)FIRSTVT(F)(E: (E: 则则(FIRSTVT(E)(FIRSTVT(E)注意技巧！注意技巧！1)1)求每个非终结符的求每个非终结符的FIRSTVTFIRSTVT和和LAS
37、TVTLASTVT59盛威网：专业的计算机学习网站表达式文法算符优先关系表：+*i()#+*i()#.60盛威网：专业的计算机学习网站1.1.构造构造FIRSTVTFIRSTVT集的两条规则集的两条规则若有产生式Aa或ABa,则aFIRSTVT(A)若aFIRSTVT(B)，且有产生式AB,则aFIRSTVT(A)2.2.构造构造FIRSTVTFIRSTVT集的算法集的算法（1 1）前期工作）前期工作 建立一个布尔数组建立一个布尔数组FmFm，nn(m(m为非终结符个数，为非终结符个数，n n为终为终结符个数结符个数) )和一个后进先出栈和一个后进先出栈STACKSTACK 将所有的非终结符排
38、序，用将所有的非终结符排序，用i iA A表示非终结符表示非终结符A A的序号，的序号，再将所有的终结符排序，用再将所有的终结符排序，用j ja a表示终结符表示终结符a a的序号的序号61盛威网：专业的计算机学习网站（2 2）算法目的）算法目的要使数组要使数组每一个每一个元素最终取值满足：元素最终取值满足：当且仅当当且仅当aFIRSTVT(AaFIRSTVT(A) )， FiFiA A，j ja a 的值为真的值为真（3 3）步骤）步骤【1】首先按第一条规则对数组元素赋初值为假，再经分析让所有初值为真的符号对(A, a)进栈STACK。【2】若栈不空，则逐项出栈记为(B, a)，对每个形如A
39、B的产生式，若FiA，ja为假，则变为真且(A, a)入栈；反复操作，直至栈空。62盛威网：专业的计算机学习网站（4 4）程序描述）程序描述PROCEDURE PROCEDURE INSERT(A,aINSERT(A,a);); IFIFNOT NOT FiFiA A，j ja a THEN THEN BEGIN BEGIN FiFiA A，j ja a:=TRUE:=TRUE PUSH(A PUSH(A，a a） ONTOONTOSTACKSTACK ENDEND INSERTINSERT过程说明：过程说明：当当aFIRSTVT(AaFIRSTVT(A) )时置时置FiFiA A，j ja
40、a为真为真，并将符号对（并将符号对（A,aA,a）下推到栈中）下推到栈中63盛威网：专业的计算机学习网站u主程序BEGINBEGIN（MAINMAIN）FORFORi i从从1 1到到m m，j j从从1 1到到n n DO DO FiFiA A，j ja a :=FALSE; :=FALSE; * */ /赋值符赋值符* */ / FOR FOR 每个形如每个形如A Aa a或或A ABaBa的产生式的产生式 DODOINSERTINSERT（A,aA,a) ) WHILE STACK WHILE STACK 非空非空DODO BEGIN BEGIN 把把STACKSTACK的顶项记为（的顶
41、项记为（B,aB,a）弹出去）弹出去 FORFOR每个形如每个形如A AB B的产生式的产生式DODOINSERTINSERT（A,aA,a) ) ENDENDENDEND（MAINMAIN）64盛威网：专业的计算机学习网站例例1010文法文法GEGE：(0) (0) E#E#E#E#(1) EE+T(1) EE+T(2) ET(2) ET(3) TT(3) TT* *F F(4) TF(4) TF(5)(5) FP FP F|PF|P(6) P(6) P(E)(E)(7) (7) PiPi 第一次扫描产生式后，栈第一次扫描产生式后，栈STACKSTACK的初的初值为：值为：（6 6） （P
42、P，i )i )（5 5） （P P，( )( )（4 4） （F F，) )（3 3） （T T，* * ) )（2 2） （E E，+ )+ )（1 1） （EE，#)#)由产生式由产生式F FP P，T TF F，E ET T栈顶（栈顶（6 6）的内容逐次改变为：）的内容逐次改变为：（F,iF,i) )，（，（T,iT,i) )，（，（E,iE,i) )65盛威网：专业的计算机学习网站再无右部以再无右部以E E开始的产生式所以（开始的产生式所以（E,iE,i) )弹出后无进栈项，弹出后无进栈项， 这时栈顶（这时栈顶（5 5）为（）为（P P，( () )，同样由产生式：，同样由产生式：
43、F FP P，T TF F，E ET T当前栈顶（当前栈顶（5 5）的变化依次为：）的变化依次为： （F,( )F,( )， （T,( ) T,( ) ，（，（E,( )E,( ) （E,( )E,( )弹出后无进栈项弹出后无进栈项, ,此时当前栈顶（此时当前栈顶（4 4）为（）为（F F，），），由产生式由产生式T TF F，E ET T当前栈顶（当前栈顶（4 4）的变化依次为：）的变化依次为： （T, )T, )， （E,) E,) （E, )E, )弹出后无进栈项弹出后无进栈项当前栈顶（当前栈顶（3 3）为（）为（T,T,* *），由产生式），由产生式E ET T，栈顶（，栈顶（3 3）
44、变为）变为（E E，* *），以下逐次弹出栈顶元素后，都再无进栈项，直至栈空），以下逐次弹出栈顶元素后，都再无进栈项，直至栈空66盛威网：专业的计算机学习网站由算法可知，凡在栈中出现过的非终结符和终由算法可知，凡在栈中出现过的非终结符和终结符对，在相应数组元素的布尔值为真，在下表的结符对，在相应数组元素的布尔值为真，在下表的数组中用数组中用“1 1”表示表示+*i()#EETFP布尔数组的值布尔数组的值1 11 11 11 11 11 11 11 11 11 11 11 11 11 11 167盛威网：专业的计算机学习网站由上表，我们得出由上表，我们得出FIRSTVTFIRSTVT（A A）集
45、合为：）集合为：FIRSTVTFIRSTVT（EE）FIRSTVTFIRSTVT（E E） + +，* *，( (，i iFIRSTVTFIRSTVT（T T） * *，(，iFIRSTVTFIRSTVT（F F） ，( (，i i FIRSTVTFIRSTVT（P P） ( (，i i与直接由定义计算结果相同。与直接由定义计算结果相同。68盛威网：专业的计算机学习网站3.3.构造构造LASTVTLASTVT集的两条规则集的两条规则若产生式若产生式AAa a，或，或AAaBaB，则，则aLASTVT(AaLASTVT(A) )若有产生式若有产生式AAB B，且，且aLASTVT(BaLASTV
46、T(B) )，则，则aLASTVT(AaLASTVT(A) )4.4.构造构造LASTVTLASTVT集的算法集的算法69盛威网：专业的计算机学习网站70盛威网：专业的计算机学习网站图中的结点为某个非终结符的图中的结点为某个非终结符的FIRSTVTFIRSTVT集或终结符集或终结符对每一个形如对每一个形如A Aa a和和A ABaBa的产生式，则构造由的产生式，则构造由FIRSTVTFIRSTVT（A A）结点到终点符结点用箭弧连接的图形）结点到终点符结点用箭弧连接的图形对每一形如对每一形如A AB B的产生式，则对应图中由的产生式，则对应图中由FIRSTVTFIRSTVT（A A）结点到）结
47、点到FIRSTVTFIRSTVT（B B）结点用箭弧连接）结点用箭弧连接若某一非终结符若某一非终结符A A的的FIRSTVTFIRSTVT（A A）经箭弧有路径能）经箭弧有路径能到达某终结符结点到达某终结符结点a a，则有，则有aFIRSTVTaFIRSTVT（A A）71盛威网：专业的计算机学习网站FIRSTVT(E)FIRSTVT(E)FIRSTVT(T)FIRSTVT(F)FIRSTVT(P)#+* ( i练习：用关系图求每个非终结符的练习：用关系图求每个非终结符的LASTVT(A)LASTVT(A)的集合的集合72盛威网：专业的计算机学习网站for for 每条产生式每条产生式BXBX
48、1 1X X2 2X Xn n for(ifor(i=1;i=1;in;in;i+)+) if ( X if ( Xi i和和X Xi+1i+1都是终结符都是终结符) ) X Xi iX Xi i+1+1; ; if (i= n-2 if (i= n-2 且且 X Xi i和和X Xi i+2+2为终结符，为终结符， X Xi+1i+1为非终结符为非终结符) ) X Xi i =X =Xi i+2+2; ; if (Xif (Xi i为终结符而为终结符而X Xi+1i+1为非终结符为非终结符) ) for FIRSTVT(X for FIRSTVT(Xi+1i+1) )中的每个元素中的每个元素
49、b b X Xi ibXbXi+1i+1; ; 73盛威网：专业的计算机学习网站例例11 11 试构造例试构造例1010中文法中文法GEGE的优先关系表。的优先关系表。 可根据优先关系表判断该文法是否为算符优先文法可根据优先关系表判断该文法是否为算符优先文法如果表中元素不存在冲突，即如果表中元素不存在冲突，即文法的任何终结符至多只文法的任何终结符至多只存在一种优先关系存在一种优先关系，则该文法是一个算符优先文法，则该文法是一个算符优先文法74盛威网：专业的计算机学习网站n算符文法的任一句型有如下形式（不允许算符文法的任一句型有如下形式（不允许N Ni i相连）：相连）：#N#N1 1a a1
50、1N N2 2a a2 2.N.Nn na an nN Nn+1n+1#,#,若若N Ni ia ai i.N.Nj ja aj jN Nj+1j+1为句为句 柄，则有柄，则有a ai-1i-1 a ai+1i+1n根据算符优先文法的定义可知算符优先分析句型有如根据算符优先文法的定义可知算符优先分析句型有如下下性质性质： 如果如果aNbaNb（或（或abab）出现在句型）出现在句型r r中，则中，则a a和和b b之间有之间有且只有一种优先关系即且只有一种优先关系即若若a ab b则在则在r r中必含有中必含有b b而不含而不含a a的短语存在的短语存在若若a ab b则在则在r r中必含有中
