资源描述：
《编译原理及其习题解答（武汉大学出版社）课件chap5》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第五章自顶向下语法分析方法要点：1.了解下推自动机2.求解First,Follow,Select及LL(1)文法的判断3.非LL(1)到LL(1)的等价变换；（消除左递归等）4.预测分析表的构造和分析过程编译原理引言语法分析是编译的核心部分。语法分析的作用：识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序）。语法分析的常用方法：自顶向下分析和自底向上分析两大类。自顶向下分析法是指从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。若能找到“匹配”的产生式且最终推导出的句子与输入串一致，则这个输入串是文法给定的句子，否则不是文法的句子。注意：文法是指上下文无关
2、文法。5.1下推自动机(PDA)下推自动机很象不确定的有穷自动机，但是多了一个下推栈。语言L(M)={anbn
3、n>=1}不是正则集，不能由有限自动机所识别，因为：任何一个有限自动机要想识别类似这样的语言，必须设法记住读了多少个“a”。而有限自动机的唯一的“存储器”是其状态，因此只能用一个状态来表示“已经读入k个a”类似这样的信息。如下图：识别anbn的“无限状态自动机”aaaa…bbbbbb…下推自动机示意图不能使用无限状态的自动机，因此引入一个下推栈。栈的操作足够简单，能保存的信息量足够大。abbca……输入带有限控制器ABB栈顶下推栈下推自动机M是一个七元组(形式定义)定义不确定的下推自
4、动机M是一个七元组，M=(K,Σ,Γ,δ,q0,Z0,F)，其中K：有限控制器的状态集合；Σ：有限的输入字母表；Γ：有限的下推栈字母表；δ：转换函数,从K×(Σ∪{ε})×Γ到K×Γ*有限子集的映射；q0：初始状态,q0∈K；Z0：下推栈起始符号，Z0∈Γ；F：终止状态的集合。下推自动机转换函数示意图转换函数δ(q,a,Z)={(p,α)}，其中q,p∈K,a∈Σ,Z∈Γ,α∈Γ*，表示在状态q，输入字符为a且下推栈的顶符为Z时，进入状态p，下推栈的栈顶符号由字符串α代替，同时读头右移一位。qpa,Z/α约定：字符串α的最左符号放在下推栈的栈顶。当α=ε时，表示下推栈的栈顶符号出栈。当a=ε时
5、，表示不考虑当前的输入字符，但控制器的状态和下推栈可以调整，即ε转换。下推自动机例1例1：构造一个PDAM，能够识别语言L(M)={anbn
6、n>=1}。解答：设PDAM=(K,Σ,Γ,δ,q0,Z0,F)，其中K={q0,q1,q2},Σ={a,b}Γ={Z0,a}F={q0}δ定义为：δ(q0,a,Z0)={(q1,aZ0)}δ(q1,a,a)={(q1,aa)}δ(q1,b,a)={(q2,ε)}δ(q2,b,a)={(q2,ε)}δ(q2,ε,Z0)={(q0,ε)}下推自动机例1的PDA状态转换图例1：构造一个PDAM，能够识别语言L(M)={anbn
7、n>=1}。δ(q0,a,Z0
8、)={(q1,aZ0)}δ(q1,a,a)={(q1,aa)}δ(q1,b,a)={(q2,ε)}δ(q2,b,a)={(q2,ε)}δ(q2,ε,Z0)={(q0,ε)}q0q2q1a,Z0/aZ0a,a/aab,a/εb,a/εε,Z0/ε下推自动机例1的PDA工作过程例1：构造一个PDAM，能够识别语言L(M)={anbn
9、n>=1}。当输入字符串为aaabbb时，M的工作过程为：q0q2q1a,Z0/aZ0a,a/aab,a/εb,a/εε,Z0/ε(q0,aaabbb,Z0)┡(q1,aabbb,aZ0)┡(q1,abbb,aaZ0)┡(q1,bbb,aaaZ0)┡(q2,bb,aa
10、Z0)┡(q2,b,aZ0)┡(q2,ε,Z0)┡(q0,ε,ε)下推自动机例2例2：构造PDAM，识别语言L(M)={ωcωR
11、ω∈{a,b}*}。解题思路：(1)从状态q0接受句子ω，将输入保存到栈中，状态不变，直到看到中心标记c；(2)当到达c时，将状态变为q1，栈不变；(3)将输入与栈顶内容匹配，状态不变，退栈，直至栈空。状态转换图为：下推自动机例2的DPDAM例2：构造PDAM，识别语言L(M)={ωcωR
12、ω∈{a,b}*}。q0q1q2a,Z/aZb,Z/bZa,a/εb,b/εc,Z/Zε,Z0/ε其中，Z∈{Z0,a,b}是一个确定的下推自动机。下推自动机例3例3：构造一个P
13、DAM，识别语言L(M)={wwR
14、w∈{a,b}*}。q0q1q2a,Z/aZb,Z/bZa,a/εb,b/εε,Z/Zε,Z0/ε其中，Z∈{Z0,a,b}是一个不确定的下推自动机。上下文无关文法与下推自动机上下文无关文法与下推自动机，是描述上下文无关语言的不同方式。给定一个CFG和由它产生的语言L(G)，必存在一个下推自动机M接受语言L(M)，使得L(M)=L(G)，反之亦然。给定CFGG，
