美文网首页
编译原理实战课---词法分析

编译原理实战课---词法分析

作者: 楼上那位 | 来源:发表于2021-08-02 09:35 被阅读0次

本节课主要涉及词法分析,将一段话使用分词器tokenizer 进行分词,关键是怎么分词?分词的规则是啥?一般我们会联想到正则文法进行匹配? 如果正则满足不了呢?等等一系列的问题。

在分词过程中我们需要有一个数学模型-有限自动机(Finite-state Automaton,FSA),或者叫做有限状态自动机(Finite-state Machine,FSM),什么是状态机呢?

状态机是有限状态自动机的简称,是现实事物运行规则抽象而成的一个数学模型。

说白了就是一张状态转换图,这里会涉及到四个概念:

  1. 状态,比如开 闭等

  2. 事件 执行某个操作触发的条件或者指令

  3. 动作,事件发生后的要执行的动作

  4. 变换transition 从一个状态变化未另一个状态

状态转换.jpg

上图是对数字字面量和标识符的状态转移过程; 进入初始状态(单线圈标识临时状态),遇到数字进入1,如果接下里还是数字继续处于1状态,如果接下来是空格,这代表此状态结束进入初始状态,此时前面的数字部分就是一个单独的token; 同理初始遇到的是一个字母,则进入2状态,接下来一个字符是数字或者字母则继续呆在2状态,除非遇到空白字符或者其他标识符导致异常出现

词法分析的过程,其实就是对一个字符串进行模式匹配的过程

词法分析器

1. 生成词法分析器

词法分析器生成工具 lex(及 GNU 版本的 flex)能够基于规则自动生成词法分析器。

2. DFA & NFA

DFA 它是“Deterministic Finite Automaton”的缩写,即确定的有限自动机。它的特点是:该状态机在任何一个状态,基于输入的字符,都能做一个确定的状态转换。前面例子中的有限自动机,都属于 DFA。

NFA,它是“Nondeterministic Finite Automaton”的缩写,即不确定的有限自动机。它的特点是:该状态机中存在某些状态,针对某些输入,不能做一个确定的转换。

3. 任何一个正则表达式都可以转化为DFA或者NFA

语法分析

掌握语法分析阶段的核心需要两个基本功:

第一,必须能够阅读和书写语法规则,也就是掌握上下文无关文法;

第二,必须要掌握递归下降算法。两种算法思路:一种是自顶向下的语法分析,另一种则是自底向上的语法分析。

相关文章

  • 编译原理实战课---词法分析

    本节课主要涉及词法分析,将一段话使用分词器tokenizer 进行分词,关键是怎么分词?分词的规则是啥?一般我们会...

  • 你不知道的JavaScript —— 作用域是什么

    1.1 编译原理 传统编译步骤 分词/词法分析(拆分成一个个词法单元)——>解析/语法分析(词法单元流转化为抽象语...

  • 编译原理->词法分析

    词法分析器的作用 词法分析器的主要任务是读入源程序的输入字符、将它们组成词素,生成并输出一个词法单元序列,每个词法...

  • 第一章作用域是什么

    1.1 编译原理 编译语言 分词/词法分析 解析/语法分析 代码生成 对于Javascript来说,大部分情况发生...

  • 什么是作用域

    编译原理 传统编译语言 词法分析:将由字符组成的字符串分解成(对编译语言来说)有意义的代码块,这些代码块被称为词法...

  • 作用域(一)

    编译原理 分词/词法分析这个过程称为分解代码块(词法单元),比如 var a = 2;。这个程序通常会被分解成为下...

  • 2018-09-07

    编译原理 Ch1 概念 编译程序 编译程序由八部分组成: 词法分析程序 语法分析程序 语义分析程序 中间代码生成程...

  • 编译原理大体概念

    编译原理学习 名词解释翻译器 translator编译器 compiler 高级语言--->低级语言词法分析 ...

  • 编译原理之词法分析

    词法分析的问题 术语 模式(pattern):产生和识别元素的规则 记号(token): 按照某个模式(或规则)识...

  • 编译原理:词法分析程序

网友评论

      本文标题:编译原理实战课---词法分析

      本文链接:https://www.haomeiwen.com/subject/bupdvltx.html