第二章前后文无关文法和语言 在20世纪50年代，N.Chomsky首先对语言的描述问题进 行了探讨。他提出了一种用来描述语言的数学系统，并以 此定义了四类性质不同的语言，称为语言文法)的 Chom.Sky分类。 人们把用一组数学符号和规则来描述语言的方式称为形式 描述，把所用的数学符号和规则称为形式语言。 ·目前，形式语言与自动机理论已成为计算机科学中的一个 重要分支。 本章将初步介绍形式语言中的某些基本概念和知识，重点 是与编译技术密切相关的一些术语和概念，诸如文法、语 言、句子、句型、短语、句柄以及句型分析等
第二章 前后文无关文法和语言 • 在20世纪50年代，N.Chomsky首先对语言的描述问题进 行了探讨。他提出了一种用来描述语言的数学系统，并以 此定义了四类性质不同的语言，称为语言（文法）的 Chomsky分类。 • 人们把用一组数学符号和规则来描述语言的方式称为形式 描述，把所用的数学符号和规则称为形式语言。 • 目前，形式语言与自动机理论已成为计算机科学中的一个 重要分支。 • 本章将初步介绍形式语言中的某些基本概念和知识，重点 是与编译技术密切相关的一些术语和概念，诸如文法、语 言、句子、句型、短语、句柄以及句型分析等
2.1文法及语言的表示 ·首先，我们确定一个概念：什么是语言？ 。 据统计，目前在世界各地，人们所使用的语言达2700多种。 Websterl的定义：“为相当大地区的公众所懂得并使用的话，以 及组成这些话’的方法的统一体” ·上述定义对于建立语言的数学理论的目的而言不够精确。 ·所以，有人又将语言定义为：“某一字母表上符号串（句子）的集合” ·此定义仍需精确化。因为： 1)还应为所定义的句子提供一种结构性的描述（语法规则）； 2)最好能再提供一种手段，以便能准确地判别什么是该语言中的正确 句子（即识别方法、分析方法等）
2.1 文法及语言的表示 • 首先，我们确定一个概念：什么是语言？ • 据统计，目前在世界各地，人们所使用的语言达2700多种。 • Webster的定义：“为相当大地区的公众所懂得并使用的‘话’，以 及组成这些‘话’的方法的统一体” • 上述定义对于建立语言的数学理论的目的而言不够精确。 • 所以，有人又将语言定义为：“某一字母表上符号串（句子）的集合” • 此定义仍需精确化。因为： 1）还应为所定义的句子提供一种结构性的描述（语法规则）； 2）最好能再提供一种手段，以便能准确地判别什么是该语言中的正确 句子（即识别方法、分析方法等）
2.1文法及语言的表示（续） ·遗憾的是，对于自然语言来说，目前尚无能够完全刻 划一语言全部句子的结构的方法。 ·然而，对大多数程序设计语言来说，此问题已被解决。 1960年，P.Naur&J.Backus首先用BNF(Backus- Naur-Formal(范式))对ALGOL语言进行了描述。 。 应指出，BNF成功地解决了程序设计语言的语法描述 问题，但描述其语义，还必须借助自然语言。 通常，可用如下方式表示或定义一种语言： （1)若语言的句子有限时，可用枚举法。例如，只含两个句子的语 言： {"I am a teacher","You are students"); (2)制定有限条规侧，用于产生所要描述的语言的全部句子（可无 限多)，这些规侧构成了该语言的文法。 (3)建立一种装置（算法或过程），它以某字母表上的符号串为输 入，判别该符号串是否为所描述语言的句子。此装置称为自动机
2.1 文法及语言的表示（续） • 遗憾的是，对于自然语言来说，目前尚无能够完全刻 划一语言全部句子的结构的方法。 • 然而，对大多数程序设计语言来说，此问题已被解决。 1960年，P.Naur & J.Backus首先用BNF（BackusNaur-Formal（范式））对ALGOL语言进行了描述。 • 应指出，BNF成功地解决了程序设计语言的语法描述 问题，但描述其语义，还必须借助自然语言。 • 通常，可用如下方式表示或定义一种语言： （1）若语言的句子有限时，可用枚举法。例如，只含两个句子的语 言： {“I am a teacher”, “You are students”}; （2）制定有限条规则，用于产生所要描述的语言的全部句子（可无 限多），这些规则构成了该语言的文法。 （3）建立一种装置（算法或过程），它以某字母表上的符号串为输 入，判别该符号串是否为所描述语言的句子。此装置称为自动机
2.2文法和语言的定义 2.2.1基本概念和术语 1。字母表（符号表，符号集）由若干元素（符号、字母）组成的有限 非空集合 2。符号串用字母表中符号所组成的任何有限序列。 符号串的长度=符号串中所含符号的个数 例：aba的长度为3。记为：aba=3 空串不含任何符号的符号串，记为ε。显然，|ε仁0。 本课约定用A、B、C、∑等表示字母表或符号串集；用a,b,c,S,T,U等 表示符号；用s,t,u,Xy,Z,β，δ等表示符号串。 3。符号串的前（后）缀及子串 设o,B,δ，x是符号串，若xaB6,则称B是x的子串；特别地，当o=e(8 8)时，称B是x的前（后）缀
2.2 文法和语言的定义 2.2.1 基本概念和术语 1。字母表（符号表、符号集） 由若干元素（符号、字母）组成的有限 非空集合 2。符号串 用字母表中符号所组成的任何有限序列。 符号串的长度 = 符号串中所含符号的个数 例：aba的长度为3。记为：|aba|=3 空串 不含任何符号的符号串，记为 。显然，| |= 0。 本课约定 用A、B、C、 等表示字母表或符号串集；用a,b,c,S,T,U 等 表示符号；用s,t,u,x,y,z,,,等表示符号串。 3。符号串的前（后）缀及子串 设,,，x是符号串，若x= ,则称是x的子串；特别地，当= （= ）时，称 是x的前（后）缀
2.2.1基本慨念和术语（续) 4。符号串的连接和方幂 连接设x,y是符号串，将y直接地拼接到x之后所得的新 符号串称为x与y的连接，记为xy 注意，一般说来，xy不等于yX;但εx=x=x 方幂符号串x与其自身的n-1次连接称为x的n次方幂， 记为 即 x! 三X x"=xn-1xn=2,3,.. 这里，我们约定：x0=
2.2.1 基本概念和术语（续） 4。符号串的连接和方幂 连接 设x,y是符号串，将y直接地拼接到x之后所得的新 符号串称为x与y的连接，记为xy 注意，一般说来，xy不等于yx；但 x=x=x 方幂 符号串x与其自身的 n-1次连接称为 x 的 n 次方幂， 记为 = = = = − 0 1 1 , : 2,3,...... x x x x x x n x n n n 这里 我们约定 即
2.2.I基本秘念和术语（续) 5。符号串集合的和与积 设A,B为两个符号串之集，定义 和A+B(或AUB)={W|W∈A,或W∈B} 积AB(或AB)={XyX∈A,y∈B 显然，A+O=O+A=A;A☑=☑A=O;{E}A=A{8}=A 6。符号串集的方幂与闭包 设A是符号串的集合，定义A的方幂： A={ε}A”=A”-A(n>0) A的传递（正）闭包：A=UA=A+A+… A的自反传递闭包：A=A+{ε}
2.2.1 基本概念和术语（续） 5。符号串集合的和与积 设A，B为两个符号串之集，定义 和 A+B（或A B） ={w | w A，或 w B} 积 A•B（或 AB）= { xy |x A, y B} 显然，A+ = +A = A ； A = A = ；{}A = A{} = A 6。符号串集的方幂与闭包 : { } ( ) : { } ( 0) , : * 2 1 0 1 = + = = + + = = + = + − A A A A A A A A A A A A n A A i i n n 的自反传递闭包 的传递 正 闭包 设 是符号串的集合 定义 的方幂
2.2.1基本慨念和术语（续) ·当我们把字母（符号）表视为由长度为1的符号串构成的 符号串集时，就可定义字母表上的连接、积、方幂等运算。 ·例A=a,b,c} A=fa,b,c) A2=faa,ab,ac,ba,bb,bc,ca,cb,cc A={8,a,b,c,aa,ab,…} A实际上就是A上所有符号串构成的集合
2.2.1 基本概念和术语（续） • 当我们把字母（符号）表视为由长度为1的符号串构成的 符号串集时，就可定义字母表上的连接、积、方幂等运算。 • 例 A={a,b,c} A 实际上就是A上所有符号串构成的集合 A a b c aa ab A aa ab ac ba bb bc ca cb cc A a b c * * 2 1 { , , , , , , } { , , , , , , , , } { , , } = = =
2.2文法知语言的形式定义 我们从“产生语言”的角度出发， ①：= 。 产生语言。 指制定出有限条规 则，借助它们就能产生出些语言的 ②：=the 句子。 ③：=：= “主-谓-宾”结构。 ⑤：=monkey 语法规则见右。其中，每个用<>括 起来的部分是所要定义语言中的一 ⑥：=banana 个语法实体（称为语法单位、语法 ⑦：=eat 结是受语精粉， ⑧：=has 其含义（并读作)“定义为”.语 ⑨：=the 法规则也称为产生式(Production) ⑩：=a
2.2 文法和语言的形式定义 • 我们从“产生语言”的角度出发, 讨论文法和语言的形式定义。 • 产生语言 指制定出有限条规 则，借助它们就能产生出些语言的 句子。 • 我们以几个英语句子构成的语言为 例进行讨论。并设每个句子都是 “主-谓-宾”结构。 • 语法规则见右。其中，每个用<>括 起来的部分是所要定义语言中的一 个语法实体（称为语法单位、语法 结构、语法范畴、语法变量等）。 “::=”是用于定义语法结构的符号， 其含义（并读作）“定义为”.语 法规则也称为产生式(Production) ①::＝ ②::= the ③::= ④::= ⑤::=monkey ⑥::=banana ⑦::=eat ⑧::=has ⑨::= the ⑩::= a
2.2文法和语言的形式定义 ● 现在，我们讨论如何用上述规侧推导出相应语言的全部句子。 。 推导从语言最大的一个语法范畴（本例中是）开始，反复 用语法规则中“：三”右侧的符号串取代其左侧符号，直到所得的符号 串中不再含有可被替换语法范畴。每次替换称为一步（直接）推导， 并用符号“一”表示。例如， 。 我们首先用规则①进行第一步推导(derivation),就可得到 ，记为 → ● 所得的符号串含有两个语法范畴，可对其中 任一个（例如对)进行新的推导（替换)： ·→ → 重复上述过程，可得到一个推导序列（见下页）
2.2 文法和语言的形式定义 • 现在，我们讨论如何用上述规则推导出相应语言的全部句子。 • 推导 从语言最大的一个语法范畴（本例中是）开始，反复 用语法规则中“::=” 右侧的符号串取代其左侧符号，直到所得的符号 串中不再含有可被替换语法范畴。每次替换称为一步（直接）推导， 并用符号“ ”表示。例如， • 我们首先用规则①进行第一步推导(derivation)，就可得到 ，记为 • 所得的符号串含有两个语法范畴，可对其中 任一个（例如对）进行新的推导（替换）： • • 重复上述过程，可得到一个推导序列（见下页）
用语法规贝则进行推导所得的推导序列 推导步骤所用规则 所得的符号串 1 ① → 2 ③ → 3 ② →the 4④ →the 5 ⑤ →the monkey 6⑦ →the monkey eat 7 ⑩ →the monkey eat a 8 ⑥ the monkey eat a banana
用语法规则进行推导所得的推导序列 推导步骤 所用规则 所得的符号串 1 ① 2 ③ 3 ② the 4 ④ the 5 ⑤ the monkey 6 ⑦ the monkey eat 7 ⑩ the monkey eat a 8 ⑥ the monkey eat a banana