avatar

编译原理

概论

编译和解释

编译器就是要生成一个程序后才能执行。

解释器将代码一行行执行。

编译过程

词法分析 -> 语法分析 -> (语义分析、中间代码生成) -> 循环优化 -> 生成目标代码

编译的T型图

左臂上是初始语言,右臂上是目标语言,下面是编译器语言

自增和移植产生代码

自增就是通过自己的语言(比如汇编)先编译一小部分目标语言,假设目标为C语言,则可以分为small C middle C large C三个部分,编译出small C,然后结合small C编译middle C这样子。

移植就是更改语言类型。

基本概念

程序语言的定义

语法是指一组规则,可以分为词法规则和语法规则

词法规则

规定了单词符号(变量名运算符那些)的形成规则,描述工具为有限自动机

语法规则

即如何从单词符号形成更大的结构(语法单位),描述工具为上下文无关文法

程序语言的语法描述

基本概念

  • 字母表

    符号的非空有限集

  • 符号串

    即符号的有穷序列,空符号串用$\epsilon$表示

  • 符号串集合

    定义很直观了,就是符号串构成的集合

  • 符号串的运算

    • 相等

    • 长度

    • 就是两个连起来,且连起来的积也是$\Sigma$上的符号串

  • 符号串集合的运算

    • 乘积

      按顺序枚举连接即可得到,如A={s,t},B={u,v} AB={su,sv,tu,tv}

    • 幂运算

      就按乘法来就可以

    • 闭包

      $A^+=A^1 \cup A^2 \cup … \cup A^n$为正闭包

      $A^* = A^0 \cup A^+$为A的闭包

约定

  • 非终结符

    A,B,C

  • 终结符

    a,b,c

  • 终结符/非终结符

    X,Y,Z

  • 终结符号串

    x,y,z

  • 终结符/非终结符构成的符号串

    $\alpha,\beta$

  • 在产生式A->$\alpha$中

    A是产生式的左边

    $\alpha$是产生式的右边

文法

一组规则用”::=”表示定义为,比如A::=$\alpha$,A为非终结符,称为产生式的左边部分,$\alpha$是由终结符或非终结符组成的一串符号,这种规则称为巴科斯范式(BNF)

文法定义为一个四元组($V_N,V_T,P,S$)

  • $V_N$为非终结符号集
  • $V_T$为终结符号集
  • P为产生式(规则)集合
  • S称作开始符号,至少要在一条规则中作为左部出现

例如文法G=({S}, {0,1}, {S->0S1, S->01}, S)或者简写为G[S]: S->0S1, S->01

句子

文法推出的只有终结符组成的符号串

语言

文法推出的句子的集合,用L(G)表示

等价

即判断L(G1) == L(G2)

二义性

最左推导

在推导的任何一步α=>β,其中α、β是句型, 都是对α中的最左(右)非终结符进行替换

若一个文法存在某个句子对应两棵不同的语法树(或一个文法存在某个句子有两个不同的最左(右)推导),则称这个文法是二义的

词法分析

术语

词法单元(token): 由词法单元名和可选的属性值组成

词素(lexeme):词法单元的实例

模式(pattern):词素可能实例组成的集合

词法分析器

例子

对于while(i == j) i++这个语句,词法分析是逐个识别输出的。

  1. <$WHILE, _>

  2. <$LPAR, _>

  3. <$ID, pointer to i>

  4. <$EQUAL, _>

  5. <$ID, pointer to j>

    ….

其中第一个元素为单词符号的助忆符,第二个为可选的属性值,例如第三行就是指向i的指针。

主要功能

  • 读取源程序生成单词符号
  • 过滤注释和空白
  • 关联编译器生成的错误与源程序的位置。

但是得注意,它只能处理不符合合法标识符拼写的错误,其他的错误只能交给其他阶段完成,但是可以完成错误链接的步骤。

设计结构

由预处理和扫描器两部分组成。预处理将源程序文本进行扫描,减去一些/\t/符号,并放置到扫描缓冲区中,等候扫描器来处理。

对于扫描缓冲区,如果只有一个顺序缓冲区,预处理程序和扫描器程序只能交替进行,即写完再读,但是通过双缓冲区的技术,将两个缓冲区的头尾连接,能够边写边读,可以大大提升速度。

状态转换图

为一个有限方向图

  • 结点代表状态
  • 状态之间用箭弧连接
  • 箭弧上的标记字符代表起始结点状态下

双圆圈代表最终状态或接收状态

image-20210315142248976

如过终态结点上打了一个星号,意味着多读进了一个不属于标识符部分的字符时,退回给输入串。

状态转换图的实现

将每个状态结点对应一段程序,转换即可。

正则表达式和有限自动机

正则表达式和正则集

  1. $\epsilon$和$\varnothing$是$\Sigma$上的正则式,其正则集为{$\epsilon$}和$\varnothing$
  2. 任何$a\in \Sigma$,a是$\Sigma$上的一个正则式,正则集为{a}
  3. 假定U和V都是$\Sigma$上的正则式,正则集为L(U)和L(V),那么对UV的交并闭包,也能产生正则集

例子

image-20210315145818981

正则式运算

相等

当且仅当两个正则式的正则集相同时,记为U=V

交并规律

跟集合操作类似

有限自动机

有限自动机作为一种识别装置,能够准确地识别正则集合,即识别正则文法所定义的语言与正则式所表示的集合。

分为确定和不确定的有限自动机(DFA和NFA),如果在同一个状态上存在不止一种的转换,我们定义这个自动机为不确定的。

DFA

定义为一个五元式 M = ($S, \Sigma, \delta, s_0, F$)分别为有限集,有穷字母表,单值映射,初态和终态集。

NFA

相比DFA单值映射变为了到S集合的单值映射,初态也变成了非空初态集,终态是一可空的终态集。

NFA的确定化

先来定义对状态集合I的几个有关运算:

  • $\epsilon$-闭包,定义为一状态集,包括
    • I中的任何状态s
    • I中s经过任意条$\epsilon$能够到达的状态的集合
  • a弧转换Ia=$\epsilon$-closure(move(I, a)) = $\epsilon$-closure(J),J定义为可从I的某一状态经过一条a弧而到达的状态的全体.

DFA最小化

即寻找一个状态数更少的DFA M’ 使得L(M) = L(M’)

最小DFA有两个条件

  • 不存在多余状态
  • 不存在相互等价的两个状态

最小化算法的核心就是将状态集分为不相交的子集

image-20210317115032453)image-20210317115047251

正则式和有限自动机的相互转换

见PPT

文章作者: X Mεl0n
文章链接: http://www.zrzz.site/posts/118b8ca3/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 X Mεl0n | 随手记

评论