第二章前后文无关文法和语言 编译过程是十分复杂的信息加工过程,加工对象是用 高级语言编写的程序。 为完成编译工作,需解决两个问题 如何确切地描述和定义一种程序设计语言 如何识别和分析这种语言 在20世纪50年代, N. Chomsky首先对语言的描述问题 进行了探讨。他提出了一种用来描述语言的数学系统, 并以此定义了四类性质不同的语言,称为语言(文法) Chomsky分类。 人们把用一组数学符号和规则来描述语言的方式称为 形式描述,把所用的数学符号和规则称为形式语言
1 第二章 前后文无关文法和语言 编译过程是十分复杂的信息加工过程，加工对象是用 高级语言编写的程序。 为完成编译工作，需解决两个问题： – 如何确切地描述和定义一种程序设计语言 – 如何识别和分析这种语言 在20世纪50年代，N.Chomsky首先对语言的描述问题 进行了探讨。他提出了一种用来描述语言的数学系统， 并以此定义了四类性质不同的语言，称为语言（文法） 的Chomsky分类。 人们把用一组数学符号和规则来描述语言的方式称为 形式描述，把所用的数学符号和规则称为形式语言
形式语言与自动机 此后,对形式语言以及识别语言的自动机的理 论与应用展开了深入研究,并取得了丰硕成果, 这些成果对编译理论、信息工程、人工智能以 及数理语言学、计算语言学产生了深远影响。 目前,形式语言与自动机理论已成为计算机科 学中的一个重要分支 本章将初步介绍形式语言中的某些基本概念和 知识,重点是与编译技术密切相关的一些术语 和概念,诸如文法、语言、句子、句型、短语、 句柄以及句型分析等
2 形式语言与自动机 此后，对形式语言以及识别语言的自动机的理 论与应用展开了深入研究，并取得了丰硕成果， 这些成果对编译理论、信息工程、人工智能以 及数理语言学、计算语言学产生了深远影响。 目前，形式语言与自动机理论已成为计算机科 学中的一个重要分支。 本章将初步介绍形式语言中的某些基本概念和 知识，重点是与编译技术密切相关的一些术语 和概念，诸如文法、语言、句子、句型、短语、 句柄以及句型分析等
21文法及语言的表示 据统计,在世界各地,人们所使用的语言达2700多种。 什么是语言? Webster的定义:“为相当大地区的公众所懂得并 使用的话’,以及组成这些‘话’的方法的统 体 上述定义对于建立语言的数学理论而言不够精确。 另一定义:“某一字母表上符号串(句子)的集合” 仍需进一步精确化: 1)为所定义的句子提供一种结构性的描述(语法规则); 2)再提供一种手段,以便能准确地判别什么是该语言中 的正确句子(即识别方法、分析方法等)
3 2.1 文法及语言的表示 据统计，在世界各地，人们所使用的语言达2700多种。 什么是语言？ – Webster的定义：“为相当大地区的公众所懂得并 使用的‘话’，以及组成这些‘话’的方法的统一 体” – 上述定义对于建立语言的数学理论而言不够精确。 另一定义：“某一字母表上符号串（句子）的集合” 仍需进一步精确化： 1）为所定义的句子提供一种结构性的描述（语法规则）； 2）再提供一种手段，以便能准确地判别什么是该语言中 的正确句子（即识别方法、分析方法等）
21文法及语言的表示(续) 如果能刻画出一种语言的所有句子,也就定义出了这 种语言。 遗憾的是,对于自然语言来说,目前尚无能够完全刻 画一语言全部句子的结构的方法 然而,对大多数程序设计语言(或者形式语言)来说 此问题已被解决。1960年,ENr& J. Backus首先用 BNF( Backus-Naur- Formal(范式))对 ALGOL语 言进行了描述。 应指出,BNF成功地解决了程序设计语言的语法描述 问题,但描述其语义,还必须借助自然语言
4 2.1 文法及语言的表示（续） 如果能刻画出一种语言的所有句子，也就定义出了这 种语言。 遗憾的是，对于自然语言来说，目前尚无能够完全刻 画一语言全部句子的结构的方法。 然而，对大多数程序设计语言（或者形式语言）来说， 此问题已被解决。1960年，P.Naur & J.Backus首先用 BNF（Backus-Naur-Formal（范式））对ALGOL语 言进行了描述。 应指出，BNF成功地解决了程序设计语言的语法描述 问题，但描述其语义，还必须借助自然语言
21文法及语言的表示(续) 通常,可用如下方式表示或定义一种语言: (1)若语言的句子有限时,可用枚举法。例如,只含两 个句子的语言:{“ am a teacher”,“ You are students”} (2)制定有限条规则,用于产生所要描述的语言的全部 句子(可无限多),这些规则构成了该语言的文法 (3)设计一种装置(算法或过程),它以某字母表上的 符号串为输入,判别该符号串是否为所描述语言的句 子。此装置称为自动机
5 2.1 文法及语言的表示（续） 通常，可用如下方式表示或定义一种语言： （1）若语言的句子有限时，可用枚举法。例如，只含两 个句子的语言：{“I am a teacher”, “You are students”}; （2）制定有限条规则，用于产生所要描述的语言的全部 句子（可无限多），这些规则构成了该语言的文法。 （3）设计一种装置（算法或过程），它以某字母表上的 符号串为输入，判别该符号串是否为所描述语言的句 子。此装置称为自动机