编译原理第三章：文法和语言

1、北京化工大学信息科学与技术学院计算机系赵瑞莲2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系2 2 22021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系2 2 2 P begin VDL;SL end. VDL VD | VD ; VDL VD var id : T SL S | S ; SL S id:= E | write(E) | read(

2、id) T int | real E id | num | E + E | E * E |(E) 2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系3 3 32021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系3 3 3Micro的词法分析的词法分析2.2 Micro2.2 Micro语言的词法分析语言的词法分析任务任务 2021-10-162021-

3、10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系4 4 4读当前字符流，直至文件结束。读当前字符流，直至文件结束。如果是：如果是： (1)(1)标识符标识符时判断是保留字时判断是保留字还是变量标识符，构造还是变量标识符，构造TokenToken表示；表示； (2)(2)数字数字时判断是整型还是时判断是整型还是实型，构造实型，构造TokenToken表示；表示； (3)(3)构造其它合法的符号的构造其它合法的符号的TokenToken表示；表示； (4)(4)遇到非法符号则报错。遇到非法符号则报错。2

4、021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系4 4 4 end2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系5 5 52021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系5 5 5说明：说明：语法分析只用到单词的语法分析只

5、用到单词的Token表示，表示， 并不改变单词的并不改变单词的Token表示表示。2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系6 6 62021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系6 6 6Procedure Parser(); begin Match($begin,1); Match($var,2); LD: Match($id,3);

6、 Match($colon,4); Match($intC/$reaC,5); Match($semi,6); ReadToken(token); if token=$line then ReadToken(token); if token=$var then goto LD; LS: case token of ($write,-）Match($Lparen,7); Expr(); Match($Rparen,8); ($read,-) Match($Lparen,9); Match($id,10); Match($Rparen,11); ($id,-) Match($assig,12);

7、Expr(); other error(13) end; ReadToken(token);2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系7 7 72021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系7 7 7语义分析过程语义分析过程 读入读入Token 遇到遇到标识符声明标识符声明时，检查是否已声明，是则报错，时，检查是否已声明，是则报错， 否则

8、构造标识符的符号表；否则构造标识符的符号表； 遇到遇到标识符定义和使用标识符定义和使用时，检查是否声明过。时，检查是否声明过。 将变量的将变量的Token改为（改为（$id,entry)形式。形式。2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系8 8 82021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系8 8 82021-10-162021-10

9、-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系9 9 92021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系9 9 92021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1010102021-10-162021-10-162021-10-16北京化工大学信息科学

10、与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1111112021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1111112021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1212122021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技

11、术学院计算机系北京化工大学信息科学与技术学院计算机系121212SemanStack(top):SemanStack的顶的顶元素元素表达式代码表达式代码生成程序生成程序id := E2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1313132021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1414142021-10-162021-10-16202

12、1-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系141414*c*d #a+b余下表达式余下表达式信息栈信息栈a+b*c*d2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1515152021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1515152021-10-1620

13、21-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系161616(a+b)*c*d2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系1717172021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系181818191919编译器各阶段工作的归纳 词法分析：识

14、别单词，至少分以下几大类：关键字（保留字）、标识符、数值量、特殊符号； 语法分析：得到语言结构（以树的形式表示）； 语义分析：考察结构正确的句子是否语义合法； 中间代码生成（可选）：生成一种既接近目标语言，又与具体机器无关的表示，便于优化与代码生成； 中间代码优化（可选）：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但是，在占用的空间上和程序执行的时间上都更省、更有效。 目标代码生成：不同形式的目标代码汇编、可重定位; 符号表管理：合理组织符号，便于各阶段查找、填写等； 出错处理：错误的种类词法错、语法错、静态语义错、动态语义错。2021-10-

15、162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系2020202021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系202020 P begin VDL;SL end. VDL VD | VD ; VDL VD var id : T SL S | S ; SL S id:= E | write(E) | read(id) T int | real E id | num

16、| E + E | E * E |(E) 2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系212121第第3 3章章 文法和语言的概念和表示文法和语言的概念和表示3.1 3.1 预备知识预备知识 - - 形式语言基础形式语言基础3.2 3.2 文法的非形式定义文法的非形式定义3.3 3.3 文法和语言的形式定义文法和语言的形式定义3.4 3.4 语法树与二义性文法语法树与二义性文法3.5 3.5 句子的分析句子的分析3.6 3.6 有关文法的实用限制有关文法的实用限制3

17、.7 3.7 文法的其它表示法文法的其它表示法3.8 3.8 文法和语言分类文法和语言分类2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系2222223.1 3.1 预备知识预备知识一、字母表和符号串一、字母表和符号串 字母表：字母表：符号的非空有限集符号的非空有限集 例：例： = =aa，b b，cc 符号：符号： 字母表中的元素字母表中的元素 例：例： a a，b b，c c 符号串：符号串：符号的有穷序列符号的有穷序列 例：例：a,aa,c,abca,aa,c,a

18、bc，. 空符号串：空符号串：无任何符号的符号串无任何符号的符号串( () 符号串集合：符号串集合：由符号串构成的集合。由符号串构成的集合。符号串的形式定义符号串的形式定义 有字母表有字母表 ，定义：，定义： （1）是是 上的符号串；上的符号串； （2）若）若x是是 上的符号串，且上的符号串，且a ，则，则ax或或xa是是 上的符号串；上的符号串； （3）y是是 上的符号串，上的符号串，iff（当且仅当）（当且仅当）y可由（可由（1）和（）和（2）产生。）产生。 2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算

19、机系北京化工大学信息科学与技术学院计算机系232323二、符号串和符号串集合的运算二、符号串和符号串集合的运算 1.符号串相等：符号串相等： 若若x、y是集合上的两个符号串，则是集合上的两个符号串，则xy iff组成组成x的每一个符号和组成的每一个符号和组成y的每一个符号依次相等。的每一个符号依次相等。 2.符号串的长度：符号串的长度： x为符号串，其长度为符号串，其长度|x|等于组成该符号串的符号个等于组成该符号串的符号个数。数。 例：例： xSTV ， |x|=33.1 3.1 预备知识预备知识2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机

20、系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系242424例：例：Aa,b,B=c,d, AB= ？ 4. 符号串集合的乘积运算：符号串集合的乘积运算： 令令A、B为符号串集合，定义为符号串集合，定义 AB xy|xA,yB ac，ad，bc，bd 3.3.符号串的联接：符号串的联接： 若若x、y是定义在是定义在是上的符号串，且是上的符号串，且xXY，yYX，则，则x和和y的联接的联接 xyXYYX也是也是上的符号串。上的符号串。 注意：一般注意：一般xyyx，而，而xx2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计

21、算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系2525256. 符号串集合的闭包运算：符号串集合的闭包运算： 设设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,

22、xyy, A1 A2 A3, x,y, xx, xy, yx,yy , xxx, xxy, xyx, xyy, A0 A1 A2 A32021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系262626若若A为某语言的基本字符集为某语言的基本字符集 Aa,b,z,0,1,9, +, /, ( , ), =B为单词集为单词集 B =begin, end, if, then,else,for, , +, /, 为什么对符号、符号串、符号串为什么对符号、符号串、符号串集合以及它们的运

23、算感兴趣集合以及它们的运算感兴趣？ 则则B A* 语言的句子是定义在语言的句子是定义在B上的符号串。上的符号串。 若令若令C为句子集合，则为句子集合，则C B * , 程序程序 C。 2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系2727272021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系2828283.2 3.2 文法的非形式讨论文法的非形式

24、讨论 1. 什么是文法：什么是文法： 文法是对语言结构的定义与描述。文法是对语言结构的定义与描述。 即从形式上用于描述和规定语言结构的称为即从形式上用于描述和规定语言结构的称为“文法文法” （或为（或为“语法语法”）。）。例：有一句子：例：有一句子：“我是大学生我是大学生” 。 这是一个在语法、语义上都正确定句子，怎么判断在语这是一个在语法、语义上都正确定句子，怎么判断在语法上是正确的？法上是正确的？2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系292929 2.2.

25、语法规则：语法规则： 我们通过建立一组规则，来描述句子的语法结构。我们通过建立一组规则，来描述句子的语法结构。 规定用规定用:= := =表示表示“由由组成组成”或或“定义为定义为”:=:= :=:=| :=:=你你| |我我| |他他 :=:= 王民王民| |大学生大学生| |工人工人| |英语英语 :=:= :=:=是是| |学习学习 :=:=| 3.2 3.2 文法的非形式讨论文法的非形式讨论2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系3030303.3. 由

26、规则推导句子：由规则推导句子： 有了一组规则之后，可以按照一定的方式用它们去有了一组规则之后，可以按照一定的方式用它们去 推导或产生句子。推导或产生句子。 推导方法：推导方法：从一个要识别的符号开始推导，即用相应从一个要识别的符号开始推导，即用相应 规则的规则的右部右部来替代规则的来替代规则的左部左部，每次仅用，每次仅用 一条规则去进行推导。一条规则去进行推导。 = = = 这种推导一直进行下去，直到所有带这种推导一直进行下去，直到所有带的符号都由的符号都由终结符号替代为止。终结符号替代为止。2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京

27、化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系313131 = = = 我我 =我我 =我我是是 =我是我是 =我是我是大学生大学生推导方法：推导方法：从一个要识别的符号从一个要识别的符号 开始推导，即用相应规则的开始推导，即用相应规则的 右部来替代规则的左部，每右部来替代规则的左部，每 次仅用一条规则去进行推导。次仅用一条规则去进行推导。2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系323232:=:= :=:= := :=the :=:=

28、big :=:=elephant :=:= :=:=ate :=:= := :=peanut例：例：有一英语句子：有一英语句子：The big elephant ate the peanut.2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系333333 = = = the = the big = the big elephant = the big elephant = the big elephant ate = the big elephant ate = the

29、big elephant ate the = the big elephant ate the peanut:=:= :=:= := :=the :=:=big :=:=elephant | peanut :=:= :=:=ate :=:= 2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系343434上述推导可写成上述推导可写成: = The big elephant ate the peanut.+说明：说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成

30、有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为分进行推导，这称之为最左推导最左推导，类似的有，类似的有最右推导最右推导（一般推（一般推 导）。导）。 (2) 从一组规则可推出不同的句子。从一组规则可推出不同的句子。3.2 3.2 文法的非形式讨论文法的非形式讨论以上规则还可推出以上规则还可推出: :大花生吃象、大花生吃花生、大大花生吃象、大花生吃花生、大象吃象等句子象吃象等句子. .它们在语法上都正确，它们在语法上都正确，但在语义上都不正确。但在语义上都不正确。2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学

31、信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系353535上述推导可写成上述推导可写成 = The big elephant ate the peanut.+ 所谓文法是在形式上对句子结构的定义与描述，所谓文法是在形式上对句子结构的定义与描述， 而未涉及语义问题。而未涉及语义问题。3.2 3.2 文法的非形式讨论文法的非形式讨论2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系363636 4.4.语法树：语法树：我们用语法树来描述一个句子的语法结构。我

32、们用语法树来描述一个句子的语法结构。Thebigelephantatethepeanut语法成分语法成分在形式语言中又在形式语言中又称称“非终结符非终结符”单词符号单词符号在形式语言中又在形式语言中又称称“终结符号终结符号”3.2 3.2 文法的非形式讨论文法的非形式讨论2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系3737373.3.5 3.3.5 句型的短语、简单短语和句柄句型的短语、简单短语和句柄 2021-10-162021-10-162021-10-16北京

33、化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系3838383.3.1 文法的定义文法的定义 3.3 文法和语言的形式定义 定义定义1. 文法文法G=（Vn，Vt，P，Z） Vn：非终结符号集：非终结符号集 Vt：终结符号集：终结符号集 P：产生式或规则产生式或规则的集合的集合 Z：开始符号（识别符号）：开始符号（识别符号） ZVnVVn Vt 称为文法的字汇表称为文法的字汇表 Vn Vt 规则的定义规则的定义规则是一个有序对规则是一个有序对(U, x), 通常写为通常写为: U : x 或或U x | U| = 1 |x| 0 2

34、021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系393939P = ； ； ； 00； 11； 99； Z = ；G=（Vn，Vt，P，Z）Vn, Vt = 0,1,2,3,9例：无符号整数的文法：例：无符号整数的文法：2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系404040几点说明几点说明： 产生式产生式左边左边符号构成集合符号构成集合Vn，

35、且，且 Z Vn。 有些产生式具有相同的左部，可以合在一起。有些产生式具有相同的左部，可以合在一起。 例、例、 ； | ； 00 | 1 | 2 | 3 | | 9文法的文法的BNF表示表示无符号整数的文法简化为：无符号整数的文法简化为： （产生式集合产生式集合+识别符号识别符号）例、例、 G ； | ； 00 | 1 | 2 | 3 | | 92021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系4141413.3.2 推导的形式定义推导的形式定义 定义定义2：文法文法G：

36、vx Uy，wxuy, 其中其中x、y V* ，UVn, u V*, 若若U : uP，则，则v w。 若若xy，有，有U : u，则，则U u根据文法和推导定义，可推出终结符号串，所谓文根据文法和推导定义，可推出终结符号串，所谓文法能推出句子来。法能推出句子来。3.3 文法和语言的形式定义称称 v直接产生直接产生w 或或w是是v直接推导直接推导 或或w直接规约到直接规约到v 2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系424242 1 1 0(6)=(1)=(3)

37、(5)=(2) 当符号串已没有非终结符号时，推导就必须终止。当符号串已没有非终结符号时，推导就必须终止。因为因为终结符不可能出现在规则左部终结符不可能出现在规则左部，所以将在规则，所以将在规则左部出现的符号称为左部出现的符号称为非终结符号非终结符号。例如：例如：G (1) ； (2) (3) (4) 0;0;(5) 1;1; (13) 9;9;请问根据文法请问根据文法G G能否推导出能否推导出1010？2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系434343 定义定

38、义3：文法文法G，U0, U1, U2,，Un V+ if v= U0 U1 U2 Unw 则则v w= G= G= G= G= G例：例： = = = =1 =1 0即即 10 = G3.3.2 推导的形式定义推导的形式定义 称称 v推导出（产生）推导出（产生）w或或w规约到规约到v（推导长度为（推导长度为n） 2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系444444 定义定义4：文法文法G，v，w V+ if v w , 或或v=w，则，则v w *= G= G

39、 定义定义5：规范推导：规范推导：有有xUy = xuy, if y Vt* ,则此推则此推 导为规范的，记为导为规范的，记为xUy = xuy |直观意义：直观意义：规范推导最右推导规范推导最右推导最最右右推导：若符号串中有两个以上的非终结符时，推导：若符号串中有两个以上的非终结符时，先推右边先推右边的。的。最最左左推导：若符号串中有两个以上的非终结符时，推导：若符号串中有两个以上的非终结符时，先推左边先推左边的。的。 称称 v推导出（产生）推导出（产生）w，或或w规约到规约到v （推导长度为（推导长度为n） 3.3.2 推导的形式定义推导的形式定义 2021-10-162021-10-16

40、2021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系454545 文法文法GZGZ所产生的所产生的 所有句子的集合所有句子的集合 形式语言理论可以证明以下两点：形式语言理论可以证明以下两点： （1）G L（G）；）； （2）L(G)G1，G2，Gn； 已知文法，求语言，通过推导；已知文法，求语言，通过推导； 已知语言，构造文法已知语言，构造文法。 无形式化方法，更多是凭经验。无形式化方法，更多是凭经验。 定义定义6：文法：文法GZ （1）句型句型：x是句型是句型 Z x,且且xV*；（2）句子句子：x是句子是句子 Z x, 且且xVt*；（3）语言语言：L（GZ）=x| xVt*, Z x ； +*3.3.3 3.3.3 语言的形式定义语言的形式定义 3.3 文法和语言的形式定义2021-10-162021-10-162021-10-16北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系北京化工大学信息科学与技术学院计算机系464646例：例：abna|n1, 构造其文法。构造其文法。 定义定义7. G和和G是两个不同的文法，若是两个不同的文法，若 L(G) = L(