sin(x)

Category: 项目笔记

正则表达式实现:编译

Thompson在他1968年的论文当中介绍了多重状态的模拟。在他的设想当中,NFA由短小精悍的机器码表示,状态的变化只是指令的调用。实际上,Thompson把正则表达式编译成了机器码。四十年之后,计算机速度变快了,机器码运行不再必要。原文使用C语言实现,并且只能编译显式连接的后缀正则表达式,而本文实现了标准的简单正则表达式的编译。

表示

本项目(SimpleRegex)采用Java语言编写,Java的两个重要特性大大方便了正则表达式引擎的实现:

  • Unicode:原生支持Unicode支持,不必额外考虑Unicode字符匹配

  • 垃圾回收:可以免去复杂的NFA链接结构的内存管理

首先需要使用特定的数据结构来表示NFA,我们把NFA表示为关于状态的链接集合。

状态

NFA由状态(AbstractState)链接而成,其中可以分为三类状态:

Continue reading

30天自制操作系统:时钟和标准I/O

《30天自制操作系统》到30天结束了,但是操作系统还有很多地方可以完善。本文将给“纸娃娃操作系统”增加获取时钟的API以及标准I/O接口

获取时钟

时钟无论是对于人来说还是计算机来说都非常重要,但是“纸娃娃操作系统”还不能获取当前的计算机时钟,所以需要增加获取时钟这个API。

实现原理

在之前实现操作系统计时器的时候,已经接触过了PIT,PIT会在一定时间内产生信号,操作系统通过PIT的信号来进行计时,从而实现任务调度等依赖于计时的功能。除了PIT之外,计算机中还存在着一个RTC,用来维持计算机的时钟,具体的时钟信息被保存在了一个CMOS RAM中,寄存器地址选择端口号为0x70,寄存器数据读取端口号为0x71,而RAM中具体时钟信息对应的寄存器如下。

Continue reading

Scheme解释器实现(四):优化

变量容器、运行环境、解析器、解释器都已经开发完毕,已经可以使用这些基础设施搭建一个Scheme解释器了。对于一个成熟的额解释器来说,性能式非常关键的,本文将对解释器进行简单的优化。

统计信息

在优化过程中,我们需要想办法衡量优化的效果,所有需要对解释过程中一些操作次数进行记录。statistic.hppstatistic.cpp实现了统计功能,提供了以下接口:

void createVariable();
void destroyVariable();
void copyVariable();
void traceVariable();
void finalizeVariable();
void printStatistic();
void applyStart();
void applyEnd();

Continue reading

Scheme解释器实现(三):解释

解释

一旦解析获得了S表达式,解释过程就可以实现了。表达式有以下几种:

  • 自求值:数字和字符串;
  • 符号:(quote <quoted>)
  • 变量:符号;
  • 定义:(define <var> <val>)或者(define (<var> <arg1> <arg2> ... <argn>) <exp1> <exp2> ... <expn>)
  • 赋值:(set! <var> <val>)
  • 和:(and <exp1> <exp2> ... <expn>)
  • 或:(or <exp1> <exp2> ... <expn>)
  • 序列:(begin <exp1> <exp2> ... <expn>)
  • if:(if <predication> <consequence> <alternative>)
  • lambda:(lambda (<arg1> <arg2> ... <argn>) <exp1> <exp2> ... <expn>)
  • cond:(cond (<condition> <consequence>) ... (else <consquence>))
  • let:(let ((<var1> <val1>) ... (<varn> <valn>)) <exp1> ... <expn>)
  • 过程调用:(<proc> <arg1> ... <argn>)

Continue reading

Scheme解释器实现(二):解析

上一篇文章中,我们实现了Scheme中的变量和环境。有了这些基础设施,现在可以将原生的字符串解析为S表达式。Scheme的文法比较简单,使用手写的LL(1)文法解析器也是可行的,但是为了日后维护和修改上的方便,还是使用词法分析和句法分析工具更佳。本项目中,词法分析工具为Flex,句法分析工具为Bison。

词法分析

词法分析程序对应源代码中的lexer.lex,对于不同的token,处理方式如下:

  • 对于字符串、符号、数值:将值放入yylval变量中,同时对应返回token类型;

  • 对于(、)、’、,、EOF这些构成S表达式结构的字符:返回对应的token类型;

  • 对于空格和注释:将所有连续的空格和注释读入,返回一个表示空格分割的token类型。

Continue reading

« Older posts Newer posts »

Copyright © 2019 sin(x)

Theme by Anders Noren, host by Coding PagesUp ↑