第二章 文法和语言

1、第二章 文法和语言 本章内容本章内容 引言和预备知识引言和预备知识 文法和语言的形式定义文法和语言的形式定义 文法的类型文法的类型 上下文无关文法及其语法树上下文无关文法及其语法树 上下文无关文法上下文无关文法的句型分析的句型分析 一、高级语言 程序语言是一个记号系统。 n语法 n语义 1.语法 任何语言程序都可以看成是一定字符集（字母表） 上的字符串。 语法：是一组规则，定义符号如何排列，排列与 符号含义无关。 语法使得这串字符形成一个形式上正确的程序。 语法=词法规则+语法规则 例如：0.5*x1+c 0.5 x1 c * + 是语言的单词符号 0.5*x1+c是语言的语法单位（表达式）

2、（1）单词符号 语言中具有独立意义的最基本结构。 p词法规则 词法规则规定了字母表中哪些字符串是单词 符号。 单词符号一般包括：常数、标识符、基本字、 算符、界符等。 用正规式和有限自动机理论来描述词法结构 和进行词法分析。 （2）语法单位 表达式、子句、语句、函数、过程、类、 程序 （3）语法规则 规定了如何从单词符号来形成语法单位。 现在多数程序语言使用上下文无关文法来描述语 法规则。 语言的词法规则和语法规则定义了程序的形式结 构，是判断输入字符串是否构成一个形式上正确 的程序的依据。 2.语义 对于一个语言来说不仅要给出词法、语法规则，而且 要定义它的单词符号和语法单位的意义。 离开语

3、义，语言只是一堆符号的集合。 各种语言中有形式上完全相同的语法单位，含义不同。 静态语义：是一系列限定规则，并确定哪些合乎语法 的程序是合适的。 动态语义：也称作运行语义或执行语义，表明程序要 做些什么，要计算什么。 目前大多数编译程序使用基于属性文法的语法指导翻 译方法来分析语义。 对于高级程序设计语言及其编译程序来说，语言 的语法定义很重要。本章主要介绍语法结构的形 式描述问题。编译原理的主要内容也可以归结为 应用形式语言理论，并将它贯穿于词法分析和语 法分析两个阶段。 本章重点讨论正规文法、上下文无关文法及其对 应的有限自动机和下推自动机，以及在构造编译 程序时如何应用。 2.1 文法的

4、直观概念和语言描述 当表述一种语言时，无非是说明这种语言的句当表述一种语言时，无非是说明这种语言的句 子，如果语言只含有有穷多个句子，则只需列出句子的子，如果语言只含有有穷多个句子，则只需列出句子的 有穷集就行了，但对于含有无穷句子的语言来讲，存在有穷集就行了，但对于含有无穷句子的语言来讲，存在 着如何给出它的有穷表示的问题。以自然语言为例，人着如何给出它的有穷表示的问题。以自然语言为例，人 们无法列出全部句子，但是人们可以给出一些规则，用们无法列出全部句子，但是人们可以给出一些规则，用 这些规则来说明这些规则来说明( (或者定义或者定义) )句子的组成结构，比如汉语句子的组成结构，比如汉语

5、句子可以是由主语后随谓语而成，构成谓语的是动词和句子可以是由主语后随谓语而成，构成谓语的是动词和 直接宾语，我们采用直接宾语，我们采用EBNFEBNF来表示这种句子的构成规则：来表示这种句子的构成规则： “我是大学生”。是否是汉语的一个句子? 句子句子=主语主语谓语谓语 主语主语=代词代词名词名词 代词代词=我我你你他他她她 名词名词=王明王明大学生大学生工人工人英语英语 谓语谓语=动词动词直接宾语直接宾语 动词动词=是是学习学习 直接宾语直接宾语=代词代词名词名词 有了一组规则以后，按照如下方式用它们导有了一组规则以后，按照如下方式用它们导 出句子：出句子： 如句子：如句子：“我是大学生我是

6、大学生”的全部动作过程是：的全部动作过程是： 句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 由此可见：由此可见：“我是大学生我是大学生”的构成符的构成符 合上述规则，合上述规则， 而而“我大学生是我大学生是”不符合上述规则，不符合上述规则， 我们说它不是句子。我们说它不是句子。 这些规则成为我们判别句子结构合法这些规则成为我们判别句子结构合法 与否的依据，换句话说，这些规则看成是一种与否的依据，换句话说，这些规则看成是一种 元语言，用它描述汉语。这里仅仅涉及汉语句元语言，用它描述汉语。

7、这里仅仅涉及汉语句 子的结构描述。子的结构描述。其中这种描述元语言称为其中这种描述元语言称为文法文法。 问：“王明学习英语” 是否是汉语的一个句子? 语言描述 语言是由句子组成的集合语言是由句子组成的集合，是由一组符号所，是由一组符号所 构成的集合。构成的集合。 汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体 英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体 程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规律（每个句子构成的规律（语法语法） 研究语言研究语言 每个句子的含义（每个句子的含义（语义语义） 每个句子和使用

8、者的关系（每个句子和使用者的关系（语用语用） 语法语法 - - 表示构成语言句子的各个记号之间的组合表示构成语言句子的各个记号之间的组合 规律规律 语义语义 - - 表示各个记号的特定含义。（各个记号和表示各个记号的特定含义。（各个记号和 记号所表示的对象之间的关系）记号所表示的对象之间的关系） 语用语用 -表示在各个记号所出现的行为中，它们的表示在各个记号所出现的行为中，它们的 来源、使用和影响。来源、使用和影响。 如果不考虑语义和语用，即只从语法这一侧如果不考虑语义和语用，即只从语法这一侧 面来看语言，这种意义下的语言称作面来看语言，这种意义下的语言称作形式语言形式语言。形。形 式语言抽象

9、地定义为一个数学系统。式语言抽象地定义为一个数学系统。 “形式形式”是指这样的事实：语言的所有规则是指这样的事实：语言的所有规则 只以什么符号串能出现的方式来陈述。形式语言是只以什么符号串能出现的方式来陈述。形式语言是 程序设计语言语法分析研究的基础。程序设计语言语法分析研究的基础。 一、符号串的基本概念 1、字母表 定义 字母表是元素的非空有穷集合。 常用表示 汉语字母表包括： 汉字、数字、标点符号等 例如：10,1 1是二进制数的字母 2a,b.z 2是英文小写字母 2、符号 定义 字母表中的元素称为符号。 例如：设有字母表+，-，*，/ 则+、-、*、/为符号 2.2字母表和符号串 3、

10、符号串 定义 由字母表中的符号组成的任何有穷序列。 例： 设字母表a; 则a,aa,aa;都是字母表a上的字符串。 设字母表a,b;则a,b,aa,ab,abb,baa,都是a，b上的 符号串。 =0，1 符号集 符号串有： 0，1，00，01，10，11 =a，b，c 符号集 符号串有：a，b，c，ab，aaca 2.2字母表和符号串 4、空符号串 定义 不含任何符号的符号串，记为 若符号串x ,则有x = x= x 5、符号串的长度 定义 设x是字母表上的符号串，符号串中包含符号 的个数称为符号串x的长度，用|x|表示。 例如：|abc|=3 |=0 2.2字母表和符号串 6、符号串集合

11、定义 字母表上若干符号串组成的集合。 例如： 设有字母表a，b，c，则有符号串集合： A=a，ab，bc ，abc 2.2字母表和符号串 二、符号串的运算 1、符号串的头尾、固有头和固有尾 如果z=xy一个符号串，那么x是z的头（前缀）， y是z的尾（后缀），如果x是非空的， 那么y是固 有尾；同样如果y 是非空的， 那么x是固有头。 例如：z=abc 头： 、a、ab、abc 尾： 、c 、bc 、abc 固有头： 、a、ab 固有尾： 、c 、bc 2.2字母表和符号串 二、符号串的运算 2、符号串的连接 设x，y是字母表上两个符号串，把y的所有符号 相继写在x的符号之后所得到的串称为x与

12、y的连接， 用xy表示。 例如：若x=ab，y=abc， 则xy=ababc 而且|xy|=|x|+|y| 显然：x=x=x 2.2字母表和符号串 二、符号串的运算 3、符号串的方幂 设x是字母表上的符号串，则x的幂运算为： x0= X1=x X2=xx Xn=xn-1x(xxn-1)(n0) 显然n0时, 有xn =xx n-1 x n-1x 2.2字母表和符号串 二、符号串的运算 4、符号串集合的乘积 定义 设A、B为两个符号串集合，其乘积为 AB=xy|xA，yB 例如: 若Aab，bc， B=ac，cb 则AB=abac，abcb，bcac，bccb 2.2字母表和符号串 二、符号串的

13、运算 5、符号串集合的幂 定义 设A为符号串集合，则A的幂运算为： A0= A1=A A2=AA An=An-1A(AAn-1)(n0) 2.2字母表和符号串 二、符号串的运算 6、集合A的闭包与正闭包 定义 集合A的闭包表示为A*（又称为自反闭包或星 闭包），具体定义为 A*= A0A1A2A3 正闭包表示为A+=A1A2A3 还可以证明： AAA*= A*A 2.2字母表和符号串 例：字母表=0,1 则 *=,0,1,00,01,10,11,000,001,01 0 =01 2. n 符号-符号串-句子-语言 一、文法 n描述语言的语法结构的形式规则。 例如：He gave me a bo

14、ok 我们热爱祖国 n文法是在形式上用以描述和规定语言结构的 一种方法。 n用有限的手段来描述无限的句子。 2.3文法和语言形式定义 二、规则 定义 一个规则是一个二元组，通常写作： U:=x 或 U x 其中：U是规则的左部，它是一个符号， x是规则的右部，它是有穷符号串，“:=” 和“”表示为“定义为”或表示为“由 组成”。规则又称为产生式。 2.3文法和语言形式定义 三、上下文无关文法 形式上，一个上下文无关文法G是一个四元组 G=(VN，VT，P，S)， 其中，VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号(识别符），SVN P：产生式集合(有

15、限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。 2.3文法和语言形式定义 三、上下文无关文法 例 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号 GS 2.3文法和语言形式定义 例例: :标识符标识符文法文法G=G=（V VN N，V VT T，P P，S S） V VN N = =标识符，字母，数字标识符，字母，数字 V VT T =a,b,c, =a,b,c,x,y,z,0,1,x,y,z,0,1,9,9 P= P= a,a, , zz 0,0, , 9 9 S=S= 文法

16、的写法文法的写法: :一般不用将一般不用将G G的四元组显式地表示出来的四元组显式地表示出来, , 而只将产生式写出。而只将产生式写出。 例例1 G1 G：SaASaAb Aab Aab AaA AaAb A A 例例2 GS2 GS： SaASaAb Aab Aab AaA AaAb A A 例例3 GSGS： SaASaAb Aab |aA Aab |aAb | | 习惯表示习惯表示 第一条产生式的左部是识别（开始）符号；用尖括第一条产生式的左部是识别（开始）符号；用尖括 号括起来的为非终结符号括起来的为非终结符, ,否则为终结符否则为终结符 或或: :大写字母：非终结符大写字母：非终结符

17、 小写字母：终结符小写字母：终结符 S AB A Ax | y B z 为了定义文法所产生的语言，需引入推 导的概念。 直接推导：就是在推导中每次替换一个规则。 定义：对于文法G，有规则U:=u，x和y是V上 的符号串，若V上存在另外两个符号串v和w 使v=xUy,w=xuy，v直接推导出w,记作 v w，也称w直接归约到v。 2.3文法和语言形式定义 为了定义文法所产生的语言，需引入推 导的概念。 直接推导：就是在推导中每次替换一个规则。 例：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 2.3文法和语言形式定义 2.

18、3文法和语言形式定义 推导： 定义：对于文法G，如果存在一直接推导序列 v=u0 u1 un=w（n0）则称v推导出 w。记作v w 例如：对文法G(E)： E i | E+E | E*E | (E) E (E) (E+E) (i+E) (i+i) + 通常，用 表示： 从1出发，经过一步或若干步，可以推出 n。 n 1 * 1n 用 表示：从1出发， 经过0步或若干步，可以推出n。 * 所以 ： 即 或 2.3文法和语言形式定义 * S ,|)( * * T V SGL 定义：假定G是一个文法，S 是它的开始符号。 若 ，则称是一个句型。 仅含终结符号的句型是一个句子。文法G所产 生的句子的

19、全体是一个语言，将它记为 L(G)。 句型、句子、语言： 2.3文法和语言形式定义 句型、句子、语言： 例：G： S0S1， S01 L(G)=0n1n|n1 例：例：GGE E ： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a E EE+T E+T T+T T+T F+T F+T a+T a+T a+Ta+T* *F F a+Fa+F* *F F a+aa+a* *F F a+aa+a* *a a 句子：用符号句子：用符号a a，+ +，* *，( (和和) )构成的算术表达式构成的算术表达式 例例 文法文法GSGS： （1 1）S SaSBEaSBE （2 2）S SaBEaBE （3 3）EBEBBEBE （4 4）aBaBabab （5 5）bBbBbbbb （6 6）bEbEbebe （7 7）eEeEeeee 判断判断aabbeeaabbee是否是该文法的句子？并写出该文法是否是该文法的句子？并写出该文法 所表示的语言。