sin(x)

Page 7 of 10

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

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

词法分析

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

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

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

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

Continue reading

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

算法导论:跳跃表

如何的实现一个高效的有序集合?最先想到的就是二叉树。当然二叉树的性能会受到输入数据的影响,一般采用二叉树的改进版本比如红黑树、AVL树。最近在看算法相关的书的时候发现,原来链表经过一定的改进也可以实现高效插入删除,这就是跳跃表。网易公开课上也有关于跳跃表的公开课,Erik Demaine大神授课,浅显易懂。完整代码见Gist

有序链表

跳跃表的基础就是有序链表,所以首选需要实现一个有序的链表。对于有序链表,加入一个空的头部节点会让整个插入过程容易很多。

下面就是一个简单的有序链表,数据结构本身没有太大难度。

Continue reading

当年我也是有喜欢的妹子的

虽然凉了,但是是我高中不可或缺的一段记忆。

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

« Older posts Newer posts »

Copyright © 2019 sin(x)

Theme by Anders Noren, host by Coding PagesUp ↑