sin(x)

Category: 项目笔记

Scheme解释器实现(一):变量和环境

《计算机程序的构造与解释》的练习5.51要求我们用“低级语言”实现一个Scheme的求值器,同时我最近重新阅读了《C++ Primer》,重新学习了一下C++,所以计划使用C++来实现一个Scheme求值器。Scheme是一种“高级语言”,曾经先进的类型无关、垃圾回收、闭包调用、S表达式…,而我较为熟悉的C/C++/Java相比较而言就显得低级了。实现一个Scheme解释器的需要以下方面的考虑:

  • 弱类型:实现弱类型的基本方法就是设计一个特殊的类来模拟。如果使用弱类型的语言(如Python)来编写的话,这个问题自然可以无视了,
  • 实现垃圾回收:如果采用Java语言编写的话,垃圾回收就不需要考虑了,交给JVM来做就好。对于C++来说,最常用的技术就是RAII,采用引用计数来实现内存的管理。引用计数效率非常高,但是遇到循环引用的时候就很难解决。
  • 实现闭包:实现闭包的思路《计算机程序的构造与解释》文中已经有现成的,就是引入求值环境的概念。
  • 实现S表达式:S表达式相比其他语言来说非常简单,由于手写还是有些麻烦,所以使用Flex+Bison来解析S表达式。
  • 尾递归:利用尾调用无需保存调用者状态的特点来优化尾递归,将尾递归过程优化为迭代过程。

当然还需要考虑很多其他的东西,但是它们并不决定整个解释器结构。本篇文章主要讨论变量和运行环境的实现,对应于源代码中的variable.hppvariable.cppenvironment.hppenvironment.cpp

Continue reading

正则表达式实现:原理

这学期的创新实践尝试自己写一个正则表达式引擎,采用Thompson NFA实现,在网上找到了一篇很棒的文章,于是把它编译(Adapted Translation)过来用作原理解析。

正则表达式

正则表达式是一种描述字符串集合的标准。当一个字符串在一个正则表达式描述的字符串集合当中时,我们认为该字符串匹配了该正则表达式。

最简单的正则表达式就是字符。除了特殊的元字符*+?()|之外,所有的字符匹配自身。为了匹配元字符,需要借助\来转义,例如\+匹配加号。

两个正则表达式可以被串联或者并联,组成新的正则表达式:如果e1匹配s并且e2匹配t,那么e1|e2匹配s或者t,e1e2匹配st。

元字符*,+,和?表示重复操作:e1*匹配任意个匹配e1的字符串;e1+匹配一个以上,而e1?匹配至多一个。

对于各种操作,有着优先级之分,优先级最高的是并联,然后是串联,最后是重复。括号可以用来改变优先级。例如ab|cd相当于(ab)|(cd)ab*相当于a(b*)

Continue reading

Newer posts »

Copyright © 2019 sin(x)

Theme by Anders Noren, host by Coding PagesUp ↑