编译原理蒋宗礼课件第4章.ppt

1、2020/6/19，1，第4章自上而下语法分析，4.1语法分析概述4.2自下而上语法分析问题和语法转换4.3预测分析4.4递归下降分析4.5章摘要，2020/6/19，2，语法分析功能和位置，语法分析(syntax analysis，图4.1解析器在编译器中的位置，2020/6/19，3，4.1解析概述，递归子程序自上而下预测分析(LL(1)运算符优先分析自下而上LR(0)、SLR(1)、LR(1)假设语法是压缩的。也就是说，单位创建和无用创建将被删除。2020/6/19，4，4.2自上而下语法分析问题和语法转换，自下而上语法分析的基本思想寻找语法开始符号中提供的输入符号字符串最左边的推导之一

2、。语法树示例(以根s开头，构成输入符号字符串)在：中为g: s xay a * | *，输入字符串为x * * y，sxay，x * * y，s，2020/6/19，5对于2-2-2-2-2-2-1语法G，如果L(G)中有多个分析树的句子，则G表示2的意思。如果从两个或多个最左边(或最右边)派生的句子存在于L(G)中，则G是异义美语法。假设一个语法g有异议，wl (g)存在，w有两个最左边的派生，解析器在对w自上而下解析时无法确定使用w的最左边的派生。gexp:ee t | e-t | t TT * f | t/f | f ff | p | p PC | id |(e)解决方法：通过改变语法和

3、引入新语法变量，解决当前问题2020/6/11在反序问题语法中，如果每个语法变量A生成右侧的A的候选项，A有多个候选项的公共前缀，则自上而下解析器不能根据当前输入符号正确选择用于推导的表达式，只能进行导航。需要返回到上一步，以确定a是否有其他候选人，这是否是回溯。Ge: et ee t ee-t TF TT * f TT/f (e) FID示例：字符串id*id输入的最左侧推导，考虑2020/6/19，7，4.2.1自上而下分析，2。回溯问题et(4.1)ETF(4.2)ETF(e)(4.3)et FID(4.4)ett * f(4.5).第4.2.2节将提取左侧元素，转换语法，减少提取过程中

4、回溯现象的发生。当然，仅凭提取左侧元素并不能完全避免回溯现象。2020/6/19，8，4.2.1自上而下分析问题，3 .左递归引起的无限诱导假设a是语法g的语法变量，推导a a 的话，语法g是递归的，当=的时候，称为左递归。语法g是间接递归的，当Aaa至少需要两步推导时，当=时，称为间接左递归。如果语法g中存在alpha a等形式，语法g是直接递归的，当=时直接称为左递归。Ger: et ee t ee-t TF TT * f TT/f (e) FID考虑设置最左边的诱导ee te t t以输入字符串id*id.2020/6/19，9，4.2.2的上下文无关语法变体，1。可以引入新的语法变量，

5、以在语法中包含更多信息。事实上，很多异义语法发生在概念不明，即语法变量的定义不明确的地方，这时可以引入新的语法变量，消除语法的异义性。 if then | if then else | other (4.7)根据if语句中的else和then对分为两类：不成对的语句和不成对的语句。上述if语句的语法没有区分这两个概念，只是简单地定义为，语法就有了两个含义。2020/6/19，10，4.2.2获取上下文无关语法的变化，并引入语法变量以表示语句对|if then else | otherif then | if then else，2020/6/左递归删除直接左递归删除(转换为右递归)引入新变量a

6、 ，从而使左递归生成式a a | 成为a a a a | e e t | t t * f | fa a 1 | a 2 | | a n | 1 | 2 | | m其中 I (I=1，2，m)不是以a开头。a 1a | 2a | | ma 1a | 2a | | na | ，2020/6/19，12，4.2.2的上下文无关语法变形，算法4.1删除左递归输入：循环诱导和-生成语法g无；输出：与g等价的非左递归语法；步骤：1。对g中的所有语法变量进行排序(编号)，排序后，对语法变量A1、A2、假设为an。2.for I 1 to n 3 .for j 1 to I-1 4 .使用ai1|2| | a

7、lpha k代替每个形式，例如生成ai Ajpa。其中aj1 |2 | | alpha k是所有当前aj生成表达式；5. 6 .Ai引用中的所有直接左递归7。，删除2020/6/19、13、4.2.2中的上下文无关语法转换，3 .提取左侧的参数，为每个语法变量a查找两个或多个候选中最长的公共前缀。时所有a生成a 1 | 2 | | n | 1 | 2 | | n，其中1，2、 n表示所有不以alpha开头的候选项。a a | 1 | 2 | | n a 1 | 2 | | | n其中a是新引入的语法变量。重复应用上述变换，直到任意语法变量的两个候选没有公共前缀。读者自己提供这种转换的算法。20

8、20/6/19，14，示例 if then | if then else提取左侧的公共元素 if then | else，2020/6/19，15，4 . 2 . 3 LSE确定的自上而下分析首先从语法的起始符号开始，在每个阶段，基于当前句型最左侧的语法变量a和当前输入符号a，选择a的候选之一，以替换a，使从导出的第一个终结符正确地为a。如果a有多个候选人，则当前选定的候选人必须是唯一的。第一个终结器表示符号字符串中的第一个符号，也可以称为第一个终结器的终止符号。在由上而下分析中，对候选人的选择起着重要作用。为此，引入了第一组符号的概念。2020/6/19，16，4.2.3 LL(1)语法，1

9、。在语法G=(V，t，p，s)中的符号字符串，即从(Vt)*，中派生的字符串中的第一组符号first():first()= a | 的话 first ()。3.语法g的所有a生成表达式都是a 1 | 2 | | m，first(1)8746；first ( 2) first ( n)和I，j，1i，j m；Ij，都有first(I)first(j)=存在的话，可以确认g的句子的自上而下分析，2020/6/19，17，4.2.3 LL(1)语法，a 1.FOLLOW(A)= A | SAAA，At，(vt)* 2。如果A是特定句型的最右侧符号，请在FOLLOW(A)中添加终止符#。3 .j的情况

10、下为I(1 im；Ij)，first(I)follow(a)=均为真时，可以对g的句子进行明确的自上而下分析，2020/6/19，18，4.2.3 LL(1)语法为g的如果或都不能导出，则first()-first()=；和至少能诱导。3.表示first()- follow(a)=g称为LL(1)语法。第一个l表示从左到右扫描输入符号字符串，第二个l表示学生最左侧的派生，第一个l表示在分析过程中每次进行每一步推导时计算前面的输入符号(，2020/6/19，19，19，LL(1)语法确定，算法4.2计算FIRST(X)。输入：语法G=(V，t，p，s)，x(Vt)；导出：FIRST(X)；步骤：

11、1。first(x)=；2.if(x-t)then first(x):= x ；3.if xv then begin 4。if(xp)then first(x):=first(x) a | xa.5。if(xp)then FIRST(x):=FIRST(x) a | xap end 6。对x-v重复下一过程7-10，直到所有第一组first均保持不变。7.if (x y.p and y/v)then first(x):=first(x)(y)-；8.if (x y1.ynp and y1.yi-1 ) then 9。for k=1 to I-1 do first(x):=first(x)(first(yk)-)；10.if y1.ynthen first(x):=first(x)；输入计算2020/6/19，20，FIRST(X)的算法的其他说明：语法G=(V，t，p，s)，X(Vt)；导出：FIRST(X)；对于Xt，first (x)=x XV和X a .对于at为a first (x) XV，对于x为first (x) XV，y1，y2，Yidu vt，生成的xy1 y2.对于yn，请输入y1、y2、对于yi-1，包括(1In)、first (y1)-、First