第2章高级语言与语法描述

1、第二章 高级语言及其语法描述知识结构： 语法 语义高级语言语用程序语言的特征字母表和符号符号和符号串符号串的运算符号串集合的运算 文法语法描述文法的形式定义产生式上下文无关文法 语法描述推导语言的形式定义句型、句子和语言最左、最右推导 语法树的构造语法树和二义性二义性文法文法的限制形式语言第一节 程序语言的定义一、高级程序语言的定义高级程序语言是用来描述算法和计算机实现这双重目的。它是一定字符集（字母表）上的字符串（有限序列）。其中包括：语法，语义，语用。语法: 描述的语言的结构语义：描述语言的含义（意义）语用：有关程序设计技术和语言成分的使用方法。二、语法语言的语法是指这样的一组规则，用它可

2、以形成和产生一个合式的程序。其中包括：词法规则，语法规则。1、词法规则是指单词符号形成的形式规则，即由基本符号构成符号串（单词）的书写规则。程序语言的单词符号类型：关键字、标识符、常数、运算符、界符。标识符书写规则标识符是由字母或数字组成的以字母为开头的一个字符串。 标识符结构图： 描述标识符的文法：单词符号可采用正规文法描述这一结构的合法性。左线性文法（从右向左）I a Ia Id （I 文法开始符号）右线性文法（从左向右）I aB a （B 变量）B aB dB a d （a 字母，d 数字）上述文法均可生成任意的合法标识符。例：标识符 a9c2I aB a9B a9cB a9c2 （右线

3、性文法）I I2 Ic2 I9c2 a9c2 （左线性文法）实常数书写规则实常数组成：整数部分，小数部分，指数符号部分，指数部分。 整数部分 小数部分 指数符号部分 指数部分 实常数类型：整数部分 + 小数部分 + 指数符号部分 + 指数部分整数部分 + 小数部分整数部分 + 指数符号部分 + 指数部分整数部分产生实常数的文法：右线性文法R dA d （R 定义实常数，A 剩余部分变量）A dA d .B （d 数字，B 小数变量）A eC eD （e 指数标记，C 指数符号变量）B dB d （D 指数变量）B dCC eD eCC +D -DD dD d2、语法规则语法规则是语法单位的形成

4、规则，采用上下文无关文法作为程序设计语言语法的描述工具。语法单位：表达式，语句，分程序，过程，程序。表达式表达式的定义方法：变量，数组元素，常数，函数均是表达式；若E 1，E 2是表达式，则E 1+E2，E 1-E 2，E 1*E2，E 1/E和（E ）都是表达式。表达式的定义式：E E OP E（E ） iOP + - * /语句语句的定义方法：程序语言中的各类语句由关键字，界符等表示它们之间的位臵关系。赋值语句的定义式：A i := E条件语句的定义：S IF E THEN S1S IF E THEN S1 ELSE S2E 为表达式， S为文法的开始符号，S i 为语句序列。3、过程 构

5、造过程语句的定义式的算法：语法图中出现的关键字（单词符号）、界限符，在产生式中作为文法的终结符；非关键字、界限符作为文法的非终结符（语法变量）；按箭头的顺序写出每个语法成分；遇到环路，用递归方式定义。过程语句的定义式：<过程说明> PROCEDURE<过程名><参数表><分程序>PROCEDURE <过程名><参数表><分程序><过程说明><过程名> i<参数表> （<标识符表>）<标识符表> i，<标识符表> i语言的词法规则和语法规则定

6、义了程序的形式结构，判定输入字符串是否构成一个形式上正确（即合式）程序的依据。三、语义1、语义的定义语义就是定义一个程序（单词符号和语法单位）意义的一组规则。2、程序语言的结构程序语言的组成：程序语言的每个组成成分都有（抽象的）逻辑和计算机实现两方面的意义。程序语言的功能：是描述数据和对数据的运算。程序的基本结构：程序表达式 数据的引用 算符 函数调用第二节 高级语言的一般特性一、高级语言的分类1、强制式语言（过程式语言）。2、应用式语言（函数式语言）。3、基于规则的语言（逻辑式语言）。4、面向对象语言。二、程序结构一个高级语言程序通常由若干子程序（过程、函数等）构造，许多语言引入了类、程序包

7、等高级结构。三、数据类型与操作1、数据类型的作用区别数据对象的属性；确定数据对象具体的值；作用于数据对象的操作。2、初等数据类型常见的初等数据类型：数值数据、逻辑数据、字符数据、指针类型。标识符和名字：标识符标识符指由字母和数字组成的以字母为开头的一个字符。 名字有明确的意义和属性, 名字代表一个抽象的存储单元。标识符和名字的区别：标识符是一个没有意义的字符序列，但名字却有明确的意义和属性。名字的属性和说明：属性名字的属性包括类型和作用域。类型决定名字值的内部表示形式及对其施加的运算。作用域规定名字值的存在范围（全局量、局部量）。说明名字的静态定义：使用说明语句和隐约规则定义名字的属性，引用时

8、进行合法性检查。隐约规则：用一些特定的字母作为名字的首字符定义名字的属性。 名字的动态定义：在名字被引用时确定其属性，并进行必要的数值转换。3、数据结构数组一个数组是由同一类型数据所组成的某种n 维矩形结构。 数组的特点：确定数组元素的个数；数组元素具有相同的结构；数组元素可随时被访问。数组的分类：确定数组:一个数组所需的存储空间大小在编译就是已知的。可变数组:一个数组所需的存储空间大小在使用时才能定义。下标：沿着每一维距离, 下标只能在该维的上、下限之内变动。例：VAR A110 OF INTEGER 下限值 上限值取值范围：下限值下标值上限值下标变量：数组的每个元素（下标变量）由数组名与各

9、维的下标值命名。 例：VAR A12，13 OF INTEGER数组元素： A2，3一维下标值（行） 二维下标值（列）数组元素的存储方式：列式存储 A1，1 A1， A2，第一列 A1，2A2，第二列 A2， A1，A2，第三列记录记录结构是由已知数据组合起来的一种结构。一个记录有若干个分量。记录栏：每个分量称为记录的一个栏（或域）。每个分量都是一个确定类型的数据，不同分量的数据类型可以不同。记录的存储方式：连续存储，便于各分量地址的计算（相对偏移量）。 四、语句与控制语句1、表达式由运算量与运算符组成。一目运算：前缀式 -X后缀式 P二目运算：由二个运算量和一个运算符组成的符号串。中缀式 X

10、+Y*Z算符优先关系：算数运算符，关系运算符，逻辑运算符。2、语句不同的语言含有各种不同形式和功能的语句。 说明语句 语句类型赋值语句执行语句控制语句输入/输出语句简单语句：不含其它成分的基本语句语句结构（如：GOTO ，赋值语句）。复合语句：句中有句的语句（如：条件语句，复合语句等）。赋值语句：不同语言的赋值语句有不同的语法结构，但多数语言所定义的语义大体相同。例：A :=B A , B 均为变量名A 为左值，代表存储单元的地址。变量名的特征B 为右值，代表存储单元的内容。控制语句：改变程序执行的路径。无条件语句条件语句控制语句的类型 循环语句过程调用语句返回语句说明语句：说明语句旨在定义名

11、字的属性（类型或作用域）。第三节 程序语言的语法描述一、字母表与符号1、字母表（字符表）这是一个非空的有限集合（用表示），也称为符号集。 例：1 = A, B, C,Z, 0, 1,92 =0, 12、符号（字符）字母表中的元素，称为符号。例：1中的A ，B ，0，9均为1中的符号二、符号串与符号串的运算1、符号串由集合中的符号构成的有限序列（称为字），也称上的字符串（符号串）。例：=0, 1，那么0，01，11，01011等均是上的符号串。 空字符串（空串）的概念：表示不含任何符号的字符串，用表示。2、符号串的运算符号串的长度：符号串的符号个数，用绝对值符号表示。例：X 1 = abc X

12、1=3X2 = X 2=0符号串的连接：设X 和Y 是符号串，称XY 为它们的连接。例1：X = aa Y = bbXY = aabb YX = bbaa例2：x =x = x空串与其它符号串连接为该符号串本身。符号串的方幂:同一个符号串的若干次连接X 0 = X 1 = XX 2 = XXX n = XXX X (共 n 个例：X = abcX 1 = abcX 2 = abcabcX 3 = abcabcabc三、符号串集合与符号串集合的运算1、符号串集合定义1：*表示（字母表）上所有字符串的全体，包括空字符串。 例： = a, b * = ，a ，b ，aa ，ab ，ba ， 定义2：

13、集合U ，V 是* 的子集，集合U ，V 中含有且仅含有U ，V 中的所有字符串。2、符号串集合的运算用U ，V 表示字母表*上的符号串的集合。字集合求和定义如下：U+V或U VUV= X X U 或X V 例：U = a, ba , V = bb, ccU V = a, ba，bb, cc 字集合乘积定义如下：UVUV = XY X U & Y V X 属于U ，Y 属于V 的所有符号串连接XY 构成的集合。例： U = a, ba , V = bb, cc UV = abb, acc, babb, bacc VU = bba, bbba, cca, ccba 空集合定义如下：不包含

14、任何元素的集合称之空集合，用或表示。为空字符集合，含一个元素。 ， 空集合，不含任何元素。U 与空集合求和：U = U = UU 与空集合求积：U = U = U 与空字符串集合求积：U = U = U字集合方幂定义如下：U 0 = U 1 = UU 2 = UUU n = UUU. (n个例：A = a, bA 0 = A 1 = a, b A 2 = aa, ab, ba, bb A 3 = aaa, aab, aba, abb, baa, bab, bba, bbb 字集合正闭包：V 为任一集合，V +表示V 的正闭包。V + = V1V 2V 3 （方幂的并集, 无穷集）例：A = a

15、, b A+ = A1A 2A 3= a, b, aa, ab, ba, bb, aaa, aab, 制作人：李明新 共36页第16页 13-5-1 字集合星闭包:V 为任一集合，V *表示V 的星闭包。V *=V0V 1V 2V 3 ，即V * = V+ V + = VV* = V*V例1：A = a A+ = a, aa, aaa, = an n 1A* = ,a, aa,aaa, = an n 0例2：A = a, bA+ = a, b, aa, ab, ba, bb, aaa, aab, aba, A* = , a, b, aa, ab, ba, bb, 思考题：1、已知V = a ，

16、求 V+，V *。2、已知V = 0，1 ，求 V0 ，V 1，V 2。3、已知 ，求 *，+。四、上下文无关文法1、文法的形式定义文法：文法是用来描述一个语言的语法结构的形式化规则（即语法规则）。这些规则必须是准确的，易于理解的，而且，应当有相当强的描述能力，足以描述各种不同的结构。产生式（规则）：制作人：李明新 共36页第17页 13-5-1 产生式是从“产生语言”出发，定义了语法单位的有限条书写规则，借助这些规则产生语言的全部句子。元语言符号：定义为： “”或： “”例：A A 为产生的左部， 、为产生的右部。上下文无关文法：定义的语法单位是完全独立于这种范畴可能出现的环境。上下文无关文

17、法的形式定义：文法G 是一个四元组G=（V N ，V T ，S ，P ）。V N ：非终结符号的有穷集合, 代表所定义的语法单位（语法范畴）。V T ：终结符号的有穷集合，组成语言的基本符号。S ：文法的开始符号，S V N 。P ：产生式的（有限）集合（定义语法单位的规则）其中：V N V T = ，用V 表示文法中所有的符号集合V= VN V T 。 每条产生式一般形式：A ，其中“”表示“定义为”，A V N ，（V N V T ）*。例：无符号整数L 1 = n n是无符号整数 G 1 =（V N ，V T ，N ，P ）制作人：李明新 共36页第18页 13-5-1 V N = N,

18、 D,V T =0, 1, 2,9P = NND, ND, D0 1 . 9 S = N利用该文法可得到所有的无符号整数，或者说所有的无符号整数均可由文法G1分析出来。2、语言的形式定义上下文无关文法定义一个语言，是从文法的开始符号出发，反复连续使用产生式（文法规则），对非终结符号施行替换和展开。例 由文法开始符号N ，推导出“340”：N ND NDD DDD 3DD 34D 340依据文法规则（产生式）可以分析某一符号串是否为该文法的句子。推导：从文法G 的开始符号出发，使用产生式的右部符号替换左部符号，直至推出给定的句型，称为一个推导。推导每前进一步总是引用一条产生式（规则），而符号“”

19、表示仅推导一步的意思。例：表达式文法E E+TE TT T*FT F制作人：李明新 共36页第19页 13-5-1 F iF (E证明输入符号串i+i*i是否为该文法的一个句子？证明：E E+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i依据表达式文法建立的一个推导，证明了i+i*i是该文法的一个句子。直接推导：若存在A ，仅当A是一条生产式（一步推导），称A直接推出 。其中：，(V N VT *，A V N 。间接推导：如果123n ，则称这个序列1到n 的一个推导。若存在一个从1到n 的推导, 则称1可推导出n 。 1+ =>n 即从1经过一步或若干步可以推出n 。1

20、* =>n 即从1经过0步（1=n ）或若干步可以推出n 。最左推导：任何一步 都是对句型中最左的非终结符进行替换。 其中：, (V N VT *。例：表达式文法的最左推导E E +TT +TF +Ti+T i+T *Fi+F *Fi+i*F i+i*i最右推导：任何一步都是对句型 最右非终结符进行替换。制作人：李明新 共36页第20页 13-5-1 例：表达式文法的最右推导E E+T E+T*F E+T *iE+F *iE +i*iT +i*iF +i*ii+i*i例1：L 2= am b nm, n 1G =（V N ，V T ，S ，P ）其中V T = a, b ,VN = S,

21、 A, BP = SAB ，A aA ，A a ，B Bb ，B b文法开始符号为S ，该语言代表若干个连续a 后跟若干个连续b 组成的字符串集合。如a 3b 2即aaabb 为该语言的一个句子。由文法推导：S A B a A B aa A B aaa B aaa B b aaabb例2：标识符文法G =（I ,D, L , 0, 1, 2,9, a, b, c,z, I, P） 其中：P = IL IL ID ，L a b c z ，D 0129 证明a1b2是该文法的一个句型：I I D I LD I DLD L DLD a D LD a1L D a1bD a1b2句型：如 S * =&g

22、t; ， 则称为一个句型。 例：i+F*F的推导E E+TT+TF+Ti+Ti+T*Fi+F*F推导每一步的结果均为句型。句子：如 S * => ，V T * ，则称为一个句子。例：i+i*i的推导EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i 推导的最终结果为句子。语言：文法G 产生所有句子的集合，为该文法所产生的语言，记为L （G ）。L(G = | S+ =>, 且 VT * 五、文法例子1、用文法产生语言例1：文法G 1S aSbS ab从文法的开始符号出发，推出如下句子。当n = 1，S ab当n = 2，S aSb aabb当n = n，S aSb

23、aaSbb aaaabbb b归纳得出从文法的开始符号S 出发，推出句子的集合： ab，aabb ，aaabbb ， ，aaa abbb b 由该文法产生的语言 L（G 1）= an b n n1 。例2：文法G 2S ABA aA aB bB b从文法的开始符号出发，推出如下句子。当n = 1，S AB aB ab当n = 2，S AB aAB aaB aabS AB aB abB abb由该文法产生的语言 L（G 2）= am b n m，n 1 。例3：证明文法G 3和G 4的等价性文法G 3：S aS aSa从文法的开始符号出发，推出如下句子。S aS aSa aaa由该文法产生的语言

24、 L（G 3）= a2n+1 n0 。 文法G 4：S aS aAA aS从文法的开始符号出发，推出如下句子。S aS aA aaS aaa由该文法产生的语言 L（G 4）= a2n+1 n0 。结论：L （G 3）= L （G 4）同一种语言可由不同的文法定义（文法不是唯一的）。2、由语言构造文法例1：语言 L（G ）= an b n n1 写出文法已知条件n 1当n = 1，得到的句子 ab；当 n > 1，得到的句子分别是 aabb，aaabbb ，aaa bbb ； 每个句子的特点，a ，b 的个数相等；引入一个文法开始符号S ：当 n = 1，S ab，S ab当 n >

25、 1，S + => an b n ，S aSb 。其中：a ，b V T ；S V N 。描述该语言的文法：S abS aSb例2：语言L （G ）= XX ( ab ）* 且X 中含有相同个数的a ，b 写出文法：S 为开始符号，（a b ）*定义X 可以为串，即L （G ）=：定义式S （a b ）*定义X 是以a 或b 开头的符号串：定义式S aB，S bA定义A 产生式，保证从A 推出a 的个数比b 的个数多1，并且a ，b 可交替或连续出现：定义式A bAAA aA aS根据对称性构造B 的定义式：定义式B aBBB bB bS描述该语言的文法：S aB bA A bAA a

26、aSB aBB b bS3、文法小结一个语言是某个特定的字母表上的符号按一定规则构成的符号串（字符串）的集合。字母表：它规定了语言中所允许出现的符号（终结符）。 目标：语言定义的目标（文法开始符号）。规则：规则应指明如何从字母表中的字符构成目标, 也称语法规则（文法中的产生式）。文法的开始符号，至少应在产生式的左部出现一次。某一种语言的文法代表了该语言的形式化定义:由开始符号所推出的所有句子都是该语言的句子。该语言的所有句子都可以由该文法推出。同一种语言可由不同的文法定义（文法不是唯一的）。第四节 语法分析树与二义性一、语法分析树（语法树）1、语法树的定义用一张图表示一个句型的推导过程称为语法

27、树（推导）。语法树的表示形式：由根结点；内部结点；叶子结点组成。结点的表示形式：根结点：由文法开始符号标记；内部结点：由文法的非终结符号标记；叶结点：由终结符号标记。例：句型i+i*i 的推导的语法树E E +TT +TF +Ti+T i+T *Fi+F *Fi+i*F i+i*i （树根文法开始符号） E + T 二、二义文法 1、二义性文法的定义如果一个文法存在某个句子，该句子对应两棵不同的语法树，即句子有两个不同的最左（最右）推导，则称该文法是二义的。例:表达式文法（二义文法）E E+E E*E ( E i此文法没有定义算符的优先级和左结合的规则(有二义 ，因此，给定的句型i+i*i的推

28、导（两个最左）对应两棵不同的语法树。运用两个最左推导，并建立两棵语法树： E E +E i+E i+E *E i+i*E i+i*i E E *E E +E*E i+E *E i+i*E i+i*I 所以该文法对于句型 i+i*I是二义性的。2、二义性的副作用语法结构的不确定，导致语义处理的不确定。同一源程序的目标代码不确定。3、二义性的解决方法修改编译算法，规定算符的优先级。直接修改文法，使得每次归约总是当前句型的句柄。三、文法二义性不等于语言二义性1、同一语言的描述可以有两种不同文法表示非二义性文法（改写后） 二义性文法（1）E E+T (1 E E+E（2）E T (2 E E*E（3）

29、T T*F (3 E ( E （4）T F (4 E i（5）F i（6）F (E非二义性文法性描述了表达式中算符的优先关系和左结合的规则。2、对于非二义性文法，任何一个句子的两个最左推导（或最右推导）都是对应同一棵语法树。3、二义性问题是不可判定的，不存在一个算法，在有限步骤内可确切判断一个文法是否为二义的。四、对文法G 的限制（简化文法）1、文法中不包含自己定义自己的产生式P P （引起文法二义性）。例：文法N SES SD DD 1E 10 0对句子110有二棵不同的语法树。 2、不包含无用的非终结符所有非终结符都必须出现在某个定义式的右部，在推导句型过程中必须被引用。例：从文法符号开始

30、，存在S * => P 即, PV N ，P + =>；P + => ，（V N U V T ）*对于P 不存在永不终结的回路。 VT * 。第五节 文法的类型根据文法G=（V N ，V T ，S ，P ）四元组中的产生式 的不同限制加以区分。一、O 型文法（短语文法，无约束文法） 图灵机，（V N U V T ），至少含一个非终结符，（V N U V T ）* 二、1型文法（上下文有关文法） 线性界限机 A ， 此处 , 不为空三、2型文法（上下文无关文法） 非确定下推自动机产生式只能为：A AV N ，（V N U V T ）*产生式的左部只能为单个非终结符，即非终结符的

31、定义与所处的上、下文无关。例：L 2=ai bi ck |i,k1 G 2=(S,A,a,b,c, S ，PP: SAc|ScA ab | aAb四、3型文法（正规文法，正则文法） 有限自动机产生式只能为左线性文法和右线性文法。左线性： AB 或 A右线性： AB 或 A 其中：A ，B V N ， V T例：L 3= ai bj ck | i,j,k 1 G 3=(S,A,B,Z,a,b,c,S,PP S aAA aA | bBB bB | cZ | cZ cZ | c 第六节 学习与理解一、填空题1、文法G ，S 是文法开始符号，如果S * =>X ，则称X 是该文法G 的句型。2、

32、文法G 产生的句子的全体是该文法描述的语言。3、文法G （S ）：SAB ， AaA ， BbBc bc描述的语言L （GS）=aj b k c k二、判断题1、正规文法不能产生语言L=an b n该语言的文法是S ab aSb ，因为不是正规文法，所 以不能产生语言L=an b n 2、正规文法一定不是二义性的。（错）因为文法的二义性问题是不可避免和不可判定的，所以正规文法也可能存在二义性的问题。3、文法的二义性和语言的二义性是两个不同的概念。（对） 因为可能有两个不同的文法G 和G，其中G 是二义性的，但是却有L （G ）= L（G）。即两个文法所产生的语言是相同的。4、一个句型对应的一棵

33、语法树包括了该句型的所有推导。（错）因为一棵语法树只能对应一个推导，所以不能包括该句型的所有推导。三、选择题1、文法G 所描述的语言是 D 的集合。A 、文法G 的字汇表V 中所有符号组成的符号串B 、文法G 的字汇表V 的闭包V *中的所有符号串C 、由文法的开始符号推出的所有符号串D 、由文法的开始符号推出的所有终结符号串2、如果一个文法满足A ，B ，C ，D ，则称该文法是二义性文法。制作人：李明新 共36页第31页 13-5-1 A 、或者文法的某一个句型存在两棵（包括两棵）以上的语法树B 、或者文法中存在某个句子，它有两个（包括两个）以上的最左（或最右）推导C 、或者文法中存在某个

34、句子，它有两个（包括两个）以上的最左（或最右）归约D 、或者在进行归约时，文法的某些规范句型的句柄不唯一四、解答题1、设字母表A=a，其上有符号串t=aa，试写出下列符号串及其长度：t 0，ttt ，t 3，t 5。解：t 0= 长度为 0ttt = aaaaaa 长度为 6t 3= aaaaaa 长度为 6t 5= aaaaaaaaaa 长度为 102、试写出符号串X=abcdddcba 中以c 打头且长度为3的子符号串。解：长度为3的子符号串是cdd ，cba 。3、设文法G ：AaAbA ab试写出相应语言L （G ）的长度不超过8的一切句子，制作人：李明新 共36页第32页 13-5-

35、1 并证明L （G ）= an b n解：文法G 的长度不超过8的所有句子有：ab ，aabb ，aaabbb ，aaaabbbb 。由A 推出的句子中的符号只有a 和b ，并且a 都在左部，b 都在右部，同时a 和b 的个数相等。因此可得L （G ）= an b n 下面就推导步数n 给出证明：当 n=1，有 Aab 语言的句子为a 1b 1，结论成立。假设当n=k时结论成立，即有A aAb aaAbb . . 步 k步 k步即语言的句子为a K b K ，则当n=k-1时, 必然有A + =>a K-1Ab K-1在此基础上, 引用产生式A aAb 一次得到A + =>a K-

36、1aAbb K-1= aK Ab K 此时, 推导步数为n=k,在此基础上, 再应用产生A ab 一次，得到A + =>a K-1aAbb K-1 aK abb K = aK+1b K+1此时, 推导步数为n=k+1。由此可见，当推导步数为n=k+1时，语言的句子为aK+1b K+1，结论成立。综合，可知结论成立，即文法描述的语言为L（G ）= an b n n 1。 4、构造文法以生成语言L （G ）=ai b j c k i ，j ，k 0解：因为句子中a ，b ，c 的个数没有直接关系，所以分别构造a i ，b j ，c k 的产生式，然后在合并。根据a i的组成字符串特点，a 的

37、个数是随i 的变化而变化，制作人：李明新 共36页第33页 13-5-1 因为已知条件i 0：当i=0，a i =，得到产生式A ;当i >0，a i = aa.a，得到产生式A aA 。同理可以得到b j 产生式是B ，B bB 。同理可以得到c k 产生式是C ，C cC 。所以得到文法G ：SABCA aA B bB C cC 5、试给出一个产生语言L （G ）=WW 0，1+，且W 不包含两个相邻的1的正规文法。解：因为语言的句子中不包含两个相邻的1，所以构造的产生式，使每一个1产生后就马上产生一个0即可满足要求。于是得到文法：S 010S 1AA 0S6、设文法GE T E+TE-TTF T*FT/FF（E ）i试给出关于（i ）与（i+i）/i的推导。ET