MENU

【编译原理】1、词法分析器

June 1, 2020 • Read: 40 • 编程之路,编译原理

编译原理目录
1、词法分析
2、语法分析(重点)
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化

1、词法分析器

词法分析的任务: 源程序字符流 => 词法分析器 => 记号流

1.1 基本概念

示例:

记号的数据结构定义

enum kind {
  IF, LPAREN,
  ID, INTLIT,
  …
};
struct token{
  enum kind k;
  char *lexeme;
};

词法分析器的任务:

  • 字符流到记号流

    • 字符流:和被编译的语言密切相关 (ASCII, Unicode, or …)
    • 记号流:编译器内部定义的数据结构,编码所识别出的词法单元。

词法分析器的实现方法

  • 手工编码实现法

    • 相对复杂、且容易出错
    • 但是目前非常流行的实现方法
    • GCC, LLVM, …
  • 词法分析器的生成器

    • 可快速原型、代码量较少
    • 但较难控制细节

转移图

转移图算法

token nextToken ()
c = getChar ();
switch (c)
  case ‘<’: c = getChar ();
            switch (c)
              case ‘=’: return LE;
              case ‘>’: return NE;
              default: rollback(); return LT;
  case ‘=’: return EQ;
  case ‘>’: c = nextChar ();
            switch (c): ...// similar

识别关键字

关键字表算法

  • 对给定语言中所有的关键字,构造关键字构成的哈希表H
  • 对所有的标识符和关键字,先统一按标识符的转移图进行识别
  • 识别完成后,进一步查表H看是否是关键字
  • 通过合理的构造哈希表H(完美哈希),可以O(1)时间完成

1.2 正则表达式(RE)

声明式规范 => 自动生成工具生成 => 词法分析器

  • 对给定的字符集 $\sum ={c1, c2, … , cn}$,归纳定义:

    • 空串ε是正则表达式
    • 对于任意$c \in \sum$, c是正则表达式
    • 如果M和N是正则表达式, 则以下也是正则表达式

      • 选择:$M | N = \{M, N\}$
      • 连接:$MN = \{mn| m\in M, n\in N\}$
      • 闭包:$M* = \{ε, M, MM, MMM, … \}$

正则表达式的形式表示

e -> ε
   | c
   | e | e
   | e e
   | e*

语法糖

  • $[c1-cn]$ == c1|c2|… |cn
  • $e+$ == 一个或多个 e
  • $e?$ == 零个或一个 e
  • $a*$ == a* 自身, 不是a的Kleen闭包
  • $e\{i, j\}$ == i到j个e的连接
  • . == 除‘ n’外的任意字符

1.3 有限状态自动机(FA)

输入函数 -> FA -> {Yes, No}

M = (\sum, S, q0, F, \delta)

  • 确定状态有限自动机DFA

    • 对任意的字符,最多有一个状态可以转移
    • $\delta:S × \sum → S $
  • 非确定的有限状态自动机NFA

    • 对任意的字符,有多于一个状态可以转移
    • $\delta:S × (\sum \cup \epsilon) → \weierp(S) $

1.4 RE → NFA (Thompson算法)

RE -> Thompson算法 => NFA -> 子集构造算法 => DFA -> Hopcroft最小化算法 => 词法分析器代码

  • 基于对RE的结构做归纳

    • 对基本的RE直接构造
    • 对复合的RE递归构造
  • 递归算法,容易实现

示例: $a(b|c)*$

1.4 NFA → DFA (子集构造算法)

示例:

求出$ε-closure(s)$,$ε-closure(s)$表示由状态s经由条件ε可以到达的所有状态的集合

ε-closure(n0) = {n0}
ε-closure(n1) = {n1,n2,n3,n4,n6,n9}
ε-closure(n2) = {n2,n3,n4,n6,n9}
ε-closure(n3) = {n3,n4,n6}
ε-closure(n4) = {n4}
ε-closure(n5) = {n3,n4,n5,n6,n8,n9}
ε-closure(n6) = {n6}
ε-closure(n7) = {n3,n4,n6,n7,n8,n9}
ε-closure(n8) = {n3,n4,n6,n8,n9}
ε-closure(n9) = {n9}

首先将初始态的转换闭包ε-closure(0)设为状态A,即A={0},接着写出状态A经过上面转换图中所有转换条件得到的状态,后继状态里面不包括自身,这里的转换条件包括a和b和c。

ε-closure(0) = A
ε-closure(move(A,a)) = ε-closure({n1}) = {n1,n2,n3,n4,n6,n9} = B
ε-closure(move(A,b)) = ε-closure({})
ε-closure(move(A,c)) = ε-closure({})
 
ε-closure(move(B,a)) = ε-closure({})
ε-closure(move(B,b)) = ε-closure({n5}) = {n3,n4,n5,n6,n8,n9} = C
ε-closure(move(B,c)) = ε-closure({n7}) = {n3,n4,n6,n7,n8,n9} = D
 
ε-closure(move(C,a)) = ε-closure({}) =
ε-closure(move(C,b)) = ε-closure({n5}) = {n3,n4,n5,n6,n8,n9}
ε-closure(move(C,c)) = ε-closure({n7}) = {n3,n4,n6,n7,n8,n9}
 

子集构造算法

q0 <- eps_closure (n0)
Q <- {q0}
workList <- q0
while (workList != [])
  remove q from workList
  foreach (character c)
    t <- e-closure (delta (q, c))
    D[q, c] <- t
    if (t\not\in Q)
      add t to Q and workList

ε-闭包的计算:深度优先

/* ε-closure: 基于深度优先遍历的算法 */
set closure = {};
void eps_closure (x)
  closure += {x}
  foreach (y: x--ε--> y)
    if (!visited(y))
      eps_closure (y)

ε-闭包的计算:宽度优先

/* ε-closure: 基于宽度优先的算法 */
set closure = {};
Q = []; // queue
void eps_closure (x) =
  Q = [x];
  while (Q not empty)
    q <- deQueue (Q)
    closure += q
    foreach (y: q--ε--> y)
      if (!visited(y))
        enQueue (Q, y)

1.5 DFA的最小化 (Hopcroft算法)

1.5.1 消除多余状态

  • 什么是多余状态

    • 从这个状态出发没有通路到达终态
    • 从开始状态出发,任何输入串也不能到达的那个状态

例如:

1.5.2 等价状态

  • 等价状态:对于两个状态s和t

    • 一致性条件:状态s和t必须同时为终态或非终态
    • 蔓延性条件:对于所有输入符号,状态s和状态t必须转化到等价的状态里

示例1:

示例2:

Hopcroft算法:

// 基于等价类的思想
split(S)
  foreach (character c)
    if (c can split S)
      split S into T1, …, Tk
hopcroft ()
  split all nodes into N, A
  while (set is still changes)
    split(S)

1.6 DFA的代码表示

  • 概念上讲, DFA是一个有向图。
  • 实际上,有不同的DFA的代码表示:转移表 (类似于邻接矩阵)、哈希表、跳转表。。。
  • 取决于在实际实现中,对时间空间的权衡。

1.6.1 转移表

驱动代码

nextToken()
  state = 0
  stack = []
  while (state!=ERROR)
    c = getChar()
    if (state is ACCEPT)
      clear(stack)
    push(state)
    state = table[state][c]
 
  while(state is not ACCEPT)
    state = pop();
    rollback();

1.6.2 跳转表

nextToken()
  state = 0
  stack = []
  goto q0
 
q0:
  c = getChar()
  if (state is ACCEPT)
    clear (stack)
  push (state)
  if (c==‘a’)
    goto q1:
 
q1:
  c = getChar()
  if (state is ACCEPT)
    clear (stack)
  push (state)
  if (c==‘b’||c==‘c’)
    goto q1

NFA→右线性文法

定理:设NFA: $M=(Q, \Sigma, \delta, q_0, F, )$,那么存在一个右线性文法$G_1$使得$L(G_1) = L(M)$,也存在一个左线性文法$G_2$,使得$L(G_2) = L(M)$

给定NFA: $M=(\Sigma, S, q_0, F, \delta)$

构造右线性文法:$G=(Q, \Sigma, P, q_0)$

  • $q→ap$ 如果(q,a)→p
  • $q→a$ 如果(q,a)→p且p∈F
  • $q_0 →ε$ 如果 $q_0$ 是终结状态。

DFA: $M=(Q, \Sigma, \delta, s, F, )$

- - - 结束 - - -
  • 文章标题:【编译原理】1、词法分析器
  • 文章链接:https://blog.canye365.cn/archives/304.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021