下载文档原格式
第六章自底向上优先分析方法•教学要求：了解简单优先分折法，掌握算符优先分析法的关系表的构造以及分析过程。
•教学重点：算符优先表构造及算符优先分析法。
1自底向上分析法的基本思想•从输入串开始，朝着文法的开始符号进行最左归约，直到到达文法的开始符号为止。
•工作方式：“移进－归约”方式。
2分析程序模型1）初态时栈内仅有栈底符“＃”，读头指针在最左单词符号上。
2）语法分析程序执行的动作：a）移进读入一个单词并压入栈内，读头后移；b）归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；c）识别成功移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符；d）识别失败语法分析程序语法表a+b……#输出带#3例如：有文法如下（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d问：语句abbcde是不是该文法的合法语句？4•例：设文法G(S)：(1) S aAcBe(2) A b(3) A Ab(4) B d 试对abbcde进行“移进－归约”分析。
bbcde bbcde b cde de deabbcde eB cA a SB A a 5成功11接受2,3,4,1＃＃S 10归约＃＃aAcBe 9移进2,3,4e ＃＃aAcB 8归约e ＃＃aAc d 7移进de ＃＃aAc 6移进2,3cde ＃＃aA 5归约cde ＃＃a Ab 4移进2bcde ＃＃aA 3归约bcde ＃＃a b 2移进bbcde ＃＃a 1移进abbcde ＃＃0动作输出带输入串栈步骤移进归约的分析过程G[S]:（1）S →aAcBe（2）A →b（3）A →Ab（4）B →d 6遇到的问题：（1）如何找出进行直接归约的简单短语？（2）找出的简单短语应直接归约到哪一个非终结符？关键：确定句柄.常用的分析方法:（1）优先分析法（2）LR分析法7b db ac eSA B A d b a c e S A B A d a c eSA B a c e A B S 没有语法树如何确定句柄？86.1 自底向上优先分析法概述•基本思想：利用文法符号中相邻符号之间的优先关系（谁先规约的优先关系）找出句柄。
五、语法分析——自底向上分析法已知文法G：EE+TE TTT*FTFF(E)Fi（1）求文法G中每个非终结符的First集和Follow集。
（2）构造文法G的SLR(1)预测分析表。
（20分）首先构造增广文法：SEEE+TE TTT*FTFF(E)FiFirst(S)=First(E)=First(T)=First(F)={(,I)Follow(S)={#} Follow(E)={+,#,}}Follow(T)={+,},#,*} Follow(F)={+,},#,*}状态Action Gotoi + * ( ) # E T F0 S5 S4 1 2 31 S6 Acc2 r 2 S7 r 2 r 23 r4 r 4 r 4 r44 S5 S4 8 2 35 r6 r 66 S5 9 37 S5 108 S6 S119 r 1 S7 r 1 r 110 r 3 r 3 r 3 r 311 r 5 r 5 r 5 r 5注：识别可归前缀的DFA共12项。
词法分析——确定性有穷自动机为以下字符集编写正规表达式，并构造与之等价的最简DFA（写出详细的具体过程）：在字母表{a,b}上的包含偶数个a且含有任意数目b的所有字符串。
（15分）（b*ab*ab*）*b a b1a状态Action GOTOa b d e f $ S R T0 S3 11 acc2 r2 S3 r2 r2 53 S6 S4 24 r4 r4 r4 r45 S10 96 77 S88 r3 r3 r3 r39 r1 r1 r110 r6 S6 S4 r6 r6 1111 S1212 r5 r5 r5五、语法分析——自底向上分析法已知文法G：S’SS bRSTS bRRdSaR eTfRaTf（1）求文法G中每个非终结符的First集和Follow集。
（2）构造文法G的SLR(1)预测分析表。
（20分）frist(s’)={b} follow(s’)={$}frist(s)={b} follow(s)={f,a, $}frist(R) ={d,e} follow( R )={a,b,f, $}frist(T)={t} follow (T)={a,f,#}五、对下面的文法（15分）S->UTa|TbT->S|Sc|dU->US|e判断是否为LR(0),SLR(1)，说明理由，并构造相应的分析表。
编译原理LR分析法编译原理中的LR分析法是一种自底向上的语法分析方法，用于构建LR语法分析器。
LR分析法将构建一个识别句子的分析树，并且在分析过程中动态构建并操作一种非常重要的数据结构，称为句柄(stack)。
本文将详细介绍LR分析法的原理、算法以及在实际应用中的一些技巧。
1.LR分析法的原理LR分析法是从右向左(Right to Left)扫描输入串，同时把已处理的输入串的右侧部分作为输入串的前缀进行分析的。
它的核心思想是利用句柄来识别输入串中的语法结构，从而构建分析树。
为了实现LR分析法，需要识别和操作两种基本的语法结构：可规约项和可移近项。
可规约项指的是已经识别出的产生式右部，可以用产生式左部进行规约。
可移近项指的是当前正在处理的输入符号以及已处理的输入串的右侧部分。
2.LR分析法的算法LR分析法的算法包括以下几个步骤：步骤1: 构建LR分析表，LR分析表用于指导分析器在每个步骤中的动作。
LR分析表包括两个部分：动作(Action)表和状态(Goto)表。
步骤2: 初始化分析栈(stack)，将初始状态压入栈中。
步骤3:从输入串中读取一个输入符号，并根据该符号和当前状态查找LR分析表中的对应条目。
步骤4:分析表中的条目可能有以下几种情况：- 移进(shift)：将输入符号移入栈中，并将新的状态压入栈中。
- 规约(reduce)：将栈中符合产生式右部的项规约为产生式左部，并将新的状态压入栈中。
- 接受(accept)：分析成功，结束分析过程。
- 错误(error)：分析失败，报告错误。
步骤5:重复步骤3和步骤4，直到接受或报错。
3.LR分析法的应用技巧在实际应用中，为了提高LR分析法的效率和准确性，一般会采用以下几种技巧：-使用LR分析表的压缩表示：分析表中的大部分条目具有相同的默认动作（通常是移进操作），因此可以通过压缩表示来减小分析表的大小。
-使用语法冲突消解策略：当分析表中存在冲突时，可以使用优先级和结合性规则来消解冲突，以确定应该选择的操作。
第五章自底向上优先分析法自底向上优先分析法，其基本思想是采用自左向右扫描，向下而上分析。
该类分析方法是从输入符号串开始，查找句柄，并使用规则把它归约成相应的非终结符号。
任何自底向上分析的关键，就是要找出这种句柄。
本章首先介绍自底向上分析一般过程，然后介绍算符优先分析法。
本章重点：句柄、算符优先分析法第一节自底向上分析一般过程。
先举例说明例1有一文法G[S]S→aAcBeA→bA→AbB→d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。
它的最右推导是：S⇒aAcBe⇒aAcde⇒aAbcde⇒abbcde 由此我们可以构造它的逆过程即归约过程。
先设一个先进后出符号栈，并且把句子左括号“#”号放入栈底，其分析过程如下所示上述归约过程，是从输入符号串开始，自底向上地通过归约当前句型的句柄来建立语法树的。
我们不难画出上述分析过程的语法树，下图。
在图中，我们仅画出与生成语法树有关的几步。
从所建立的语法树，可以清楚看出，上述每一步确实都是归约当前句型的句柄。
且句柄出现在符号栈栈顶，不会在栈中间，其实上述分析过程并未真正解决句柄的识别问题。
例如，对于上面的例子，分析进行到第（5）步，当时栈内符号串为aAb。
根据该符号串，我们有规则A→Ab。
和规则A→b。
那么，符号串Ab和b都是某条规则的右部，故都有可能被判别是句型的句柄。
假如我们选择b作为句柄，并把b归约为A，那么，最终就达不到归约到S的目的。
因而，我们也就无从得知输入串abbcde是一个句子了。
在自底向上分析中，如何寻找确定一个句型的句柄是构造一个自左向右扫描，自底向上分析方法必须要解决的一个问题。
第二节算符优先分析法众所周知，作算术式的四则运算时，为了保证计算过程和结果的唯一性，必须要规定一个统一四则运算法则。
这种法则的主要方面，就是规定运算之间的优先顺序。
现在人们所遵循的统一法则是：乘除运算优先于加减运算，故在算术中要先作乘除运算后作加减运算；同优先级的运算符是先左后右（即左结合），先作左边的运算符的运算，后作右边运算符的运算。
第五章语法分析——自下而上分析要紧内容:[1]自下而上分析的大体问题[2]算符优先分析法[3]算符优先分析表和优先函数的构造[4]LR分析器的大体原理大体要求:[1]明白得自下而上分析法的大体思想[2]明白得有关归约、短语、句柄、标准归约等概念[3]把握算符优先分析法[4]了解算符优先表和优先函数的构造技术[5]了解LR 分析器大体原理和工作方式教学要点：本章介绍自下而上语法分析方式。
所谓自下而上分析法确实是从输入串开始，慢慢进行“归约”，直至归约到文法的开始符号；或说，从语法树的结尾开始，步步向上“归约”，直到根结。
讲义摘要：5.1 自下而上分析大体问题自下而上分析法的大体思想：从输入串开始，慢慢进行“归约”，直到文法的开始符号。
即从树结尾开始，构造语法树。
所谓归约，是指依照文法的产生式规那么，把产生式的右部替换成左部符号。
自上而下分析的核心问题是：如何判定符号串的可归约性，和如何归约。
即，识别可归约串的问题。
归约自下而上分析法事实上确实是一种“移进－归约”法，即，采纳“移进－归约”思想进行。
实现思想是：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句型对应某产生式的右部，即栈顶生成了某产生式的右部的文法符号串），就将栈顶的这一部份替换成 (归约为) 该产生式的左部符号，这称为归约。
重复这一进程直到归约到栈中只剩文法的开始符号时那么为分析成功，也就确认输入串是文法的句子。
现举例说明。
例1：设文法G[S]为：(1) S→aAcBe(2) A→b(3) A→Ab(4) B→d试对abbcde进行“移进－归约”分析。
步骤: 1 2 3 4 5 6 7 8 9 10解：动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1)表1符合栈的转变进程自下而上语法分析的进程也可看成自底向上构造语法树的进程，每步归约都是构造一棵子树，最后当输入串终止时恰好构造出整个语法树，如图1所示。
