编译原理 - 词法分析

2023-12-21 10:10:40

词法分析

编译器的前端可以分成如下过程:

=》前端=》词法分析器=》记号=》语法分析器=》抽象语法树=》语义分析器=》中间表示=》

词法分析的任务是将程序员所写的程序切分成记号流。

if (x > 5)
	y = "hello";
else
	z = 1;

经过词法分析器分析之后,会被字符切分为如下内容

IF LPAREN IDENT(x) GT INT(5) RPAREN
	IDENT(y) ASSIGN STRING("hello") SEMICOLON
ELSE
	IDENT(z) ASSIGN INT(1) SEMICOLON EOF

记号

记号的数据结构定义,类似如下代码

enum kind {IF, LPAREM, ID, INTLIT, ...}
struct token
{
    enum kind k;
    char *lexeme;
}

词法分析器的任务:字符流到记号流的转换

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

词法分析器的实现方法

至少两种的实现方案:

  • 手工编码实现法
    • 相对复杂,且容易出错
    • 但是目前非常流行的实现方法
      • GCC,LLVM,…
  • 词法分析器的生成器
    • 可快速原型,代码量少
    • 但是较难控制细节

手工编码实现法

如果我们有<=、<>、<、=、>、>=、>符号,如下图,我们的提取步骤,根据第一个字符,我们可以按照下图步骤读取对应的符号。

在这里插入图片描述

其他的标识符转移图和上述的类似。

标识符和关键字
  • 很多语言中标识符和关键字是有交集的
    • 从词法分析的角度看,关键字是标识符的一部分
  • 以C语言为例:
    • 标识符:以字母或者下划线开头,后面跟了零个或者多个字母,下划线或者数字
    • 关键字:if while else
如何识别关键字
  • 在标识符识别的时候,单独加上标识符的识别

  • 关键字表算法

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

词法分析器的生成器

正则表达式
  • 对给定的字符集 A = {c1, c2…cn}
  • 归纳定义
    • 空串a是正则表达式
    • 对于任意的c 属于A, c是正则表达式
    • 如果M和N是正则表达式,则一下也是正则表达式
      • 选择 M | N = {M, N}
      • 连接 MN = {mn | m属于M, n属于N}
      • 闭包 M* = {c, M,MM, MMM, … }

如何使用正则表达式?

  • 关键字
    • C语言中的关键字 if while 如何使用正则表达式表示呢 if
  • 表示符
    • C语言中的标识符需要以字母或下划线开头,后面跟零个或者多个字母i,数字或者下划线。 如何使用正则表达式表示呢?
正则表达式语法糖

参见正则表达式文章连接:正则表达式-CSDN博客

有限状态自动机(FA)

输入的字符串=》FA=》{YES, NO}

  • 确定的有限状态自动机:DFA
    • 对任意字符,对多只有一个状态可以转移
  • 非确定的有限状态自动机:NFA
    • 对任意的字符,有多余一个状态可以转移
DFA的实现

可以看成一个有边和节点的有向图;

  • 边上有信息
  • 节点上也有信息

正则表达式到非确定有限状态自动机

  • Thompson算法:正则表达式=》NFA

  • 子集构造算法:NFA=>DFA

  • Hopcroft最小化算法:DFA=>词法分析器代码

Thompson算法
  • 基于对RE的构造做归纳
    • 对基于的RE直接构造
    • 对复合的RE递归构造
  • 递归算法,容易实现
子集构造算法
  • 不动点算法
    • 算法为什么能工运行终止
  • 时间复杂度
    • 最坏情况O(2^n)
    • 但是在实际中不常发生
      • 因为并不是每个子集都会出现
  • ε-闭包的计算:深度优先或者是广度优先
Hopcroft最小化算法
DFA的代码表示
  • 概念上讲,DFA是一个有向图
  • 实际上,有不同的DFA的代码表示
    • 转移表
    • 哈希表
    • 跳表等
  • 取决于在实际实现中,对时间空间的权衡
转移表
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()

上述伪代码中的stack 是为了 最长匹配

跳转表
netxToken()
    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

文章来源:https://blog.csdn.net/turbolove/article/details/135122347
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。