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

编译原理-词法分析器

news 2025/6/21 16:43:59

文章目录

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

日语AI面试高效通关秘籍：专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

编程新知 2025/6/19 11:27:43

盘古信息PCB行业解决方案：以全域场景重构，激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

编程新知 2025/6/20 22:10:36

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

编程新知 2025/6/15 8:59:06

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

编程新知 2025/6/16 15:03:51

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

编程新知 2025/6/18 3:15:40

江苏艾立泰跨国资源接力：废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

编程新知 2025/6/18 20:38:15

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

编程新知 2025/6/21 5:49:39

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

编程新知 2025/6/16 12:49:42

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

编程新知 2025/6/20 15:48:55

安卓基础（aar）

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

编程新知 2025/6/21 1:43:55