首页
归档
友情链接
关于
Search
1
在wsl2中安装archlinux
116 阅读
2
nvim番外之将配置的插件管理器更新为lazy
85 阅读
3
2018总结与2019规划
65 阅读
4
PDF标准详解(五)——图形状态
43 阅读
5
为 MariaDB 配置远程访问权限
34 阅读
软件与环境配置
博客搭建
从0开始配置vim
Vim 从嫌弃到依赖
archlinux
Emacs
MySQL
Git与Github
AndroidStudio
cmake
读书笔记
编程
PDF 标准
从0自制解释器
qt
C/C++语言
Windows 编程
Python
Java
算法与数据结构
PE结构
Thinking
FIRE
菜谱
登录
Search
标签搜索
c++
c
学习笔记
windows
文本操作术
编辑器
NeoVim
Vim
win32
VimScript
emacs
elisp
linux
文本编辑器
Java
反汇编
读书笔记
OLEDB
数据库编程
数据结构
Masimaro
是金子总会发光的,可你我都是老铁
累计撰写
319
篇文章
累计收到
31
条评论
首页
栏目
软件与环境配置
博客搭建
从0开始配置vim
Vim 从嫌弃到依赖
archlinux
Emacs
MySQL
Git与Github
AndroidStudio
cmake
读书笔记
编程
PDF 标准
从0自制解释器
qt
C/C++语言
Windows 编程
Python
Java
算法与数据结构
PE结构
Thinking
FIRE
菜谱
页面
归档
友情链接
关于
搜索到
319
篇与
的结果
2024-03-03
PDF标准详解(二)——PDF 对象
上一篇文章我们介绍了一个PDF文档应该包含的最基本的结构,并且手写了一个最简单的 “Hello World” 的PDF文档。后面我们介绍新的PDF标准给出示例时将以这个文档为基础,而不再给出完整的文档示例,小伙伴想自己测试可以根据上一节的文档来进行配置。对象上一节我们看到一个个奇奇怪怪的元素,可能也好奇它们的写法,现在我们来正式介绍它们的相关内容,它们就是PDF文档中一个个的对象。PDF 支持5种基本对象:整数和实数:例如43和12.2 这种数字字符串,PDF种字符串被包裹在小括号中,例如上一节中的 (hello world), 我们也可以给字符串制定编码,这个在后面介绍名称:一般用于字典中的键,以/ 开头,例如上一节中的 /Page 就是一个名称的对象布尔值: 由关键字 true 和 false表示null 对象,由关键字 null 表示PDF支持3种复合对象数组: 包含其他对象的有序集合,数组中的元素可以是其他任何类型的对象,例如可以像 [0 0 0 0 1] 这样只包含数字,也可以像上一节中的 [2 0 R] 包含其他对象的一个引用字典: 字典是由无序对的集合组成,将名称映射到对象。字典中的映射被包含在 <<>> 对中,例如 <</Kids [2 0 R]>> 就是一个字典,它将Kids这个名称映射到 [2 0 R] 这个间接引用的对象上流:流中一般包含二进制的数据流以及描述属性的字典,一般page中的content都是一个个的流对象。间接引用间接引用形成从一个对象到另一个对象的链接,为了将PDF拆分成一个个单独的对象,我们通过间接引用将它们链接在一起,例如上一篇文章中提到的1 0 obj << /Kids [2 0 R] /Count 1 /Type /Pages >>对象中就包含间接引用,PDF解析器,知道这个对象是一个Pages对象之后,可以通过Kids 对象指定的间接引用对象知道,当前PDF文档只有一页,这个页面对象就是2 0 这个对象。 这里的R 代表 reference 也就是引用,它是一个关键字,前面的 2 0 代表的是对象编号是2,世代号是0(这里我们不考虑世代号,默认的世代号都是0)流和过滤器流用于存储二进制数据,它们由字典和一大块二进制数据组成,字典根据流所放置的特定用途,列出数据的长度,以及可选的其他参数。从语法上将,流由字典组成,后跟 stream 关键字,换行符,0个或者多个字节的数据,另一个换行符,最后是一个endstream 关键字。根据上一篇文章中给出的页面流对象的定义来看4 0 obj << /Length 202 % 流的长度 >> stream %关键字 1. 0. 0. 1. 50. 700. cm % 202 字节的数据,这里是图形流,下面是图形流的数据 BT /F0 36. Tf (Hello, World!) Tj ET endstream % 流对象结束的关键字 endobj
2024年03月03日
22 阅读
0 评论
0 点赞
2024-01-18
PDF标准详解(一)——PDF文档结构
已经很久没有写博客记录自己学到的一些东西了。但是在过去一年的时间中自己确实又学到了一些东西。一直攒着没有系统化成一篇篇的文章,所以今年的博客打算也是以去年学到的一系列内容为主。通过之前Vim系列教程的启发,我发现还是写一些系列文章对自己的帮助最大。它能最大化自己的学习成果,并强迫自己深入了解一些内容。所以今年我想还是以系列文章为主,如果中间有需要穿插一些bug处理或者语言特性相关的,可能也会有这方面的内容吧。好了,废话就到这里,下面开始正式介绍PDF相关的内容PDF简介PDF的全称是 Portable document format(可移植文档格式),是描述打印页面的世界领先语言。最早于1990年代由Adobe Systems创造。早期是Adobe专有格式,直到2008年作为开放标准发布。后续经过一系列的发展,目前已经发展到了2.0版本,由于PDF完全向后兼容,并且大部分都是向前兼容的,因此,这里不打算固定在某个具体的版本,而是介绍一些PDF通用的标准和规则。PDF的文档结构PDF主要由四个部分构成,文件头、文件体、交叉引用表以及文件尾文件头将文件标识为PDF并给出它的版本号,例如%PDF-1.0 % PDF 版本号为 1.0 的文件头文件体是PDF文档的主体内容,主要由对象组成,它规定了页面信息和页面内容元素等信息交叉引用表给出了每个对象距离文件首部的地址偏移,这样在解析PDF的时候就不用从头到尾解析每个对象,而是根据需要通过交叉引用表来寻址到具体的对象地址,只单独解析某个对象,提高了解析效率文件尾给出交叉引用表的位置并且以%%EOF作为结尾PDF文件的逻辑结构一个标准的PDF文档需要在文件体中包含下列元素对象:根节点元素,类似于xml的根节点,它是整个文档的根节点对象Pages对象,它包含了PDF文档的页面信息,一般通过它来定义整个PDF文档有多少页Page 页面对象,它用来描述每个具体的页Page Content 对象,它来描述每个具体页中都有哪些对象,一般是一个字节流用来表示将在页面中显示哪些内容Page Resource 对象,它是内容的资源字典,供Content对象引用,资源包括字体、画刷、画笔等等trailer 字典,可以将它看作pdf文档对象的入口,通过它我们可以知道当前PDF文档的一些具体信息,例如根节点的位置,交叉引用表的大小它们之间的关系如下图:PDF版的Hello World说了这么多,我们来试试来自己编辑一个hello world文档,首先建立一个文本文件,将后缀改为.PDF 。我们先写上文件头:%PDF-1.0 % PDF 版本号为 1.0 的文件头主要对象我们按照之前的分析的PDF文档中需要包含的对象,来逐一定义首先给出Pages节点的定义1 0 obj % 对象1 << /Type /Pages % 这是一个页面列表 /Count 1 % 只有一页 /Kids [2 0 R] % 页面对象编号列表。这里只是对象2 >> endobj % 对象1结束对象的内容我们在后续会专门介绍,所以这里不需要额外关注它的语法,这里只需要知道1 0 obj定义了一个对象1,后续通过1 这个编号可以找到这个对象。这个对象中定义了他的类型是 Pages表示它是一个pages对象,/Count表示整个PDF文档只有一页,Kids是一个数组,表示每一页的页面对象,这里它只有一个页面对象,就是对象2接着我们定义页面对象2 0 obj << /Type /Page % 这是一个页面 /MediaBox [0 0 612 792] % 纸张尺寸为美国信肖像(612点x792点) /Resources 3 0 R % 对象3的资源引用 /Contents [4 0 R] % 图形内容在对象4中 >> endobj页面对象中我们定义了页面纸张的大小,单位是磅。因为PDF是可移植文档,它需要在不同设备上显示同样的内容,这里不能使用像素,如果使用像素,在同样尺寸的显示器上如果显示器的像素分辨率不同,那么显示的结果将会不同。所以这里一般使用磅作为单位。同时在页面对象中定义了页面中将要使用的资源以及将要显示的内容接着我们来定义资源对象3 0 obj << /Font % 字体字典 << /F0 % 只有一种字体,称为/F0 << /Type /Font % 这三行引用了内置字体Times Italic /BaseFont /Times-Italic /Subtype /Type1 >> >> >> endobj资源对象中,我们定义了一个字体资源,字体为 Times Italic,并且定义了这种字体资源的名称为 F0, 后面可以通过F0 这个名称来直接引用这个字体然后我们来定义页面内容对象4 0 obj % 页面内容流 << >> stream % 流的开始 1. 0. 0. 1. 50. 700. cm % 位置在(50,700) BT % 开始文本块 /F0 36. Tf % 在36pt选择/F0字体 (Hello, World!) Tj % 放置文本字符串 ET % 结束文本块 endstream % 流结束 endobj通过stream来定义一个流对象,在这个流对象中,我们定义它在页面的 (50, 700) 坐标位置显示字符,显示字符内容通过后面的 (Hello, World!) Tj来定义,并且定义了字符采用F0 字体,也就是上面定义的Times-Italic字体页面相关的内容我们已经定义完了,接着我们需要定义一些结构相关的对象,方便PDF解析器找到并解析页面内容。我们来定义根节点5 0 obj << /Type /Catalog %文件目录 /Pages 1 0 R %参考页面列表 >> endobj根节点包含了一个Pages定义,通过根节点就可以找到Pages节点接着我们来定义交叉引用表xref %这里我们跳过了交叉引用表的开始 0 6交叉引用表包含一些偏移地址信息,我们单纯的通过文本文档很难计算各个对象的偏移,所以这里我们只给出文档中对象数量为6,具体的地址我们先不给出,这样PDF解析器也能解析出各个对象之前我们给出了5个对象的定义,但是交叉引用表的条目却是6,这是因为交叉引用表的第一条一般是一个没有什么用处的,有效的对象从第二条定义开始。下面给出 Trailer 字典的定义trailer << /Size 6 %交叉引用表的行数 /Root 5 0 R % 参考文档目录 >>Trailer 字典以 trailer关键字开始。条目下面包括了交叉引用表的行数以及根节点的对象最后我们给出交叉引用表在PDF文档中的偏移,由于交叉引用表的内容为空,所以这里我们直接给0startxref 0 %xref表开始的字节偏移量,这里设置成0最后我们以%%EOF结尾来表示整个PDF文档结束到这里我们已经得到了一个PDF阅读器可以打开的PDF文档。我们使用PDF阅读器可以得到如下的页面PDF文档一般的读取过程不知道各位小伙伴们是否能看懂上面 Hello World 文档的定义。下面我们通过一个完整的 PDF文档来将上面所有定义的对象串起来,希望各位能对PDF文档有一个完整的认识。我们不用纠结各个部分的写法,以及为什么要这么写,只需要明白各个对象的功能即可。具体对象定义相关的语法和每个对象的详细解释将会在后面一系列文章中给出,相信那个时候再来看这个 Hello Word 文档一定会有一个更清晰的认识。再说明文档读取的过程前,我们先使用一些工具来补全这个文档,这里使用 pdftk 工具。可以在这里 进行下载,完成之后,使用如下命令进行补全pdftk hello.pdf output hello-full.pdf成功后会得到如下内容%PDF-1.0 %忏嫌 1 0 obj << /Kids [2 0 R] /Count 1 /Type /Pages >> endobj 2 0 obj << /Resources 3 0 R /MediaBox [0 0 612 792] /Contents [4 0 R] /Type /Page >> endobj 3 0 obj << /Font << /F0 << /BaseFont /Times-Italic /Subtype /Type1 /Type /Font >> >> >> endobj 4 0 obj << /Length 202 >> stream % 娴佺殑寮€濮? 1. 0. 0. 1. 50. 700. cm % 浣嶇疆鍦紙50,700锛? BT % 寮€濮嬫枃鏈潡 /F0 36. Tf % 鍦?6pt閫夋嫨/F0瀛椾綋 (Hello, World!) Tj % 鏀剧疆鏂囨湰瀛楃涓? ET % 缁撴潫鏂囨湰鍧? endstream endobj 5 0 obj << /Pages 1 0 R /Type /Catalog >> endobj xref 0 6 0000000000 65535 f 0000000015 00000 n 0000000074 00000 n 0000000168 00000 n 0000000267 00000 n 0000000523 00000 n trailer << /Root 5 0 R /Size 6 >> startxref 573 %%EOF 这个我将整个PDF文档都粘贴了出来,从这里我们可以看到,它已经为我们补全了交叉引用表。下面通过整个文档来说明一般读取过程PDF解析程序,先通过文件头来确定是否是PDF文件,并且得到PDF文件的版本在文件末尾找到%%EOF 关键子,确定文件尾。接着向上查找到 startxref 关键字,该关键字后面将会给出交叉引用表的偏移,通过这个偏移地址可以找到交叉引用表接着查找trailer关键字,通过trailer关键字可以得到文档的一些信息,这里关键的是得到 Root 节点的对象。根据交叉引用表可以很块定位到Root 节点对象,也就是对象5根据Root 对象中的 Pages属性可以找到Pages对象,也就是PDF页面信息对象根据Pages对象中的Kids 数组,可以找到PDF包含的所有页面对象,这个文档只有一个页面对象找到Page 对象后可以根据 Resources 和Contents属性可以找到页面内容和页面引用的资源。例如该文档就可以使用Times-Italic字体显示 hello world字符串
2024年01月18日
7 阅读
0 评论
0 点赞
2024-01-13
2023 年度回顾与2024 年展望
时间如白驹过隙,转眼已经2024年了,本来打算2024年元旦那天写写年度回顾的,但是因为一些琐事耽误了,平时上班路程远回来也就懒得动了,一直就拖到今天才开始着手这个每年的例行公事。2023年的回顾回顾整个2023年,从我自己来说并没有什么特别大的事情发生。年初我把自己的小孩接到身边来,由家里的老人过来帮忙带孩子,我则是和媳妇上班。每天下班回来都逗小孩,确实挺快乐的。随着孩子慢慢长大,慢慢会走路,会叫爸爸妈妈。现在每天下班开门都有一个小朋友晃晃悠悠的朝你身边走过来伸手让你抱抱,并且笑着喊你爸爸。看到这一幕上班一整天的疲惫似乎一扫而空。瞬间又充满了力量,随时为了这个小宝宝去冲锋陷阵。有了一个小孩,家里欢乐的时光多了不少。这个可能是我这一整年每天都能感到的幸福时光。对于工作上的事情,22年年末刚入职,很多事情并不那么熟悉,去年写总结的时候没怎么总结在新公司的一些工作。现在我已经在公司工作一年多了,随着公司给予的培训和同事领导平时的照顾,我已经慢慢的从刚入公司接受一些边角料的活到现在已经能独立负责项目中一整个大的模块,在项目组中我自认为已经成为整个团队非常重要的一个组成部分。回顾这一整年在新公司的工作,工作相对比较清闲,没有互联网公司那么卷,每天按时上下班,各个任务给的时间相对也比较充足,新的项目仍在开发中,目前项目已经持续了一年多了,这在以前的公司是无法想象的。通过这段时间的工作经历我突然意识到,也许只有在一个不那么卷的公司自己才能有足够多的成长。想象以前做项目都是用开源项目直接套,似乎并不关注它怎么实现,整个团队都追求快速出成果。遇到段时间内无法攻克的难题,加班加点,改方案,改架构几乎是家常便饭。根本没有时间考虑使用合适的架构,合适的语言,甚至加上单元测试,编写完善的文档都是奢望。似乎每个难点在领导眼里解决时间都不超过2小时,不然就是能力问题。有时候我也怀疑自己的能力,难道我真的没有独立解决问题的能力?我没有独立带队完成可商用项目的能力?我的眼光不够长远,没有预先想到客户的使用场景和使用需求?而在新的公司中,这些问题完全不存在。首先一个是,项目开始前都会反复论证,并且给予充分的时间。而且遇到问题,给出合理的理由项目时间可以适当往后延长。我们经常开发到一半会过来重新考虑之前的架构是否合理,并且给予时间进行重构,或者进行文档的补充,又或者在某个程度团队成员都会花时间讲解自己这部分的架构以便让整个团队对整个项目都有完整的概念。甚至有想法的话可以在跟对应的人员充分沟通后一起重构之前不属于你的代码。所以在这一年中我感觉自己完全融入整个团队,我不仅能改自己的bug,甚至当别人无法抽身时我也能试着挑战别人的bug。我想这才是软件开发应该有的团队氛围和管理方式。总之目前来说我还是比较喜欢当前的工作环境和氛围的。虽说工资无法与互联网大厂相比,但是我待在这里还是蛮舒服的。在学习方面,我的博客已经断更很久了。主要是因为周末都是在家陪孩子玩,没怎么抽出时间来看书或者学习。有时候看着身边的小伙伴都在趁着周末要么接项目搞钱,要么学习新的知识。我心里也有点慌,那些人学历比我好,工资比我高,能力比我强,周末也比我努力。我在现在的公司虽说待着比较舒服,但是毕竟手里没有多少钱,当孩子大了,我也超过35岁了不知道能不能继续给她提供一个稳定的生活环境。毕竟北京这边未来会面临很多问题。但是我作为打工人每天只用工作8小时,一周也就上5天班,带孩子却是需要7*24小时,周末在家时我想稍微给家里的老人减轻点负担。现在也是充满矛盾。还有一个就是读书方面,虽然现在在地铁通勤时间不少,但是大部分时间都拿去玩手机了,看书的时间并没有多少,满打满算也就8本书左右。现在还在读一个长篇小说大概是6本,现在读到第3本,所以之前读完的篇章并没有往读书记录里面加。果然手机是罪恶之源。心里虽然有些愧疚但是手机真的是一拿起来就放不下去。2024年计划在制定计划这个方面,我想制定一些靠谱的或者说对自己有吸引力的目标,以便自己能够完成。我参考了一些如何制定计划的书和文章,现在制定出下面几个计划,我想暂时分成这么几类吧。生活今年带着老婆孩子出去旅游一次,暂时就定在:上海、长沙、三亚、青岛这么几个城市,到时候再一起商量一下春天带孩子去公园踏青,去一次大兴的野生动物圆健康给父母买一个体检套餐,并陪着他们去体检一次去年自己的体检结果已经出现轻度脂肪肝和稍微的超重,所以今年的一个目标就是控制饮食加稍微的锻炼,使体重回归到正确的水平参加公司组织的体检并努力做到今年的体检结果都正常工作上尝试着引入新的工作方式,以及多调试一下项目代码,多做做笔记抽时间更新一下项目文档。特别是自己维护的那部分代码个人学习方面仍然坚持更新博客,我想今年以系列为主,就像之前更新vim系列一样,公司毕竟是做Office和PDF的,那就以这两个部分为主读书方面,今年给自己定的目标是读完12本书,平均每个月一本理财方面今年开始记录家庭支出和收入情况每个月流出一笔钱用作定投纳指和存银行定期个人娱乐方面《王国之泪》 玩100个小时,尽量不看攻略,看看今年能不能通关
2024年01月13日
6 阅读
0 评论
0 点赞
2023-04-18
从0开始自制解释器——重构代码
在上一篇文章中,完成了对括号的支持,这样整个程序就可以解析普通的算术表达式了。但是在解析两个括号的过程中发现有大量的地方需要进行索引的回退操作,索引的操作应该保证能得到争取的token,这个步骤应该放在词法分析的阶段,如果在语法分析阶段还要考虑下层词法分析的过程,就显得有些复杂了。而且随着后续支持的符号越来越多,可能又得在大量的地方进行这种索引变更的操作,代码将难以理解和维护。因此这里先停下来进行一次代码的重构。基本架构这里的代码我按照教程里面的结构进行组织。将按照程序的逻辑分为3层,最底层负责操作字符串的索引保证下次获取token的时候索引能在正确的位置。第二层是词法分析部分,负责给字符串的每个部分都打上对应的token。第三个部分是语法分析的部分,它负责解析之前设计的BNF范式,并计算对应的结果。详细的代码上面给出模块划分的概要可能没怎么说清楚,下面将通过代码来进行详细的说明。Token 模块为了支持这个设计,首先变更一下全局变量的定义,现在定义的全局变量如下所示extern Token g_currentToken; //当前token extern int g_nPosition; //当前字符索引的位置 extern char g_currentChar; //当前字符串之前通过 get_next_char() 来返回当前指向的token并变更索引的时候发现我们在任何时候想获取当前指向的字符时永远要变更索引,这样就不得不考虑在某些时候要进行索引的回退。比如在解析整数退出的时候,此时当前字符已经指向下一个字符了,但是我们在接下来解析其他符号的时候调用 get_next_char() 导致索引多增加了一个。这种情况经常出现,因此这里使用全局变量保存当前字符,只在需要进行索引增加的时候进行增加。另外我们不希望上层来直接操作这个索引,因此在最底层的Token模块提供一个名为 advance() 的函数用于将索引加一,并获取之后的字符。它的定义如下void advance() { g_nPosition++; // 如果到达字符串尾部,索引不再增加 if (g_nPosition >= strlen(g_pszUserBuf)) { g_currentChar = '\0'; } else { g_currentChar = g_pszUserBuf[g_nPosition]; } }这样在对应需要用到当前字符的位置就不再使用 get_next_char() , 而是改用全局变量 g_currentChar。例如现在的 skip_whitespace 函数现在的定义如下void skip_whitespace() { while (is_space(g_currentChar)) { advance(); } }这样我们在获取下一个token的时候只在必要的时候进行索引的递增。lex 模块由于打标签的工作交个底层的Token模块了,该模块主要用来实现词法分析的功能,也就是给各个部分打上标签,根据之前Token部分提供的接口,需要对 get_next_token 函数进行修改。bool get_next_token() { dyncstring_reset(&g_currentToken.value); while (g_currentChar != '\0') { if (is_digit(g_currentChar)) { g_currentToken.type = CINT; parser_number(&g_currentToken.value); return true; } else if (is_space(g_currentChar)) { skip_whitespace(); } else { switch (g_currentChar) { case '+': g_currentToken.type = PLUS; dyncstring_catch(&g_currentToken.value, '+'); advance(); break; case '-': g_currentToken.type = MINUS; dyncstring_catch(&g_currentToken.value, '-'); advance(); break; case '*': g_currentToken.type = DIV; dyncstring_catch(&g_currentToken.value, '*'); advance(); break; case '/': g_currentToken.type = MUL; dyncstring_catch(&g_currentToken.value, '/'); advance(); break; case '(': g_currentToken.type = LPAREN; dyncstring_catch(&g_currentToken.value, '('); advance(); break; case ')': g_currentToken.type = RPAREN; dyncstring_catch(&g_currentToken.value, ')'); advance(); break; case '\0': g_currentToken.type = END_OF_FILE; break; default: return false; } return true; } } return true; }在这个函数中,将不再通过输出参数来返回当前的token,而是直接修改全局变量。同时也不再使用get_next_char 函数来获取当前指向的字符,而是直接使用全局变量。并且在适当的时机调用advance 来实现递增。另外在上层我们直接使用 g_currentToken 拿到当前的token,而在适当的时机调用新增的eat() 函数来实现更新token的操作。bool eat(LPTOKEN pToken, ETokenType eType) { if (pToken->type == eType) { get_next_token(); return true; } return false; }该函数接受两个参数,第一个是当前token的值,第二个是我们期望当前token是何种类型。如果当前token的类型与期望的不符则报错,否则更新token。interpreter 模块该模块主要负责解析根据前面的BNF范式来完成计算并解析内容。这个模块提供三个函数get_factor、get_term、expr。这三个函数的功能没有变化,只是在实现上依靠lex 模块提供的功能。主要思路是直接使用 g_currentToken 这个全局变量来获得当前的token,使用 eat() 来更新并获得下一个token的值。这里我们以get_factor() 函数为例int get_factor(bool* pRet) { int value = 0; if (g_currentToken.type == CINT) { value = atoi(g_currentToken.value.pszBuf); *pRet = eat(&g_currentToken, CINT); } else { if (g_currentToken.type == LPAREN) { bool bValid = true; bValid = eat(&g_currentToken, LPAREN); value = expr(&bValid); bValid = eat(&g_currentToken, RPAREN); *pRet = bValid; } } return value; }与前面分析的相同,该函数主要负责获取整数和计算括号中子表达式的值。在解析完整数和括号中的子表达式之后,需要调用eat分别跳过对应的值。只是在识别到括号之后需要跳过左右两个括号。这样就完成了对应的分层,每层只负责自己该做的事。不用在上层考虑修改索引的问题,结构也更加清晰,未来在添加功能的时候也更加方便。剩下几个函数就不再贴出代码了,感兴趣的小伙伴可以去对应的GitHub仓库上查阅相关代码。
2023年04月18日
7 阅读
0 评论
0 点赞
2023-03-24
从0开始自制解释器——添加对括号的支持
在上一篇我们添加了对乘除法的支持,也介绍了BNF范式,并且针对当前的算术表达式写出了对应的范式,同时根据范式给出相应的代码实现。这篇我们将继续为算数表达式添加对括号的支持。对应的BNF 范式在上一篇我们给出了乘除法对应的范式<expr>::=<term>{(PLUS|MINUS)<term>} <term>::=<factor>{(DIV|MUL)<factor>} <factor>::={(0|1|2|3|4|5|6|7|8|9)}针对乘除法的优先级比加减法高,我们的做法是将乘除法单独作为一个部分,然后在最外层表达式中只处理加减法。基于这种思路,我们来看如何处理括号的问题。例如下面的算数表达式((1+2)*3+4) - (5 - 6 / 3)这里我们直接给出对应的文法,然后再来分析一下该如何由这个文法得到对应的表达式<expr>::=<term>{(PLUS|MINUS)<term>} <term>::=<factor>{(DIV|MUL)<factor>} <factor>::=({(0|1|2|3|4|5|6|7|8|9|)})|LPAREN<expr>RPAREN首先根据表达式,它应该由两个term来组成 expr = term - term接着看看两个term,它们并不是单纯的加法运算,所以两个term应该只有单纯的一个factor,也就是 expr = factor - factor因为最外层都有括号,所以再次展开 expr = (expr1) - (expr2)这时就又到了分析expr的过程了,左侧的expr最外层是一个加法,所以这里可以得到 expr1 = term + term右侧的expr 最外层是一个减法,也就是 expr2 = term - term结合最外层的表达式可以得到 expr = (term1 + term2) - (term3 - term4)term1 部分有一个乘法,所以它可以解析为 term1 = factor * factorterm2 部分就是单独的数字所以可以得到 term2 = factor,并且进一步得到 term2=4term3 部分就是单纯的数字,可以得到 term3 = factor,并且进一步得到 term3=5term4 部分有一个除法,所以它可以解析为 term3 = factor / factor此时整个表达式可以表示为 expr = (factor1 * factor2 + 4) - (5 - factor3 / factor4)factor1 本身也是一个括号,加表达式,所以它可以表示为 factor1 = (expr)factor2 是一个数字,所以它表示为 factor2 = 3factor3 是一个数字,所以它表示为 factor3 = 6factor4 是一个数字,所以它表示为 factor4 = 3此时表达式可以是 expr = ((expr1) * 3 + 4) - (5 - 6 / 3)此时再次分析这个 expr1 可以得到 expr1 = 1+2这个时候,整个表达式就出来了 expr = ((1+2) * 3 + 4) - (5 - 6 / 3)用图来表示大概可以表示如下代码实现有了范式,我们就可以按照范式来组织代码实现。首先我们先在 ETokenType 中添加针对括号的标签typedef enum e_TokenType { CINT = 0, //整数 PLUS, //加法 MINUS, //减法 DIV, //乘法 MUL, //除法 LPAREN, //左括号 RPAREN, //右括号 END_OF_FILE // 字符串末尾结束符号 }ETokenType;然后在 get_next_token 函数中添加对括号进行词法分析并打标签的功能bool get_next_token(LPTOKEN pToken) { char c = get_next_char(); dyncstring_reset(&pToken->value); if (is_digit(c)) { dyncstring_catch(&pToken->value, c); pToken->type = CINT; parser_number(&pToken->value); } else if(is_space(c)) { skip_whitespace(); return get_next_token(pToken); } else { switch (c) { case '+': pToken->type = PLUS; break; case '-': pToken->type = MINUS; break; case '*': pToken->type = DIV; break; case '/': pToken->type = MUL; break; case '(': pToken->type = LPAREN; break; case ')': pToken->type = RPAREN; break; case '\0': pToken->type = END_OF_FILE; break; default: return false; } } return true; }这里我对这个函数进行了一些改写,针对依靠单个字符就能打上标签的采用switc来进行处理,像空白字符、数字这种有多种字符类型的就采用普通的if处理。然后在get_oper 中添加对括号的识别 if (get_next_token(&token) && (token.type == PLUS || token.type == MINUS || token.type == DIV || token.type == MUL || token.type == LPAREN || token.type == RPAREN)) { oper = token.type; if (pRet) *pRet = true; }然后根据文法,get_factor 需要能够返回一个 expr的结果,所以这里需要添加以下代码 if (token.type == LPAREN) { bool bValid = true; value = expr(&bValid); if (!bValid) *pRet = false; if (get_next_token(&token) && token.type == RPAREN) *pRet = true; else *pRet = false; }如果我们得到的标签不为括号则按照原来的处理方式来处理,如果是括号,则将括号中的内容作为表达式并计算表达式的值,作为整数来返回。之前的expr 函数我们仅仅将结果打印并返回是否解析成功,这里需要做一些改进。我们使用一个传出参数来返回解析是否成功,而将计算结果作为值进行返回。另外需要特别注意的是,我们将反括号的判断放到了 get_factor 函数中,所以在 get_term 和 expr 中,遇到反括号应该考虑对位置索引进行递减,并且遇到反括号应该认为到达末尾并推出。这里的代码就不贴出来了。有兴趣的小伙伴可以看github上上传的代码。地址
2023年03月24日
6 阅读
0 评论
0 点赞
2023-03-22
从0开始自制解释器——添加对乘除法的支持
在上一篇中,我们实现了对减法的支持,并且介绍了语法图。针对简单的语法进行描述,用语法图描述当然是没问题的。但是针对一些复杂的语法进行描述,如果每个部分都通过语法图来描述就显得有些繁琐了。这篇我们先介绍另一种描述语法的方式,并进一步介绍一些关于语法分析的知识。BNF范式与上下文无关文法巴科斯范式 以美国人巴科斯(Backus)和丹麦人诺尔(Naur)的名字命名的一种形式化的语法表示方法,用来描述语法的一种形式体系,是一种典型的元语言。又称巴科斯-诺尔形式(Backus-Naur form)。它不仅能严格地表示语法规则,而且所描述的语法是与上下文无关的。它以递归方式描述语言中的各种成分,凡遵守其规则的程序就可保证语法上的正确性。它具有语法简单,表示明确,便于语法分析和编译的特点。BNF表示语法规则的方式为:非终结符用尖括号括起。每条规则的左部是一个非终结符,右部是由非终结符和终结符组成的一个符号串,中间一般以“::=”分开。具有相同左部的规则可以共用一个左部,各右部之间以直竖“|”隔开。所谓非终结符就是语言中某些抽象的概念不能直接出现在语言中的符号,终结符就是可以直接出现在语言中的符号。其实这些都是一些官话,初看起来只觉得拗口和难以理解,但是它的形式非常简单。它主要是用下面几个符号来表达含义使用<>来表示必须包含的部分使用[]来表示可选部分使用{}来表示可以重复0次或者无数次使用|来表示左右两边任选一部分,相当于OR使用::=来表示被定义为现在来给出具体的例子,我们都看过《西游记》,里面的取经4人组包括唐僧、孙悟空、猪八戒和沙僧。使用BNF范式进行定义,可以写成 <取经团队>::=<唐僧><孙悟空><猪八戒><沙僧>。我们再来举一个例子,我们知道一个文章由若干个段落组成、一个段落由若干个句子组成、一个句子由符合一定语法规则的汉字组成并且以句号作为结尾。我们简单的将句子的语法规则定义为主谓宾三个部分。而这里的主谓宾我们简单的用一些名词和动词来定义。因此这里的一系列结构可以定义为如下内容<文章>::={<段落>}<段落>::={<句子>}<句子>::=<主语><谓语><宾语>。<主语>::=人|狗|猫|天<谓语>::=吃|抓|下<宾语>::=饭|雨|肉|鱼根据这个表达式我们很容易的推出类似 人吃饭。、天下雨。、猫抓鱼。 这样的句子。相信到这里小伙伴应该明白BNF范式的一些基本概念和使用方式了。我们再来插入一个题外话,既然这里提到BNF范式是一种上下文无关文法,那什么是上下文、什么是上下文无关。先别着急了解概念,我们仍然通过例子来说明。在上述的句子的定义中,我们一共可以生成 4 * 3 * 4 = 48 种 结果,我们可以获得类似 人吃饭。、猫抓鱼。这种有意义的句子,也可能产生像天吃鱼。、人下雨 这种读起来感觉别扭的非正常语句。但是在上下文无关的语法中,主语宾语和谓语的内容没有相互关联,也就是说谓语和宾语的产生与主语无关。那上下文有关的文法呢?这里为了产生一些有意义的句子,我们给它加上一些限定。例如人后面只能接 吃 抓作为谓语、而当吃作为谓语时只能将 饭、肉、鱼作为宾语。针对这种需求,我们可以进行如下定义<句子>::=<主语><谓语><宾语>。<主语>::=人|狗|猫|天人<谓语>::=人(吃|抓)吃<宾语>::=吃(饭|肉|鱼)这样我们对这个产生式进行了一些限定,当主语是人的时候,谓语只能产生吃和抓这样的宾语。这种情况下的描述就被称之为上下文有关。上下文无关我自己的理解就是后续表达式的产生不依赖前面已产生的内容。而上下文有关的含义则与之相法。这个上下文就跟我们这么多年阅读理解题里面写的“请根据上下文来理解某个词表达了作者怎样的心情”这里的上下文类似。当然更加规范的说法就是,在应用一个产生式进行推导时,前后已经推导出的部分结果就是上下文。上下文无关就是只要文法的定义里面有一个定义,不管前面的产生串是什么都可以应用相应的产生推导后面的内容。代码编写上面的定义只是开胃菜,希望通过上面的描述,小伙伴能够理解BNF范式的应用,至于上下文无关和上下文有关。这些暂时不用考虑,毕竟我们目前还是在做上下文无关文法相关的内容。这里我们要支持乘法和除法,首先要做的就是在 ETokenType 结构中添加对乘法和除法相关的定义typedef enum e_TokenType { CINT = 0, //整数 PLUS, //加法 MINUS, //减法 DIV, //乘法 MUL, //除法 END_OF_FILE // 字符串末尾结束符号 }ETokenType;接着在 get_next_token和 get_oper() 函数中添加对这两个运算符的支持// get_next_token else if (c == '*') { pToken->type = DIV; dyncstring_catch(&pToken->value, '*'); } else if (c == '/') { pToken->type = MUL; dyncstring_catch(&pToken->value, '/'); } // get_oper if (get_next_token(&token) && (token.type == PLUS || token.type == MINUS || token.type == DIV || token.type == MUL)) { oper = token.type; if (pRet) *pRet = true; }现在词法分析部分已经可以支持乘除法的符号解析了。接着来完成语法分析的部分。首先我们来定义一下这个简单计算器的文法。<expr>::=<term>{<oper><term>} <term>::={0|1|2|3|4|5|6|7|8|9} <oper>::=PLUS|MINUS|DIV|MUL回忆一下上一节给出的语法图,理解这个表达式并不算困难。但是这里我们定义的文法有一个问题,就是从文法上体现不出运算的优先级。学过小学数学的都知道算数运算中优先计算乘除法,最后算加减法。但是根据这个文法我们无法体现出乘除法的优先级。因此这里我们需要修改定义。优先计算乘除法在文法上可以理解成,乘除法单独成一个部分,我们获取这个部分的计算结果最后与其他部分一起计算加减法。用BNF范式来体现就是<expr>::=<term>{(PLUS|MINUS)<term>} <term>::=<factor>{(DIV|MUL)<factor>} <factor>::={0|1|2|3|4|5|6|7|8|9}与语法图类似,范式也可以很容易转化为代码。允许出现多次的我们在代码实现上体现为循环。而文法中相关的定义我们直接采用一些get方式来获取对应被打上标记的值即可。上述文法描述可以转化为如下的c 代码int expr() { bool bRet = false; int result = get_term(&bRet); int bEOF = false; do { ETokenType oper = get_oper(&bRet); switch (oper) { case PLUS: { int num = get_term(&bRet); if(bRet) result += num; } break; case MINUS: { int num = get_term(&bRet); if(bRet) result -= num; } break; case END_OF_FILE: printf("%d\n", result); bEOF = true; break; default: bRet = false; break; } } while (bRet && !bEOF); if (!bRet) { printf("Syntax Error!\n"); } return 0; }上述expr的定义就是由一个term加若干个 +|- 和后面的若干个term 来组成,因此这里有一个循环。来取出所有term 和所有加减法,并进行计算。int get_term(bool* pValid) { int result = get_factor(pValid); int bEOF = false; do { ETokenType oper = get_oper(pValid); switch (oper) { case DIV: { int num = get_factor(pValid); if (*pValid) result *= num; } break; case MUL: { int num = get_factor(pValid); if (*pValid) result /= num; } break; case PLUS: case MINUS: { g_pPosition--; bEOF = true; } break; case END_OF_FILE: { g_pPosition--; bEOF = true; } } } while (pValid && !bEOF); return result; }而term 则是由整数以及若干个乘除法和另一个整数组成,所以代码中也用循环来取一直到取到不是这个term 定义所组成的部。注意这里与之前一样,当取到term的结束部分,我们仍然需要将索引进行递减。而最终的oper 和 factor 则保持原来的算法不变。好了,本篇到此也就结束了,小伙伴可以到该位置 取出代码来进行阅读和修改。
2023年03月22日
4 阅读
0 评论
0 点赞
2023-03-14
从0开始自制解释器——实现多个整数的加减法
在上一篇我们实现了一个可以计算两个多位整数加减法的计算器。本章我们继续来给这个计算器添加功能,这次要给它添加可以连续计算多个整数相加减的功能。例如我们可以计算 1 + 2 + 3 这样的表达式。语法图在正式写代码之前让我们先来学习一下一些基本的理论知识。这次要介绍的理论是语法图。什么是语法图呢?语法图是编程语言语法语法规则的图形表示。它体现了词法分析的运行规则。语法图直观的展示了在编程语言中哪些语句是符合语法的,哪些是不符合语法规范的。语法图的阅读非常容易,它类似于程序的流程图,只要顺着箭头指向的路径来读即可。与程序流程图类似,语法图中有些路径表示选择,有些表示循环。我们试着来读一下下面的语法图这张语法图表示的含义是,一个术语(term) 可选的跟上一个加号或者减号,而后面又需要跟上另一个术语。接着又可以有选择的跟上另一个加号或者减号。但是加号或者减号后面必须跟上另一个术语。这里又提到另一个单词,term 它的中文意思是术语。似乎很难用其他文字来解释何为术语。你只需要知道在这里它代表的是一个整数,它并不影响我们阅读这个语法图代码展示在上一篇中我们提到,将Token流识别为对应结构的过程被称之为词法分析,我们代码中的词法分析的实现主要在函数 expr 中。在这个函数中我们主要实现了词法分析以及最后的解释执行。我们按照语法图修改一下词法分析的代码我们先给出下面的伪代码获取第一个整数作为计算结果保存 while(解析到最后一个字符) { 获取操作符(+/-) switch(操作符) { case +: 获取下一个整数,如果不是整数则退出并报错 与结果相加 break; case -: 获取下一个整数,如果不是整数则退出并报错 与结果相减 break; } } 最终打印计算结果或者打印语法错误基于这个思路我们给出具体的实现代码int expr() { bool bRet = false; int result = get_term(&bRet); int bEOF = false; do { ETokenType oper = get_oper(&bRet); switch (oper) { case PLUS: { int num = get_term(&bRet); if(bRet) result += num; } break; case MINUS: { int num = get_term(&bRet); if(bRet) result -= num; } break; case END_OF_FILE: printf("%d\n", result); bEOF = true; break; default: bRet = false; break; } } while (bRet && !bEOF); if (!bRet) { printf("Syntax Error!\n"); } }这里为了便于理解,我将获取整数和操作符的模块又进行了一次封装,提供了两个函数分别是 get_term() 和 get_oper()。它们的代码如下int get_term(bool *pRet) { Token token = { 0 }; dyncstring_init(&token.value, DEFAULT_BUFFER_SIZE); int value = 0; if (get_next_token(&token) && token.type == CINT) { value = atoi(token.value.pszBuf); if (pRet) *pRet = true; } else { if (pRet) *pRet = false; } dyncstring_free(&token.value); return value; }ETokenType get_oper(bool* pRet) { Token token = { 0 }; dyncstring_init(&token.value, DEFAULT_BUFFER_SIZE); int oper = 0; if (get_next_token(&token) && (token.type == PLUS || token.type == MINUS)) { oper = token.type; if (pRet) *pRet = true; } else if (token.type == END_OF_FILE) { oper = END_OF_FILE; if (pRet) *pRet = true; } else { oper = -1; if (pRet) *pRet = false; } dyncstring_free(&token.value); return oper; }到此为止,就实现了多个整数的算术运算。整个实现过程的代码我都放到该位置。有兴趣的小伙伴可以自己对照着代码跟着我一起来实现属于自己的解释器。
2023年03月14日
5 阅读
0 评论
0 点赞
2023-03-08
从0开始自制解释器——实现多位整数的加减法计算器
上一篇我们实现了一个简单的加法计算器,并且了解了基本的词法分析、词法分析器的概念。本篇我们将要对之前实现的加法计算器进行扩展,我们为它添加以下几个功能计算减法能自动识别并跳过空白字符不再局限于单个整数,而是能计算多位整数提供一些工具函数首先为了支持减法,我们需要重新定义一下TokenType这个类型,也就是需要给 - 定义一个标志。现在我们的TokenType的定义如下typedef enum e_TokenType { CINT = 0, PLUS, MINUS, END_OF_FILE }ETokenType;由于需要支持多个整数,所以我们也不知道最终会有多少个字符,因此我们提供一个END_OF_FILE 表示我们访问到了最后一个字符,此时应该退出词法分析的过程。另外因为整数个数不再确定,我们也就不能按照之前的提供一个固定大小的数组。虽然可以提供一个足够大的空间来作为存储数字的缓冲,但是数字少了会浪费空间。而且考虑到之后要支持自定义变量和函数,采用固定长度缓冲的方式就很难找到合适的大小,太大显得浪费空间,太小有时候无法容纳得下用户定义的变量和函数名。因此这里我们采用动态长度的字符缓冲来保存。我们提供一个DyncString 的结构来保存这些内容#define DEFAULT_BUFFER_SIZE 16 // 动态字符串结构,用于保存任意长度的字符串 typedef struct DyncString { int nLength; // 字符长度 int capacity; //实际分配的空间大小 char* pszBuf; //保存字符串的缓冲 }DyncString, *LPDyncString; // 动态字符串初始化 // str: 被初始化的字符串 // size: 初始化字符串缓冲的大小,如果给0则按照默认大小分配空间 void dyncstring_init(LPDyncString str, int size); // 动态字符串空间释放 void dyncstring_free(LPDyncString str); //重分配动态字符串大小 void dyncstring_resize(LPDyncString str, int newSize); //往动态字符串中添加字符 void dyncstring_catch(LPDyncString str, char c); // 重置动态数组 void dyncstring_reset(LPDyncString str);它们的实现如下/*----------------------------动态数组的操作函数-------------------------------*/ void dyncstring_init(LPDyncString str, int size) { if (NULL == str) return; if (size == 0) str->capacity = DEFAULT_BUFFER_SIZE; else str->capacity = size; str->nLength = 0; str->pszBuf = (char*)malloc(sizeof(char) * str->capacity); if (NULL == str->pszBuf) { error("分配内存失败\n"); } memset(str->pszBuf, 0x00, sizeof(char) * str->capacity); } void dyncstring_free(LPDyncString str) { if (NULL == str) return; str->capacity = 0; str->nLength = 0; if (str->pszBuf == NULL) return; free(str->pszBuf); } void dyncstring_resize(LPDyncString str, int newSize) { int size = str->capacity; for (; size < newSize; size = size * 2); char* pszStr = (char*)realloc(str->pszBuf, size); str->capacity = size; str->pszBuf = pszStr; } void dyncstring_catch(LPDyncString str, char c) { if (str->capacity == str->nLength + 1) { dyncstring_resize(str, str->capacity + 1); } str->pszBuf[str->nLength] = c; str->nLength++; } void dyncstring_reset(LPDyncString str) { dyncstring_free(str); dyncstring_init(str, DEFAULT_BUFFER_SIZE); } /*----------------------------End 动态数组的操作函数-------------------------------*/另外提供一些额外的工具函数,他们的定义如下void error(char* lpszFmt, ...) { char szBuf[1024] = ""; va_list arg; va_start(arg, lpszFmt); vsnprintf(szBuf, 1024, lpszFmt, arg); va_end(arg); printf(szBuf); exit(-1); } bool is_digit(char c) { return (c >= '0' && c <= '9'); } bool is_space(char c) { return (c == ' ' || c == '\t' || c == '\r' || c == '\n'); }主要算法我们还是延续之前的算法,一个字符一个字符的解析,只是现在需要额外的将多个整数添加到一块作为一个整数处理。而且需要添加跳过空格的处理。首先我们对上次的代码进行一定程度的重构。我们添加一个函数专门用来获取下一个字符char get_next_char() { // 如果到达字符串尾部,索引不再增加 if (g_pPosition == '\0') { return '\0'; } else { char c = *g_pPosition; g_pPosition++; return c; } }expr() 函数里面大部分结构不变,主要算法仍然是按次序获取第一个整数、获取算术运算符、获取第二个整数。只是现在的整数都变成了采用 dyncstring 结构来存储int expr() { int val1 = 0, val2 = 0; Token token = { 0 }; dyncstring_init(&token.value, DEFAULT_BUFFER_SIZE); if (get_next_token(&token) && token.type == CINT) { val1 = atoi(token.value.pszBuf); } else { printf("首个操作数必须是整数\n"); dyncstring_free(&token.value); return -1; } int oper = 0; if (get_next_token(&token) && (token.type == PLUS || token.type == MINUS)) { oper = token.type; } else { printf("第二个字符必须是操作符, 当前只支持+/-\n"); dyncstring_free(&token.value); return -1; } if (get_next_token(&token) && token.type == CINT) { val2 = atoi(token.value.pszBuf); } else { printf("操作符后需要跟一个整数\n"); dyncstring_free(&token.value); return -1; } switch (oper) { case PLUS: { printf("%d+%d=%d\n", val1, val2, val1 + val2); } break; case MINUS: { printf("%d-%d=%d\n", val1, val2, val1 - val2); } break; default: printf("未知的操作!\n"); break; } dyncstring_free(&token.value); }最后就是最终要的 get_next_token 函数了。这个函数最主要的修改就是添加了解析整数和跳过空格的功能bool get_next_token(LPTOKEN pToken) { char c = get_next_char(); dyncstring_reset(&pToken->value); if (is_digit(c)) { dyncstring_catch(&pToken->value, c); pToken->type = CINT; parser_number(&pToken->value); } else if (c == '+') { pToken->type = PLUS; dyncstring_catch(&pToken->value, '+'); } else if (c == '-') { pToken->type = MINUS; dyncstring_catch(&pToken->value, '-'); } else if(is_space(c)) { skip_whitespace(); return get_next_token(pToken); } else if ('\0' == c) { pToken->type = END_OF_FILE; } else { return false; } return true; }在这个函数中我们先获取第一个字符,如果字符是整数则获取后面的整数并直接拼接为一个完整的整数。如果是空格则跳过接下来的空格。这两个是可能要处理多个字符所以这里使用了单独的函数来处理。其余只处理单个字符可以直接返回。parser_number 和 skip_whitespace 函数比较简单,主要的过程是不断从输入中取出字符,如果是空格则直接将索引往后移动,如果是整数则像对应的整数字符串中将整数字符加入。void skip_whitespace() { char c = '\0'; do { c = get_next_char(); } while (is_space(c)); // 遇到不是空白字符的,下次要取用它,这里需要重复取用上次取出的字符 g_pPosition--; } void parser_number(LPDyncString dyncstr) { char c = get_next_char(); while(is_digit(c)) { dyncstring_catch(dyncstr, c); c = get_next_char(); } // 遇到不是数字的,下次要取用它,这里需要重复取用上次取出的字符 g_pPosition--; }唯一需要注意的是,最后都有一个 g_pPosition-- 的操作。因为当我们发现下一个字符不符合条件的时候,它已经过了最后一个数字或者空格了,此时应该已经退回到get_next_token 函数中了,这个函数第一步就是获取下一个字符,因此会产生字符串被跳过的现象。所以这里我们执行 -- 退回到上一个位置,这样再取下一个就不会有问题了。最后为了能够获取空格的输入,我们将之前的scanf 改成 gets。这样就大功告成了。我们来测试一下结果最后的总结最后来一个总结。本篇我们对上一次的加法计算器进行了简单的改造,支持加减法、能跳过空格并且能够计算多位整数。在上一篇文章中,我们提到了Token,并且说过,像 get_next_token 这样给字符串每个部分打上Token的过程就是词法分析。get_next_token 这部分代码可以被称之为词法分析器。这篇我们再来介绍一下其他的概念。词位(lexeme): 词位的中文解释是语言词汇的基本单位。例如汉语的词位是汉字,英语的词位是基本的英文字母。对于我们这个加法计算器来说基本的词位就是数字以及 +\- 这两个符号parsing(语法分析)和 parser(语法分析器) 我们所编写的expr函数主要工作流程是根据token来组织代码行为。它的本质就是从Token流中识别出对应的结构,并将结构翻译为具体的行为。例如这里找到的结构是 CINT oper CINT。并且将两个int 按照 oper 指定的运算符进行算术运算。这个将Token流中识别出对应的结构的过程我们称之为语法分析,完成语法分析的组件被称之为语法分析器。expr 函数中即实现了语法分析的功能,也实现了解释执行的功能。
2023年03月08日
5 阅读
0 评论
0 点赞
2023-03-07
从0开始自制解释器——实现简单的加法计算器
为什么要学习编译器和解释器呢?文中的作者给出的答案有下面几个:为了深入理解计算机是如何工作的:一个显而易见的道理就是,如果你不懂编译器和解释器是如何工作的那么你就不明白计算机是如何工作的编译器和解释器用到的一些原理和编程技巧以及算法在其他地方也可以用到。学习编译器和解释器能够学到并强化这些技巧的运用为了方便日后能编写自己的编程语言或者专用领域的特殊语言接下来我们就从0开始一步一步的构建自己的解释器。跟着教程先制作一个简单的加法计算器,为了保证简单,这个加法计算器能够解析的表达式需要满足下面几点:目前只支持加法运算目前只支持两个10以内的整数的计算表达式之间不能有空格只能计算一次加法举一个例子来说,它可以计算诸如"1+2"、"5+6" 这样的表达式,但是不能计算像 "11+20"(必须是10以内)、"1.1+2"(需要两个数都是整数)、"1 + 2"(中间不能有空格)、"1+2+3"(只能计算一次加法)有了这些限制,我们很容易就能实现出来。实现的算法假设我们要计算表达式 5+6。这里主要的步骤是通过字符串保存表达式,然后通过索引依次访问每个字符,分别找到两个整数和加法运算符,最后实现两个整数相加的操作。第一步,我们的索引在表达式字符串的开始位置,解析得到当前位置的字符是一个整数,我们给它打上标记,类型为整形,值为5。第二步,索引向前推进,解析当前位置的字符是一个+。还是给它打上标记,类型为plus,值为+。第三步,索引继续前进,解析到当前位置的字符是一个整数,我们给它打上标记,类型为整形,值为6最后一步,根据得到的两个整数以及要执行的算术运算,我们将两个数直接进行相加得到最终结果具体的代码首先我们定义这个标记的类型,目前支持整数以及加法的标记typedef enum e_TokenType { CINT = 0, //整型 PLUS //加法运算符 }ETokenType; // 这里因为只支持10以内的整数,所以表示计算数字的字符只有一个,加上字符串最后的结束标记,字符数组只需要两个即可 typedef struct Token { ETokenType type; //类型 char value[2]; //值 }Token, *LPTOKEN;接着定义一些全局变量来保存算术运算的表达式和当前指针的索引char* g_pszUserBuf = NULL; char* g_pPosition = NULL;接着我们定义一个函数来模拟上述说到的不断解析每一个字符的过程bool get_next_token(LPTOKEN pToken) { char* sz = g_pPosition; g_pPosition++; pToken->value[0] = '\0'; if (*sz >= '0' && *sz <= '9') { pToken->type = CINT; pToken->value[0] = *sz; return true; } else if (*sz == '+') { pToken->type = PLUS; pToken->value[0] = *sz; return true; } else { pToken->value[0] = '\0'; return false; } }最后我们定义一个函数来执行获取每个标记并最终计算结果的操作int expr() { int val1 = 0, val2 = 0; Token token = { 0 }; if (get_next_token(&token) && token.type == CINT) { val1 = atoi(token.value); } else { printf("首个字符必须是整数"); return -1; } if (get_next_token(&token) && token.type == PLUS) { } else { printf("第二个字符必须是操作符,并且当前只支持 + 运算"); return -1; } if (get_next_token(&token) && token.type == CINT) { val2 = atoi(token.value); } printf("%d+%d=%d\n", val1, val2, val1 + val2); }在main函数里面我们只需要建立一个缓冲来保存字符,并且在循环中不断等待用户输入,完成解析并输出结果即可// 重制当前解析环境 void reset() { memset(g_pszUserBuf, 0x00, 16 * sizeof(char)); scanf_s("%s", g_pszUserBuf); g_pPosition = g_pszUserBuf; } int main() { g_pszUserBuf = (char*)malloc(16 * sizeof(char)); while (1) { printf(">>>"); reset(); if (strcmp(g_pszUserBuf, "exit") == 0) { break; } expr(); } return 0; }最终执行的结果如下最后的总结程序我们已经写完了,你可能觉得这个程序太简单了,只能做这点事情。别着急,后面将会逐步的去完善这个程序。以便它能实现更加复杂的运算。最后我们来引入一些概念性的东西:我们将输入内容按照一定规则打上的标记被称之为Token上述get_next_token函数体现的将一段字符串分割并打上有意义的标签的过程被称为词法分析。解释器工作的第一步就是将输入的字符串按照一定的规则转换为一系列有意义的标记。完成这个工作的组件被称之为词法分析器,也可以被称为扫描器或者分词器
2023年03月07日
5 阅读
0 评论
0 点赞
2023-03-04
从0开始自制解释器——综述
作为一个程序员,自制自己的编译器一直是一个梦想。之前也曾为了这个梦想学习过类似龙书、虎书这种大部头的书,但是光看理论总有一些云里雾里的感觉。看完只觉得脑袋昏昏沉沉并没有觉得有多少长进。当初看过《疯狂的程序员》这本书,书里说,真正能学会编译原理并不是靠看各种书然后通过相关考试,而是有一天你的领导找到你对你说:“小X啊,你是我们公司技术能力最强的人,咱们现在用的编译器性能有点跟不上,要不你看看能不能改进一下”。所以想要学习编译原理相关的知识首先要做的还是实践——实现一个自己的编译器。之前也看过类似的教你如何自制编译器,但是他们有一个共同的问题就是在很大程度上都借助第三方工具,隐藏了一些底层的细节。我希望的是每一行代码都是自己的完成的。所以一直怀揣着这个梦想直到最近我找到了一篇教程。一起写一个简单的编译器——魔力Python。这篇教程是实用Python完成的,但是这里我不打算使用Python,我打算实用最纯粹的C 语言来完成这个任务,我考虑使用C主要基于以下几个原因:Python 有一些封装的细节,不方便全方位的展示相关算法。原教程使用的就是Python,还用一样的话思路会受到教程的影响,要真正的理解需要自己一行行的敲代码,最好的方式就是用另一种语言来实现同样的算法现在市面上大多数都是用c来实现编译器,如果后续想要更近一步学习编译原理可以考虑在我完成的这版中很方便的加入一些新学的知识点自己有使用C的能力,而且用C写编译器自带装B属性基于以上理由,我准备开始跟着教程使用C来实现自己的解释器。这并不是一篇教程什么的,更多的是作为一篇实践笔记。而且根据我之前写的Vim专栏的经验来说,将它已专栏的形式发布出来之后鸽的可能性更小,更有动力来完成它。当然如果各位能从专栏中学到什么那就更好了。总之后面让我们一起进入学习编译原理的路程吧
2023年03月04日
13 阅读
1 评论
0 点赞
1
...
5
6
7
...
32