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

编译原理-词法分析器

news 2025/11/13 0:00:44

文章目录

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

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

编程新知 2025/10/31 17:25:40

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

编程新知 2025/11/12 21:10:47

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

编程新知 2025/11/10 16:37:29

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

编程新知 2025/11/10 18:35:01

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

编程新知 2025/9/12 8:21:45

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

编程新知 2025/11/12 18:57:19

Redis：现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

编程新知 2025/11/1 8:05:41

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

编程新知 2025/11/12 20:31:25

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

编程新知 2025/11/3 8:50:43

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

编程新知 2025/10/26 9:51:09