编译原理第三章

第三章 文法和语言

3.1 3.2 3.3 3.4 3.5 3.6 3.7

文法的直观概念 符号和符号串 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 句型的分析 有关文法实用中的一些说明

第三章 文法和语言

程序设计语言与自然语言一样，完整的定义包括语法和 语义两个方面。 所谓语法是指一组规则，用它可以形成和产生一个合适 的程序。 语法只是定义什么样的符号序列是合法的，与符号的含 义无关。 语义有两种类型：静态语义是一系列限定规则，确定哪 些合乎语法的程序是合适的；动态语义也称运行语义或 执行语义，表明程序要做些什么？要计算什么。 文法是阐明语法的一种工具，描述语法的规则。

3.1 文法的直观概念

语法是用来描述语言的组成规则。语句是组成语 言的基本元素。而组成语言的语句往往是无穷列 举的，这时就要给出一些规则来描述句子的组成 结构。 构成语句的组织规则就是语法的表现。而这种规 则或者说这种语言的描述就是文法。 使用文法工具，不仅为了严格地定义句子的结构， 也是为了用适当条数的规则把语言的全部句子描 述出来，是以有穷的集合刻画无穷的集合的工具。

以自然语言为例，人们无法列出全部句子，但 是人们可以给出一些规则，用这些规则来说明 (或者定义)句子的组成结构，比如汉语句子可 以是由主语后随谓语而成，构成谓语的是动词 和直接宾语。“我是大学生”。是汉语的一个 句子 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷=我|你|他

〈名词〉∷=王明|大学生|工人|英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是|学习

〈直接宾语〉∷=〈代词〉|〈名词〉

有了一组规则以后，按照如下方式用它们导出句子：开始 去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符 号串代替，这个动作表示成： 〈句子〉 〈主语〉〈谓语〉, 然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或 〈谓语〉,再用相应规则的∷=右端代替之。 句子：“我是大学生”的全部动作过程是： 〈句子〉 〈主语〉〈谓语〉 〈代词〉〈谓语〉 我〈谓语〉 我〈动词〉〈直接宾语〉 我是〈直接宾 语〉 我是〈名词〉 我是大学生“我是大学生”的构成符合上述规则，而“我大学生是” 不符合上述规则，我们说它不是句子。这些规则成为我们 判别句子结构合法与否的依据，换句话说，这些规则看成 是一种元语言，用它描述汉语。这里仅仅涉及汉

语句子的 结构描述。其中一种描述元语言称为文法。

3.2 符号和符号串

程序设计语言的表达方式就是一个一个的程序。而程序 又是由一个个指令语句组成。语句又是由数字和字母这 样一些基本符号所组成。 程序设计语言可以看成是在基本符号集上定义的，按照 一定规则构成的一切基本符号串组成的集合。 字母表：是元素的非空有穷集合，这里所指的元素就是 符号。不同的语言可以有不同的字母表。 符号串：由字母表中的符号组成的任何有穷序列称为符 号串。 符号串涉及的有关概念有：符号的顺序、符号串的长度、 空符号串、符号串的头尾、符号串的省略写法、符号串 的连接、符号串的幂、符号串的集合。

符号串集合：若集合A中所有元素都是某字母表 上的符 号串，则称A为字母表 上的符号串集合。 两个符号串集合A和B的乘积定义为AB = xy|x A且y B 。 若集合A= ab,cde ,B= 0,1 ,则 AB= ab1,ab0,cde0,cde1 。 使用 * 表示 上的一切符号串(包括ε )组成的集合。 Σ *称为Σ 的闭包。 上的除ε 外的所有符号串组成的集合记为 + 。Σ +称为 Σ 的正闭包。 例：Σ ={a,b} Σ *={ε ,a,b,aa,ab,ba,bb,aaa, } Σ +={a,b,aa,ab,ba,bb,aaa,aab, }

指定字母表Σ, Σ*表示Σ上的所有有穷长 的串的集合。 Σ={0,1} Σ* ={ε,0,1,00,01,10, 11,000,001,010,…} Σ*= Σ0U Σ1U Σ2 U … U Σ n U … Σ*称为集合Σ的闭包: 正闭包:Σ+= Σ1U Σ2 U … U Σ n U … Σ*= Σ0U Σ+ Σ+ = Σ Σ*= Σ* Σ

目标是用有穷的规则描述无穷的语言

3.3文法和语言的形式定义

如何来描述一种语言？ 如果语言是有穷的(只含有有穷多个句子),可以将 句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的有 穷表示有两个途经： 生成方式

(文法):语言中的每个句子可以用严格定义的规 则来构造。 识别方式(自动机):用一个过程，当输入的一任意串属于语 言时，该过程经有限次计算后就会停止并回答“是”,若不属 于，要麽能停止并回答“不是”,(要麽永远继续下去。)

3.3文法和语言的形式定义 规则(也称重写规则、产生式或生成

式):是形如α →β 或α ::=β 的 (α ,β )有序对，其中α 为字母表的 正闭包中的符号， β 为字母表的闭 包中的符号，α 称为规则的左部， β 称为规则的右部。 规则是文法的核心。

3.3 文法和语言的形式定义

所谓的形式定义就是用符号串来描述文法规则 的表述。 形式定义1:文法G定义为四元组(VN,VT,P, S)。其中， VN为非终结符号(或语法

实体，或变量)集； VT为终结符号集； P为产生式(也称规则)的集合； (VN,VT和P是非空有穷集。) S称做识别符号或开始符号，它是一个非终结符，至

少要在一条规则中作为左部出现。 VN和VT不含公共的元素，即VN VT= 。通常用V表 示VN VT,V称为文法G的字母表或字汇表。

例文法G =(VN,VT,P,S),其中 VN ={S} VT ={0,1} P ={S 0S1, S 01} 可见该文法中非终结符中只含一个符号S, 终结符中含两个符号0和1,由两个产生式，开 始符号是S.

例 文法G=(VN,VT,P,S) VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…, <字母>→z <数字>→0,…, <数字>→9 } S=<标识符>

很多时候不用将文法的四元组显式地表 示出来，而只将产生式写出。 一般约定：第一条产生式的左部是识别 符号；用尖括号括起来的是非终结符 号；不用尖括号括起来的是终结符号。 或者用大写字母表示非终结符号，小 写字母表示终结符号。 如：G: S 0S1 S 01

文法的写法 1 G:S→aAb A→ab A→aAb A→ε 2 G[S]:S→aAb A→ab A→aAb 3 G[S]:S→aAb A→ab |aAb |ε

A→ε

3.3 文法和语言的形式定义

为定义文法所产生的语言，引入推导概念。 形式定义2:如 是文法G=(VN,VT,P,S)的规则 (或说是P中的一产生式), 和 是V*中的任意符号，若有 符号串v,w满足： v= ,w= 。则说v(应用 规则 )直接产生w,或说w是v的直接推导，或者说 w直接规约到v,记作： v w。 形式定义3:如果存在直接推导的序列： v =w0 w1 w2… wn=w(w>0) 则称v推导出(产生) w(推导长 + 度为 n),或称w规约到v。记作v w + * 形式定义4:若有v w,或v w,则记作： v w

推导的举例例：G: S→0S1, S→01 S 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1<程序> <分程序>. <分程序>. <变量说明部分>

<语句>.

VAR<标识符>;BEGIN READ(<标识符>)END. VAR A;BEGIN READ(<标识符> ) END.

例：G: S→0S1, S→010S1 00S11 00S11 000S111 000S111 00001111

S 0S1 00S11 000S111 00001111 S =>+ 00001111 S =>* S 00S11 =>* 00S11

一定是从文法开始符号出发进行推导

3.3 文法和语言的形式定义

形式定义5:设G[S]是一文法，如果符号串 x是 * 从识别符号推导出来的，即有S x,则称x是文 法G[S]的句型。 * 若x仅由终结符号组成，即S x,x V*T,则称x 为G[S]的句子。

例：G: S→0S1, S→01 S 0S1 00S11 000S111 00001111 G的句型S,0S1 ,00S11 ,000S111,00001111 G的句子00001111, 01

本文来源：https://www.bwwdw.com/article/eiii.html