第2章 文法和语言的基本知识.ppt

1、第二章学习语法和语言的基本知识，本章的目的，学生通过学习了解高级程序语言的一些基本概念及其分类。 用语法结构的形式说明问题。 讲义六课以板书为主，本章主要介绍乔姆斯牛鼻子语法及其分类、语法的二义判断和证明、上下文相关语法的简化和语法树。 重点和难点，本章重点是二义判断和转换以及高级语言语法的内容。 语法分类是一个难点，2.1字母和符号串的基本概念，1 .字母是元素的非空穷集合。 例如，=a、b、c是由a、b、c三个元素组成的字母表，按字母表的定义。 字母至少包含一个要素。 字母表的要素。 可以使用字符、数字或其他符号。 2.1.1字母和符号串。 例如，=0，1是字母，由0和1两个元素组成。 不

2、同的语言有不同的字母。 例如，英语字母由26个字符组成，数字和标点符号的集合，而习语言字母由字母、数字和几个专用符号组成。 2 .符号(文字)字母的要素称为符号或文字。 例如，在上面的示例中，a、b和c是字母表中的符号. 0和1是字母表中的符号。 3 .符号串(字)符号的贫穷系列称为符号串。 例如，如果设置字母=a、b、c，则存在代码串a、b、ab、ba、cba、abc。 符号串始终在特定的字母表上创建，由字母表上的多个贫穷符号组成。 象征符列中的象征符顺序很重要。 例如，ab和ba是字母上的两个不同的象征符列。 不包含符号的符号串被称为空符号串，并且被表示为:即，空符号串由0个符号组成，其长

3、度=0。 1 .假定符号串的连接x和y是符号串，则字符串xy被称为它们的连接。 也就是说，xy是在x符号串之后写入y符号串的符号串。 例如，假设x=abc，y=10a，则xy=abc10a，yx=10aabc。 注:对于任何符号串x，都有x=x=x。2.1.2代码串的运算，设集合的积为a和，设代码的集合，则a和b的积，例如设Aa、bB=c、d，定义为AB=ac、ad、bc，的集合的积，是由满足xA、yB的所有符号串xy构成的集合。 对于任何符号串x，通常x=x=x，因此对于任何集合a，A=A=A，尤其是表示由空符号串而不是集合组成的集合，而不是该集合。 假设符号串的平方运算x是符号串，则x的平

4、方运算是x0=X1=x x2=xx xn=http:/www.B /小毛毛/x=xxn-1 (n 0)例如，假设x=abc，x0=x1=abc x2=xx=abcabc 4.的集合的幂运算为a代码串的集合，则集合a的幂运算定义为a0，b A0=A1=a，b a2=aa，ab，ba，ba 如果是aab、aba、abb、baa、Bab，则将A=a、b、aa、ab、ba、bb、aaa、aab、A*=、a、b、aa、ab、ba、bb、aaa、2.2语法和语言的形式定义、序列的集合称为形式语言。 即，每个形式语言是按照字母上的给定规则配置的所有符号串的集合，相反，任何字母上的符号串的集合

5、都可以定义为一个形式语言。 不考虑形式语言的意义。 例如，习语言是它的基本符号系统上的符号串的集合，每个习语言柱计程仪是基本符号的符号串。 2.2.1形式语言、形式语言的记述有两种方法:语言是穷困的集合时，用列举方法来表示语言:例如，如果设置了字母A=a、b、c，对于L1=a、b、c L2=a，则需要设定语法来记述:例集合a显然可以表示为A0 a-1 aa-0 aa-1并且由a产生的符号串所属的，这就是用语法来描述的语言。 1 .规则也称为生成式。 这是符号和符号串的规则对(a，)，通常写成a (或A:=)。 其中，a是规则的左部，是符号表示规则的右部，它是符号串，“:=”表示“定义”或“生成

6、”，左部符号是右部的符号串定义或左部符号来生成右部符号串。2.2.2语法的形式定义，例如，在上例中，规则A0 A1 AA 0 AA 1描述的语言序列的定径套仅为由0和1组成的符号串(=0，1，00，00，01，10，000，100 )。 出现在规则中的符号分为终止符和非终止符两种。 非终止符导出符号或符号串、即特定符号串的集合，并可以用大写字母表示，或者用尖括号将非终止符括起来。 例如，例子中的a。 的双曲馀弦值。 终止符是构成语言的基本符号，是语言不可分离的基本符号，通常用小写字母表示。 例如，上面示例中的0和1。 2 .语法语法是规则的非空穷集合，通常表示为四组G=(VN，VT，p，s )

7、。 VN是规则中的非终止符的集合。VT是规则中的终止符的集合。 p是语法规则的集合。 s是非终止符的，并且应当作为至少一个规则的左边部分被称为语法开始符号或者语法识别符号。 下面的例子显示了在某种语言l之后，如何写出能够正确记述该语言的语法g。 设字母=a，b，试着设定语法。 由于记述语言L=a2n，b2n| n 1分析: n=1 L=aa，bb是n=2 L=aaaa，bbbb，n=的bbbbb，所以定义了语言l的语法G=VN，VT，p，VN=A，b，d，VT=a，BP=AAA|aab 但p是AB|D Baa|aBa Dbb|bDb G和g是两种不同的语法，如果它们所描述的语言相同，则喀呖声来

8、说明应该属于语言l的方法，为什么不是g呢？ G=(A，a，b，p，a )其中，p是Aaa|bb|Aaa|Abb，对于语法g来说，它生成的所有符号串都应该属于语言l，但是试着修改一下表示g生成的符号串，例如aabb，问题:所有标识符的语法。VN=I，l，D VT=a，b，c.x，y，z，0，1，2，9 p=il|ldla|b|la|b|c| x|y|z d0|1|2|3|9此语法不能定义ab，abc，它是一个仅由字符串组成的标识符在语法中，定义包括*的算术表和表达式，并且定义以下自然语言描述:变量是表达式，并且如果E1和E2是算术表达式，则E1 E2和(E1 )也是算术表达式。 解析算术表达式的

9、定义用自然语言来描述，这是算术表达式的非形式定义，题意用语法来定义算术表达式，即用形式化的方法来定义表达式。 定义算术表达式的语法是G=(E，I，*，(，)，p，e )，其中p是Ei|E E|E*E|(E )。 字母=a， 作为b，一个句子，当试图设置和校正该方法时，描述语言L=abna|n0具有如下结构特征:分析该语言中符号串的结构特征，n=0 L=aa(b0=)，n=1 L=aba，n=2l，其中1 .直接导出的命令g是语法，我们将xAy直接从xAy导出，并且只有Aa在g的一个规则中是x，y(VNVT)*，即，从符号串xAy中直接挤出xAy，并且只使用一个规则。 例如，设置了语法GS=(S

10、，0，1，p，s )、2.2.3语法的格式定义，其中，p是如下直接导出的:在s处，x=0，y=100 s 11=000 s 11 二是对于语法g中的任意规则Aa，A=，即导出的依据是规则。 2 .导出:如果存在a0=a1=a2=an，那么序列为以a0到an的长度为n的导出，其指示a0=an (即a0=an )起点于a0，且可通过一步或多次规则导出an。 3 .广义的导出a0 an表示可以从a0起经过0或几个步骤来导出an。 即，a0a-n意味着a0a-n或a0a-n。 已经证明的是，在上面的示例中，存在E E E i i*i，其中，直接导出的长度为1，所导出的长度至少为1，广义导出的长度至少为

11、0。 解析是语法GE的语句，只要证明符号串(i*i i )对于语法g存在一个导出。 因为存在e(e)(ee)(e*e)(i*e)(i*ie)(i*i )或e(i*i )，所以在5 .语言语法GS中生成的符号串(i*i )的所有句子的集合被称为语法g中定义的语言因为s是语法的开始符号，因此在使用s-x时，SVN能够有S=x，其不符点为xVT*。 此时的x不是句子。 从语言定义可以看出，(1)如果给予语法，语言也确定。 (2)L(G )是VT*的子定径套，即，属于VT*的符号串x不一定属于L(G )。 设定语法GA: AyB，BxB|，求出用该语法定义的语言。 因为分析可以从语法开始符号a得到多个

12、x结尾跟在y开头之后的符号串，所以该语法定义的语言为L(GA)=yxn| n1。 形式语言理论可以证明，下面的两点:(1)提供语法，使得它的语言，即，GL(G )可以在结构上是唯一的。 (2)给定一种语言，可以确定该语法，但该语法不是唯一的，即，该语法是LG1、G2或Gn。 语法和语言密切，语法中定义的任何句型和句子都可以从语法中导出，与导出过程中选择的非终止符顺序无关。 例如，设置了语法GN1: N1N NND|D D0|1|2的语法所定义的语言是由数字0、1和2组成的无符号整数。 2.2.4规范导出和规范归约，符号串12是该语法的一个句子，该句子根据以下三个不同的导出序列，3360n1nn

13、dn2d2d212最右导出N1 N ND DD 1D 12最左导出N1 N ND DD D2 12通常并不仅考虑最右导出和最左导出这两个特殊的导出。最左(最右)导出是指对于一个导出序列的每个步骤直接导出，并以中间的最左(最右)非终止符进行替换。 最右导出也称为规范导出，规范导出中导出的句型也称为规范句型。 规范导出的逆过程，又称最左归约，又称规范归约。 导出是用规则的右边置换句型中的非终止符的过程，归纳是用非终止符置换句型中的某个子串的过程。 例如，语法GN1中如果有规范导出N1 N ND N2 D2 12，则规范递归约为12d2n 2ndn-1，1 .具有递归规则的递归规则是指在规则的左部和

14、右部具有相同的非终止符的规则。 如果语法中有规则AA，则称为规则左递归。 如果语法中有规则A A，则称为规则右递归。 如果语法中有规则AA，就称为规则递归。 2、语法递归语法的递归性是指语法中的任何非终止符、2.2.5递归规则和语法的递归性，如果能建立导出过程，则在导出过程中得到的符号串中出现该非终止符本身，语法是递归的，否则不递归。 如果语法中有导出A A，就称为语法左递归。 如果语法中有导出AA，则称为语法右递归。 如果语法中有导出AA，就称为语法递归。 例如，在语法中，如下所示的规则: UVx VUy|z这3个规则都不是递归规则，但是如果有U Uyx，则该语法是左递归的。 再考虑语法GN

15、1 :N1N NND|D，考虑语法GA:因为AaB|bB Ba|b在该语法中没有递归性，它所描述的语言很穷。 这个语法记述的语言是L(GA)=aa、ab、ba、bb。 D0|1|2如果该语法中有直接左递归规则NND，则将该语法称为左递归语法或语法左递归，其定义的语言称为0、1、2。 当一种语言是无限集合时，定义该语言的语法必须是递归的。 因为软件编程语言是无限集合，所以描述它们的语法必须是递归的。 2.3句，直接句和驾驶盘，把g称为语法，把s称为语法的开始符号，假定语法g的句型，如果有S A且a，就称为对非终止符a的句型句。 特别是，如果有S A且a，则称为直接短语。 2.3.1句和直接句，一个句型的最左直接句称为该句型的句型。 驾驶盘特征: (1)是直接短语，即某个规则的右部。 (2)最左性。 语法GS