[编译原理]编译基础之名词及概念部分

一、前言

　　编译原理这门课介绍的是程序设计语言翻译的原理与技术&＃xff0c;大略可分为词法分析->语法分析->语义分析及中间代码生成->中间代码优化->目标代码生成五个步骤&＃xff0c;刚开始看这编译原理简明教程这本书时&＃xff0c;里面的新概念多的使人晕头转向&＃xff0c;因为缺乏实践性的学习&＃xff0c;只认识了一些新词汇和概念&＃xff0c;但我想这些词汇和概念或许可能就是编译原理的基础吧&＃xff0c;那就勉强先把基础学牢实点&＃xff0c;然后再看进阶点的书籍&＃xff0c;动手完成书本中所介绍的编译工具&＃xff0c;为了使自己印象更加深刻&＃xff0c;写了这篇博客。

二、编译原理中的前端和后端

　　概念上&＃xff0c;有时会把编译程序划分为编译前端和编译后端。前端主要由源语言有关&＃xff0c;但与目标机无关的那些部分组成&＃xff0c;这些部分通常包括词法分析&＃xff0c;语法分析&＃xff0c;语义分析与中间代码生成&＃xff0c;有的代码优化工作也可以包括在前端。
　　后端包括编译程序中与目标机有关的那些部分&＃xff0c;如与目标机有关的代码优化和目标代码生成等。后端不依赖于源语言&＃xff0c;仅依赖于中间语言。

三、文法

　　文法是描述语言的语法结构的形式规则&＃xff0c;即语法规则&＃xff0c;这些规则必须是准确的&＃xff0c;易于理解的&＃xff0c;而且要有很强的描述能力&＃xff0c;足以描述各种不同的结构。由这种规则所形成的程序语言应有利于句子的分析和翻译。
　　这里以一句中文 ” 我是大学生” 来分析该句子的构成规则&＃xff0c;以下先列出一组语法规则:

<句子> &＃xff0d;> <主语><谓语>
<主语> &＃xff0d;> <代词>|<名词>
<代词> &＃xff0d;> 你|我|他
<名词> &＃xff0d;> 小明|大学生|英语|工人
<谓语> &＃xff0d;> <动词><直接宾语>
<动词> &＃xff0d;> &＃61;是|学习
<直接宾语> &＃xff0d;> <代词>|<名词>

把刚才那句话往上对照&＃xff0c;就可以发现这是一句合法的语句&＃xff0c;并且这套规则可以表示无数个句子。

四、符号和符号串

　　上面分析了句子的构成规则&＃xff0c;句子又是由各种符号构成的&＃xff0c;比如单词和标点符号等&＃xff0c;为了给出语言的形式定义&＃xff0c;下面首先讨论符号和符号串的概念。
(1).字母表
　　字母表是元素的非空有穷集合&＃xff0c;例如&＃xff36;&＃xff1d;{a,b,c}等&＃xff0c;&＃xff23;语言的字母表是由字符&＃xff0c;数字&＃xff0c;若干符号组成的。习惯上使用Σ&＃xff0c;&＃xff36;或其它大写字母表示。
　　 　　
(2).符号串
　　由字母表中符号组成的任何有穷序列都叫符号串&＃xff0c;例如aa,bb,cc,ab,ac,abc等&＃xff0c;符号串的顺序不同代表的含义一般也不同。如果某符号串x有m个符号&＃xff0c;则称其长度为m&＃xff0c;记作 |x| &＃61; m&＃xff0c;不包含任何符号的符号串用　ε　表示&＃xff0c;即 |ε|&＃61;0。
　　
(3)符号串的运算
&＃xff13;.&＃xff11;.符号串的集合　　
　　若集合&＃xff21;中的一切元素都是字母表上的符号串&＃xff0c;则称&＃xff21;为该字母表上的符号串集合
&＃xff13;.&＃xff12;.符号串的连接
　　假如有两个符号串分别为x,y&＃xff0c;则xy符号串是把y符号串写在x符号串后面之后得到的符号串&＃xff0c;由ε的定义显然有εx&＃61;xε&＃61;x
&＃xff13;.&＃xff13;.符号串的方幂
　　设x是符号串&＃xff0c;把x自身连接n次得到的符号串z为z&＃61;xxxxx称为符号串x的方幂&＃xff0c;写作z&＃61;x^n
　　对于符号串集合的方幂也一样
　　{x,y,z}^2 &＃61; {x,y,z}{x,y,z}
　　　　　　&＃61;{xx,xy,xz,yx,yy,yz,zx,zy,zz}　　　
　　　　　　&＃xff08;可理解为符号串集合的n次方幂　等于　符号串集合中所有元素组合长度为n的集合&＃xff09;
　　　　　　
(4)特殊集合
　　在规定字母表Σ后&＃xff0c;该表上的符号串集合有两种比较特殊的形式&＃xff0c;Σ^*称为Σ的闭包&＃xff0c;Σ^&＃43;称为Σ的正闭包
　　
　　Σ^*表示Σ上的所有有穷长的串的集合。
　　例如　Σ&＃xff1d;{0,1}
　　则　　Σ^*&＃61;{ε,0,1,00,01,10,11,000,001,010,……..}&＃xff0c;也可以表示为字母表的方幂形式如下:
　　　　　Σ^*&＃61; Σ^0 ∪ Σ^1 ∪ Σ^2 … ∪ Σ^n
　　
　　Σ^&＃43;的概念是由于发现很多时候需要描述一个语言连接1次或以上得到的集合
　　所以Σ^&＃43; &＃61; Σ^1 ∪ Σ^2 … ∪ Σ^n

由以上可得出 Σ^&＃43; &＃61; Σ^*r &＃61; rΣ^* (r为非空符号)
　　　　　　 Σ^* &＃61; Σ^&＃43;|ε
　　

五、文法和语言的形式定义

　　规则&＃xff0c;也称重写规则&＃xff0c;产生式或生成式&＃xff0c;形如a -> b 或 a::&＃61;b的(a,b)有序对&＃xff0c;其中a 称为规则的左部&＃xff0c;b称为规则的右部&＃xff0c;中间的符号　->　或 ::&＃61; 读作”定义为”&＃xff0c;例如A->a可以读作”&＃xff21;定义a&＃xff0c;也可以说成是关于&＃xff21;的规则(产生式)
　　
定义一.文法&＃xff27;定义为四元组(Vn,Vt,P,S)
　　其中&＃xff36;n为非终结符(或语法实体,或变量)集&＃xff0c;Vt为终结符集;&＃xff30;为规则(α&＃xff0d;>β)的集合&＃xff0c;α∈(Vn ∪ Vt)^*且至少包含一个非终结符&＃xff0c;β∈(Vn ∪ Vt)^*;Vn&＃xff0c;Vt,和P是非空有穷集。S称为识别符或开始符&＃xff0c;它是一个非终结符&＃xff0c;至少要在一条规则中作为左部出现&＃xff0c;
　　Vt和Vn不含共同元素&＃xff0c;即Vt∩Vn &＃61; Ø
　　通常的V表示Vt∪Vn表示文法G的字母表或字汇表。
　　

定义二.如果a->b是文法G&＃61;(Vn,Vt,P,S)中的一条规则&＃xff0c;c和d是文法G字母表中的任意符号&＃xff0c;若有符号串e,f满足
　　　　　　　　　　　　　　　　e&＃61;cad　　f&＃61;cbd
则 e 应用规则 a->b 直接产生 f &＃xff0c;或说 f 是 e 的直接推导&＃xff0c;或说 f 直接归约到 e&＃xff0c;记作 e&＃61;>f

定义三.如果存在直接推导序列
　　　　　　　　　　e&＃61;f0 &＃61;> f1 &＃61;> f2 &＃61;> f3 &＃61;> f4 &＃61;> ……. &＃61;>fn &＃61; f (n>0)
则称 e 推导出 f &＃xff0c;推导长度为 n&＃xff0c;或称 f 归约到 e&＃xff0c;记作 e &＃61;&＃43;> f

定义四.若有e&＃61;&＃43;>f&＃xff0c;或e&＃61;f&＃xff0c;则记作e&＃61;*>f.

定义五.设G[S]是一文法&＃xff0c;如果符号串 x 是由识别符号推导出来的&＃xff0c;即有&＃xff33;&＃61;*>x&＃xff0c;则称 x 是文法&＃xff27;[S]的句型。若 x 仅由终结符号组成&＃xff0c;即S&＃61;*>x&＃xff0c;x∈&＃xff36;t*&＃xff0c;则称x为&＃xff27;[S]的句子。即符号串中若还存在非终结符则是句型否则是句子。

定义六.文法&＃xff27;所产生的语言的定义为集合{x|S&＃61;*>x&＃xff0c;其中&＃xff33;为文法识别符号&＃xff0c;且 x ∈&＃xff36;t*}。可用L(G)表示该集合。
从中可以得出两点&＃xff0c;第一&＃xff0c;符号串 x 可从识别符号推出&＃xff0c;也即 x 是句型。
　　　　　　　　　第二&＃xff0c; x 仅由终结符号组成&＃xff0c;即 x 是文法&＃xff27;的句子。
　也就是说&＃xff0c;文法描述的语言是该文法一切句子的集合。
　

六、文法的类型

　　乔姆斯基把文法分成&＃xff14;种类型&＃xff0c;即&＃xff10;型(短语文法)&＃xff0c;&＃xff11;型(上下文相关文法)&＃xff0c;&＃xff12;型(上下文无关文法)&＃xff0c;&＃xff13;型(正规文法)
　　
0-型文法&＃xff08;无限制文法或短语结构文法&＃xff09;包括所有的文法。即它产生的每一个 α->β都是这样的&＃xff0c;α ∈(Vn∪Vt)^&＃43;且至少含有一个非终结符&＃xff0c;而 β ∈(Vn∪Vt)^*。&＃xff10;型文法的能力相当于图灵机&＃xff0c;或者说任何&＃xff10;型语言都是递归可枚举&＃xff1b;反之&＃xff0c;递归可枚举语言必须是&＃xff10;型语言。

1-型文法&＃xff08;上下文相关文法&＃xff09;生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号&＃xff0c;而 α, β 和 γ 是包含非终结符号与终结符号的字串&＃xff1b;α, β 可以是空串&＃xff0c; γ 必须不能是空串&＃xff1b;这种文法也可以包含规则 S->ε &＃xff0c;但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。

2-型文法&＃xff08;上下文无关文法&＃xff09;生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号&＃xff0c;γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。

3-型文法&＃xff08;正规文法&＃xff09;生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号&＃xff0c;产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号&＃xff1b;如果所有产生式的右侧都不含初始符号 S &＃xff0c;规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受&＃xff0c;也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。