《编译原理实践及应用》第2章高级语言设计基础

高级语言设计基础第二章本章要求•主要内容：符号串，文法和语言的概念及分类，高级语言的定义过程•重点掌握：符号串及其运算，上下文无关文法、推导、句型、句子、语言，语法树、二义文法、文法的语言生成过程，高级语言的设计过程•以C和PASCAL为例复习高级语言–1语言的基本字符集的定义(字母,数字,符号)–2单词的定义–3数据类型的定义–4各种表达式的定义–5各种语句的定义–6程序定义•PASCAL和C的主要区别2.1符号和符号串•1.字母表：高级语言程序能够使用的全体字符构成的集合，是元素的有穷非空集合Σ•2.符号：字母表中的每个元素，因此字母表也称为符号集。–不同的语言可以有不同的字母表，例如英文的字母表中26个字母、数字及标点符号等。C语言的字母表是由字母、数字、若干专用符号组成。•符号是某语言能识别的字符，字母表是该语言能识别的所有符号的全体（字符集）。基本概念(续)•3.符号串:由字母表中的符号组成的任何有穷序列称为符号串，例如001110是字母表=｛0，1｝上的符号串字母表A=｛a,b,c｝上的一些符号串有：a,b,c,ab,aaca等。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba，abca和aabc也不同。符号串STR表示“由符号S、T和R，并按此顺序组成基本概念(续)•4.符号串的运算–符号串的长度:符号串中符号的个数如：某符号串中有m个符号,则称其长度为m，表示为|x|=m，如001110的长度是6。–空符号串:即不包含任何符号的符号串，用ε表示，其长度为0，即|ε|=0。–符号串的连接：字符串αβ称为字符串α和β的连接如：=01，β=110，则β=01110，β=11001–集合U、V的乘积：UV={αβ|α∈U&β∈V}长度相加即:集合UV中的符号串是由U和V的符号串连接而成。U={aa,bb}V={00,11}则UV=?UV≠VU–集合的方幂：n个相同集合的乘积•Vn=VVVV….V规定V0={ε}例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}–集合的闭包、正闭包Σ的闭包*表示上的所有符号串（包括ε）组成的集合。包括长度为0，1，2，…Σ的正闭包+表示*上的除ε外的所有符号串组成的集合。......32=+V={0,1}V*=?V+=?......32={ε}*形式语言的概念•Σ*中的任意一个按一定规则构成的子集称为Σ上的一个（形式）语言，•属于该语言的符号串称为该语言的句子。•例：令L＝{A,B,…,Z,a,b,…,z}，D＝{0,1,…,9}，。由于单个符号可以看成是长度为1的符号串，L和D可以分别看成是有穷的语言集。用集合的运算作用于L和D所得到新语言：（1）L∪D是字母和数字的集合；（2）LD是所有一个字母后随一个数字的符号串的集合；（3）L*是所有字母串（包括）的集合；（4）L(L∪D)*是以字母开头的所有字母数字串的集合2.2文法与语言•程序设计语言的语法结构的形式化描述称为文法。是一种工具，用于严格定义句子的结构；用有穷的规则刻划无穷的集合•文法是被用来精确而无歧义地描述语言的句子的构成方式.•文法描述语言的时候不考虑语言的含义。引例例1：有如下规则句子主语谓语(表示由…组成)主语代词|名词代词我名词大学生谓语动词直接宾语动词是直接宾语代词|名词•现要求根据如上规则得出句子：我是大学生句子=主语谓语=代词谓语=代词动词直接宾语=代词动词名词=我是大学生句子“我是大学生”也可以如下图示分析•在有规则的情况下，每一次用上述规则的右边去替换左边，得到“我是大学生”是符合上述规则的句子句子主语谓语代词动词直接宾语名词大学生我是上下文无关文法的形式定义•由四部分组成：–终结符号：是组成该语言的最基本的符号，是不可再分的基本符号,如保留字、标识符等。–非终结符号：规则中用尖括号括起来的符号，表示一些语法成分，可以推导出其他的语法成分,表示一定符号串的集合，是一个类，如表达式。–开始符号：规则中的一个特殊的非终结符号，语言中的句子都从它开始推导,如程序、句子–产生式：定义语法成分的规则，上例中的产生式为所有规则句子主语谓语主语代词|名词代词我名词大学生谓语动词直接宾语动词是直接宾语代词|名词文法的形式定义(续)•一个文法G抽象地表示为四元组G=（Vn,Vt,P,S）–其中Vn表示非终结符号–Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ–S是开始符号，–P是产生式，形如：αβ(α∈V+且至少含有一个非终结符号，β∈V*)–上例中：G=（Vn,Vt,P,句子）Vn=（句子，主语，谓语，代词，动词，名词，直接宾语）Vt=(我，是，大学生)P=句子主语谓语主语代词|名词代词我名词大学生谓语动词直接宾语动词是直接宾语代词|名词例：某语言中标识符定义的文法G=（VN，VT，P，S）其中：VN={标识符，字母，数字}VT={a,b,c,…y,z,0,1,…9}S=标识符P={标识符→字母标识符→标识符字母标识符→标识符数字字母→a字母→b……字母→z数字→0……数字→9}•产生式的形式为：Aα左部符号，非终结符右部，可以含有非终结符和终结符又称为一条规则有时一个产生式不足以描述该语法范畴，就用多个产生式，如算术表达式的描述为：(递归定义)EE+EEE*EEiEE+E|E*E|i相同左部的一个右部又称一个候选式–上下文无关文法所定义的语法成分独立于它可能出现的环境，即不考虑上下文。算术表达式的文法定义•变量是表达式•表达式+表达式是表达式•表达式*表达式是表达式•(表达式)是表达式EE+EEE*EE(E)EiEE+E|E*E|(E)|i•从上下文无关文法得到某个符号串的方法:从文法的开始符号出发,反复连续使用产生式,对左边的非终结符进行替换和展开，直到全部为终结符为止。•例：表达式定义规则EE+EEE*EE(E)Ei(i+i)E=(E)=(E+E)=(i+E)=(i+i)•推导:连续使用产生式右部去替换左部某个非终结符的过程,得到的连续序列称为一个推导。•直接推导：又称一步推导(用符号=表示),就是用某条规则的右部去替换该规则的左部。•归约：推导的逆过程称为归约（Reduction）。•直接归约：直接推导的逆过程。几个概念的形式定义•直接推导:如果αβ是文法G=（Vn,Vt,P,S）的产生式，γ和δ是Ｖ*中的任意符号，若有符号串v,w满足：v=γαδ,w=γβδ,则说v直接产生w，(w是v的直接推导)记作：v=w*+例：S01,0S0=0010(直接推导γ＝０,δ＝０)•如果存在v=w0=w1=w2...=Wn=w(n0)，则称v推导出w（长度为n），记作v=w(至少一步)•若有ｖ=w或v=w，则记作v=w(0步或若干步)•例3:G=({E},{i,+,*,(,)},P,E)P：EE+E|E*E|(E)|i表达式(i)和(i+i)*i的推导：E(E)(i)EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*iEE0步推导E(i+i)*i6步推导E(i+i)*i6步推导E(E)直接推导•句型：设Ｇ(s)是一文法，如果符号串x是从开始符号推导出来的，即有s=x,则称x是文法G(s)的一个句型。即:任何由开始符Ｓ推导出来的符号串都是句型。•句子：若x仅由终结符号组成，则称x为G(S)的句子*•练习文法G：SaAcB|BdAAaB|cBbScA|b写出句型aAcbBdcc和句子acabcbbdcc的推导过程。•文法G所产生的语言定义为：L(G)={x|S=x,其中S为文法的开始符号，x∈Vt*}。即:一个文法G可以推导出的所有句子构成的一个集合,就确定了一个语言。*•例：考虑文法G:它定义了什么语言。SbAAaA|a推导过程：S=bA=baS=bA=baA=baa……………..S=bA=baA=…=ba…a归纳得：L(G1)={ban|n≥1}•练习：文法Ｇ＝({A,B,S},{a,b,c},P,S)SAc|aBAabBbc写出Ｌ(G)的全部元素L(G)={abc}•例：考虑文法G2:•它定义的语言是：SABAaA|aBbB|bL(G2)={ambn|m,n≥1}•思考：构造一个文法G3使得：L(G3)={anbn|n≥1}SaSbSaba,b的个数相同,则文法G3为：•文法等价：若文法G1和文法G2所产生的语言相同，即L(G1)=L(G2)，则称文法G1和文法G2等价。例：有如下两个文法，判断它们是否等价？G1=（{S}，{0}，S，{S0S，S0}）G2=（{S}，{0}，S，{SS0，S0}）S0S0S00……………S0S00S…000……0L(G1)={0n|n≥1}对于G2：对于G1：SS0S00…000……0L(G2)={0n|n≥1}G1G2，但L(G1)=L(G2)，文法G1和G2等价例3:G=({E},{i,+,*,(,)},P,E)P：EE+E|E*E|(E)|i表达式(i+i)*i的推导过程：(1)EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i(2)EE*EE*i(E)*i(E+E)*i(E+i)*i(i+i)*i对给定的文法，定义的语言是由利用所有的产生式经过各种方式推导出所有可能的句子构成的，并没有规定推导使用产生式的顺序。因此从一个句型到另一个句型(句子)的推导过程不是唯一的。•最左推导:在整个推导过程中,任何一步推导α=β都是对α中最左边的非终结符进行替换。•最右推导:•在推导之前确定推导的顺序，是对句子进行确定性分析所必须的例3：G=({E},{i,+,*,(,)},P,E)P：EE+E|E*E|(E)|i(i+i)*i的最左推导过程：EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i最右推导过程：EE*EE*i(E+E)*i(E+i)*i(i+i)*i文法的二义性•语法树：推导的形式化表示，有助于理解句子语法结构的层次•每个结点都有一个标记，该标记属字母集中的一个符号，根由开始符号Ｓ标记。•当某个非终结符被它的某个候选式所替换时，就产生相应的下一层的结点，候选式中自左至右的每个符号对应一个新的结点，并标记它，画出其与父结点之间的连线。例：对文法G=({E},{i,+,*,(,)},P,E)P：EE+E|E*E|(E)|i句子(i+i)*i的语法树：•在语法树的推导过程中的任何时刻，没有后代的端末结点自左至右排列起来就是一个句型•一棵语法树表示了一个句型很多可能的不同推导过程。(包括最左推导和最右推导)例3：G=({E},{i,+,*,(,)},P,E)P：EE+E|E*E|(E)|i句子(i*i+i)的语法树：(1)EE+EE*E+Ei*E+Ei*i+Ei*i+i(2)EE*Ei*Ei*E+Ei*i+Ei*i+i并不是任何情况下一个句型就唯一地对应一棵语法树。•定义：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的•对二义文法中的某个句子的分析不是唯一的，因此总是希望文法是无二义的。•但是二义文法有时也是有用的。证明下述文法是二义文法。例：设if语句S的文法G=({E，S}，{if，then，else，a