编译原理-第四章

编译原理

——第四章语法分析(自上而下分析)王金伟计算机与信息工程学院天津师范大学TJNU-COCIE-WJW22023/2/5第四章语法分析(自上而下分析)4.1上下文无关文法4.2带回溯的自上而下语法分析4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序TJNU-COCIE-WJW32023/2/5语法分析的任务在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器执行语法分析的程序称为语法分析器其功能是输入：由单词符号组成的有限序列输出：语法范畴(语法单位)TJNU-COCIE-WJW42023/2/5语法分析的方法自上而下分析法(由文法开始符号推出句子)一般分析方法(穷举，带回溯)递归下降分析法(消除左递归，不带回溯)预测方法(LL(1)方法，一张分析表和一个栈)自下而上分析法(由输入串开始逐步归约到文法开始符号)算符优先分析法LR分析法TJNU-COCIE-WJW52023/2/5语法分析器在编译程序中的核心地位语法分析器词法分析器编译程序后续部分符号表单词符号取下一个单词符号语法分析树源程序TJNU-COCIE-WJW62023/2/54.1上下文无关文法1.文法 是描述语言的语法结构的形式规则（语法规则）

例如： 自然语言句子的主谓宾结构一、文法概述TJNU-COCIE-WJW72023/2/52.上下文无关文法

(1)它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的（与它所在的上下文无关）

例如：程序设计语言中的一个算术表达式

A*B

(2)自然语言中不适合于上下文无关文法

例如：汉语中的“打”字是一个泛义动词 “打毛衣” —— “编织” “打篮球” —— “玩” “打水” —— “取得”

(3)对于程序设计语言来说用上下文无关的文法来描述就足够了TJNU-COCIE-WJW82023/2/51.引例：有一个由英语单词组成的一个单词串

Theboyseesthegirl

用→表示“由…组成”或“定义为”，定义一些语法规则

<句子>→<主语><谓语><宾语> <主语>→<冠词><名词> <谓语>→<动词> <宾语>→<冠词><名词> <冠词>→the <名词>→boy <名词>→girl <动词>→sees二、文法和语言的形式定义TJNU-COCIE-WJW92023/2/51.引例（续） 问题：Theboyseesthegirl

是不是一个语法上正确的句子？ 思想：是否可以利用我们定义的这些语法规则推导出这个句子 方法：从<句子>出发，反复把上述规则中的“→”左边成分替换成右边成分TJNU-COCIE-WJW102023/2/5

推导过程：

<句子>=><主语><谓语><宾语> =><冠词><名词><谓语><宾语> =>The<名词><谓语><宾语> =>Theboy<谓语><宾语> =>Theboy<动词><宾语> =>Theboysees<宾语> =>Theboysees<冠词><名词> =>Theboyseesthe<名词> =>Theboyseesthegirl<句子>→<主语><谓语><宾语><主语>→<冠词><名词><谓语>→<动词><宾语>→<冠词><名词><冠词>→the<名词>→boy<名词>→girl<动词>→seesTJNU-COCIE-WJW112023/2/5也可以用语法分析树来表示这种推导

<句子> <主语> <谓语> <宾语><冠词><名词><动词><冠词><名词>TheboyseesthegirlTJNU-COCIE-WJW122023/2/52.

引出几个概念(1)终结符号 不带尖括号的部分，就是单词符号，语法分析角度是不可再分的基本符号例如：the、boy、sees、girl等前面说的：基本字、标识符、常数、算符和界符等TJNU-COCIE-WJW132023/2/5(2)非终结符号带尖括号的部分，代表一类语法成分(语法范畴)例如：<句子>、<主语>、<冠词>、

<名词>、<谓语>、<宾语>等前面说的：算数表达式、布尔表达式、赋值语句、分程序、过程等TJNU-COCIE-WJW142023/2/5(3)开始符号(识别符号，纲符号)A.指定一个非终结符号为开始符号，表示推导从它开始B.代表所定义语言中我们最感兴趣的语法范畴C.是由其他语法范畴构造起来的例如：句子 句子是由主语、谓语、宾语这些语法范畴构成的前面说的：程序 程序是由分程序、过程这些语法范畴构成的TJNU-COCIE-WJW152023/2/5(4)产生式(产生规则、规则)是定义语法范畴的一种书写规则， 形式为： A→αA是某个非终结符号,称为产生式的左部，α可以是终结符号,也可以是非终结符号，还可以是终结符号和非终结符号组成的任意符号串，称为产生式的右部例如：<句子>→<主语><谓语><宾语> <主语>→<冠词><名词> <谓语>→<动词><宾语>→<冠词><名词><冠词>→the<名词>→boy <名词>→girl<动词>→seesTJNU-COCIE-WJW162023/2/53.上下文无关文法的形式定义上下文无关文法G定义为四元式(VT，VN，S，P)VT是非空有限集，是终结符号集合，它的每个元素称为终结符号，用小写字母表示。VN是非空有限集，是非终结符号集合，它的每个元素称为非终结符号，用大写字母表示，并且VN∩VT=ΦS∈VN，是一个开始符号，也称为是识别符号，是一个非终结符，至少在一个产生式作为左部出现P是一个产生式的集合(有限)，它的每个元素称为一条产生式(一条规则)，形式：

P→α其中P∈VN，α∈(VN∪VT)*TJNU-COCIE-WJW172023/2/5例：设有文法G(VT，VN，S，P)，其中VT={i，+，*，（，）}VN={E}S=EP：E→

i E→

E+E E→

E*EE→(E)其中i代表变量描述了一类由变量和+*运算组成的算数表达式文法TJNU-COCIE-WJW182023/2/5注意：(1)文法的核心是一组产生式，而开始符号S是文法所要识别的语法范畴（语法单位）(2)若有这样一些左部相同的产生式：

P→α1 P→α2 … P→αn可以合并为一个，缩写成

P→α1|α2|…|αn其中每个αi

称为P的一个候选式，|读作“或”例如：

P：E→

i|E+E|E*E|(E)TJNU-COCIE-WJW192023/2/5例：设有文法G(VT，VN，S，P)，其中VT={i，+，*}VN={E，A}S=EP：E→

i|EAE A→+|*注意：这里P有4条产生式规则。TJNU-COCIE-WJW202023/2/54.推导(1)直接(一次)推导

=>

设一个文法G(VT，VN，S，P)

α,β∈(VN∪VT)* (α,β是终结符或非终结符或终结符和非终结符组成的任意符号串)

且，A→γ是G的一个产生式，如果有

αAβ

=>αγβ

就称αAβ直接推导出αγβ

注意：推导是用产生式的右部替换产生式的左部TJNU-COCIE-WJW212023/2/5(2)α1

到αn的推导如果α1=>α2=>…=>αn则称这个序列是从α1

到αn的一个推导①α1

αn从α1

出发经过1步或若干步推出αn②α1

αn从α1

出发经过0步或若干步推出αn注意：α1

αn

α1=αn

α1

αnTJNU-COCIE-WJW222023/2/5例：设有文法GP：E→

i|E+E|E*E|(E)求从E到(i*i+i)的推导解：

E=>(E) =>(E+E) =>(E*E+E) =>(i*E+E) =>(i*i+E) =>(i*i+i)TJNU-COCIE-WJW232023/2/5注意：常用的推导有两种(1)最左推导任何一步α

=>β都对α最左边的那个非终结符号进行替换例如：E=>(E)=>(E+E)=>(E*E+E)=>(i*E+E)=>(i*i+E)=>(i*i+i)(2)最右推导任何一步α

=>β都对α最右边的那个非终结符号进行替换例如：

E=>(E)=>(E+E)=>(E+i)=>(E*E+i)=>(E*i+i)=>(i*i+i)TJNU-COCIE-WJW242023/2/55.句型设G是一个文法，S是它的开始符号，如果Sα，且α∈(VN∪VT)*则称α是G的一个句型6.句子设G是一个文法，S是它的开始符号，如果Sα，且α∈VT*则称α是G的一个句子注意：(1)句子实际上是仅含有终结符号的句型(2)从一个句型到另一个句型的推导过程不唯一TJNU-COCIE-WJW252023/2/5例：设有文法G(VT，VN，S，P)，其中P：E→

i|E+E|E*E|(E)VT={i，+，*，（，）} ；VN={E}；S=E推导(i*i+i)解：

E =>(E) =>(E+E) =>(E*E+E) =>(i*E+E) =>(i*i+E) =>(i*i+i) (句型)(句型)(句型)(句型)(句型)(句型)(句型,句子)TJNU-COCIE-WJW262023/2/57.语言文法G所产生的句子的全体就是一个语言，记为L(G)L(G)={α|Sα&α∈VT*}8.文法和语言的关系(1)给定一个文法，就能从结构上唯一确定其语言

G-〉L(G) (唯一的)(2)给定一种语言，能找到其文法，但该文法不是唯一的，即

L-〉G1或G2或…TJNU-COCIE-WJW272023/2/5例1：设有文法G(VT，VN，S，P)，其中VT={a,b} ；VN={Z}；S=ZP：Z→

aZb Z→

ab试构造其语言解： 因为Z=>aZb=>a2Zb2=>a3Zb3

=>…=>an-1Zbn-1=>anbn

所以L(G)={anbn

|n≥1}TJNU-COCIE-WJW282023/2/5例2：已知语言L(G)={abna

|n≥1}可构造文法G1：P：S→

aBa B→bB|b还可构造文法G2：P：S→

aBa B→

Bb|bTJNU-COCIE-WJW292023/2/51.语法分析树 用一棵树来表示句型的推导，简称语法树三、语法分析树与二义性TJNU-COCIE-WJW302023/2/5例：设有文法G为E→

i|E+E|E*E|(E)推导：(i*i+i)解：E=>(E)=>(E+E)=>(E*E+E)=> (i*E+E)=>(i*i+E)=>(i*i+i) E 第1代

(E) 第2代

E+E 第3代

E*E 第4代 第5代iiiTJNU-COCIE-WJW312023/2/52.句子的二义性 若一个文法的一个句子对应两棵不同的语法树，则称该句子是二义性句子例：有个句子：手提包 <句子>

<名词>

<手提包><句子><主><谓><宾>

手提包TJNU-COCIE-WJW322023/2/53.文法的二义性 如果一个文法含有二义性的句子，则称该文法是二义性文法TJNU-COCIE-WJW332023/2/5E=>(E)=>(E+E)=>(E*E+E)=>(i*E+E)=>(i*i+E)=>(i*i+i) E (E) E+E E*E

iii例：设有文法G为E→i|E+E|E*E|(E)推导：(i*i+i)E=>(E)=>(E*E)=>(i*E)=>(i*E+E)=>(i*i+E)=>(i*i+i) E (E) E*EE+EiiiTJNU-COCIE-WJW342023/2/5对于上例，规定’*’比‘+’优先级高，且都服从左结合构造无二义性的文法G为E→T|E+T，T

→F|T*F

，F→(E)|i，推导：(i*i+i)解:E=>T=>F=>(E)=>(E+T)=>(T*F+T)=>(F*F+T)=>(i*F+T) =>(i*i+T)=>(i*i+F)=>(i*i+i)ETF(E)E+TT*FFiiiFTJNU-COCIE-WJW352023/2/5乔姆斯基形式语言理论：1956年建立，发展至今，对产生式加以不同限制得到4种类型的文法：

0型

1型

2型

3型四、文法分类TJNU-COCIE-WJW362023/2/50型文法也称为短语结构文法定义：设G=(VN,VT,P,S)，如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*

，则G是一个0型文法任何0型语言都是递归可枚举的，而递归可枚举集必定是一个0型语言其它三类文法都是对0型文法产生式的形式作某些限制得到的TJNU-COCIE-WJW372023/2/51型文法：也称为上下文有关文法定义：设G=(VN,VT,P,S)，如果它的每个产生式有如下形式：xAy→xβy，A∈VN，β∈(VN∪VT)+，x、y∈(VN∪VT)*，则G是一个1型文法对非终结符进行替换时必须考虑上下文，A只有在x和y这样的上下文环境中才能替换为β另一种定义：设G=(VN,Vt,P,S)，如果它的每个产生式α→β满足|β|>=|α|，则G是一个1型文法；把产生式S→ε作为产生式的特例加入1型文法的产生式集合中，但S不能出现在产生式的右部1型文法对程序设计语言的应用来说一般太复杂了，难于应用TJNU-COCIE-WJW382023/2/52型文法也称为上下文无关文法定义：设G=(VN,VT,P,S)，如果它的每个产生式有如下形式：A→β，A∈VN，β∈(VN∪VT)*，则G是一个2型文法2型文法等价于下推自动机（语法分析）2型文法有足够能力来描述现今的多数程序设计语言的语法结构我们今后主要讨论2型文法，就是上下文无关的文法，今后所说的文法，如无特别声明，就是指上下文无关的文法TJNU-COCIE-WJW392023/2/53型文法也称为正规文法、正则文法、线性文法定义：设G=(VN,VT,P,S)，如果它的每个产生式有如下形式：A→aB或A→a，其中A、B∈VN，a∈VT，则G是一个3型文法3型文法等价于有限自动机上述定义给出的定义是右线性文法，如果产生式的形式是：A→Ba或A→a，则称为左线性文法3型文法常用于编译器的词法分析程序的构造TJNU-COCIE-WJW402023/2/54.2带回溯的自上而下语法分析

就是从文法开始符号出发，向下推导，最后推导出句子一、自上而下语法分析TJNU-COCIE-WJW412023/2/5 1.基本思想 对任何一个输入串，试图用一切可能的办法，从文法的开始符号(根节点)出发，根据文法自上而下地为输入串建立一棵语法树，即为输入串寻找一个最左推导。

思想本质：是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。二、带回溯的自上而下语法分析TJNU-COCIE-WJW422023/2/52.例子:设有文法(1)S→xAy(2)A→**|*分析输入串x*y。分析过程如下：利用规则输入串语法树TJNU-COCIE-WJW432023/2/53.构造方法 让每个非终结符号对应一个递归子程序。每个子程序可以作为一个布尔过程(返回“真”或“假”)：

(1)一旦发现该非终结符的某个候选式与输入串相匹配，就用这个候选式去扩展语法树，并返回“真”值；

(2)该候选式和输入串不匹配，则保持原来的语法树和IP值不变(IP回溯)，并返回“假”值TJNU-COCIE-WJW442023/2/51.文法左递归 一个文法存是含有左递归的，如果存在非终结符P，有 P Pα

当试图用P去匹配输入串时，在没有识别任何输入符号的情况下，又得重新要求P去进行新的匹配，这样一来，使推导无限循环下去。2.回溯问题 匹配不成功，需要回溯。但已经走了一大段错路，最后又必须回头，就需要把已经做过的一大堆工作(各种表格工作、语义分析等)推倒重来，既费时又费力三、存在的困难和问题TJNU-COCIE-WJW452023/2/53.虚假匹配设有文法(1)S→xAy(2)A→*|**分析输入串x**y。分析过程如下：利用规则输入串语法树x**y不能被识别TJNU-COCIE-WJW462023/2/54.不易知道错误位置 当最终报告分析不成功时，难于知道输入串中出错的确切位置5.效率极低 由于带回溯，实际上才用了一种穷尽一切可能的试探法，因此，效率很低，代价极高。该方法只有理论意义，在实践上价值不大TJNU-COCIE-WJW472023/2/54.3LL(1)分析法目的： 构造不带回溯的自上而下分析算法要求：

(1)消除文法的左递归性

(自上而下分析方法不允许文法含有左递归) (2)找出克服回溯的充分必要条件

(不要回溯)TJNU-COCIE-WJW482023/2/51.直接左递归

直接见于产生式的左递归称为直接左递归.

例如：产生式 U→U…2.间接左递归 若有 U U…

例如:文法

S→Aa|b A→Ac|Sd|εS=>Aa=>Sda一、消除文法的左递归TJNU-COCIE-WJW492023/2/53.消除直接左递归引例： 设有产生式

P→Pα|β (1)

其中β不以P开头，α不为ε。那么，我们可以把P的规则改为如下的非直接左递归形式：

P→βP’ P’→αP’|ε (2)

(1)式和(2)式是等价的TJNU-COCIE-WJW502023/2/5引例(续) P→Pα|β (1)

P→βP’ P’→αP’|ε (2)对于(1)式：P=>Pα=>Pαα=>…=>Pαα…α=>βαα…α对于(2)式：P=>βP’=>βαP’=>βααP’=>…=>βαα…αP’ =>βαα…αTJNU-COCIE-WJW512023/2/5

例：设有文法G E→E+T|T

T→T*F|F F→(E)|i消除其产生式的直接左递归解：对于E→E+T|T (P=E，α=+T，β=T)变成

E→TE’ E’→+TE’|ε

P→Pα|β----------------P→βP’P’→αP’|ε 同理：E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iTJNU-COCIE-WJW522023/2/5例：设有文法G E→E+T|T

T→T*F|F F→(E)|i

E=>E+T=>E+T+T=>E+T+…+T=>T+T+…+TE=>TE’=>T+TE’=>T+T+TE’=>T+T+…+TE’ =>T+T+…+TE→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iTJNU-COCIE-WJW532023/2/5消除直接左递归方法： 设有产生式

P→Pα1|Pα2|…|Pαm|β1|β2|…|βn

其中每个βi不以P开头，每个αi不为ε

消除P的直接左递归性就是把这些规则改写成：

P→β1P’|β2P’|…|βnP’ P’→α1P’|α2P’|…|αmP’|εTJNU-COCIE-WJW542023/2/5几点注意：①消除直接左递归的代价是引进了若干非终结符和ε产生式②用上述办法实际上把直接左递归变成直接右递归

P→Pα|β P→βP’ P’→αP’|ε③上述办法不意味着可以消除整个文法的左递归性

例如：有文法

S→Qc|c Q→Rb|b R→Sa|a

已经不具有直接左递归，但却是间接左递归的 因为：S=>Qc=>Rbc=>SabcTJNU-COCIE-WJW552023/2/54.消除整个文法的左递归的算法 如果文法不含回路（形如的推导），也不含有以ε为右部的产生式，则下面算法可以消除左递归

(1)把文法G的所有非终结符按任一种顺序排列成 P1,P2,…,Pn；按此顺序执行

(2)fori=1tondo forj=1toi-1do

把形如Pi→Pjγ的规则改写成: Pi→δ1γ|δ2γ|…|δkγ。 其中Pj→δ1|δ2|…|δk是关于Pj的所有产生式

Endfor

消除关于Pi的直接左递归

Endfor (3)化简由(2)得到的文法：除去从开始符号无法达到的非终结符的产生式TJNU-COCIE-WJW562023/2/5例子：考虑以下文法，消除其左递归性

S→Qc|c Q→Rb|b R→Sa|a解：(1)把该文法的非终结符排列为R、Q、S.(2)对于R，不存在直接左递归，不用消除对于Q，把R代入到Q的有关候选式后，把Q的产生式改写为

Q→Sab|ab|b现在Q不存在直接左递归，不用消除对于S，把Q代读到S的有关候选式后，把S的产生式改写为

S→Sabc|abc|bc|cS有直接左递归，消除S的直接左递归为

S→abcS’|bcS’|cS’ S’→abcS’|εTJNU-COCIE-WJW572023/2/5得到消除左递归性的文法为

S→abcS’|bcS’|cS’ S’→abcS’|ε Q→Sab|ab|b R→Sa|a

(3)显然，Q和R的产生式已经是多余的，将它们去掉 化简后的文法是：

S→abcS’|bcS’|cS’ S’→abcS’|ε注意：由于对非终结符排序的不同，最后所得的文法在形式上可能不一样，但它们都是等价的TJNU-COCIE-WJW582023/2/5例如：考虑刚才的文法，消除其左递归性

S→Qc|c Q→Rb|b R→Sa|a解：(1)把该文法的非终结符排列为S、Q、R(2)对于S，不存在直接左递归，不用消除对于Q，不存在直接左递归，不用消除对于R，把S代入到R的有关候选式后，把R的产生式改写为

R→Qca|ca|a把Q代入到R的有关候选式后，把R的产生式改写为

R→Rbca|bca|ca|aTJNU-COCIE-WJW592023/2/5 R→Rbca|bca|ca|aR有直接左递归，消除S的直接左递归为

R→bcaR’|caR’|aR’ R’→bcaR’|ε得到消除左递归性的文法为

S→Qc|c Q→Rb|b R→bcaR’|caR’|aR’ R’→bcaR’|εTJNU-COCIE-WJW602023/2/51.消除回溯的要求 对文法的任何非终结符，当要它去匹配输入串时，能够根据该非终结符所面临的输入符号准确地指派它的一个候选式去匹配，并且此候选式匹配后得到的工作结果应该是确信无疑的，即：

(1)若该候选式匹配成功，那么该匹配不是虚假匹配

(2)若该候选式无法完成最终的匹配任务，则其他任何候选式肯定也无法完成二、消除回溯TJNU-COCIE-WJW612023/2/5

例如： 假设当前轮到非终结符A去匹配输入串，A的产生式为

A→α1|α2|…|αn A所面临的第一个输入符号为a，如果A指派αi去匹配，那么就肯定没有回溯。

注意： 这里A不再是让某个αi去试探匹配，而是根据所面临的输入符号的不同准确制定一个αi去匹配，若匹配到最后没能识别整个字串，则该字串一定不是该文法中的句子。TJNU-COCIE-WJW622023/2/5 2.消除回溯的条件 定义FIRST集 令文法G是不含左递归的文法，对G的非终结符的候选α，定义它的开始符号（终结首符）集合：特别地，如果α ε，则ε∈FIRST(α)如果非终结符A的任意两个候选式αi和αj的开始符号集满足FIRST(αi)∩FIRST(αj)=Φ，则A可以根据所面临的第一个输入符号，准确地指派一个候选式α去执行任务，α是那个FIRST集含a的候选式，即a

∈FIRST(α)TJNU-COCIE-WJW632023/2/5例如： 假设A的产生式为

A→α1|α2|…|αn当前输入符号为b，b∈VT如果b∈FIRST(α1)，则用α1去匹配b如果b∈FIRST(α2)，则用α2去匹配b…如果b∈FIRST(αn)，则用αn去匹配bFIRST(α1)∩FIRST(α2)∩…∩FIRST(αn)=ΦTJNU-COCIE-WJW642023/2/5 3.改造文法

问题： 对于许多程序设计语言的文法，都有产生式

语句→if条件then语句else语句

|if条件then语句这两个候选式的FIRST集合相交不为Φ

TJNU-COCIE-WJW652023/2/53.改造文法(续)改造方法：提取公共左因子假设A的产生式为

A→δβ1|δβ2|…|δβn|γ1|γ2|…|γm其中每个γ不以δ开头那么把这些产生式改写为: A→δA’|γ1|γ2|…|γm A’→β1|β2|…|βn反复提取左因子(包括对新引进的非终结符，例如A’)TJNU-COCIE-WJW662023/2/5问题：

当一个文法不含左递归，并且满足每个非终结符的所有候选首符集两两不相交的条件，是不是一定能进行有效的自上而下分析了呢？

若空字ε属于某个非终结符的候选式的首符集，就会有问题三、LL(1)分析条件TJNU-COCIE-WJW672023/2/51.引例对于消除左递归的文法E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i对输入串i+i进行分析FIRST(TE’)={(，i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)={(，i}FIRST(*FT’)={*}FIRST(ε)={ε}FIRST((E))={(}FIRST(i)={i}T’自动匹配ε

，IP不动TJNU-COCIE-WJW682023/2/51.引例对于消除左递归的文法E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i对输入串i(进行分析FIRST(TE’)={(，i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)={(，i}FIRST(*FT’)={*}FIRST(ε)={ε}FIRST((E))={(}FIRST(i)={i}T’自动匹配ε

，IP不动TJNU-COCIE-WJW692023/2/5 2.定义FOLLOW集对文法G的任何非终结符A，定义它的后继符号集合：特别地，如果S …A，则#∈FOLLOW(A)FOLLOW(A)集合是所有句型中出现在紧接A之后的终结符号或#所组成的集合当非终结符A面临输入符号a，且a不属于A的任意候选式的FIRST集但A的某个候选式的FIRST集包含ε时，只有当a∈FOLLOW(A)，才可能允许A自动匹配TJNU-COCIE-WJW702023/2/5 3.不带回溯的自上而下分析的文法条件（LL(1)文法）

(1)文法不含左递归

(2)对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即，若

A→α1|α2|…|αn

则 FIRST(αi)∩FIRST(αj)=Φ(i≠j) (3)对于文法中的每个非终结符A，若它的某个候选首符集包含ε,则

FIRST(A)∩FOLLOW(A)=Φ

如果一个文法G满足以上条件，则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串，第2个L代表最左推导，1表示分析时每一步只看1个符号)TJNU-COCIE-WJW712023/2/54.不带回溯的自上而下分析的方法 对于LL(1)文法，假设要用非终结符A进行匹配，面临输入符号为a，A的所有产生式为

A→α1|α2|…|αn (1)若a∈

FIRST(αi)

，则指派αi去匹配

(2)若a不属于任何一个候选首符集，则： ①若ε属于某个FIRST(αi)且a∈FOLLOW(A)，则让A与ε自动匹配；

②否则，a的出现是一种语法错误TJNU-COCIE-WJW722023/2/54.4递归下降分析程序构造

文法满足LL(1)条件（是LL(1)文法）

对文法的每个非终结符号编写一个递归子程序一、构造条件二、构造方法TJNU-COCIE-WJW732023/2/5

例：对于LL(1)文法E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i构造其递归下降分析程序TJNU-COCIE-WJW742023/2/5E→TE’PROCEDUREE;BEGIN T;E’END;E’→+TE’|εPROCEDUREE’;IFSYM=‘+’THENBEGIN ADVANCE; T;E’END;T→FT’PROCEDURET;BEGIN F;T’END;T’→*FT’|εPROCEDURET’;IFSYM=‘*’THENBEGIN ADVANCE; F;T’END;F→(E)|IPROCEDUREF;IFSYM=‘i’THENADVANCEELSEIFSYM=‘(’THENBEGIN ADVANCE; E; IFSYM=‘)’THENADVANCE ELSEERRORENDELSEERRORADVANCE把输入串指示器IP指向下一个输入符号SYM是指IP当前所指的那个输入符号ERROR为出错处理程序TJNU-COCIE-WJW752023/2/5第2次上机作业

根据《编译原理》P69页文法4.2，构造其递归下降分析程序参考P74伪代码要求加入输入输出，用C编写输入使用前面词法分析程序的结果，其中i代表标识符或常数输入符号串，输出递归过程(非终结符号序列)和识别结果(是否正确句子)TJNU-COCIE-WJW762023/2/54.5预测分析程序

用高级语言的递归过程描述递归下降分析器只有当具有实现这种过程的编译系统时才有意义 实现LL(1)分析的另一种有效方法是使用 一张分析表 一个栈 本节介绍预测分析程序TJNU-COCIE-WJW772023/2/51.总体结构……a………#预测分析表M总控程序输出X...#一、预测分析程序的结构TJNU-COCIE-WJW782023/2/51.总体结构(续1)总控程序 控制分析表和分析栈的工作分析栈 用于存放文法符号。分析开始时先放一个‘#’，然后放进文法开始符号。同时假定输入串之后也总有一个‘#’，标志输入串的结束TJNU-COCIE-WJW792023/2/51.总体结构(续2)一张分析表M

用一个矩阵来表示，即M[A,a] (1)A为非终结符

(2)a是终结符或者’#’(这里‘#’不是文法的终结符，我们把它作为输入串的结束符号) (3)矩阵的元素M[A,a]中存放着一条关于A的产生式，指出当A面临输入符号a时所应采用的候选式。也可能放一个“出错标志”，指出A根本不该面临输入符号a。TJNU-COCIE-WJW802023/2/5例子：有文法E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iE#i+i*i#IPTJNU-COCIE-WJW812023/2/51.分析开始时，各部分格局如下然后反复执行2中所列的工作#SIPa1a2…an#二、预测分析程序的工作过程TJNU-COCIE-WJW822023/2/5#x1x2…xm-1WV

UIPaiai+1…an#2.假设在分析的某一步，分析栈及余留下的输入串处于如下格局#x1x2…xm-1xmIPaiai+1…an#(1)若xm

∈VN则用xm

和ai

去查找分析表M(xm

，ai)若M(xm

，ai)=“xm→UVW”，则把xm

从栈顶托出，把UVW按反序压进栈。若M(xm

，ai)=ERROR，则调用出错处理程序TJNU-COCIE-WJW832023/2/52.假设在分析的某一步，分析栈及余留下的输入串处于如下格局#x1x2…xm-1xmIPaiai+1…an#(2)若xm=ai≠‘#’则xm

从栈顶托出，IP指针向前移动一个字符的位置#x1x2…xm-1IPaiai+1…an#TJNU-COCIE-WJW842023/2/52.假设在分析的某一步，分析栈及余留下的输入串处于如下格局#x1x2…xm-1xmIPaiai+1…an#(3)若xm=ai=‘#’表示整个输入串匹配成功，分析结束。TJNU-COCIE-WJW852023/2/5例：有文法E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iTJNU-COCIE-WJW862023/2/5

栈 输入 产生式

#E i+i*i# #E’T i+i*i# E→TE’ #E’T’F i+i*i# T→FT’ #E’T’i i+i*i# F→i #E’T’ +i*i# #E’ +i*i# T’→ε #E’T+ +i*i# E’→+TE’ #E’T i*i#TJNU-COCIE-WJW872023/2/5

栈 输入 产生式

#E’T’F i*i# T→FT’ #E’T’i i*i# F→i #E’T’ *i# #E’T’F* *i# T’→*FT’ #E’T’F i# #E’T’i i# F→i #E’T’ # #E’ # T’→ε # # E’→εTJNU-COCIE-WJW882023/2/5 1.

定义FIRST集 令文法G是不含左递归的文法，对G的非终结符的候选α，定义它的开始符号（终结首符）集合：特别地，如果α ε，则ε∈FIRST(α)如果非终结符A的任意两个候选式αi和αj的开始符号集满足FIRST(αi)∩FIRST(αj)=Φ，则A可以根据所面临的第一个输入符号，准确地指派一个候选式α去执行任务，α是那个FIRST集含a的候选式，即a

∈FIRST(α)三、预测分析表M(xm，ai)的构造方法TJNU-COCIE-WJW892023/2/52.对每个文法符号X∈VN∪VT构造其FIRST(X)连续使用以下规则，直至每个FIRST集不再增大为止

(1)若X∈VT，则FIRST(X)={X}. (2)若X∈VN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。

(3)若X→Y…是一个产生式，且Y∈VN，则把FIRST(Y)中所有非ε元素都加到FIRST(X)中； 若X→Y1Y2…Yk是一个产生式，Y1Y2…Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε(即Y1…Yi-1=>ε)，则把FIRST(Yi)中的所有非ε元素都加到FIRST(X)； 特别是，若所有的FIRST(Yj)均含有ε，j=1，2，…，k，则把ε加到FIRST(X)中。TJNU-COCIE-WJW902023/2/53.

对于文法的任意符号串α=X1X2…Xn构造集合FIRST(α) (1)置FIRST(α)=FIRST(X1)\{ε} (2)若对任何1≤j≤i-1，ε∈FIRST(Xj)，则把FIRST(Xi)\{ε}加至FIRST(α)中

(3)特别的，若所有的FIRST(Xj)均含有ε，1≤j≤n，则把ε

也加至FIRST(α)中TJNU-COCIE-WJW912023/2/5 4.定义FOLLOW集对文法G的任何非终结符A，定义它的后继符号集合特别地，如果S …A，则#∈FOLLOW(A)FOLLOW(A)集合是所有句型中出现在紧接A之后的终结符号或#所组成的集合当非终结符A面临输入符号a，且a不属于A的任意候选式的FIRST集但A的某个候选式的FIRST集包含ε时，只有当a∈FOLLOW(A)，才可能允许A自动匹配TJNU-COCIE-WJW922023/2/55.对每个文法A∈VN构造其FOLLOW(A)连续使用一下规则，直至每个集合FOLLOW不再增大为止

(1)对于分发开始符号S，置#与FOLLOW(S)中；

(2)若A→αBβ是一个产生式，则把FIRST(β)\{ε}加至FOLLOW(B)中；

(3)若A→αB是一个产生式，FOLLOW(A)加至FOLLOW(B)中 或A→αBβ是一个产生式而βε(即ε∈FIRST(β))，FOLLOW(A)加至FOLLOW(B)中其中α,β∈(VN∪VT)*，B∈VNTJNU-COCIE-WJW932023/2/5

例：设有文法G(VT，VN，S，P)，其中

VT={i，+，*，(，)}；VN={E,E’,T,T’,F}；S=E P:E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i (1)构造每个终结符号的FIRST集

(2)构造每个非终结符号的FIRST集

(3)构造每个候选式的FIRST集

(4)构造每个非终结符号的FOLLOW集TJNU-COCIE-WJW942023/2/5 P:E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i

解：根据，若X∈VT，则FIRST(X)={X}. FIRST(i)={i}; FIRST(+)={+}; FIRST(*)={*}; FIRST(()={(}; FIRST())={)};TJNU-COCIE-WJW952023/2/5

P:E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i解：FIRST(F)={}; FIRST(T’)={};FIRST(T)={};FIRST(E’)={}; FIRST(E)={};(2)若X∈VN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。(3)若X→Y…是一个产生式，且Y∈VN，则把FIRST(Y)中所有非ε元素都加到FIRST(X)中；若X→Y1Y2…Yk是一个产生式，Y1Y2…Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε(即Y1…Yi-1=>ε)，则把FIRST(Yi)中的所有非ε元素都加到FIRST(X)；特别是，若所有的FIRST(Yj)均含有ε，j=1，2，…，k，则把ε加到FIRST(X)中。(,i*,ε(,i+,ε(,iTJNU-COCIE-WJW962023/2/5

P:E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i解：FIRST(TE’)={}; FIRST(+TE’)={};FIRST(ε)={};FIRST(FT’)={}; FIRST(*FT’)={}; FIRST(ε)={};FIRST((E))={}; FIRST(i)={};α=X1X2…Xn

构造FIRST(α)(1)置FIRST(α)=FIRST(X1)\{ε}(2)若对任何1≤j≤i-1，ε∈FIRST(Xj)，则把FIRST(Xj)\{ε}加至FIRST(α)中(3)特别的，若所有的FIRST(Xj)均含有ε，1≤j≤n，则把ε也加至FIRST(α)中(i+(,iε(,iFIRST(F)={(,i};FIRST(T’)={*,ε};FIRST(T)={(,i

};FIRST(E’)={+,ε};FIRST(E)={(,i

};FIRST(i)={i};FIRST(+)={+};FIRST(i)={*};FIRST(()={(};FIRST())={)};*εTJNU-COCIE-WJW972023/2/5

P:E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i解：FOLLOW(E)={};FOLLOW(E’)={};FOLLOW(T)={};FOLLOW(T’)={};FOLLOW(F)={};(1)对于分发开始符号S，置#于FOLLOW(S)中；(2)若A→αBβ是一个产生式，则把FIRST(β)\{ε}加至FOLLOW(B)中；(3)若A→αB是一个产生式，或A→αBβ是一个产生式而ε∈FIRST(β)，FOLLOW(A)加至FOLLOW(B)中。#,)+,FIRST(F)={(,i};FIRST(T’)={*,ε};FIRST(T)={(,i

};FIRST(E’)={+,ε};FIRST(E)={(,i

};FIRST(i)={i};FIRST(+)={+};FIRST(i)={*};FIRST(()={(};FIRST())={)};*,#,)#,)+,#,)+,#,)TJNU-COCIE-WJW982023/2/56.构造分析表M的算法是

(1)对于文法G的每个产生式A→α，执行(2)(3) (2)对每个终结符a∈FIRST(α)，把A→α加至M[A,a]中；

(3)若ε∈FIRST(α)，则对任何b∈FOLLOW(A)把A→ε加至M[A,b]中；

(4)把所有无定义的M[A,a]标上”出错标志”TJNU-COCIE-WJW992023/2/5例:E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFIRST(TE’)={(,i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)={(,i

}FIRST(*FT’)={*}FIRST(ε)={ε}FIRST((E))={(}FIRST(i)={I}FOLLOW(E)={#,)}FOLLOW(E’)={#,)

}FOLLOW(T)={+,#,)

}FOLLOW(T’)={+,#,)

}FOLLOW(F)={*,

+,#,)

}TJNU-COCIE-WJW1002023/2/5 1.文法不含左递归

2.对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即，若

A→α1|α2|…|αn

则 FIRST(αi)∩FIRST(αj)=Φ(i≠j) 3.对于文法中的每个非终结符A，若它的某个候选首符集包含ε,则

FIRST(A)∩FOLLOW(A)=Φ

如果一个文法G满足以上条件，则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串，第2个L代表最左推导，1表示分析时每一步只看1个符号)四、LL(1)文法TJNU-COCIE-WJW1012023/2/5例:有文法GE→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i证明该文法是LL(1)文法FIRST(TE’)={(,i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)={(,i

}FIRST(*FT’)={*}FIRST(ε)={ε}FIRST((E))={(}FIRST(i)={i}FOLLOW(E)={#,)}FOLLOW(E’)={#,)

}FOLLOW(T)={+,#,)

}FOLLOW(T’)={+,#,)

}FOLLOW(F)={*,

+,#,)

}证明：FIRST(+TE’)∩FIRST(ε)={+}∩

{ε}=ΦFIRST(*FT’)∩FIRST(ε)={*}∩{ε}=ΦFIRST((E))∩FIRST(i)={i}∩{(}=ΦFIRST(E’)∩FOLLOW(E’)={+,ε}∩{#,)

}=ΦFIRST(T’)∩FOLLOW(T’)={*,ε}∩{+,#,)

}=Φ所以，文法G是LL(1)文法TJNU-COCIE-WJW1022023/2/5例:有文法G(VT，VN，S，P)，其中

VT={i，+，*，(，)}；VN={S,X,Y,Z}；S=SP:S→XX→Y|XiYY→Z

|Y+ZZ→)X*|((1)消去G的所有左递归(该文法不含间接左递归)(2)计算修改后的文法的每个非终结符的FIRST集和FOLLOW集(3)证明G是LL(1)文法(4)构造它的预测分析表TJNU-COCIE-WJW1032023/2/5解:P:S→XX→XiY

|

YY→Y+Z|

Z

Z→)X*|((1)消去G的所有左递归

X→XiY

|

Y变为 X→YX’ X’→iYX’|εY→Y+Z|

Z变为 Y→ZY’ Y’→+ZY’

|ε

所以原文法消除左递归为

S→X

X→YX’ X’→iYX’|ε

Y→ZY’ Y’→+ZY’

|ε

Z→)X*|(TJNU-COCIE-WJW1042023/2/5解: S→X

X→YX’ X’→iYX’|ε

Y→ZY’ Y’→+ZY’

|ε

Z→)X*|((2)计算每个非终结符的FIRST集和FOLLOW集FIRST(Z)={),(};FIRST(Y’)={+,ε};FIRST(Y)={),(

};FIRST(X’)={i,ε};FIRST(X)={),(

};FIRST(S)={),(

};(2)若X∈VN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。