今天一哥们突然提到正则表达式的实现。嗯，当然没有例外，是用的有穷自动机啦。但是突然想到：工作中，某些程序需要匹配一系列的正则式。是不是可以用下推自动机实现呢？
下推自动机相比有穷自动机（叫有限状态自动机可能更形象些，可惜上课老师不是这么教的）多出了一个理论上长度不受限制的栈。如果将一系列需要逐一匹配的正则表达式预处理为一个下推自动机。那么运行的速度应该会大大提高。等闲下来考虑一下这个。
我们目前提高效率的方式是借助操作系统这门课的经验，用LRU淘汰掉较少使用的。可惜正在编写这一部分的哥们马上要离职了。天啊……
谢谢编译原理老师，在我点名未到的时候让我不及格。这样使我在毕业之前用很大心思去看相关的知识，至少让我知道往哪个方向去思考了。很多理论上的知识还是用得着的。嗯，理论，理论，说着都晕
Tags: 足球
文章 (RSS)