编译原理 第3章 语法分析

第3章语法分析第3章语法分析3.1文法和语言3.2推导与语法树3.3自上而下分析方法3.4自下而上分析方法3.5LR分析法第3章语法分析3.1文 法 和 语 言文法是程序语言的生成系统，而自动机则是程序语言的识别系统；用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。第3章语法分析3.1.1文法和语言的概念1．语言通常我们用Σ表示字母表，字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的，程序语言的字母表通常是ASCII字符集。由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串或字，字母表Σ上的所有字符串(包括空串)组成的集合用Σ*表示。那么，对字母表Σ来说，Σ*上的任意一个子集都称为Σ上的一个语言，记为L(LΣ*)，该语言的每一个字符串称为语言L的一个语句或句子。第3章语法分析2．文法文法通常表示成四元组G=(VT，VN，S，ξ)，其中：(1)VT为终结符号集，这是一个非空有限集，它的每个元素称为终结符号；(2)VN为非终结符集，它也是一个非空有限集，其每个元素称为非终结符号，且有VT∩VN=Φ；(3)S为一文法开始符，是一个特殊的非终结符号，即S∈VN；第3章语法分析(4)ξ是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(α，β)，通常写作α→β或α::=β读作“α是β”或“α定义为β”。在此，α为产生式的左部，而β为产生式的右部，α、β是由终结符和非终结符组成的符号串，α∈(VT∪VN)+且至少有一个非终结符，而β∈(VT∪VN)*。第3章语法分析终结符号是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号。非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。第3章语法分析文法开始符号是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量；如表达式文法的语言目标是表达式，而程序语言的目标通常为程序。产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如，有：P→α1P→α2P→αn第3章语法分析为书写方便，可将这些有相同左部的产生式合并为一个，即缩写成P→α1∣α2∣…∣αn其中，每个αi(i=1,2,…,n)称为P的一个候选式，直竖“∣”读为“或”，它与“→”一样是用来描述文法的元语言符号(即不属于Σ的字符)。第3章语法分析例3.1试构造产生标识符的文法。[解答]首先，标识符是以字母开头的字母数字串，我们用L表示“字母”类非终结符，用D表示“数字”类非终结符，而用T表示“字母或数字”类非终结符，则有：L→a∣b∣…∣zD→0∣1∣…∣9T→L∣D其次，如果用S表示“字母数字串”类，则T是一字母或数字，ST也是字母数字串，即有S→T∣ST其中，产生式S→T∣ST是一种左递归形式，由它可以产生一串T。第3章语法分析最后，作为“标识符”的非终结符I，它或者是一单个字母，或者为一字母后跟字母数字串，即I→L∣LS因此，产生标识符的文法G[I]为：G=({a,b,…,z,0,…,9},{I,S,T,L,D},I,ξ)ξ:I→L∣LSS→T∣STT→L∣D第3章语法分析L→a∣b∣…∣zD→0∣1∣…∣9例3.2写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。[解答]根据题意，我们可以将奇数划分为如图3–1所示的三个部分，即最高位允许出现1～9，用非终结符B表示；中间部分可以出现任意多位数字0～9，每一位用非终结符D表示；最低位只允许出现1、3、5、7、9等奇数，用A表示。第3章语法分析图3–1奇数划分示意MB…最高位中间位DDDA最低位第3章语法分析由于中间部分可出现任意位，所以另引入了一个非终结符M，它包括最高位和中间位部分。假定开始符为N，则可得到文法G[N]为：G=({0,1,…,9},{N,A,M,B,D},N,ξ)ξ:N→A∣MA/*一位数字│多位数字*/M→B∣MD/*仅两位数字(无中间位)│多于两位数字*/A→1∣3∣5∣7∣9B→1∣2∣3∣4∣5∣6∣7∣8∣9D→0∣B第3章语法分析3．文法产生的语言设文法G=(VT,VN,S,ξ)且α、β∈(VT∪VN)*，如果存在产生式A→δ(δ∈(VT∪VN)*)，则称αAβ可直接推出αδβ，即αAβαδβ其中“”表示直接推导出，是应用产生规则进行推导的记号。注意“”与“→”不同，“→”是产生式中的定义记号。直接推导是对文法符号串αAβ中的非终结符A用相应的产生式A→δ的右部δ来替换，从而得到αδβ。我们给出推导的说明如下：第3章语法分析(1)如果α1可直接推出α2，α2可直接推出α3，…，αn-1可直接推出αn，即存在一个自α1至αn的推导序列：α1α2α3…αn(n0)，则我们称α1可推导出αn，记为α1αn，它表示从α1出发经过一步或若干步可推导出αn。(2)如果记α1α1，则α1αn表示从α1出发，经过0步或若干步可推导出αn；也即α1αn意味着或者α1=αn，或者α1αn。例如，对下面的文法G[E]：E→E+E∣E*E∣(E)│i(3.1)第3章语法分析其中，惟一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发进行一系列的推导，如表达式i+i*i的推导如下：EE+EE+E*EE+E*iE+i*ii+i*i第3章语法分析假定G[S]是一个文法，S是它的开始符号，如果Sα，α∈(VT∪VN)*，则称α是文法G[S]的一个句型；如果α∈VT*，则称α是文法G[S]的一个句子。仅含终结符的句型是一个句子。由定义可知，开始符S本身只能是文法的一个句型而不可能是一个句子；此外，上面推导出的i+i*i是文法G[E]的一个句子(当然也是一个句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法G[E]的句型。对于文法G[S]，它所产生的句子的全体称为由文法G[S]产生的语言，记为L[G]，即有L(G)={α∣Sα且α∈VT*}第3章语法分析3.1.2形式语言分类语言学家NoamChomsky于1956年首先建立了形式语言的描述，定义了四类文法及相应的形式语言，并分别与相应的识别系统相联系，它对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。1．0型文法与0型语言(对应图灵机)如果文法G的每一个产生式具有下列形式：α→β第3章语法分析其中，α∈V*VNV*(注：V=VN∪VT)，即至少含有一个非终结符；β∈V*；则称文法G为0型文法或短语文法，记为PSG。0型文法相应的语言称为0型语言或称递归可枚举集，它的识别系统是图灵(Turing)机。第3章语法分析2．1型文法与1型语言(对应线性界限自动机，自然语言)文法G的每一个产生式α→β，均在0型文法的基础上增加了字符长度上满足∣α∣≤∣β∣的限制，则称文法G为1型文法或上下文有关文法，记为CSG。1型文法相应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。1型文法的另一种定义方法是文法G的每一个产生式具有下列形式：αAδ→αβδ第3章语法分析其中，α、δ∈V*，A∈VN，β∈V+；显然它满足前述定义的长度限制，但它更明确地表达了上下文有关的特性，即A必须在α、δ的上下文环境中才能被β所替换。第3章语法分析3．2型文法与2型语言(对应下推自动机，程序设计语言)文法G的每一个产生式具有下列形式：A→α其中，A∈VN，α∈V*，则称文法G为2型文法或上下文无关文法，记为CFG。2型文法相应的语言称为2型语言或上下文无关语言，它的识别系统是下推自动机。第3章语法分析4．3型文法与3型语言(对应有限自动机)文法G的每个产生式具有下列形式：A→a或A→aB其中，A、B∈VN，a∈VT*，则文法G称为3型文法、正规文法或右线性文法，记为RG。3型文法相应的语言为3型语言或正规语言，它的识别系统是有限自动机。3型文法还可以呈左线性形式：A→a或A→Ba第3章语法分析5．四类文法的关系与区别由四类文法的定义可知，从0型文法到3型文法逐渐增加限制。1～3型文法都属于0型文法，2、3型文法均属于1型文法，3型文法属于2型文法。四类文法的区别如下：(1)1型文法中不允许有形如“A→ε”的产生式存在，而2、3型文法则允许形如“A→ε”的产生式存在；(2)0、1型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符，而2型和3型文法的产生式左部只允许是单个的非终结符号。第3章语法分析例3.3试判断下列产生式集所对应的文法和产生的语言：(1)①S→ACaB(2)①S→aSBC(3)①S→Ac(4)①S→aS②Ca→aaC②S→aBC②S→Sc②S→aA③CB→DB③CB→DB③A→ab③A→bA④CB→E④DB→DC④A→aAb④A→bB⑤aD→Da⑤DC→BC⑤B→cB⑥AD→AC⑥aB→ab⑥B→c⑦aE→Ea⑦bB→bb⑧AE→ε⑧bC→bc⑨cC→cc第3章语法分析[解答]由四类文法的定义与区别可知，1～4分别为0～3型文法。(1)该0型文法产生的0型语言为L0(G)={a2n∣n0}。例如：当n=2时，句子a2×2=aaaa,(1)(2)(3)(5)(6)(2)(2)(2)(1)(4)(7)(7)(7)(8)SACaBAaaCBAaaDBAaDaBADaaBACaaBAaaCaBAaaaaCBAaaaaEAaaaEaAaaEaaAaEaaaAEaaaaaaaa第3章语法分析(2)该1型文法产生的1型语言为L1(G)={anbncn∣n≥1}。例如，当n=2时，句子a2b2c2=aabbcc是通过下列推导得到的：(1)(2)(6)(3)(4)(5)(7)(8)(9)SaSBCaaBCBCaabCBCaabDBCaabDCCaabBCCaabbCCaabbcCaabbcc第3章语法分析(3)该2型文法产生的2型语言为L2(G)={anbncm∣m、n≥1}。例如当n=2、m=3时，句子a2b2c3=aabbccc是通过下列推导得到的：(2)(2)(1)(4)(3)SScSccAcccaAbcccaabbccc第3章语法分析(4)该3型文法产生的3型语言为L3(G)={ambnck∣m、n、k≥1}。例如当m=2、n=3、k=4时，句子a2b3c4=aabbbcccc是通过下列推导得到的：(1)(2)(3)(3)(4)(5)(5)(5)(6)SaSaaAaabAaabbAaabbbBaabbbcBaabbbccBaabbbcccBaabbbcccc第3章语法分析由例3.3可知：{anbncn∣n≥1}{anbncm∣m、n≥1}{ambnck∣m、n、k≥1}，这说明对文法规则定义形式的限制虽然加强了，但相应的语言反而更大了。因此，不能主观认定文法限制越大则语言越小，也即下述结论是不成立的：3型语言2型语言1型语言0型语言在编译方法中，通常用3型文法来描述高级程序语言的词法部分，然后用有限自动机FA来识别高级语言的单词；利用2型文法来描述高级语言的语法部分，然后用下推自动机PDA来识别高级语言的各种语法成分。第3章语法分析例3.4给出字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有字符串集合的正规文法。[解答]为了构造字母表Σ={a,b}上同时只有奇数个a和奇数个b的所有字符串的正规表达式，我们画出如图3–2所示的DFA