第二章高级语言及其语法描述n

2.1 2.1 程序语言的语法和语义程序语言的语法和语义 1 1 语法语法任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。（字母表）上的一个符号串。对于自然语言来说，它们是定义在某个字母表上的对于自然语言来说，它们是定义在某个字母表上的句子的集合句子的集合。对于程序语言来说，它们也是定义在某个字母表上的对于程序语言来说，它们也是定义在某个字母表上的句子句子的集合。这里的集合。这里的句子，就是一个源程序。的句子，就是一个源程序。词法规则词法规则 单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。规则所确定的，即词法规则规定了单词符号的形成规则。语法规则语法规则 上下文无关文法上下文无关文法 “我是大学生”。是汉语的一个句子 用语法来描述：句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词 2 2 语义语义 定义程序的意义。定义程序的意义。没有公认的形式系统描述语义。3 高级语言的分类 强制式语言(Imperative Language)/过程式语言 FORTRAN,C,Pascal 应用式语言(Applicative Language)/函数式语言 LISP 基于规则的语言(Rule-based Language)Prolog 面向对象语言(Object-oriented Language)2.3 2.3 程序语言的语法描述程序语言的语法描述一、一、字母表和符号串字母表和符号串 字母表字母表：符号的非空有限集合 例：=a，b，c 符号符号：字母表中的元素 例：a，b，c 符号串符号串：符号的有穷序列 例：a,aa,ac,abc，.空符号串空符号串：无任何符号的符号串()符号串的形式定义符号串的形式定义 有字母表，定义：（1）是上的符号串；（2）若x是上的符号串，且a，则ax或xa是上的符号串；（3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。符号串集合符号串集合：由符号串构成的集合。二、二、符号串和符号串集合的运算符号串和符号串集合的运算 1.符号串相等符号串相等：若x、y是集合上的两个符号串，则xyiff（当且仅当）组成x的每一个符号和组成y的每一个每一个符号依次相等。2.符号串的长度符号串的长度：x为符号串，其长度|x|等于组成该符 号串的符号个数。例：xSTV，|x|=3例：Aa,b,B=c,d,AB=？4.符号串集合的乘积运算符号串集合的乘积运算：令A、B为符号串集合，定义 AB xy|xA,yB ac，ad，bc，bd 因为xxx，所以A=A=A 3.3.符号串的连接符号串的连接：若x、y是定义在是上的符号串，且xXY，yYX，则x和y的连接 xyXYYX也是上的符号串。注意：一般xyyx，但xx6.6.符号串集合的闭包运算符号串集合的闭包运算：设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正则闭包。A*A0 A称为集合A的闭包。例：A=x,y A？A*？5.符号串集合的幂运算符号串集合的幂运算：有符号串集合A，定义A0=,A1=A,A2=AA,A3=AAA,AnAn-1A=AAn-1 ，n0 x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A3 为什么对符号、符号串、符号串集合以及它们的运算感兴趣？为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集 Aa,b,z,0,1,9,+,_/,(,),=B为单词集 B=begin,end,if,then,else,for,则B A*。语言的句子是定义在B上的符号串。若令C为句子集合，则C B*,程序 C三三 文法的直观理解文法的直观理解 1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。例：有一句子：“我是大学生”。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的合法性？有穷语言无穷语言 2.2.语法规则语法规则：我们通过建立一组规则（产生式），来描述句子的语法结构结构。规定用“:=”表示“由组成”。:=:=|:=你|我|他:=王民|大学生|工人|英语:=:=是|学习:=|由产生式推导推导句子：有了一组产生式之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。=这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。=我=我=我是=我是=我是大学生:=:=:=:=|:=:=你你|我我|他他:=:=王民王民|大学生大学生|工人工人|英语英语:=:=:=:=是是|学习学习:=:=|推导方法：推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。例：有一英语句子：The big elephant ate the peanut.:=:=:=the:=big:=elephant:=:=ate:=:=peanut =the =the big =the big elephant =the big elephant =the big elephant ate =the big elephant ate =the big elephant ate the =the big elephant ate the peanut:=:=:=:=:=:=the:=:=big:=:=elephant|peanut:=:=:=:=ate:=:=上述推导可写成=the big elephant ate the peanut+说明：(1)有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。(2)从一组产生式可推出不同的句子，如以上产生式还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们 在语法上都正确，但在语义上都不正确。所谓文法文法是在形式上对句子结构的定义与描述，而未涉及语义问题。4.语法树：我们用语法树来描述一个句子的语法结构。Thebigelephantatethepeanut语法成分（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)1文法的定义文法的定义四 文法和语言的形式定义 定义1:文法G=（VN，VT，P，Z）VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号）ZVNVVNVT称为文法的字汇表产生式：U:xU VN,xV*其中其中:A.产生式：产生式：产生式是一个有序对(U,x),通常写为:U:x 或U x；|U|=1|x|0B.非终结符号：非终结符号：出现在产生式的左部,且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为VN。C.终结符号：终结符号：不出现在产生式的左部,且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为VT。P=；0；1；9；Z=；例：无符号整数的文法：G=（VN，VT，P，Z）VN,VT =0,1,2,3,9几点说明几点说明：产生式左边符号构成集合VN，且 Z VN有些产生式具有相同的左部，可以合在一起例、；|；0|1|2|3|9 文法的BNF表示给定一个 文法，实际只需给出产生式集合，并指定识别符号例、G ；|；0|1|2|3|92 推导与归约推导与归约 定义2：直接推导：文法G：vx Uy，wxuy,其中x、y V*，UVN,u V*,若U:uP，则v w。若xy，有U:u，则U u 换句话说，x和y是符号串，若使用一次产生式可以从x变换出y，则称x直接推导出y(或者说y是x的直接推导），记为x y。当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在产生式左部，所以将在产生式左部出现的符号称为非终结符号。例如：例如：GN：N ND|D D 0|1|2|3|4|5|6|7|8|9N ND NDD ND9 N09 D09 109 (6)=(1)=(3)(4)=(2)(5)=N=109定义3：+推导：x和y是符号串，若使用若干次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导），记为x y。N ND NDD ND9 N09 D09 109 (6)=(1)=(3)(4)=(2)(5)=例：则：定义4：*推导：x和y是符号串，若使用0次或若干次产生式可以从x变换出y，则称x*推导出y(或者说y是x的*推导），记为x y。*N=109则：*N=N或者说：若有直接推导序列：x=U0=U1=U2=Un=y,则 x=y 。+规范推导最右推导 定义5：最右推导：若符号串中有两个以上的非终结符时，对推导的每一步坚持把中的最右非终结符进行替换，称为最右推导。最左推导：若符号串中有两个以上的非终结符时，对推导的每一步坚持把中的最左非终结符进行替换，称为最左推导。定义6：推导的逆过程称之为归约。例：x=y,可称为x直接推导出y，也可称为y直接归约出x。x=y,可称为x推导出y，也可称为y归约出x。3 语言的形式定义语言的形式定义文法GZ所产生的所有句子的集合 定义7：文法GZ （1）句型句型：x是句型 Z x,且xV*；（2）句子句子：x是句子 Z x,且xVT*；（3）语言语言：L（GZ）=x|Z x，xVT*；+*+例：abna|n1,构造其文法 G1Z：ZaBa,Bb|bB G2Z：ZaBa,Bb|Bb 定义8.G和G是两个不同的文法，若 L(G)=L(G),则G和G为等价文法。编译感兴趣的问题是编译感兴趣的问题是:给定终极符x,文法G,求x L(G)?x算法1算法2x L(G)?Gyn出错处理停机4 文法分类 形式语言：用文法和自动机所描述的没有语义的语言。文法定义：乔姆斯基将所有文法都定义为一个四元组：G=（VN，VT，P，Z）VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号）ZVN 语言定义：L（GZ）=x|Z=x,xVT*,+文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。定义9：0型文法：P：u v 其中uV，vV*0型语言：L0 这种语言可以用图灵机(Turing)接受.0型文法称为短语结构文法。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。定义10：1型文法：P：xUy xuy 其中 UVN，x、y、uV*1型语言：L1 这种语言可以由一种线性界限自动机接受.称为上下文敏感或上下文有关。也即只有在x、y这样的上下文中才能把U改写为u定义11：2型文法：P：U u 其中 UVN，uV*2型语言：L1 这种语言可以由下推自动机接受.称为上下文无关文法。也即把U改写为u时，不必考虑上下文。注意：2型文法与BNF表示相等价。（右线性）P：U T 或 U Tw 其中 U、wVN TVT 3型语言：L3 又称正则语言、正则集合 这种语言可以由有穷自动机接受.3型文法称为正则文法。它是对2型文法进行进一步限制。（左线性）P：U T 或 U wT 其中 U、wVN TVT定义12：3型文法：根据上述讨论，L0 L1 L2 L30型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。5 语法树与二义性文法1 推导与语法树推导与语法树语法树：句子结构的图示表示法，通常表示成一棵倒立的树。结点：符号 根结点：识别符号识别符号 中间结点：非终结符非终结符 叶结点：终结符或非终结符终结符或非终结符 边：表示结点间的派生关系。ZUVabcd 注意一个重要事实：文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其 推导出来。语法树的生成规律不同，但最终生成的语 法树形状完全相同。某些文法有此性质，而某些文法 不具此性质。句型的推导及语法树的生成（自顶向下）给定GZ，句型w：可建立推导序列，Z=w 可建立语法树，以Z为树根结点，每步推导生成语法树的一枝，最终可生成句型的语法树。*1(1)(2)(3)(5)(4)0一般推导：树与推导句型推导过程 句型语法树的生长过程 由推导构造语法树由推导构造语法树1从识别符号开始，自左向右建立推导序列。由根结点开始，自上而下建立语法树。P=；0；1；9；Z=；例：无符号整数的文法：G=（VN，VT，P，E）VN,VT =0,1,2,3,9例：G句型10=0 0=0=110=最右推导 由语法树构造推导由语法树构造推导2自叶而根修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。从句型开始，自右向左地逐步进行归约，建立推导序列。2 文法的二义性文法的二义性 定义 若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。下面举一个二义性文法的例子：GE:E:=E+E|E*E|(E)|i VN=E VT=+,*,(,),i 对于句子Sii *i L（GE），存在不同的规范推导：EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(1)E=E+E=E+E*E=E+E*i=E+i*i=ii *i(2)E=E*E=E*i=E+E*i=E+i*i=ii*i 定义 若一个文法的某句子存在两个不同的规范推导，则该文法是二义性的，否则是无二义性的。若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。由于无二义性文法比较简单，我们也可以采用另一种解决办法：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。例例:算术表达式的文法算术表达式的文法 E:=E+E|E*E|(E)|i E:=E+T|T T:=T*F|F F:=(E)|i例例:Pascal 条件语句的文法条件语句的文法:=If then|If then else :=|.小 结 掌握符号串、文法、句型、句子和语言的定义 几个重要概念：语法树、文法的二义性等。了解文法分类。本 章 作 业 P36：6#，7#，8#，9#，10#