编译原理学习笔记：文法与语言

编译原理

前言

本学期开了编译原理课，嗯写作本文的原因就这么简单...

基本概念

  • 字母表：非空有限集，一般用∑∑表示，如∑＝{a,b,c}∑＝\{a,b,c\}
  • 符号： ∑∑中的元素称为符号。
  • 符号串：符号的有穷序列称符号串，也可称为字，用ε表示空字符串。
  • 长度：符号串中包括的符号的个数，如∣ab∣＝2,∣ε∣＝0|ab|＝2,|ε|＝0
  • 连接：设x和y是字符串，则称x⋅yx·y是其连接，符号‘·’一般可省略。 对于任意字符串ββ，有βε＝εβ＝ββε＝εβ＝β
  • 乘积：设A和B是符号串集，则用AB表示它们的乘积：
AB＝{xy∣x∈A,y∈B}AB＝\{xy|x∈A,y∈B \}

显然{ε}A=A{ε}=A\{ε\}A=A\{ε\}=A

  • 空集：不含任何元素的集合φ，对任何字符串集A有：
φA＝Aφ＝AφA＝Aφ＝A
  • 方幂：设A是字符串集，则A的方幂定义为：
A0={ε};A1＝A;An＝An−1AA^0 =\{ε\}; A^1 ＝A; A^n ＝A^{n-1} A

特别地，若x是∑∑中的字符，则x的n次自身连接即xnx^n

  • 闭包/正闭包/星闭包：设A是符号集， 用A+A^+表示A的正闭包:
A+=A1∪A2∪⋯∪An∪…A^+=A^1∪A^2∪\dots∪A^n∪\dots

用A∗A^*表示A的星闭包:

A∗＝A0∪A1∪A2∪⋯∪An∪⋯={ε}∪A+A^*＝A^0∪A^1∪A^2∪\dots∪A^n∪\dots=\{ε\}∪A^+

两者统称为A的闭包。

举个例子1： 设A={a,b}A = \{a,b\} 则：

A0＝{ε}A1={a,b}A2=AA={aa,ab,ba,bb}A3=AAA={aaa,aab,aba,abb,baa,bab,bba,bbb}…\begin{aligned} &A^0 ＝ \{ε\}\cr &A^1 = \{a,b\}\cr &A^2 = AA = \{aa,ab,ba,bb\}\cr &A^3 = AAA = \{aaa,aab,aba,abb,baa,bab,bba,bbb\}\cr &\dots\cr \end{aligned}

符号和符号串

任何程序设计语言都是某一基本符号集上的字符序列，其中的字符用来构造单词，单词构造更大的语法单位，表达式、语句等复合对象。其中，单词是最小的语义单位,它不包含任何子结构，因此每个单词是简单的字符序列。

语言

程序设计语言是一个记号系统，同自然语言一样，完整的定义应包括语法和语义两个方面。

语言的语法是指一组规则，用它可以形成和产生一个合适的程序。语法规定了特定符号序列的合法性，而与符号的含义没有关系。任何程序设计语言都是某一基本符号集上的字符序列。

对于语义的分析与处理到目前为止仍然没有公认的形式系统用于自动构造正确的编译程序。

形式语言

形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。

每个形式语言都是某个字母表上按某种规则构成的所有符号的集合，反之，任何一个字母表上符号串的集合均可定义为一个形式语言，不涉及考虑语义问题。

语言间的运算

因为形式语言在本质上是由数学定义的的集合，所以语言间的运算就是Σ∗Σ^*幂集上的运算。与普通的集合数学运算无异。

语言的表示方法

从形式语言的角度看，一个语言也就是字符串集。如果字符串集是有穷的，可以用枚举的办法表示出来。 例如，设有字母表 A={a,b,c}A=\{a,b,c\}，则

L1={a,b,c}L2={a,aa,ab,ac}L3={c,cc}\begin{aligned} &L_1 = \{a,b,c\}\cr &L_2 = \{a,aa,ab,ac\}\cr &L_3 = \{c,cc\} \end{aligned}

均表示字母表A上的一个形式语言。

当集合无穷时，我们可以使用无限猴子定理枚举的办法就不行了，需要寻找合适的有穷表示方法——文法。

除形式文法外，语言也可使用正则表达式或某些自动机表示，在本章暂不讨论。

文法

在形式语言理论中，文法（为了避免歧义，常称作“形式文法”）是形式语言中字符串的一套产生式规则。这些规则描述了如何用语言的字母表生成符合语法的有效的字符串。文法不描述字符串的含义，也不描述在任何上下文中可以用它们做什么——只描述它们的形式。 形式文法是从一个“开始符号”出发的一套重写字符串的规则。因此，文法通常被认为是语言生成器。2

ps: 形式语言理论是应用数学的一个分支，是研究形式文法和语言的学科。

规则

我们以汉语句子的文法为例：

句子 → 主语·谓语

主语 → 代词∣名词

代词 → 我∣你∣他

名词 → 司机∣农民∣学生∣汽车∣锄头

谓语 → 动词·直接宾语

动词 → 学习∣拿起∣开

直接宾语 → 代词∣名词

其上的每一条被称为产生式或语法规则，符号“→”也可以写成“∷=”，表示“被定义为”。

符号“·”和“∣”是集合运算符号，“·”表示“连接”，该符号往往被省略，“∣”表示“或”，该符号两边的符号串称候选串。

由上面的规则可以产生或推导出句子，引进符号“=>”表示推导，比如句子“农民拿起锄头”的推导过程为：句子=>主语·谓语=>名词·谓语=>农民·谓语=>农民·动词·直接宾语=>农民·拿起·直接宾语=>农民·拿起·名词=>农民拿起锄头

形式定义

接下来我们以数学为工具，利用符号和公式，精确地定义文法和语言。

文法的形式定义

文法是规则的非空有穷集合。其形式定义为四元组G[S]=(VN,VT,P,S)G[S]=(V_N,V_T,P,S)

  • VNV_N是规则中非终结符号的集合。
  • VTV_T是规则中终结符号的集合，显然文法在这里结束。
  • P是文法规则的合集。
  • S是一个非终结符号，显然文法从这里开始。

语言的形式定义

当一个文法已知时，我们可以确定出该文法所定义的语言，但在此之前我们需要先弄明白什么是句子，这里我们需要引入推导的概念。

推导

如果存在一个直接推导序列

a0⇒a1⇒a2⇒⋯⇒ana_0 \Rightarrow a_1 \Rightarrow a_2 \Rightarrow \dots \Rightarrow a_n

则称这个序列是a0a_0到ana_n的长度为n的推导，记为a0⇒+ana_0\stackrel{+}{\Rightarrow}a_n。

表示从a0a_0出发，经过1到n步可以推导出ana_n。

广义推导

广义推导的符号为⇒∗\stackrel{*}{\Rightarrow}

a0⇒∗ana_0 \stackrel{*}{\Rightarrow} a_n表示从a0a_0出发，经过0到n步可以推导出ana_n。

句型与句子

对于文法 G[S]G[S]，如果

S⇒∗xS \stackrel{*}{\Rightarrow} x

称符号串x为文法 G[S]G[S] 的句型。

S⇒∗x,x∈VT∗S \stackrel{*}{\Rightarrow}x, x∈V_T^*

则称符号串x是文法G[S]G[S]的句子。

有了以上概念后，我们可以给出语言的形式定义：

文法 G[S]G[S] 产生的所有句子的集合称为文法G所定义的语言，记为L(G[S])L(G[S])

L(G[S])={x∣S⇒+x,x∈VT∗}L(G[S])=\{x|S\stackrel{+}{\Rightarrow}x,x∈V_T^*\}

Reference

Footnotes

  1. 编译原理 刘铭、徐兰芳等｜电子工业出版社 ↩

  2. 维基百科 形式文法 ↩