编译

先给出编译的简要概念:专指由高级语言转换为低级语言。

编译阶段主要分为三个阶段:编译——汇编——运行

  • 在编译时:编译器将源程序通过编译程序转换成汇编语言
  • 在汇编时:编译器将汇编语言通过汇编程序转换成目标代码
  • 在运行时:初始数据会通过目标代码运行子程序然后计算结果

在编译原理这门课中,我们主要研究的就是编译程序的过程,编译程序的工作一般有如下步骤:

  • 词法分析
  • 语法分析
  • 语义分析和中间代码生成
  • 优化
  • 目标代码生成

具体的每个内容,我以后会写在博客中,下面来聊一聊语法这个东西。

语法

对于高级语言来讲,其实程序语言就是一个记号系统,其主要分为语法和语义,而语法是用来起约束作用的。

任何语言程序都可以看成是一定字符集上的字符串,而语法使得这串字符形成一个形式上正确的程序,这句话其实很好理解,比如在英语中,我们通过语法连词成句,使其形成一个形式上正确的句子。

所以可以看出,语法其实是由词法规则和语法规则组成的,比如0.5 * x1 + c,其中0.5, x1, c, *,+是语言的单词符号,而0.5 * x1 + c是语言的语法单位。

语法组成:

  1. 单词符号:也就是语言中具有独立意义的最基本结构
    1. 词法规则:词法规则规定了字母表中哪些字符串是单词符号; 单词符号一般包括常数、标识符、基本字、算符、界限符等。
  2. 语法单位:也就是一些语法
    1. 语法规则:语法规则规定了如何从单词符号来形成语法单位;语法规则一般由表达式、子句、语句、函数、过程、程序构成

语言的词法规则和语法规则定义了程序的形式结构,是判断输入字符串是否构成一个形式上正确的程序的依据。

了解一下字母表和符号串

还是先看看一堆概念:

  • 字母表:是符号的非空有穷集合,用\(\Sigma\)、\(V\)表示
  • 符号:语言中最基本的不可再分的单位
  • 符号串:字母表中符号组成的又穷序列,空串比较特殊,表示不含有任何富豪的串称为空串,记作\(\varepsilon\)
  • 句子:字母表上符合某种规则构成的串
  • 语言:字母表上句子的集合
  • Note:一般用\(a\), \(b\), \(c\)来表示符号,用\(\alpha\),\(\beta\),\(\gamma\)表示符号串,用\(A\), \(B\), \(C\)表示其集合

在符号串集合上的一些运算:

  1. 连接运算,也叫乘积运算,其定义如下:若串集\(A=\left\{ \alpha _1,\alpha _2,\cdots \right\}\),串集\(B=\left\{ \beta _1,\beta _2,\cdots \right\}\),则称乘积\(AB=\left\{ \alpha \beta | \alpha \in A\,\,and\,\,\beta \in B \right\}\)
    1. 串集自身的乘积乘坐串集的方幂
    2. \(A^0=\left\{ \varepsilon \right\}\)
    3. 字母表\(A\)的\(n\)次方幂是字母表\(A\)上的所有长度为\(n\)的串集
  2. 闭包运算,也叫星闭包:\(A^*\):\(A^*=A^0\cup A^1\cup \cdots\),也就是由\(A\)上符号组成的所有串的集合(包括空串)
  3. 正闭包运算:\(A^+=A^1\cup A^2\cup \cdots =A^*-\left\{ \varepsilon \right\}\),由\(A\)上符号组成的所有串的集合,当然,不包括空串
  4. 语言:是字母表上符合某种规则的语句组成的,而字母表上的语言,就是字母表上正闭包的子集

文法

文法就是描述语言的语法结构的形式规则,这样定义非常抽象,我们来看个栗子:

加入我们由这样的一个例子:Young men like pop music.

英语语法规则大家应该都懂:

而文法其实就是上面的这些东西,也就是一些语法结构的一些规则,然后将其形式化了。

文法的一些概念

一个文法一般是由如下东西组成的:\(G=\left( V_N, V_T, P, S \right)\),也就是一个四元组,其中

  • \(G\),就是\(grammer\),表示文法
  • \(V_N\):\(nonterminal - variable\),表示非终结符集合,一般出现在规则的左部,用<>括起来,表示一定语法概念的次
  • \(V_T\):\(terminal - variable\),表示终结符集合,语言中不可再分割的字符串
  • \(P\):\(production\),表示产生式集合,用来定义符号串之间关系的一组规则
  • \(S\):\(start\),起始符号集合,表示所定义的语法范畴的非终结符

还有一些什么推导和规约的概念非常简单,这里就不再详述了,有个地方要解释一下就是最左推导和最右推导,最左规约和最右规约

  • 最左(右)推导:每次使用一个规则,以其右部取代符号串最左(右)的非终结符
  • 最左(右)规约:是最右(左)推导的逆过程
  • Note:最左推导和最右推导称为规范推导,最左规约称为规范规约

句子, 句型和语言:

  • 句型:从文法的开始符号S开始,每步推导所得到的字符串\(\alpha\),记作:\(S\overset{*}{\rightarrow}\alpha\),其中\(\alpha \in \left( V_N\cup V_T \right) ^*\),通俗的讲就是在推导过程中出现的式子都叫句型
  • 句子:仅含终结符的句型
  • 语言:语言是由\(S\)开始,通过1步或者1步以上的推导所得到的句子的集合,记作:\(L\left( G \right) =\left\{ \alpha |S\overset{+}{\rightarrow}\alpha , \text\{且\}\alpha \in V_T* \right\}\)

文法的分类

Chomsky对文法施加的限制,可分为四类:0型文法,1型文法,2型文法,3型文法,下面我们分别来对每一类文法进行介绍:

  • 0型文法(短语文法或无限制文法):
    • \(P\)中产生式\(\alpha \rightarrow \beta\),其中\(\alpha\)中至少有一个符号(\(\alpha \in V^+\)),并且至少含有一个非终结符,而不对\(\beta\)作任何要求:\(\beta \in V^*\),总的来说就是对左边要求有一个非终结符
    • 识别0型语言的自动机称为图灵机
    • 0型语言是对产生式限制最少的文法
    • 任何0型语言都是递归可枚举的
    • 对0型文法产生的形式作某些限制,可得到其他类型的文法的定义
  • 1型文法(上下文有关文法或长度增加文法)
    • \(P\)中产生式\(\alpha \rightarrow \beta\),除可能有开始符号产生空串(\(S \rightarrow \varepsilon\))外均有右边长度大于左边长度(\(|\beta |\geqslant |\alpha |\)),若有(\(S \rightarrow \varepsilon\)),则规定S不得出现在产生式的右部
    • 或者,\(P\)中产生式\(\alpha \rightarrow \beta\),出可能有开始符号产生空串外,均有\(\alpha A\beta \rightarrow \alpha \gamma \beta\),其中\(\alpha ,\beta \in V^*, A\in V_N,\gamma \in V^+\),也就是说\(A\)这个非终结符,在前面是\(\alpha\),后面是\(\beta\)的条件下,可以变成\(\gamma\),而\(\gamma\)不能为空,所以其长度必然是大于等于1的,也就是大于等于A,这就和上面的定义相呼应了。
    • 识别1型文法的自动机称为线性界限自动机(LBA)
    • 1型文法意味着,对非终结符进行替换时务必考虑上下文,并且,一般不允许替换成\(varepsilon\),除非是开始符号产生\(varepsilon\)
  • 2型文法(上下文无关文法)
    • \(P\)中产生式具有形式:\(A \rightarrow B\),其中\(A \in V_N, \beta \in V^*\)
    • 也就是说,2型文法对产生式的要求是:产生式左部一定是非终结符,产生式右部可以是终结符、非终结符和空串,非终结符的替换,不必考虑上下文。
    • 识别2型语言的自动机称为下推自动机
  • 3型文法(正则文法、右线性文法或左线性文法)
    • \(P\)中产生式具有形式\(A \rightarrow \alpha B, A \rightarrow \alpha\)(右线性),或者\(A \rightarrow B\alpha, A \rightarrow \alpha\)(左线性),其中\(A, B \in V_N, \alpha \in V_T^*\)
    • 也就是说,一个非终结符要么产生一个终结符,要么产生一个终结符后面跟一个非终结符,这个就叫做右线性文法,或者要么产生一个终结符,要么产生一个非终结符后面跟一个终结符,这个就叫做左线性文法
    • 3型文法中的产生式要么均是右线性产生式,要么均是左线性产生式,不能既有左线性产生式,又有右线性产生式,若所有产生式都为左线性产生式,则称其为左线性文法,否则为右线性文法
    • 识别3型语言的自动机称为有限状态自动机

以上就是对各类文法的一些简单介绍,可以看出,这些文法是逐级限制,逐级包含的,下面的图很清楚的可以表达这个意思:

也就是说,如果一个文法是3型文法,那么你也可以说他满足0型文法、1型文法、2型文法,都是可以的。

我在这里只是简单的介绍了各类文法,这几类文法都比较抽象,刚开始看不懂很正常的,最好结合着书上的例子来研究。

文法与语言

所谓的语言,比如i型语言,起始就是由i型文法生成的语言,称为i型语言,记为:\(L\left( G \right) :L\left( G \right) =\left\{ w|w\in V_{T}^{*}, \text{且}S\overset{+}{\rightarrow}w \right\}\)

有一类题目:根据文法推语言:

eg.1 设文法\(G_1=\left( \left\{ S \right\} ,\left\{ a, b \right\} , P, S \right)\),其中\(P\)为:(0)S->aS (1)S->a (2)S->b

简单分析一下可以知道,S最终肯定会以a或者b结尾,所以只需要考虑前面:

所以,前面应该都是a,语言:\(L\left( G \right) =\left\{ a^i\left( a|b \right) | i\ge 0 \right\}\)

eg2.设文法\(G_2=\left( \left\{ S \right\} ,\left\{ a, b \right\} , P, S \right)\),其中\(P\)为:(0) S->aSb (1)S->ab

画图:

起始就是ab、aabb、aaabbb,所以文法:\(L\left( G_2 \right) =\left\{ a^nb^n| n\ge 1 \right\}\)

还有一类题目:由语言构造文法,这里还是随便举几个例子,这种题目没有什么通发,一般都是直接观察的:

例:设\(L_1=\left\{ a^{2n}b^n|n\ge 1,\text{且}a,b\in V_T \right\}\),试构造生成\(L_1\)的上下文无关文法\(G_1\)

我们先写几项出来:n = 1, L1 = aab; n = 2, L2 = aaaabb; n = 3, L3 = aaaaaabbb

观察一下,发现,每次都是在前一个的基础上增加两个a,1个b,初始状态:S->aab,后续:S->aaSb(在S的基础上,前面添加两个a,后面添加一个b,并递归)

所以最后的结果就是:S -> aaSb, S -> aab。

最后一个内容应该是语法树和二义性,这块比较简单,有空再写hhh