当前位置： 首页 > news >正文

编译原理-词法分析器

news 2026/1/3 4:18:18

文章目录

  • 对于词法分析器的要求
    • 概念
    • 词法分析器的功能和输出形式
  • 词法分析器的设计
    • 词法分析器的`结构`
    • 单词符号的识别：超前搜索
    • 状态转换图
  • 正规表达式和有限自动机
    • 正规式和正规集
    • 确定有限自动机（`DFA`）
    • 非确定有限自动机（`NFA`）

对于词法分析器的要求

概念

  • 词法分析的任务：从左到右逐个字符地对源程序进行扫描，产生一个个单词符号
  • 词法分析器：又称扫描器，执行词法分析的程序

词法分析器的功能和输出形式

  • 功能：输入源程序，输出单词符号
  • 关键字：程序语言定义的具有固定意义的标识符，例如Pascal中的begin、end、if、while
  • 标识符：表示各种名字：如变量名、数组名和过程名
  • 常数：整型、实型、布尔型、文字型。
  • 运算符：+、-、*、/
  • 界符：逗号、分号、括号
  • 输出的单词符号：（单词种别， 单词符号的属性值）
    • 单词种别：单词种别通常用符号编码表示
      image
  • 词法分析器在编译器中的地位
    image

词法分析器的设计

词法分析器的结构

image

  • 输入缓冲区:输入源程序文本，输入串放在一个缓冲区中,
  • 扫描缓冲区：
    image
  • 预处理子程序主要的工作:剔除无用的空白、空格、换行、回车等字符
  • 扫描器：处理经过预处理子程序处理过的相对规整的字符串

单词符号的识别：超前搜索

  • 关键字的识别：
    image
  • 标识符的识别：字母开头的字母数字串，后跟界符或算符
  • 常数识别：识别出算术常数并将其转变为二进制内码表示，有些也要超前搜索
  • 算符和界符的识别：把多个字符结合而成的算符和界符拼合成一个单一单词符合
  • 几点限制-不必使用超前搜索：
    1.所有关键字都是保留字
    2.关键字作为特殊的标识符处理，都是用保留字表
    3.如果基本字、标识符、常量之间没有确定的运算符或界符做间隔，则必须使用一个空白符做间隔

状态转换图

  • 节点：代表状态，用圆圈表示
    image
  • 箭弧：状态之间用箭弧连接，箭弧上的标记代表射出结状态下可能出现的输入字符或字符类
    有限个状态必须有初态和终态
  • 状态转换图可用于识别一定的字符串：若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于alfa，则称alfa为改状态转换图所识别。
    image
    image

正规表达式和有限自动机

正规式和正规集

image

  • 正规式：正规集的名字，当我们一看到正规式的时候就能想起来正规式对应的正规集
  • 正规集：真正的字集，可以理解为我们要研究的程序语言单词的集合就是正规集
  • 正规式等价：若两个正规式所表示的正规集相同，则认为二者等价

image

确定有限自动机（DFA）

确定有限自动机是状态转换图的一种形式化表示
image

image
eg：
image
答案：B

我们考虑转换到状态1的条件：我们只有在接收到字符a的时候才会转换成状态1，而想要从状态1转换的状态3则必须要再接收一个字符a，考虑状态2，只有在接收到字符b的情况下才会转换到状态2，然后终态一定是以aa或bb结尾吗？我们看到终态还可以接收a|b转圈，所以一定不是以aa|bb结尾，但是要想从初态到终态，一定会经过1、2两个状态中的一个，所以一定会出现连续的aa|bb

image

ans:A
A:识别的是空串，从初态到终态可以一个字都不接收
B:识别的是空集

非确定有限自动机（NFA）

NFA和DFA统称为有限自动机

  • 定义：image
    下图是DFA和NFA的状态转换图
    image
    image

  • DFA是NFA的区别
    image
    DFA和NFA的转换：子集法

  1. 将初态唯一化
  2. 将弧上面的多个字符集|正规式变成单个字符
    image
  3. 将弧上的ε去掉、且做唯一化
    image

这一步是将弧上的ε去掉，这样我们把这些识别字相同的状态放在一起了，这样直接放在一起还会有一个问题就是他们还有自己的识别状态

image
经过a弧：严格意义上经过一个a弧,强调个数,再对J做ε闭包

I 和 Ia的关系：I和Ia都是一个状态，I经过若干个弧（第一个弧是a后面的弧都是ε）可以到达Ia，实际意义就是I识别一个a字符到达Ia，
这一步进行的意义是将状态之间的转换，变为状态集之间的转换，这样就有可能消除映射不是单值部分映射的问题

image

image

相关文章：

编译原理-词法分析器

文章目录 对于词法分析器的要求概念词法分析器的功能和输出形式 词法分析器的设计词法分析器的结构单词符号的识别：超前搜索状态转换图 正规表达式和有限自动机正规式和正规集确定有限自动机（DFA）非确定有限自动机（NFA&#xff09…...

编程日记 2023/10/25 4:53:52

Kafka与MySQL的组合使用

根据上面给出的student表，编写Python程序完成如下操作： （1）读取student表的数据内容，将其转为JSON格式，发送给Kafka； 创建Student表的SQL语句如下： create table student( sno ch…...

编程日记 2023/10/25 4:52:50

2018年亚太杯APMCM数学建模大赛A题老年人平衡能力的实时训练模型求解全过程文档及程序

2018年亚太杯APMCM数学建模大赛 A题 老年人平衡能力的实时训练模型 原题再现 跌倒在老年人中很常见。跌倒可能会导致老年人出现许多并发症，因为他们的康复能力通常较差，因此副作用可能会使人衰弱，从而加速身体衰竭。此外，对跌倒…...

编程日记 2023/10/25 4:51:49

华盛顿特区选举委员会：黑客可能已侵入整个选民名册

导语 近日，华盛顿特区选举委员会（DCBOE）传来了一条令人担忧的消息：黑客可能已经侵入了整个选民名册。这一事件引发了公众的广泛关注和担忧。本文将为大家详细介绍这一事件的经过以及可能带来的后果，并探讨选民数据的保…...

编程日记 2023/10/25 4:49:45

kali安装nodejs、npm失败

更新apt-get再安装，更新时间比较久，看网速，中间有一些确认步骤 22 apt-get update23 apt-get upgrade24 apt-get install nodejs25 node26 npm27 apt-get install npm...

编程日记 2023/10/25 4:48:42

插入排序（学习笔记）

插入排序 每一轮插入排序后的结果与打扑克牌取牌原理相似，将取到的牌插入到合适的位置，但在程序实现方面还是基于交换的算法。 它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。 import java.util.…...

编程日记 2023/10/25 4:46:41

wps excel js编程

定义全局变量 const a "dota" function test() {Debug.Print(a) }获取表格中单元格内容 function test() {Debug.Print("第一行第二列",Cells(1,2).Text)Debug.Print("A1:",Range("A1").Text) }写单元格 Range("C1").Val…...

编程日记 2023/10/25 4:45:40

Python 类继承解释

一、说明 类继承是Python中数据科学家和机器学习工程师需要了解的一个重要概念。在这里，我们的专家解释了它的工作原理。 在Python中，类包含属性和方法。属性是存储数据的变量。类方法是属于类的函数，通常对类属性执行一些逻辑。在本文中&…...

编程日记 2023/10/25 4:44:38

Reactor反应器模式

文章目录 一、单线程Reactor反应器模式二、多线程Reactor反应器模式 在Java的OIO编程中，最初和最原始的网络服务器程序使用一个while循环，不断地监听端口是否有新的连接，如果有就调用一个处理函数来处理。这种方法最大的问题就是如果前一个网…...

编程日记 2023/10/25 4:43:36

alibaba.fastjson的使用（六） -- JavaBean==》Json字符串、JSONObject、JSONArray

目录 1. JavaBean转 Json字符串 2. JavaBean转 JSONObject 3. List转JSONArray 在pom文件中引入依赖: <dependency><groupId>com.alibaba</groupId><artifactId>fastjson</artifactId><version>2.0.14</version></dependency&…...

编程日记 2023/10/25 4:42:35

uniapp 自定义导航栏

自定义导航栏 修改 pages.json 在 pages.json 中将 navigateionStyle 设为 custom 新建 systemInfo.js systemInfo.js 用来获取当前设备的机型系统信息&#xff0c;放在 common 目录下 /*** 此 js 文件管理关于当前设备的机型系统信息*/ const systemInfo function() {/***…...

编程日记 2023/10/25 4:40:33

查分小程序：一键查询成绩，班主任和家长的得力助手

作为一名老师&#xff0c;是否曾经为了让学生能够方便地查询成绩而烦恼&#xff1f;担心学生忘记密码&#xff1f;还是手动输入成绩太繁琐&#xff1f;今天&#xff0c;给大家分享一个超级实用的查分小程序&#xff0c;让成绩查询变得更轻松&#xff01; 什么是成绩查询系统&am…...

编程日记 2023/10/25 4:39:32

Linux内核驱动开发的步骤

Linux操作系统的内核是一个强大的、开源的操作系统内核&#xff0c;它为各种硬件设备提供支持。为了让硬件设备能够与Linux系统无缝协作&#xff0c;需要编写相应的内核驱动程序。本文将介绍Linux内核驱动开发的一般步骤&#xff0c;以帮助开发者了解如何创建自己的内核驱动。 …...

编程日记 2023/10/25 4:38:31

【Java 进阶篇】HTML DOM 事件详解

当用户在网页上点击按钮、输入文本、鼠标移动到某个区域或执行其他互动操作时&#xff0c;这些动作都可以触发事件。HTML DOM&#xff08;文档对象模型&#xff09;允许我们使用JavaScript来捕获、处理和响应这些事件&#xff0c;以实现网页的交互和动态性。本篇博客将围绕HTML…...

编程日记 2023/10/25 4:37:30

redis 从小白到大师系列

字符串 Redis 字符串数据类型 set 字符串 /*** 设置字符串*/ $t $redis->set(o1,o1); //返回true or false var_dump($t);get字符串 /*** 获取字符串*/ $t $redis->get(o1); //返回true or false var_dump($t);结果&#xff1a; string(2) “o1” 返回 key 中字符串…...

编程日记 2023/10/25 4:35:28

vue使用.filter方法检索数组中指定时间段内的数据

假设你有一个名为dataArray的数组&#xff0c;其中包含了你要筛选的数据。那么&#xff0c;你可以按照以下步骤进行筛选&#xff1a; 创建一个名为filteredArray的新数组&#xff0c;用于存储筛选后的结果。使用数组的filter方法遍历dataArray&#xff0c;并对每个元素应用筛选…...

编程日记 2023/10/25 4:34:27

Ubuntu 安装 npm 和 node

前言 最近学习VUE&#xff0c;在ubuntu 2204 上配置开发环境&#xff0c;涉及到npm node nodejs vue-Cli脚手架等内容&#xff0c;做以记录。 一、node nodejs npm nvm 区别 &#xff1f; node 是框架&#xff0c;类似python的解释器。nodejs 是编程语言&#xff0c;是js语言的…...

编程日记 2023/10/25 4:33:26

Matlab论文插图绘制模板第122期—函数折线图（fplot）

本期分享的是函数折线图的绘制模板。​ 所谓函数折线图&#xff0c;就是将自定义线函数进行可视化表达​。 先来看一下成品效果&#xff1a; 特别提示&#xff1a;本期内容『数据代码』已上传资源群中&#xff0c;加群的朋友请自行下载。有需要的朋友可以关注同名公号【阿昆的…...

编程日记 2023/10/25 4:32:25

IK分词器如何修改支持跨版本ES

一、问题描述&#xff1a;IK分词器版本和ES版本不一致&#xff0c;无法找到和自己ES版本匹配的分词器。 IK分词器&#xff0c;提供的插件版本&#xff0c;远赶不上ES的更新版本&#xff0c;在使用过程中&#xff0c;不一定能顺利的找到与自己使用的ES版本相对应。在ES集群中使用…...

编程日记 2023/10/25 4:31:22

Spring MVC常用十大注解

Spring MVC常用十大注解 一&#xff0c;什么要使用注解 使用注解可以简化配置&#xff0c;提高代码的可读性和可维护性。通过注解可以实现依赖注入&#xff0c;减少手动管理对象的代码量。注解还支持面向切面编程&#xff0c;实现切面、切入点和通知等。此外&#xff0c;注解提…...

编程日记 2023/10/25 4:30:20

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

编程新知 2025/11/6 5:46:16

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

编程新知 2025/12/29 5:44:43

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

编程新知 2025/11/20 18:42:48

Swift 协议扩展精进之路：解决 CoreData 托管实体子类的类型不匹配问题（下）

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

编程新知 2025/12/18 18:21:12

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

编程新知 2026/1/3 1:56:43

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

编程新知 2025/11/21 22:02:37

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

编程新知 2025/12/31 16:07:18

排序算法总结（C++）

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

编程新知 2026/1/2 15:15:07

Netty从入门到进阶（二）

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

编程新知 2025/12/30 23:25:07

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

编程新知 2025/12/4 0:13:33