（注：本文包含数学公式，使用 SVG 图形格式，请不要在 RSS 阅读器里阅读本文） 基本上每个程序员都会对 Quake 那个神一样的常量 0x5f3759df 感到惊奇。在 Quake 里，有一段代码是计算光照时候使用的函数，计算 ，那段代码写的真叫经典： float Q_rsqrt( float number ){ long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df – [...]
Tag Archives: math
自己动手开发编译器（四）利用 DFA 转换表建立扫描器
原文地址：http://www.cnblogs.com/Ninputer/archive/2011/06/12/2078671.html 上回我们介绍了两种有穷自动机模型——确定性有穷自动机 DFA 和非确定性有穷自动机，以及从正则表达式经过 NFA 最终转化为 DFA 的算法。有些同学表示还是难以理解 NFA 到底怎么转化为 DFA。所以本篇开头时我想再多举一个例子，看看 NFA 转化为 DFA 之后到底是什么样。首先我们看下面的 NFA，它是从一组词法分析所用的正则表达式转换而来的。这个 NFA 合并了 IF、 ID、 NUM、 error 这四个单词的 NFA。因此，它的四个接受状态分别代表遇到了四种不同的单词。
Posted in Depth, dotNET/mono, 中文 Also tagged algorithm, compiler, development, DFA, lexer, NFA, regex, theory, ~ninputer Leave a comment
自己动手开发编译器（三）有穷自动机
原文地址： http://www.cnblogs.com/Ninputer/archive/2011/06/10/2077991.html 上回我们说到用正则表达式来表示词法分析中的单词规则。正则表达式的规则很容易理解，但是正则表达式并不能直接用来解析字符串，我们还要引入一种适合转化为计算机程序的模型。今天我们引入的这种模型就叫做 有穷自动机（finite automation， FA），有时也叫有穷状态机（finite state machine）。有穷自动机首先包含一个有限状态 的集合，还包含了从一个状态到另外一个状态的转换。有穷自动机看上去就像是一个有向图，其中状态是图的节点，而状态转换则是图的边。此外这些状态中还必须有一个初始状态 和至少一个接受状态。下面的图展示了一个有穷自动机，有根从外边来的箭头指向的状态表示初始状态，有个黑圈的状态是接受状态：
Posted in Depth, dotNET/mono, 中文 Also tagged algorithm, compiler, development, DFA, lexer, NFA, regex, theory, ~ninputer 2 Comments