编译原理 第07章new.ppt

第七章 LR分析 高晓雷 gaoxl@dgut.edu.cn 学习目标 理解LR分析法的基本思想 理解可归前缀和子前缀概念 理解识别活前缀的有限自动机概念 掌握LR分析器的构造思想和方法 对给定的文法能构造LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器，并能判断所给文法是四种分析器的哪几类。 对给定的输入符号串能用构造的分析器判断该输入串是否是所给文法的句子 了解某些二义性文法在LR分析中的应用。 难重点 可归前缀和子前缀概念 识别活前缀的有限自动机概念 对可归前缀为规范归约的句柄的理解 构造LR(1)项目集族时有哪些信誉好的足球投注网站符的计算 LR分析器的关键部分是分析表的构造 对给定的文法能构造LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器 当一个文法能构造出不含移进-归约或归约-归约冲突时的LR(0)/ SLR(1)/ LALR(1)/ LR(1)分析表时，称这个文法为LR(0) / SLR(1)/ LALR(1)/ LR(1)文法。 对给定的文法能判断是四种LR类文法的哪几类 了解某些二义性文法在LR分析中的应用 第七章 LR分析法 RL分析的特征: 规范归约 符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀) 分析决策依据栈顶状态和现行输入符号 识别活前缀的 DFA。 RL分析的优点： 适用范围广；分析速度快；报错准确。 构造分析器的工作量很大，不大可能手工构造；用软件工具yacc-Yet Another Compiler Compiler,Bell,1974. RL分析的四种分析法 LR(0) SLR(1) LR(1) LALR(1) LR驱动程序算法流程 7.2 LR(0)分析 LR(0)分析法 在分析的每一步只需根据当前栈顶的状态就能确定应采取何种动作(归约或移进) ，而不需要向前查看输入符号。 适用于LR(0)文法 LR(0)文法能力最弱，理论上最重要 存在FA识别活前缀 识别活前缀的DFA如何构造 （LR(0)项目集规范族的构造） LR(0)分析表的构造 拓广文法 引入一新非终结符作为文法的新开始符， 添加一新产生式： S’→S :S’为新开始符，S为原来的开始符号。 拓展文法的目的： 使文法只有一个以识别符号作为左部的产生式，从而使构造出来的分析器有唯一的接受状态。 S→aS|bc 7.2.2 识别活前缀的有限自动机（直观） 手工找出活前缀，然后，对每一个活前缀构造识别其的自动机 该自动机将文法中的终结符和非终结符一起作为自动机的输入字符，在可归前缀的两两符号之间加入状态而构成。 也可以把可归前缀看作正规式，由正规式构造等价的自动机。 例7.1文法G[S]的每条产生式编上序号用[i]表示加在产生式的尾部，使产生式变为： 　　S′→S[0] 　　S→aAcBe[1]　　A→b[2]　　A→Ab[3]　　B→d[4]　列出句子abbcde的可归前缀：　　S[0]　　Ab[2]　　aAb[3]　　aAcd[4]　　aAcBe[1] 7.2.3 活前缀和可归前缀的一般计算法 定义设G=（VN，VT，P，S）是上下文无关文法，对于A属于VN有 LC(A) ={?|S??(*R)?A?，??V*， ??V*T} 其中， S?是G的拓广文法G?的开始符。 LC(A)是句型?A?中A的左边缩出现的符号串的集合。 推论：若文法中有产生式B→?A?，则有： LC(A) ? LC(B)?? 由定义推论和文法的产生式我们可列出例6.1文法的方程组 LC(S?)＝{?} LC(S)＝ LC(S?) · {?}= {?} LC(A)＝LC(S) · {a} ? LC(A)· {?} = {a} LC(B)＝LC(S) ?{aAc}= {aAc} 也可等价地表示为正规式 LC(S?)＝? LC(S)＝ ? LC(A) = a LC(B)＝aAc 这里求出的是不包含句柄的的串 规定：LR(0)CONTEXT(A?? )=LC(A) ·? , LR(0)CONTEXT(A?? )可简写为LR(0)C (A?? ) 例6.1文法包含句柄的活前缀有 LR(0)C (S??S )=S LR(0)C (S?aAcBe )=aAcBe LR(0)C (A?b )=ab LR(0)C (A?Ab )=aAb LR(0)C (B?d )=aAcd 与上面求出的一样 例 设文法G’为：S′→ E，E→aA， E→bB， 　　A→cA，A→d，B→cB， B→d 求不包含句柄在内的活前缀方程组为： LC(S?)＝? LC(E)＝ LC(S?)