工学第4章编译原理课件

第4章语法分析—自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL（1）分析法4.4递归下降分析程序构造4.5预测分析程序第4章语法分析—自上而下分析第4章语法分析—自上而下分析4.1语法分析器的功能内容回顾句型、句子和语言的定义句型有文法G[S]，若S==*>α，且α∈Ｖ*,

则称是α是文法G的一个句型句子有文法G[S]，若S==*>α，且α∈ＶT*,

则称是α是文法G的一个句子语言由文法G产生的所有句子的集合

L(G)={α|S==+>α,且α∈ＶT*}内容回顾内容回顾句型、句子和语言的定义内容回顾最左(最右)推导在推导的任何一步α==*>β(其中α和β是句型)，都对α中的最左(最右)非终结符进行替换句型分析(句子分析)识别一个符号串是否为某文法的句型(句子)的过程也就是某文法的某个推导的构造过程设文法G为:E→E+T|TT→T*F|FF→(E)|i请问符号串i+i*i是否为该文法的句子?自上而下自下而上EE+TT*FFFTiii内容回顾最左(最右)推导设文法G为:请问符号串i+i*i是自上术语解释分析算法(分析器、识别算法)在语言的编译实现中，把完成句型(句子)分析的程序称为分析程序或识别程序从左到右的分析算法即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号内容回顾术语解释分析算法(分析器、识别算法)内容回顾4.1语法分析器的功能任务分析并判定输入的单词符号串是否符合该语言的语法规则(上下文无关文法)实质就是按照文法的产生式，识别输入符号串是否为一个句子(合法程序，语句，表达式等)词法扫描器语法分析器语义处理单词符号语法树4.1语法分析的功能4.1语法分析器的功能任务词法扫描器语法分析器语义处理单词符设计思想判断是否能从文法的开始符号出发推导出这个输入串或者,判断能否建立一棵与输入串匹配的语法分析树输入单词符号串输出语法分析树格式化的程序合法的表达式、语句、函数出错处理要求尽快发现错误，准确定位可能时进行恢复处理，继续语法分析4.1语法分析的功能设计思想4.1语法分析的功能根据建立方法，语法分析算法可分为两大类:自上而下分析法从文法的开始符号出发，反复使用各种产生式向下推导，寻找与输入符号串匹配的推导自下而上分析法从输入串开始，逐步进行归约，直至归约到文法的开始符号两种方法反映了两种不同的语法树的构造过程自上而下——从树根推导到树叶自下而上——从树叶归约到树根4.1语法分析的功能根据建立方法，语法分析算法可分为两大类:4.1语法分析的功能4.2自上而下分析面临的问题基本方法对任何输入串,试图从文法的开始符号出发，自上而下地为输入串建立一棵语法树或者说，为输入串寻找一个最左推导过程本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程如何选择哪个产生式进行推导?4.2自上而下分析面临的问题4.2自上而下分析面临的问题基本方法4.2自上而下分析面临例文法G[S]S→xAyA→ab|a

判断输入串w=xay是否为该文法的句子？SxAy试探ab失败回溯a试探成功分析结束SxAy==>xay==>问题产生回溯的原因是什么?4.2自上而下分析面临的问题例文法G[S]S→xAyA→ab|aSxAy试探公共左因子——产生回溯例文法G:S→xAyA→ab|a无法确定非终结符A面临输入符号a时选用哪个关于A的候选式左递归——无限循环例文法G:S→Sa|abaw=abaaaSSaSa…无法确定何时用S→aba产生式进行推导某些文法导致自上而下分析具有不确定性4.2自上而下分析面临的问题公共左因子——产生回溯w=abaaaSSaSa…无法确定4.3LL(1)分析法为了构造不带回溯的自上而下分析算法消除文法的左递归消除回溯、提取左因子LL(1)分析条件LL(1)文法4.3LL（1）分析法4.3LL(1)分析法为了构造不带回溯的自上而下分析算法4.3.1左递归的消除关于非终结符P的规则直接左递归定义：若P→Pα｜βα、β∈Ｖ*例如E→E+T｜T（含有E的左递归）

T→T*F｜F（含有T的左递归）

F→(E)｜i4.3LL（1）分析法4.3.1左递归的消除关于非终结符P的规则4.3LL（间接左递归定义：若P==+>Pαα∈Ｖ*例如间接左递归

S→AaA→Sb|bS==>Aa==>Sba即S==+>Sb用S的产生式右部替换A右部的S得：

A→Aab|b

变成A的产生式含有直接左递归4.3LL（1）分析法间接左递归定义：4.3LL（1）分析法消除直接左递归的方法改写为等价的右递归形如：P→Pα｜β

α非ε，β不以P开始

改写为：P→βP’（P’为新增加的非终结符）

P'→αP'｜ε改写前产生式可产生短语P==>Pα==>βα

改写后产生式可产生短语

P==>βP’

==>βαP'

==>βα

等价4.3LL（1）分析法消除直接左递归的方法改写为等价的右递归等价4.3LL（E→E+T｜TT→T*F｜FF→(E)｜iE→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜i4.3LL（1）分析法E→E+T｜TE→TE'4.3LL（1）分消除多个直接左递归若有多个左递归的产生式如：P→Pα1|Pα2|…|Pαm|β1|β2|…|βn消除左递归后变为：

P→β1P’|β2P’|…|βnP’ P’→α1P’|α2P’|…|αmP’|ε消除左递归要求文法：

1.无回路（A==*>A）

2.无空产生式（A→ε）4.3LL（1）分析法消除多个直接左递归若有多个左递归的产生式如：消除左递归后变为练习例如有文法：

K→Ka|Kb|Kc|d|e

消除左递归后变为：

K→dK’|eK’

K’→aK’|bK’|cK’|ε4.3LL（1）分析法练习例如有文法：消除左递归后变为：4.3LL（1）分析法间接左递归消除举例S→Qc｜cQ→Rb｜b

R→Sa｜aS=>Qc=>Rbc=>Sabc

是间接左递归消除方法1：将非终结符排序：

RQS将R的右部代入Q，S：

Q→Sab｜ab｜bS→Qc｜c（不变）将Q的右部代入S：

S→Sabc｜abc｜bc｜c消除S的直接左递归：

S→abcS’｜bcS’|cS’S’→abcS’|εQ→Sab｜ab|bR→Sa｜a整理化简：删除Q，R（无用）消除左递归后得：

S→abcS’｜bcS’|cS’S’→abcS’|ε4.3LL（1）分析法间接左递归消除举例S→Qc｜c将Q的右部代入S：4.

S→Qc｜cQ→Rb｜b

R→Sa｜a消除方法2：将非终结符排序：

SQR将S的右部代入Q，R：

Q→Rb｜b（不变）

R→Qca｜ca|a将Q的右部代入R：

R→Rbca｜bca|ca|a消除R的直接左递归：

R→bcaR’｜caR’|aR’

R’→bcaR’|ε

整理化简：S，Q（有用）消除左递归后得：

S→Qc｜cQ→Rb｜bR→bcaR’｜caR’|aR’R’→bcaR’|ε4.3LL（1）分析法S→Qc｜c将Q的右部代入R：4.3LL（1）分消除左递归算法1.以某种S顺序将文法的非终结符排列

P1，P2，…,Pn

2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pjγ的规则改写成

Pi→δ1γ|δ2γ|…|δkγ,其中

Pj→δ1|δ2|…|γ是关于Pj的所有规则;

消除Pi的直接左递归

END3.化简由2所得的文法，即去除那些从开始符号出发永远无法到达的非终结符的产生式当非终结符的排列顺序不同时，变换后的文法形式可能不同，但是它们都和原文法是等价的4.3LL（1）分析法消除左递归算法1.以某种S顺序将文法的非终结符排列当非终结符4.3.2消除回溯、提左因子消除回溯目的对文法的任何非终结符，当它去匹配输入串时，能够根据输入符号，准确地选择合适的候选式去匹配若需要非终结符A去匹配输入串，A的候选式为A→α1|α2|…|αn

，

A所面临的第一个输入符号为a时，A能准确地选择αi去执行匹配任务，则无需回溯4.3LL（1）分析法4.3.2消除回溯、提左因子消除回溯目的4.3LL（1提取公共左因子方法对于所有形如A→αβ1｜αβ2｜...｜αβn｜γ的规则其中，α为左因子，γ不以α开头改写为A→αA'｜γ其中A’为新增加的非终结符

A'→β1｜β2｜...｜βn例如

S→xAyA→ab|a提左因子后变换为

S→xAy

A→aA’

A’

→b|ε4.3LL（1）分析法提取公共左因子方法对于所有形如提左因子后变换为4.3L4.3.3LL(1)分析条件FIRST集合的定义FOLLOW集合的定义LL(1)分析条件LL(1)文法的定义4.3LL（1）分析法4.3.3LL(1)分析条件FIRST集合的定义4.3FIRST(α)集合的定义设G=(ＶT，ＶN，S，P）α∈Ｖ*

FIRST(α)={a|α==*>a…，a∈ＶT}若α==*>ε，则ε∈FIRST(α)FIRST(α)是α的所有可能推导的首遇终结符号或ε，是选择产生式的依据αa……

E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜iFIRST((E))={(}（E）==0>（E）FIRST（TE’）={（，i}TE’==>FT’E’==>（E）T’E’TE’==>FT’E’==>iT’E’4.3LL（1）分析法FIRST(α)集合的定义设G=(ＶT，ＶN，S，P）α∈FOLLOW(A)集合的定义A∈ＶN

FOLLOW(A)={a｜S==*>…Aa…，a∈ＶT}若S==*>…A，则#∈FOLLOW（A）#—输入串的结束符也可看作是句子的括号#S#FOLLOW(A)表示了句型中可能紧跟在A后面的终结符号S…Aa…E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜i

）∈FOLLOW（E）S==>TE’==>FT’E’==>（E）T’E’

+

∈FOLLOW（T）S==>TE’==>T+TE’

#∈FOLLOW（E）S==0>E4.3LL（1）分析法FOLLOW(A)集合的定义A∈ＶNS…Aa…E→消除回溯的条件非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选α和β，满足：

FIRST(α)∩FIRST(β)=φ

当要求A

匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选去执行任务，这个候选就是那个终结首符集含a的α4.3LL（1）分析法消除回溯的条件非终结符A的所有候选首符集两两不相交，4.3非终结符A的自动匹配当非终结符A面临输入符号a，但a不属于A

的任何候选首符集，如果A有候选式A→ε(A

的某个候选首符集包含ε)，可以让A自动得到匹配，即A匹配于空字ε，但输入符号不读进要想让A自动匹配成功，需要考察FOLLOW(A)4.3LL（1）分析法非终结符A的自动匹配当非终结符A面临输入符号a，但a不属i+i#的推导过程设有文法GE→TE’

E’→+TE’|ε

T→FT’

T’→*FT’|ε

F→(E)|i

i∈FIRST(i)+∈FIRST(+TE’)+∈FOLLOW(T’)#∈FOLLOW(E’)#∈FOLLOW(T’)ＥＴＥ’ＦＴ’iε＋ＴＥ’ＦＴ’iεε生成语法分析树4.3LL（1）分析法i+i#的推导过程设有文法GＥＴＥ’ＦＴ’iε＋ＴＥ推导过程的分析输入输出输入：符号串(有序的)输出：结构化的符号串(树结构)产生式的选择根据当前符号（单词）语法分析树的表示按照使用序列排列的产生式序列4.3LL（1）分析法推导过程的分析输入输出4.3LL（1）分析法无回溯的自上而下分析的文法的条件文法不含左递归对于文法的每个非终结符A的任何两个不同的产生式A→α|β 1)FIRST(α)∩FIRST(β)=φ 2)α==*>和β==*>不能同时成立

3)如果β==*>，则

FISRT(α/A)∩FOLLOW(A)=φ满足以上条件的文法称为LL(1)文法4.3LL（1）分析法无回溯的自上而下分析的文法的条件文法不含左递归4.3LLLL(1)分析含义第一个L表示从左向右扫描输入符号串第二个L表示生成最左推导1表示读入一个符号可确定下一步推导对于LL（1）文法，可以对输入串进行有效的无回溯的自上而下分析。对于文法G，当面临的输入符号为a，要用非终结符A进行匹配时，假设A的所有产生式为A→α1|α2|…|αn 1)若a∈FIRST(αi

)，则指派αi去执行任务

2)若a不属于任何候选首符集，则： ①若ε属于某个FIRST(αi

)且

a∈FOLLOW(A)，则让A与ε自动匹配 ②否则，a的出现是一种语法错误4.3LL（1）分析法LL(1)分析含义4.3LL（1）分析法4.4递归下降分析程序构造不带回溯的自上而下分析程序分析程序一组递归过程每个非终结符一个子过程LL（1）文法构造分析程序从开始符号所对应的过程开始运行子过程的功能：对相应非终结符产生式右部进行语法分析4.4递归下降分析程序构造4.4递归下降分析程序构造不带回溯的自上而下分析程序分析例表达式文法的递归下降分析器消除左递归后的表达式文法G为：

E→TE' E'→+TE’|ε T→FT' T'→*FT’|ε F→(E)|i可以证明

G是一个LL（1）文法E()E’()T()T’()F()5个非终结符构造5个子过程4.4递归下降分析程序构造例表达式文法的递归下降分析器消除左递归后的表达式文法G为：递归下降分析器构造说明C语言

E（）

{ T;E’; }E’TE（1）E（）：完成对E→TE’的右部分析PASCAL语言 procedureE; begin T;E’; end;右部有非终结符时，调用该非终结符对应的子过程来完成递归下降分析器构造说明C语言 E’TE（1）E（）：完成对E’(){ if(c==‘+’){p++;T;E’;}}E’TE’（2）E’（）：完成对E→+TE’|ε的右部分析procedureE’; ifsym=‘+’thenbeginadvance;T;E’;end；+其它非+字符自动匹配εadvance：把输入指针ip下移一位sym：当前所面临的输入符号4.4递归下降分析程序构造E’()E’TE’（2）E’（）：完成对E→+TE’|C语言练习T(){ F;

T’;}(3)T():T→FT’procedureT; begin

F;T’; end;T’FT4.4递归下降分析程序构造C语言练习(3)T():T→FT’procedure(4)T’():T’→*FT’|εC语言练习T’(){ if(c==‘*’)

{p++;F;T’;}

}procedureT’; ifsym=‘*’thenbeginadvance;F;T’;end；T’F*其它非*字符自动匹配εT’4.4递归下降分析程序构造(4)T’():T’→*FT’|εC语言练习proce(5)F():F→(E)|iprocedureF;beginifsym='('thenbeginadvance;E;ifsym=‘)’thenadvanceelseerror{括号不匹配}endelseifsym=‘i’thenadvance elseerror{F面临非（，i输入符号，语法错误}endEF()i其它非(,i字符出现语法错误4.4递归下降分析程序构造(5)F():F→(E)|iprocedureF;Ｆ的子程序F(){ if(c==‘(‘){p++;E;if(c==‘)’)p++;elseerror;}/*括号不匹配*/

elseif(c==‘i’)p++;elseerror;/*F面临非(,i输入符号，语法错误*/

}EF()i其它非(,i字符出现法错误4.4递归下降分析程序构造Ｆ的子程序EF()i其它非(,i字符出现法错误4.4递i+i的递归下降分析过程ＥＴＥ’ＦＴ’Ｔ＋Ｅ’iεＦＴ’iεε生成语法分析树i+i#匹配成功返回，指针下移自动匹配，返回自动匹配，返回自动匹配，返回匹配成功继续，指针下移匹配成功返回，指针下移分析成功结束4.4递归下降分析程序构造i+i的递归下降分析过程ＥＴＥ’ＦＴ’Ｔ＋Ｅ’iεＦＴ’i递归下降分析程序优缺点分析优点：1）直观、简单、可读性好2）便于扩充缺点：1)递归算法的实现效率低2)处理能力相对有限3)通用性差，难以自动生成4.4递归下降分析程序构造递归下降分析程序优缺点分析优点：4.4递归下降分析程序构

递归下降分析程序课堂练习文法G为：

S→(T)|a+S|a

T

→T,S|S

消除左递归：

S→(T)|a+S|a

T→ST’

T’

→，ST’|ε提取左因子：

S→(T)|aS’

S’→+S|ε

T→ST’T’→，ST’|ε4个子程序：

S（）S’（）

T（）T’（）

BEGIN4.4递归下降分析程序构造递归下降分析程序课堂练习文法G为：消除左递归：提取左因

递归下降分析程序课堂练习答案（1）S→(T)|aS’S(){if(c=‘(‘)/*匹配第一候选式*/{p++;T;if(c=‘)’)p++;elseerror;/*括号不匹配*/}elseif(c=‘a’){p++;S’;}/*匹配第二候选式*/elseerror;/*语法错误*/}4.4递归下降分析程序构造递归下降分析程序课堂练习答案（1）S→(T)|aS’(2)S’→+S|εS’(){if(c=‘+‘){p++;

S;}}(3)T→ST’T(){S;T’;}(4)T’→,ST’|εT’(){if(c=‘,’){p++;

S;T’;}}4.4递归下降分析程序构造(2)S’→+S|ε(3)T→ST’(4)T’→,ST’4.5预测分析程序实现LL(1)分析的另一种有效方法使用一张二维分析表（预测分析表）和一个分析栈（文法符号栈）联合进行控制来实现自上而下分析技术4.5预测分析程序4.5预测分析程序实现LL(1)分析的另一种有效方法使用

预测分析表说明预测分析表实际上是一个矩阵M[A,a]M[A，a]=A→αi当A面临a时所应选用的候选式空(error)A不可能与a匹配出现语法错误待匹配栈顶非终结符所面临输入符号4.5.1预测分析程序工作过程预测分析表说明预测分析表实际上是一个矩阵M[A,a]M[A表达式文法的预测分析表M[E’，+]=E’→+TE’E’面临+时选用E’→+TE’M[T’，)]=T’→εT’面临）时选用T’→εM[F，*]=errorF面临*时出现语法错误表达式文法的预测分析表M[E’，+]=E’→+TE’E分析栈的说明分析栈用于存放分析过程中的文法符号topstack栈顶指针分析栈初始化时：栈底压入一个‘#’底顶#Stoptop次栈底压入文法开始符S入栈操作push出栈操作poptop分析栈的说明分析栈用于存放分析过程中的文法符号topstac

预测分析器模型

输入缓冲区:…a…#

X┆#

栈总控制程序预测分析表输出所选用产生式序列查找4.5预测分析程序预测分析器模型输入缓冲区:…a…#总控制程序预总控程序执行时可能动作对于任何（X，a）X是栈顶符号a是面临输入符号(1)X∈ＶT

且X＝a＝‘#’，分析成功结束，输入串是一个合法句子(2)X∈ＶT

且X＝a≠‘#’，X出栈，输入指针指向下一输入符号(3)X∈ＶN，查分析表M[X，a]

若M[X，a]=X→αi，X出栈，αi逆序入栈，输入指针不动若M[X，a]=空，则调用error程序，进行错误处理4.5预测分析程序总控程序执行时可能动作对于任何（X，a）X是栈顶符号a是执行例子：i*i+i分析过程

栈输入缓冲区所用产生式0#E

i*i+i#E→TE'E'T入栈1#E'Ti*i+i#T→FT'2#E'T'F

i*i+i#F→i3#E'T'ii*i+i#i出栈，a下移4#E'T'

*i+i#T'→*FT'5#E'T'F**i+i#*出栈，a下移6#E'T'F

i+i#F→i

7#E'T'ii+i#i出栈，a下移4.5预测分析程序执行例子：i*i+i分析过程栈输入i*i+i分析

过程续

栈输入缓冲区所用产生式8#E'T'

+i#T'→ε9#E'+i#E'→+TE'10#E'T+

+i#11#E'Ti#T→FT'12#E'T'F

i#F→i13#E'T'ii#14#E'T'

#T'→ε15#E'#E'→ε16#

##=#分析成功结束输出的产生式序列形成了按最左推导生成的语法分析树4.5预测分析程序i*i+i分析

过程续栈输入缓冲区课堂练习一：i+i分析过程栈输入缓冲区所用产生式0#E

i+i#E→TE'1#E'Ti+i#T→FT' 2#E'T'F

i+i#F→i3#E'T'ii+i# 4#E'T'+i#T'→ε5#E'+i#E'→+TE'6#E'T+

+i# 7#E'Ti#T→FT'4.5预测分析程序课堂练习一：i+i分析过程栈输入缓冲区i+i分析

过程

续栈输入缓冲区所用产生式8#E'T'F

i#F→i9#E'T'ii#10#E'T'

#T'→ε11#E'#E'→ε12#

##=#分析成功4.5预测分析程序i+i分析

过程

续栈输入缓冲区所用课堂练习二：i+i*i分析过程栈输入缓冲区所用产生式0#Ei+i*i#E→TE'1#E'T

i+i*i# T→FT'2#E'T'Fi+i*i#F→i3#E'T'i

i+i*i# 4#E'T'+i*i#T'→ε5#E'

+i*i#E'→+TE'6#E'T++i*i#7#E'T

i*i#T→FT'4.5预测分析程序课堂练习二：i+i*i分析过程栈输入缓冲i+i*i分析

过程

续栈输入缓冲区所用产生式8#E'T'Fi*i#F→i9#E'T'ii*i#10#E'T'*i#T'→*FT'11#E'T'F**i#12#E'T'Fi#F→i13#E'T'ii#14#E'T'#T'→ε15#E'#E'→ε16##4.5预测分析程序i+i*i分析

过程

续栈输入缓冲区总控程序实现算法描述BEGINPUSH(STACK,’#’)；PUSH(STACK,开始符号);a=第一个输入符号；

FLAG:=TRUE；

WHILEFLAGDOBEGINX=POP(STACK);IFX∈ＶTTHENIFX=aTHENa=下一个符号{终结符匹配}ELSEERROR{与当前输入符号不匹配}4.5预测分析程序总控程序实现算法描述BEGIN4.5预测分析程序ELSEIFX=‘#’THENIFX=aFLAG:=FALSEELSEERRORX=a=‘#’

分析成功结束ELSEIFM[A，a]={X→X1X2…Xk}

把Xk…X2X1一一推进STACK栈]ELSEERRORENDOFWHILESTOP{分析成功,过程完毕}END4.5预测分析程序ELSEIFX=‘#’THENX=a=‘#’分析成4.5.2预测分析表的构造设有文法G，预测分析表构造过程：计算所有候选式α的首符集

FIRST（α）计算所有非终结符A的后继符集

FOLLOW（A）构造预测分析表

M4.5预测分析程序4.5.2预测分析表的构造设有文法G，预测分析表构造过程：FIRST(α)的计算法FIRST(α)={a｜α==*>a

…，a∈ＶT}若α==*>ε，则ε∈FIRST(α)计算文法符号X的FIRST（X）计算文法符号串α=X1X2…Xn的FIRST(α)4.5预测分析程序FIRST(α)的计算法FIRST(α)={a｜α==*FIRST(X)的计算法重复以下计算，直到FIRST（X）不再增大为止：1)若X∈ＶT，则FIRST(X)={X}。例FIRST（+）={+}FIRST（i）={i}2)若X∈ＶN，若有X→a…，则将a加入FIRST(X)；例E'→+TE'+∈FIRST（E’）

F→（E）|i

（，i∈FIRST（F）若有X→ε，则将ε加入FIRST(X)。例E’→εε∈FIRST（E’）4.5预测分析程序FIRST(X)的计算法重复以下计算，直到FIRST（X若有X→Y1…Yi-1Yi…Yk

，并对于某个i， 有1≤j≤i-1，ε∈FIRST（Yj），即Y1，…，Yi-1==*>ε，则将所有FIRST(Yj)-{ε}∪FIRST(Yi)-{ε}

加入FIRST(X)中；-{ε}-{ε}3)若有X→Y…，且Y∈ＶN

，则FIRST(Y)-{ε}加入FIRST(X);例F→(E)|iFIRST(F)={（，i}T→FT'FIRST(T)=FIRST(F)-{ε}={（，i}若所有Y1,…,Yk==*>ε，则将ε加入到FIRST(

X

)。-{ε}-{ε}3)若有X→Y…，且Y∈ＶN，例计算X→Y1…Yi-1Yi…YkFIRST(X)集举例若有文法G为：

X→Y1Y2Y3

Y4Y5

Y1→a｜εY2→b｜ε

Y3

→c｜εY4→d｜εY5→e｜fFIRST集Y1Y2Y3Y4Y5Xa，εb，εc，εd，εe，fa,b,c,d,e,fεε

因为Y5==*>ε，所以ε∈FIRST（X）ε==*>ε==*>ε因为Y5==*>ε，所以ε∈FIRST（X）4.5预测分析程序计算X→Y1…Yi-1Yi…YkFIRST(X)集举例若有计算表达式文法FIRST(X)集举例文法G为：

E→TE’ E'→+TE'｜ε T→FT' T'→*FT'｜ε F→(E)｜i先找以终结符开头的产生式FIRST(F)={(,i}FIRST(E')={+，ε}FIRST(T')={*,ε}再找右部以非终结符开头的产生式FIRST(T)=FIRST(F)FIRST(E)=FIRST(T)={(,i}4.5预测分析程序计算表达式文法FIRST(X)集举例文法G为：先找以终结符开计算FIRST(X)集合课堂练习={a，c，d，q}文法G为：

S→Ap｜Bq

A→a｜cA B→dB｜ε先找以终结符开头的产生式FIRST(A)={a

,c

}FIRST(B)={d

,ε}再找右部以非终结符开头的产生式FIRST(S)=FIRST(A)-{ε}∪FIRST(B)-{ε}因为B==>εε∈FIRST(S),因为S==*>ε∪FIRST(q)4.5预测分析程序计算FIRST(X)集合课堂练习={a，c，d，q}计算表达式文法候选式FIRST(α)集举例候选式的FIRST集FIRST(TE’)=FIRST(T)={(,i}FIRST(+TE’)={+}FIRST(FT’)=FIRST(F)={(,i}FIRST(*FT’)={*}FIRST((E))={(}FIRST(i)={i}FIRST(ε)={ε}文法G为：

E→TE’

E'→+TE’|ε

T→FT’

T'→*FT’|ε

F→(E)|i非终结符的FIRST集FIRST(E)={(,i}FIRST(E')={+,ε}FIRST(T)={(,i}FIRST(T')={*,ε}FIRST(F)={(,i}4.5预测分析程序计算表达式文法候选式FIRST(α)集举例候选式的FIRST计算FIRST(α)集合课堂练习文法G为：S→Ap｜Bq

A→a｜cA

B→

dB｜ε非终结符的FIRST集FIRST(S)={a,c,d,q}FIRST(A)={a,c}FIRST(B)={d,ε}候选式的FIRST集FIRST(Ap)=FIRST(A)={a,c}FIRST(Bq)=FIRST(B)-{ε}∪FIRST(q)={d,q}FIRST(a)={a}FIRST(cA)={c}FIRST(dB)={d}FIRST(ε)={ε}4.5预测分析程序计算FIRST(α)集合课堂练习文法G为：非终结符的FIRSFOLLOW(A)的计算法FOLLOW(A)={a｜S==*>…Aa…，a∈ＶT}若S==*>…A，则#∈FOLLOW（A）重复以下计算，直到每个FOLLOW(A)不再增大为止：1)将#加入到FOLLOW(S)中例#

∈FOLLOW(E)2)若A→αBβ,

则将FIRST(β)-{ε}加入FOLLOW(B)例E→TE’

FIRST(E’)-{ε}加入FOLLOW(T)

T→FT’

FIRST(T’)-{ε}加入FOLLOW(F)4.5预测分析程序FOLLOW(A)的计算法FOLLOW(A)={a｜S==3)若A→αB

，或A→αBβ，且β==*>ε，即ε∈FIRST(β)，A≠B

则将FOLLOW(A)所有元素加入FOLLOW(B)ε例E→TE’FOLLOW(E)加入FOLLOW(E’)E→T

E’E'→εFOLLOW(E)加入FOLLOW(T)T→FT’FOLLOW(T)加入FOLLOW(T’)T→F

T’FOLLOW(T)加入FOLLOW(F)T'→ε4.5预测分析程序3)若A→αB，或A→αBβ，ε例E→T计算表达式文法的FOLLOW集举例#∈FOLLOW（开始符号）对每个非终结符查看其在产生式右边的出现G：E→TE’

E'→+TE’|εT→FT’

T'→*FT’|εF→(E)|i#∈FOLLOW(E)=FIRST(E’)-{ε}FOLLOW(T)∪FOLLOW(E)={+,),#}FOLLOW(F)=FIRST(T’)-{ε}∪FOLLOW(T)={*,+,),#}FOLLOW(E)={),#}FOLLOW(E')=FOLLOW(E)={),#}FOLLOW(T')=FOLLOW(T)={+,),#}相同不需处理计算表达式文法的FOLLOW集举例#∈FOLLOW（开始符号计算FOLLOW(A)集合课堂练习文法G为：S→Ap｜Bq A→a｜cA B→dB｜ε非终结符的FIRST集FIRST(S)={a,c,d,q}FIRST(A)={a,c}FIRST(B)={d,ε}

非终结符FOLLOW集FOLLOW(S)={#}FOLLOW(A)=FIRST(p)-{ε}={p}FOLLOW(B)=FIRST(q)-{ε}={q}4.5预测分析程序计算FOLLOW(A)集合课堂练习文法G为：非终结符的FIR表达式文法是LL(1)文法满足条件（3）：

E’→εFIRST(+TE’)={+}FOLLOW(E’)={),#}φ

T’→εFIRST(*FT’)={*}FOLLOW(T’)={+,),#}φ文法G是LL（1）文法满足条件（1）：已消除左递归满足条件（2）：FIRST(+TE’)={+}FIRST(ε)={ε}

φFIRST(*FT’)={*}

FIRST(ε)={ε}

φFIRST((E))={(}

FIRST(i)={i}φ

文法G：E→TE'E'→+TE'

|ε

T→FT'T'→*FT'

|ε

F→(E)｜i表达式文法是LL(1)文法满足条件（3）：满足条件（1）预测分析表的构造算法(4)把所有无定义的M[A,a]标上“出错标志”(1)对文法G的每个产生式A→α，执行(2)和(3)(2)对每个终结符a∈FIRST(α)，

把A→α填入M[A,a](3)若ε∈FIRST(α)，则对任何b∈FOLLOW(A)

把A→α填入M[A,b]4.5预测分析程序预测分析表的构造算法(4)把所有无定义的M[A,a]标上“预测分析表的构造算法举例E→TE’

FIRST(TE’)={(,i}M[E,(]=E→TE’M[E,i]=E→TE’

E’→+TE’

FIRST(+TE’)={+}M[E’,+]=E’→+TE’E’→ε

FOLLOW(E’)={),#}M[E’,)]=E’→εM[E’,#]=E’→εF→(E)|i

M[F,(]=F→(E)M[F,i]=F→i若文法G的分析表不含多重入口，则G是LL(1)文法4.5预测分析程序预测分析表的构造算法举例E→TE’FIRST(TE’)预测分析法（状态矩阵法）1)编写文法，消除二义性；2)消除左递归、提取左因子；3)求FIRST集合和FOLLOW集合4）检查是不是LL(1)文法若不是LL(1),说明文法的复杂性超过自上而下方法的分析能力5）按照LL(1)文法构造预测分析表6）实现预测分析器4.5预测分析程序预测分析法（状态矩阵法）1)编写文法，消除二义性；4.5LL（1）分析中的错误处理语法错误：栈顶终结符与当前输入符不匹配栈顶非终结符A面临输入符a，但分析表M中M[A,a]为空解决方法：跳过输入串中的符号直至遇到“同步符号”4.5预测分析程序LL（1）分析中的错误处理语法错误：4.5预测分析程序预测分析程序课堂综合练习文法G为：S→aBc｜bABA→aAb｜bB→b｜ε1.非终结符的FIRST集FIRST(S)={a,b}FIRST(A)={a,b}FIRST(B)={b,ε}2.非终结符FOLLOW集FOLLOW(S)={#}FOLLOW(A)=FIRST(b)∪FIRST(B)-{ε}∪FOLLOW(S)={b,#}FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}问题：构造预测分析表，并分析符号串baabbb是否为该文法的句子？S→bABB==>εS→bAB预测分析程序课堂综合练习文法G为：1.非终结符的FIRST集文法G为：S→aBc｜bABA→aAb｜bB→b｜εFOLLOW(B)={c,#}SABabc#S→aBcS→bABA→aAbA→bB→bB→εB→ε3.构造预测分析表若分析表无多重入口，则G是LL(1)文法4.5预测分析程序文法G为：S→aBc｜bABA→aAb｜bB→b｜ε综

合

练

习

续

符号栈输入缓冲区所用产生式0#S

baabbb#S→bAB1#BAb

baabbb#移进b 2#BA

aabbb#A→aAb3#BbAa

aabbb#移进a4#BbA

abbb#A→aAb5#BbbAa

abbb#移进a6#BbbA

bbb#A→b7#Bbbb

bbb#移进b8#Bbb

bb#移进b9#Bb

b#移进b10#B

#B→ε11##分析成功结束4.b

a

a

b

b

b

分

析

过

程综

合

练

习

续符号栈输入缓冲区所用产作业：P8123、文法G[A]如下：4、已知文法G[S]如下：A→BaC|CbB

S→aABbcd|εB→Ac|cA→ASd|εC→Bb|bB→SAh|eC|ε

消除其左递归C→Sf|Cg|εD→aBD|ε

求每一非终结符的FIRST

集合和FOLLOW集合，该文法是LL（1）文法吗？为什么？作业作业：P812作业第4章语法分析—自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL（1）分析法4.4递归下降分析程序构造4.5预测分析程序第4章语法分析—自上而下分析第4章语法分析—自上而下分析4.1语法分析器的功能内容回顾句型、句子和语言的定义句型有文法G[S]，若S==*>α，且α∈Ｖ*,

则称是α是文法G的一个句型句子有文法G[S]，若S==*>α，且α∈ＶT*,

则称是α是文法G的一个句子语言由文法G产生的所有句子的集合

L(G)={α|S==+>α,且α∈ＶT*}内容回顾内容回顾句型、句子和语言的定义内容回顾最左(最右)推导在推导的任何一步α==*>β(其中α和β是句型)，都对α中的最左(最右)非终结符进行替换句型分析(句子分析)识别一个符号串是否为某文法的句型(句子)的过程也就是某文法的某个推导的构造过程设文法G为:E→E+T|TT→T*F|FF→(E)|i请问符号串i+i*i是否为该文法的句子?自上而下自下而上EE+TT*FFFTiii内容回顾最左(最右)推导设文法G为:请问符号串i+i*i是自上术语解释分析算法(分析器、识别算法)在语言的编译实现中，把完成句型(句子)分析的程序称为分析程序或识别程序从左到右的分析算法即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号内容回顾术语解释分析算法(分析器、识别算法)内容回顾4.1语法分析器的功能任务分析并判定输入的单词符号串是否符合该语言的语法规则(上下文无关文法)实质就是按照文法的产生式，识别输入符号串是否为一个句子(合法程序，语句，表达式等)词法扫描器语法分析器语义处理单词符号语法树4.1语法分析的功能4.1语法分析器的功能任务词法扫描器语法分析器语义处理单词符设计思想判断是否能从文法的开始符号出发推导出这个输入串或者,判断能否建立一棵与输入串匹配的语法分析树输入单词符号串输出语法分析树格式化的程序合法的表达式、语句、函数出错处理要求尽快发现错误，准确定位可能时进行恢复处理，继续语法分析4.1语法分析的功能设计思想4.1语法分析的功能根据建立方法，语法分析算法可分为两大类:自上而下分析法从文法的开始符号出发，反复使用各种产生式向下推导，寻找与输入符号串匹配的推导自下而上分析法从输入串开始，逐步进行归约，直至归约到文法的开始符号两种方法反映了两种不同的语法树的构造过程自上而下——从树根推导到树叶自下而上——从树叶归约到树根4.1语法分析的功能根据建立方法，语法分析算法可分为两大类:4.1语法分析的功能4.2自上而下分析面临的问题基本方法对任何输入串,试图从文法的开始符号出发，自上而下地为输入串建立一棵语法树或者说，为输入串寻找一个最左推导过程本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程如何选择哪个产生式进行推导?4.2自上而下分析面临的问题4.2自上而下分析面临的问题基本方法4.2自上而下分析面临例文法G[S]S→xAyA→ab|a

判断输入串w=xay是否为该文法的句子？SxAy试探ab失败回溯a试探成功分析结束SxAy==>xay==>问题产生回溯的原因是什么?4.2自上而下分析面临的问题例文法G[S]S→xAyA→ab|aSxAy试探公共左因子——产生回溯例文法G:S→xAyA→ab|a无法确定非终结符A面临输入符号a时选用哪个关于A的候选式左递归——无限循环例文法G:S→Sa|abaw=abaaaSSaSa…无法确定何时用S→aba产生式进行推导某些文法导致自上而下分析具有不确定性4.2自上而下分析面临的问题公共左因子——产生回溯w=abaaaSSaSa…无法确定4.3LL(1)分析法为了构造不带回溯的自上而下分析算法消除文法的左递归消除回溯、提取左因子LL(1)分析条件LL(1)文法4.3LL（1）分析法4.3LL(1)分析法为了构造不带回溯的自上而下分析算法4.3.1左递归的消除关于非终结符P的规则直接左递归定义：若P→Pα｜βα、β∈Ｖ*例如E→E+T｜T（含有E的左递归）

T→T*F｜F（含有T的左递归）

F→(E)｜i4.3LL（1）分析法4.3.1左递归的消除关于非终结符P的规则4.3LL（间接左递归定义：若P==+>Pαα∈Ｖ*例如间接左递归

S→AaA→Sb|bS==>Aa==>Sba即S==+>Sb用S的产生式右部替换A右部的S得：

A→Aab|b

变成A的产生式含有直接左递归4.3LL（1）分析法间接左递归定义：4.3LL（1）分析法消除直接左递归的方法改写为等价的右递归形如：P→Pα｜β

α非ε，β不以P开始

改写为：P→βP’（P’为新增加的非终结符）

P'→αP'｜ε改写前产生式可产生短语P==>Pα==>βα

改写后产生式可产生短语

P==>βP’

==>βαP'

==>βα

等价4.3LL（1）分析法消除直接左递归的方法改写为等价的右递归等价4.3LL（E→E+T｜TT→T*F｜FF→(E)｜iE→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜i4.3LL（1）分析法E→E+T｜TE→TE'4.3LL（1）分消除多个直接左递归若有多个左递归的产生式如：P→Pα1|Pα2|…|Pαm|β1|β2|…|βn消除左递归后变为：

P→β1P’|β2P’|…|βnP’ P’→α1P’|α2P’|…|αmP’|ε消除左递归要求文法：

1.无回路（A==*>A）

2.无空产生式（A→ε）4.3LL（1）分析法消除多个直接左递归若有多个左递归的产生式如：消除左递归后变为练习例如有文法：

K→Ka|Kb|Kc|d|e

消除左递归后变为：

K→dK’|eK’

K’→aK’|bK’|cK’|ε4.3LL（1）分析法练习例如有文法：消除左递归后变为：4.3LL（1）分析法间接左递归消除举例S→Qc｜cQ→Rb｜b

R→Sa｜aS=>Qc=>Rbc=>Sabc

是间接左递归消除方法1：将非终结符排序：

RQS将R的右部代入Q，S：

Q→Sab｜ab｜bS→Qc｜c（不变）将Q的右部代入S：

S→Sabc｜abc｜bc｜c消除S的直接左递归：

S→abcS’｜bcS’|cS’S’→abcS’|εQ→Sab｜ab|bR→Sa｜a整理化简：删除Q，R（无用）消除左递归后得：

S→abcS’｜bcS’|cS’S’→abcS’|ε4.3LL（1）分析法间接左递归消除举例S→Qc｜c将Q的右部代入S：4.

S→Qc｜cQ→Rb｜b

R→Sa｜a消除方法2：将非终结符排序：

SQR将S的右部代入Q，R：

Q→Rb｜b（不变）

R→Qca｜ca|a将Q的右部代入R：

R→Rbca｜bca|ca|a消除R的直接左递归：

R→bcaR’｜caR’|aR’

R’→bcaR’|ε

整理化简：S，Q（有用）消除左递归后得：

S→Qc｜cQ→Rb｜bR→bcaR’｜caR’|aR’R’→bcaR’|ε4.3LL（1）分析法S→Qc｜c将Q的右部代入R：4.3LL（1）分消除左递归算法1.以某种S顺序将文法的非终结符排列

P1，P2，…,Pn

2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pjγ的规则改写成

Pi→δ1γ|δ2γ|…|δkγ,其中

Pj→δ1|δ2|…|γ是关于Pj的所有规则;

消除Pi的直接左递归

END3.化简由2所得的文法，即去除那些从开始符号出发永远无法到达的非终结符的产生式当非终结符的排列顺序不同时，变换后的文法形式可能不同，但是它们都和原文法是等价的4.3LL（1）分析法消除左递归算法1.以某种S顺序将文法的非终结符排列当非终结符4.3.2消除回溯、提左因子消除回溯目的对文法的任何非终结符，当它去匹配输入串时，能够根据输入符号，准确地选择合适的候选式去匹配若需要非终结符A去匹配输入串，A的候选式为A→α1|α2|…|αn

，

A所面临的第一个输入符号为a时，A能准确地选择αi去执行匹配任务，则无需回溯4.3LL（1）分析法4.3.2消除回溯、提左因子消除回溯目的4.3LL（1提取公共左因子方法对于所有形如A→αβ1｜αβ2｜...｜αβn｜γ的规则其中，α为左因子，γ不以α开头改写为A→αA'｜γ其中A’为新增加的非终结符

A'→β1｜β2｜...｜βn例如

S→xAyA→ab|a提左因子后变换为

S→xAy

A→aA