编译原理 - 词法分析

简介: 编译原理 - 词法分析

词法分析


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


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

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

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()
z


上述伪代码中的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
目录
相关文章
|
自然语言处理 前端开发 算法
编译原理 (二)词法分析、语法分析、语义分析以及中间代码生成器的基本概念
编译原理 (二)词法分析、语法分析、语义分析以及中间代码生成器的基本概念
920 0
|
自然语言处理 C语言
编译原理实验-词法分析
编译原理实验C语言实现
123 0
|
9月前
|
安全 关系型数据库 MySQL
mysql 安装插件 validate_password
mysql 安装插件 validate_password
419 0
|
9月前
|
存储 自然语言处理 编译器
【编译原理】词法分析:C/C++实现
【编译原理】词法分析:C/C++实现
367 1
|
9月前
|
域名解析 网络协议 安全
【域名解析DNS专栏】DNS递归查询与迭代查询的区别及影响
【5月更文挑战第24天】DNS的递归查询与迭代查询是域名解析的两种方式。递归查询由客户端发起,DNS服务器负责全程解析,速度快但可能增加服务器负载和安全风险。迭代查询则需客户端参与多次查询,虽慢但分散负载,提高安全性。理解两者差异有助于优化网站访问体验和安全性。
1271 0
【域名解析DNS专栏】DNS递归查询与迭代查询的区别及影响
|
9月前
|
存储 JSON 安全
一文带你了解cookie、session、token区别
【4月更文挑战第10天】
516 3
一文带你了解cookie、session、token区别
|
缓存 网络协议 Linux
网络的救命稻草:重传机制如何确保数据顺利传输?
在网络传输中,数据的可靠性和稳定性一直是一个重要的挑战。幸运的是,重传机制应运而生,为我们解决了这个问题。本文将深入探讨重传机制在网络中的应用和工作原理。我们将介绍TCP中最常见的超时重传和快速重传,以及SACK和D-SACK这两种高级重传机制。了解这些机制如何工作可以帮助我们更好地理解数据传输的可靠性和稳定性的保障。
467 1
网络的救命稻草:重传机制如何确保数据顺利传输?
|
安全 Linux 程序员
「技术干货」一文搞懂C语言内存模型与栈
「技术干货」一文搞懂C语言内存模型与栈
|
索引
什么是RFC?
RFC及RFC编辑者:    RFC(Request For Comments)-意即“请求注解”,包含了关于Internet的几乎所有重要的文字资料。如果你想成为网络方面的专家,那么RFC无疑是最重要也是 最经常需要用到的资料之一,所以RFC享有网络知识圣经之美誉。
1949 0
|
JSON 前端开发 JavaScript
从零开始搭建Vue2.0项目(二)之集成axios
上一篇主要介绍了如何安装通过**webpack**安装一个具有完整线上依赖的项目,其中我们通过`webpack-template`安装了vue2.0项目的`Vue-Core`、`Vue-Router`以及`ESLint`依赖。下面我们来完成前后端接口通信操作
369 0
从零开始搭建Vue2.0项目(二)之集成axios

热门文章

最新文章