《(精品)编译原理第四章_(1).ppt》由会员分享，可在线阅读，更多相关《(精品)编译原理第四章_(1).ppt（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 语法分析(Parsing/Syntax Analysis)自顶向下分析方法 Grammar/Syntax:the way in which words are put together to form phrases,clauses,or sentences.Parse:to analyze or separate into more easily processed components.1l在设计语言时，每种程序设计语言都有一组精在设计语言时，每种程序设计语言都有一组精确的规则来描述良构（确的规则来描述良构（well-formed)程序的语程序的语法结构。法结构。l高级语言的大部分
2、语法结构可用上下文无关文高级语言的大部分语法结构可用上下文无关文法描述，因而宜于将上下文无关文法用作语法法描述，因而宜于将上下文无关文法用作语法分析的基础。分析的基础。2语法分析在编译程序中的逻辑位置语法分析在编译程序中的逻辑位置表表 处处 理理 错错 误误 处处 理理 目目标标代代码码生生成成中中间间代代码码优优化化中中间间代代码码生生成成语语义义分分析析语语语语法法法法分分分分析析析析词词法法分分析析目目标标程程序序源源程程序序3l语法分析程序的功能语法分析程序的功能 l语法分析方法的分类：语法分析方法的分类：自顶向下语法分析方法自顶向下语法分析方法(Top-Down)自底向上语法分析方法
3、自底向上语法分析方法(Bottom-Up)l两种自顶向下语法分析方法：两种自顶向下语法分析方法：F非确定的自顶向下语法分析方法非确定的自顶向下语法分析方法F确定的自顶向下语法分析方法：确定的自顶向下语法分析方法：f递归下降子程序方法递归下降子程序方法fLL（1）方法）方法lFirst 集、集、Follow集、集、Predict集集主主 要要 内内 容容4l语法分析的任务是语法分析的任务是：把词法分析的输出作为输入，按照文法规则，从源把词法分析的输出作为输入，按照文法规则，从源程序符号串中识别出各类语法成分，同时进行语法程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备
4、检查，为语义分析和代码生成做准备;抽象地说语法分析就是已知文法，判断一给定的字抽象地说语法分析就是已知文法，判断一给定的字符串是否是该文法的句子符串是否是该文法的句子;词法分析给出的单词的内部表示是上下文无关文法词法分析给出的单词的内部表示是上下文无关文法中的终极符。中的终极符。4.1 语法分析程序介绍语法分析程序介绍4.1.1 4.1.1 语法分析程序的功能语法分析程序的功能5设有文法设有文法G:E T|E+T T F|T*F F (E)|Int|Id Int 0|1 Int|2 Int|3 Int|4 Int|5 Int|6 Int|7 Int|8 Int|9 Int Int|0 Int|
5、1 Int|2 Int|3 Int|4 Int|5 Int|6 Int|7 Int|8 Int|9 Int Id a Id|b Id|y Id|z Id|A Id|B Id.|Y Id|Z Id Id|a Id|z Id|A Id.|Z Id|0 Id.|Z Id|0 Id单词内部表示是上下文无单词内部表示是上下文无关文法中的终极符关文法中的终极符?设有文法设有文法G:E T|E+T T F|T*F F (E)|int|id($id,count)($id,is )($assi,)($id,sum)($plus,)4.1.1 4.1.1 语法分析程序的功能（续语法分析程序的功能（续语法分析程序的
6、功能（续语法分析程序的功能（续2 2）issumcount;:=+设有文法设有文法G:E T|E+T T F|T*F F (E)|（$int,-）|($id,-)6词法分析时作为字符串的词法分析时作为字符串的单词单词的形式化式的形式化式描述（描述（3型文法，自动机及正则表达）：终极符？型文法，自动机及正则表达）：终极符？语言的基本字符集语法分析时作为字符串的语法分析时作为字符串的程序程序的的2型文法描述：终极符？型文法描述：终极符？Token.typeToken？4.1.1 语法分析程序的功能（续语法分析程序的功能（续3）7例例 某程序片段如下：某程序片段如下：sum:=first+count
7、*10 ($id,sum)($assi,)($id,first)($plus,)($id,count)($mult,)($int,10)$id$assi$id$plus$id$mult$int 4.1.1 4.1.1 语法分析程序的功能语法分析程序的功能语法分析程序的功能语法分析程序的功能（续（续（续（续4 4）id :=id +id *int 8l语法分析器（语法分析器（Parser ）：）：执行语法分析任务的程序称为语法分析程序，也称执行语法分析任务的程序称为语法分析程序，也称为语法分析器。为语法分析器。l分析器分析器(程序）和识别器程序）和识别器(程序）的区别程序）的区别a识别器的主要功
8、能是识别输入的字符串是否合法；识别器的主要功能是识别输入的字符串是否合法；a分析器的功能是识别输入字符串的合法性和语法结分析器的功能是识别输入字符串的合法性和语法结构。构。a单词里不能再包含其它结构，即单词是不可分的简单词里不能再包含其它结构，即单词是不可分的简单对象，因此单词处理实际上用的是识别器。单对象，因此单词处理实际上用的是识别器。a编译器在进行语法处理时，需要识别和分解程序中编译器在进行语法处理时，需要识别和分解程序中的各种成分，因此语法处理需要用分析器。的各种成分，因此语法处理需要用分析器。4.1.1 4.1.1 语法分析程序的功能（续语法分析程序的功能（续语法分析程序的功能（续语
9、法分析程序的功能（续5 5）9语法分析器编译程序的后续部分语法树语法树/语法错误信息语法错误信息源程序的CharList词法分析器词法分析后的TokenList4.1.1 语法分析程序的功能（续语法分析程序的功能（续6）10语法分析器编译程序的后续部分语法树语法树/语法错误信息语法错误信息源程序词法分析器Token取下一个单词4.1.1 语法分析程序的功能（续语法分析程序的功能（续7）11l语法分析方法的分类：语法分析方法的分类：自顶向下语法分析方法自顶向下语法分析方法(Top-Down)，亦称，亦称面向目标的分析方法面向目标的分析方法;自底向上语法分析方法自底向上语法分析方法(Bottom-
10、Up)。4.1.1 语法分析程序的功能（续语法分析程序的功能（续8）12自顶向下分析概述自顶向下分析概述 从文法开始符出发试图最左推导出所给的终极符串。从文法开始符出发试图最左推导出所给的终极符串。例例 Gz:Gz:1 Z 1 Z aBdaBd 2 B 2 B d d 3 B 3 B c 4 B c 4 B bBbB 对给定的终极符串对给定的终极符串abcdabcd，推导过程：推导过程：Z Za aB Bd db bB Bc cZ Z 1 1 aBdaBd 4 4 abBdabBd33 abcdabcd13自底向上分析概述自底向上分析概述 从终极符串出发归约（从终极符串出发归约（reducer
11、educe）出文法的开始符。出文法的开始符。例例 Gz:1 Z Gz:1 Z aBdaBd 2 B 2 B d d 3 B 3 B c 4 B c 4 B bBbB 对给定的终极符串对给定的终极符串abcdabcd，归约过程：归约过程：ababc cd d 3 3 a abBbBd d 4 4 aBdaBd 33 Z ZZ Za ab bc cd dB BB B144.1.2 4.1.2 语法错误的处理原则语法错误的处理原则 1 1源程序中可能出现的错误源程序中可能出现的错误l词法错误词法错误 非法字符等，如非法字符等，如:。l语法错误语法错误 语法错误是指语法结构出错，常见错误有：语法错误是
12、指语法结构出错，常见错误有：程序的开始符，语句（表达式）的开始符（后程序的开始符，语句（表达式）的开始符（后继符）错；继符）错；标识符（常量）错：该出现时未出现；标识符（常量）错：该出现时未出现；括号类错误：不匹配；括号类错误：不匹配；分隔符错。分隔符错。例如：例如：beginbeginx:=a+bx:=a+by:=x;y:=x;15l语义错误语义错误静态语义错误：如类型不一致、参数不匹配等；静态语义错误：如类型不一致、参数不匹配等；如：如：a,b:integera,b:integer;x:array1.10 of integer;x:array1.10 of integer;x:=x:=a+
13、ba+b;动动态态语语义义错错误误（逻逻辑辑错错误误）：如如无无穷穷递递归归、变变量量为零时作除数等。为零时作除数等。如：如：while(t).;while(t).;a:=a/b;a:=a/b;大多数错误的诊断和恢复集中在语法分析阶段。一个原大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分析方法的因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。准确性，它们能以非常有效的方法诊断语法错误。在编译的时侯，想要准确诊断语义或逻辑错误有时是很在编译的时侯，想要准确诊断语义或逻辑错误有时是很困难的。困难的。4.1
14、.2 4.1.2 语法错误的处理原则语法错误的处理原则（续（续1 1）164.1.2 4.1.2 语法错误的处理原则语法错误的处理原则（续（续2 2）2 2语法错误处理的目标语法错误处理的目标 对语法错误的处理，一般希望达到以下基本目标：对语法错误的处理，一般希望达到以下基本目标：清楚而准确地报告错误的出现，地点正确、不漏清楚而准确地报告错误的出现，地点正确、不漏 报、不错报也不多报；报、不错报也不多报；迅速地从每个错误中恢复过来（以便分析继续进迅速地从每个错误中恢复过来（以便分析继续进 行）；行）；不应使语法正确源程序的分析速度降低太多。不应使语法正确源程序的分析速度降低太多。173 3语法
15、错误的基本恢复策略语法错误的基本恢复策略 l紧急方式恢复：紧急方式恢复：抛弃若干输入，直到遇到同步记号。抛弃若干输入，直到遇到同步记号。l短短语语级级恢恢复复：采采用用串串替替换换的的方方式式对对剩剩余余输输入入进进行行局局部部纠正（抛弃插入）。纠正（抛弃插入）。l出出错错产产生生式式：用用出出错错产产生生式式捕捕捉捉错错误误（预预测测错错误误）。预置型的短语级恢复方式。预置型的短语级恢复方式。l全局纠正：全局纠正：对错误输入序列对错误输入序列x x，找相近序列找相近序列y y，使得使得x x变换成变换成y y所需的修改、插入、删除次数最少。所需的修改、插入、删除次数最少。4.1.2 4.1.
16、2 语法错误的处理原则语法错误的处理原则（续（续3 3）18例例 下下述述两两条条是是有有语语法法错错误误的的语语句句，其其中中第第一一条条赋赋值值句句结结束束时时忘忘记记加加分分号号，采采用用紧紧急急恢恢复复方方式式和和短短语语级级恢恢复方式的可能结果分别如下所示。复方式的可能结果分别如下所示。x:=a+bx:=a+b y:=c+d;y:=c+d;紧急方式：紧急方式：x:=a+b+d;x:=a+b+d;注注：丢丢弃弃b b之之后后的的若若干干记记号号，直直到到遇遇到到同同步步记记号号+为止。为止。短语级恢复：短语级恢复：x:=a+b;x:=a+b;y:=c+d;y:=c+d;注：加入分号，使
17、之成为一个赋值句。注：加入分号，使之成为一个赋值句。4.1.2 4.1.2 语法错误的处理原则语法错误的处理原则（续（续4 4）194.1.3 自顶向下语法分析基本思想自顶向下语法分析基本思想l自顶向下语法分析方法，亦称面向目标的分析方法。自顶向下语法分析方法，亦称面向目标的分析方法。l思想：从文法的开始符出发企图用思想：从文法的开始符出发企图用最左推导最左推导推推导出与输入的单词串完全相匹配的句子。若输导出与输入的单词串完全相匹配的句子。若输入的单词串是给定文法的句子，则必能推出，入的单词串是给定文法的句子，则必能推出，反之必然以推导失败而终止。反之必然以推导失败而终止。l自顶向下语法分析方
18、法分为：自顶向下语法分析方法分为：1、非确定的自顶向下语法分析方法、非确定的自顶向下语法分析方法;2、确定的自顶向下语法分析方法：实现方法简、确定的自顶向下语法分析方法：实现方法简单、直观，便于手工构造和自动生成，是目前单、直观，便于手工构造和自动生成，是目前常用的语法分析方法。常用的语法分析方法。u 递归下降方法；递归下降方法；u LL（1）方法。）方法。20非确定的自顶向下语法分析方法（带回溯过程的自顶向下语法分析非确定的自顶向下语法分析方法（带回溯过程的自顶向下语法分析方法）方法）已知已知GS:SAy|BAy AaAaBxBx 输入串为输入串为xay是否正确。是否正确。AyBAy aAy
19、a xBAyx xxBAyx xxAyS xAya xaAya xaaAy xaay xay ay BAy21 综述：综述：非确定的自顶向下语法分析方法是一种穷举非确定的自顶向下语法分析方法是一种穷举的试探方法，由于回溯导致语义推导重来、不能确的试探方法，由于回溯导致语义推导重来、不能确切报告错误位置、不能处理左递归文法、效率低、切报告错误位置、不能处理左递归文法、效率低、代价高，因此，尽管这种方法适合于更广泛的文法，代价高，因此，尽管这种方法适合于更广泛的文法，但也只是一种理论上可行的方法，极少使用。但也只是一种理论上可行的方法，极少使用。22确定的自顶向下语法分析方法：确定的自顶向下语法分
20、析方法：实现方法简单、实现方法简单、直观，便于手工构造和自动生成，是目前常直观，便于手工构造和自动生成，是目前常用的语法分析方法。用的语法分析方法。u 递归下降方法；递归下降方法；u LL（1）方法。）方法。234.1.4 三个重要的集合三个重要的集合 lFirst集集 First()=a VT|*a.(if *then else )lFollow集集 Follow(A)=a VT|S+.Aa.(if S*.A then#else )lPredict集集(Select集集)Predict(A)First()当当 First()=First()-Follow(A)当当 First()SS#24对
21、每一文法符号对每一文法符号X计算计算First(X)集集l 若若X VT：First(X)=Xl若若X VN:对关于对关于X的每一个产生式进行如下处理的每一个产生式进行如下处理:uStep1.形如形如:X ,则则:First(X)uStep2.形如形如:X a,a VT则则:a First(X)25uStep3.对对形如下的产生式形如下的产生式:XY1Y2Yi-1YiYn若：若：Y1,Y2,Yi VN且且Y1,Y2,Yi-1*则则:First(Y1)-,First(Y2)-,First(Yi-1)-,First(Yi)都包含在都包含在First(X)中。中。若：若：Yi VN且且Yi*(i=1
22、,2,n),则则:First(Y1),First(Y2),First(Yn)都包含在都包含在First(X)中。中。重复重复Step3，直至对所有，直至对所有A VN，First(A)收敛为止。收敛为止。对每一文法符号对每一文法符号X计算计算First(X)集集26例：l E T El E +T E|l T F Tl T *F T|l F id|(E)文法符号文法符号First集集EETTF ,+,*id,(id,(id,(27计算计算First()集集若符号串若符号串=X1X2Xn，l当当X1,X2,Xi-1*，Xi 不能不能*，则则:First()=1i-1(First(Xj)-)Firs
23、t(Xi)l若所有若所有Xi 都能都能*，则则:First()=1n First(Xj)28例：l E T El E +T E|l T F Tl T *F T|l F id|(E)符号串符号串First集集T E id,(文法符号文法符号First集集EETTF id,(id,(id,(+,*,id,(F TE T T+,*,id,(E T +,*,291:对所有对所有A VN 且且 A非非开始符开始符:令令Follow(A):=；对开始符对开始符 S:令令Follow(S)=#；2:若有产生式若有产生式AxBy：如果如果 First(y)则：则：Follow(B)=Follow(B)(Fir
24、st(y)Follow(A)否则：否则：Follow(B)=Follow(B)First(y)3:重复重复2和和3，直至对所有，直至对所有A VN，Follow(A)收收 敛为止。敛为止。计算计算Follow(A)(AVVN N)?返回返回30例：E T E E +T E|T F T T *F T|F id|(E)文法符号文法符号First集集EETTF id,(id,(id,(+,*,#Follow集集,)#,),#,)+,#,)+,#,),+*算法回顾算法回顾31计算计算Predict集集lPredict(A)First()，当，当First()不含不含=First()-Follow(A)
25、，当当First()含含32例：l E T El E +T E|l T F Tl T *F T|l F id|(E)文法符号文法符号First集集Follow集集E id,(),#E+,),#T id,(+,),#T*,+,),#F id,(*,+,),#Predict(ETE)=first(TE)=id,(Predict(E+TE)=first(+TE)=+Predict(E )=follow(E)=),#Predict(T FT)=first(FT)=id,(33例：l E T El E +T E|l T F Tl T *F T|l F id|(E)文法符号文法符号First集集Follo
26、w集集E id,(),#E+,),#T id,(+,),#T*,+,),#F id,(*,+,),#Predict(T*FT)=first(*FT)=*Predict(T )=follow(T)=+,),#Predict(F id)=first(id)=id Predict(F(E)=first(E)=(34例：l S ABcl A al A l B bl B 文法符号文法符号First集集SAB ,aa,b,c,bFollow集集#cb,cPredict(S ABc)=first(ABc)=a,b,c Predict(A a)=a Predict(A )=follow(A)=b,c Pred
27、ict(B b)=bPredict(B )=follow(B)=c 35l非确定的自顶向下语法分析方法主要问题：虚假非确定的自顶向下语法分析方法主要问题：虚假匹配而引起回溯，原因是：匹配而引起回溯，原因是：1.由于相同左部的产生式的右部的由于相同左部的产生式的右部的FIRST集的交集集的交集不为空而引起回溯。不为空而引起回溯。例：有如下文法例：有如下文法GZ：Z cAe|cAd A eb|a分析字符串分析字符串cad。First(cAe)First(cAd)Predict(Z cAe)Predict(ZcAd)至多有一个至多有一个产产生式被生式被选择选择的条件是：的条件是：predict(Ap
28、redict(Ak k)predict(Apredict(Aj j)=)=，当，当k k j jNEXT362.由于某由于某非终极符非终极符的产生式的右部能推导出的产生式的右部能推导出，且该非终极，且该非终极符的符的FOLLOW集中含有其某个产生式右部的集中含有其某个产生式右部的FIRST集中集中的元素。的元素。例：例：有如下文法有如下文法GS：S aAS|b A bAS|d分析字符串分析字符串ab。First(bAS)First(d)=Predict(A bAS)Predict(A )至多有一个至多有一个产产生式被生式被选择选择的条件是：的条件是：predict(Apredict(Ak k)
29、predict(Apredict(Aj j)=)=，当，当k k j jFirst(bAS)First()=First(d)First()=Follow(A)=b,a Predict(A d)Predict(A )=NEXT Predict(A d)Predict(A bAS)=373.由于文法的左递归由于文法的左递归。例：例：有如下文法有如下文法GS：S Sa S b分析字符串分析字符串baa。Predict(S Sa)Predict(S b)至多有一个至多有一个产产生式被生式被选择选择的条件是：的条件是：predict(Apredict(Ak k)predict(Apredict(Aj j
30、)=)=，当，当k k j j该该条件就是不条件就是不带带回溯的自回溯的自顶顶向下向下语语法分析方法法分析方法（确定的（确定的自顶向下语法分析方法）自顶向下语法分析方法）的条件。的条件。满满足足该该条件的文法称条件的文法称为为LL(1)文法，文法，递归下降子程序文法递归下降子程序文法。NEXT38l非非LL(1)文法到文法到LL(1)文法的等价转换文法的等价转换消除左公共前缀消除左公共前缀消除消除直接直接左递归左递归 消除左递归消除左递归注意注意1：即使文法没有公共前缀和左递归也并不意即使文法没有公共前缀和左递归也并不意味着文法一定是味着文法一定是LL(1)文法，有时还需要其它的转文法，有时还
31、需要其它的转换方法。换方法。示例示例1注意注意2：通常程序设计语言的文法大都可以转换成通常程序设计语言的文法大都可以转换成LL(1)文法，但已经证明，非文法，但已经证明，非LL(1)文法是存在的，文法是存在的，即有些文法是无法变换成即有些文法是无法变换成LL(1)文法的。文法的。示例示例239 4.2 递归下降法递归下降法4.2.1 递归下降法语法分析原理递归下降法语法分析原理l递归下降法递归下降法(Recur(Recursive-Descent Parsing)-Descent Parsing)对对每个非终极符每个非终极符构造相应的一个子程构造相应的一个子程序序(称为语法分析子程序称为语法分
32、析子程序)，其功能是识别、，其功能是识别、分析该分析该非终极符所能推导出的字符串。非终极符所能推导出的字符串。40例如：一条产生式例如：一条产生式：StmStmwhilewhile ExpExp dodo StmStm 则则对对应应产产生生式式右右部部的的语语法法分分析析程程序序部部分如下：分如下：beginbegin Match(while)；Exp；Match(do)；Stm endend 41 begin Match($while)；Exp；Match($do)；Stm end while x y do if x y then x :=y+x else y:=x递归下降分析示图递归下降分
33、析示图424.2.2 递归下降法语法分析程序的递归下降法语法分析程序的构造构造一、递归下降法语法分析程序的构造一、递归下降法语法分析程序的构造引进下面两个基本动作：引进下面两个基本动作：lReadToken：从输入流把下一个：从输入流把下一个TOKEN码读到变量码读到变量token中。中。lMatch(a)：检查：检查token=a?若是，则执行若是，则执行ReadToken，否则报错并作相应的处理。，否则报错并作相应的处理。其中其中a是终极符（是终极符（TOKEN的语法信息）。的语法信息）。43l 对每一个非终极符对每一个非终极符A构造构造子程：子程：当产生式中形如当产生式中形如:A:A 1
34、 1|2 2|n n 则按下面的方法编写子程序则按下面的方法编写子程序A A：procedure A()procedure A()begin begin if token if token Predict(APredict(A1 1)then)then (1 1)else else if token if token Predict(APredict(A2 2)then)then (2 2)else else if token if token Predict(APredict(An)then n)then (n n)else else err()err()end end 语法分析主程序：语法
35、分析主程序：Begin ReadToken;S；Match(#)end44终极符终极符产生匹配命令，而产生匹配命令，而非终极符非终极符则产生调用命则产生调用命令。因为文法递归相应子程序也递归，所以称这令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。种方法为递归子程序方法或递归下降法。其中：令其中：令 i=X0X1X2Xn，则：，则：(i)=(X0);(X1);(X2);(Xn);如果如果X V VN N，(X)=X 如果如果X V VT T，(X)=Match(X)如果如果X=,()=skip(空语句空语句)45例：假设有文法例：假设有文法Z a B aB b B
36、|cPredict(ZaBaaBa)=a,Predict(BbBbB)=b,PredictBc=c则相应的递归子程序可如下：则相应的递归子程序可如下：procedure Z()begin if token=a then Match(a)；B；Match(a)else err(1)end;procedure B()begin if token=b then Match(b);B;else if token=c then Match(c);else err(2)end;语法分析主程序：语法分析主程序：Begin ReadToken;Z；Match(#)endReadTokenReadToken46
37、例：E T E E +T E|T F T T *F T|F id|(E)Predict(ETE)=first(TE)=id,(Predict(E+TE)=first(+TE)=+Predict(E )=follow(E)=),#Predict(T FT)=first(FT)=id,(Predict(T*FT)=first(*FT)=*Predict(T )=follow(T)=+,),#Predict(F id)=first(id)=id Predict(F(E)=first(E)=(procedure E()begin if token id,(then T；E；else err(1)end
38、;语法分析主程序：语法分析主程序：Begin ReadToken;E；Match(#)end47procedure E()begin if token=“+”then Match(+);T；E else if token ),#then skip else err(2)end;例：E T E E +T E|T F T T *F T|F id|(E)Predict(ETE)=first(TE)=id,(Predict(E+TE)=first(+TE)=+Predict(E )=follow(E)=),#Predict(T FT)=first(FT)=id,(Predict(T*FT)=first
39、(*FT)=*Predict(T )=follow(T)=+,),#Predict(F id)=first(id)=id Predict(F(E)=first(E)=(48例：E T E E +T E|T F T T *F T|F id|(E)Predict(ETE)=first(TE)=id,(Predict(E+TE)=first(+TE)=+Predict(E )=follow(E)=),#Predict(T FT)=first(FT)=id,(Predict(T*FT)=first(*FT)=*Predict(T )=follow(T)=+,),#Predict(F id)=first
40、(id)=id Predict(F(E)=first(E)=(procedure T()begin if token id,(then F；T else err(3)end;49procedure T()begin if token=“*”then Match(*);F；T else if token +,),#then skip else err(4)end;例：E T E E +T E|T F T T *F T|F id|(E)Predict(ETE)=first(TE)=id,(Predict(E+TE)=first(+TE)=+Predict(E )=follow(E)=),#Pred
41、ict(T FT)=first(FT)=id,(Predict(T*FT)=first(*FT)=*Predict(T )=follow(T)=+,),#Predict(F id)=first(id)=id Predict(F(E)=first(E)=(50procedure F()begin if token=“id”then Match(id)else if token=“(”then Match();E;Match()else err(5)end;例：E T E E +T E|T F T T *F T|F id|(E)Predict(ETE)=first(TE)=id,(Predict(
42、E+TE)=first(+TE)=+Predict(E )=follow(E)=),#Predict(T FT)=first(FT)=id,(Predict(T*FT)=first(*FT)=*Predict(T )=follow(T)=+,),#Predict(F id)=first(id)=id Predict(F(E)=first(E)=(51ETFiiM(i)ETFiiM(i)ETFTi+i*i#递归下降分析过程递归下降分析过程+M(+)*#*M(*)i#skip#M(i)skipETEE+TETFTT*FTF(E)iT+skipTEFT+TEFTiii*FT语法分析主程序：语法分析主
43、程序：Begin ReadToken;E；Match(#)end52q递归子下降子程序方法的条件：递归子下降子程序方法的条件：predict(Apredict(A k k)predict(Apredict(A j j)=)=，当，当k k j j 二、递归子程序方法的进一步讨论二、递归子程序方法的进一步讨论q产生式产生式AA 被选择的条件是：被选择的条件是：当前的输入符属于当前的输入符属于predict(predict(AA)。q至多一个产生式被选择的条件是：至多一个产生式被选择的条件是：predict(Apredict(A k k)predict(A predict(A j j)=)=，当，
44、当k k j j53三、对递归下降分析法的评价三、对递归下降分析法的评价l递归下降分析法的优点是：递归下降分析法的优点是：简单、直观、简单、直观、程序结构和层次清晰明了，易于手工实程序结构和层次清晰明了，易于手工实现；现；l递归下降分析法的缺点是：递归下降分析法的缺点是：对文法要求对文法要求高；另一个缺点是频繁的递归调用使得高；另一个缺点是频繁的递归调用使得速度慢且占用空间多。速度慢且占用空间多。54z作业：作业：写出下面文法写出下面文法GpGp的递归下降语法分析的递归下降语法分析程序程序:P P D D;S SD D int:iint:i|D D;int:i;int:iS S i|i:=i|
45、i:=E E|i:|i:S S|gotogoto i i|if|if E E then then S S|while|while E E do do S S|begin|begin L L end end|L L S S|L L;S SE E i|(i|(E E)|)|E E i i55z练习题：练习题：已知文法已知文法GS:GS:S SAB|bC AB|bC A A|b|b B B|aD|aD C C AD|b AD|b D D aS|c aS|c 1 1、计算每个非终极符的、计算每个非终极符的FirstFirst集、集、FollowFollow集。集。2 2、计算每个产生式的、计算每个产生
46、式的PredictPredict集合。集合。3 3、判断该文法是否为递归下降文法？、判断该文法是否为递归下降文法？56文法符号文法符号First集集Follow集集S a,b,#A b,a,c,#B a,#C a,b,c#D a,c#SAB|bC A|b B|aD C AD|b D aS|c57Predict(SAB )=a,b,#Predict(S bC)=b Predict(A )=a,c,#Predict(Ab)=b Predict(B )=#Predict(B aD)=a Predict(C AD)=a,b,c Predict(C b)=b 由于：由于：Predict(SAB )Pre
47、dict(S bC)=b Predict(C AD)Predict(C b)=b 所以所以该文法不是递归下降文法。该文法不是递归下降文法。58示例示例1：设有如下文法：设有如下文法：Stm Label:UnLabeledStmStm idUnLabeledStm id:=ExpLabel idStm id StmStm :UnLabeledStm|UnLabeledStm id:=ExpStm id:UnLabeledStmStm idUnLabeledStm id:=Exp59示例示例2：S if id then S ELSES OtherStmELSE else SELSE 因:Predict(ELSEelse S)=else Predict(ELSE)=Follow(ELSE)=else,该文法不是LL(1)文法。Follow(ELSE)=Follow(ELSE)Follow(S)Follow(S)=Follow(S)First(ELSE)-6061