#include <string>
#include <fstream>
using namespace std
int main()
{
ifstream ifile
ifile.open("test.c")里边写你的C文件名就可以了
if (ifile.is_open())
{
string line1,line2
while(!ifile.eof())
{
getline(ifile, line1)
line2 = line2 +"\n" + line1
}
ifile.close()
string::size_type pos = line2.find("float", 0)
if (pos!= line2.npos)
{
line2.replace(pos, 6, "double")
ofstream ofile
ofile.open("test.c")
if (ofile.is_open())
{
ofile<<line2
}
ofile.close()
}
}
return 0
}
lexbot如何用如下Lex的基本工作原理为:由正规式生成NFA,将NFA变换成DFA,DFA经化简后,模拟生成词法分析器。
其中正规式由开发者使用Lex语言编写,其余部分由Lex翻译器完成.翻译器将Lex源程序翻译成一个名为lex.yy.c的C语言源文件,此文件含有两部分内容:一部分是根据正规式所构造的DFA状态转移表,另一部分是用来驱动该表的总控程序yylex()。当主程序需要从输入字符流中识别一个记号时,只需要调用一次yylex()就可以了。为了使用Lex所生成的词法分析器,我们需要将lex.yy.c程序用C编译器进行编译,并将相关支持库函数连入目标代码
Lex源程序必须按照Lex语言的规范来写,其核心是一组词法规则(正规式)。一般而言,一个Lex源程序分为三部分,三部分之间以符号%%分隔。[第一部分:定义段]%%第二部分:词法规则段[%%第三部分:辅助函数段]
其中,第一部分及第三部分和第三部分之上的%%都可以省略(即上述方括号括起的部分可以省略)。以%开头的符号和关键字,或者是词法规则段的各个规则一般顶着行首来写,前面没有空格。
怎样写一个解释器解释器是比较深入的内容。虽然我试图从最基本的原理讲起,尽量让这篇文章不依赖于其它的知识,但是这篇教程并不是针对函数式编程的入门,所以我假设你已经学会了最基本的 Scheme 和函数式编程。如果你完全不了解这些,可以读一下 SICP 的第一,二章。当然你也可以继续读这篇文章,有不懂的地方再去查资料。我在这里也会讲递归和模式匹配的原理。如果你已经了解这些东西,这里的内容也许可以加深你的理解。
解释器其实不是很难的东西,可是好多人都不会写,因为在他们心目中解释器就像一个 Python 解释器那样复杂。如果你想开头就写一个 Python 解释器,那你多半永远也写不出来。你必须从最简单的语言开始,逐步增加语言的复杂度,才能构造出正确的解释器。这篇文章就是告诉你如何写出一个最简单的语言 (lambda calculus) 的解释器,并且带有基本的的算术功能,可以作为一个高级计算器来使用。
一般的编译器课程往往从语法分析(parsing)开始,折腾 lex 和 yacc 等工具。Parsing 的作用其实只是把字符串解码成程序的语法树(AST)结构。麻烦好久得到了 AST 之后,真正的困难才开始!而很多人在写完 parser 之后就已经倒下了。鉴于这个原因,这里我用“S-expression”来表示程序的语法树(AST)结构。S-expression 让我们可以直接跳过 parse 的步骤,进入关键的主题:语义(semantics)。
这里用的 Scheme 实现是 Racket。为了让程序简洁,我使用了 Racket 的模式匹配(pattern matching)。如果你用其它的 Scheme 实现的话,恐怕要自己做一些调整。
解释器是什么
首先我们来谈一下解释器是什么。说白了解释器跟计算器差不多。它们都接受一个“表达式”,输出一个 “结果”。比如,得到 '(+ 1 2) 之后就输出 3。不过解释器的表达式要比计算器的表达式复杂一些。解释器接受的表达式叫做“程序”,而不只是简单的算术表达式。从本质上讲,每个程序都是一台机器的“描述”,而解释器就是在“模拟”这台机器的运转,也就是在进行“计算”。所以从某种意义上讲,解释器就是计算的本质。当然,不同的解释器就会带来不同的计算。
需要注意的是,我们的解释器接受的参数是一个表达式的“数据结构”,而不是一个字符串。这里我们用一种叫“S-expression”的数据结构来表示表达式。比如表达式 '(+ 1 2) 里面的内容是三个符号:'+, '1 和 '2,而不是字符串“(+ 1 2)”。从结构化的数据里面提取信息很方便,而从字符串里提取信息很麻烦,而且容易出错。
从广义上讲,解释器是一个通用的概念。计算器实际上是解释器的一种形式,只不过它处理的语言比程序的解释器简单很多。也许你会发现,CPU 和人脑,从本质上来讲也是解释器,因为解释器的本质实际上是“任何用于处理语言的机器”。
递归定义 (recursive definition)
解释器一般都是“递归程序”。之所以是递归的原因,在于它处理的数据结构(程序)本身是“递归定义”的结构。算术表达式就是一个这样的结构,比如:'(* (+ 1 2) (* (- 9 6) 4))。每一个表达式里面可以含有子表达式,子表达式里面还可以有子表达式,如此无穷无尽的嵌套。看似很复杂,其实它的定义不过是:
“算术表达式”有两种形式:
1) 一个数
2) 一个 '(op e1 e2) 这样的结构(其中 e1 和 e2 是两个“算术表达式”)
看出来哪里在“递归”了吗?我们本来在定义“算术表达式”这个概念,而它的定义里面用到了“算术表达式”这个概念本身!这就构造了一个“回路”,让我们可以生成任意深度的表达式。
很多其它的数据,包括自然数,都是可以用递归来定义的。比如常见的对自然数的定义是:
“自然数”有两种形式:
1) 零
2) 某个“自然数”的后继
看到了吗?“自然数”的定义里面出现了它自己!这就是为什么我们有无穷多个自然数。
所以可以说递归是无所不在的,甚至有人说递归就是自然界的终极原理。递归的数据总是需要递归的程序来处理。虽然递归有时候表现为另外的形式,比如循环(loop),但是“递归”这个概念比“循环”更广泛一些。有很多递归程序不能用循环来表达,比如我们今天要写的解释器就是一个递归程序,它就不能用循环来表达。所以写出正确的递归程序,对于设计任何系统都是至关重要的。其实递归的概念不限于程序设计。在数学证明里面有个概念叫“归纳法”(induction),比如“数学归纳法”(mathematical induction)。其实归纳法跟递归完全是一回事。
我们今天的解释器就是一个递归程序。它接受一个表达式,递归的调用它自己来处理各个子表达式,然后把各个递归的结果组合在一起,形成最后的结果。这有点像二叉树遍历,只不过我们的数据结构(程序)比二叉树复杂一些。
模式匹配和递归:一个简单的计算器
既然计算器是一种最简单的解释器,那么我们为何不从计算器开始写?下面就是一个计算器,它可以计算四则运算的表达式。这些表达式可以任意的嵌套,比如 '(* (+ 1 2) (+ 3 4))。我想从这个简单的例子来讲一下模式匹配(pattern matching) 和递归 (recursion) 的原理。
下面就是这个计算器的代码。它接受一个表达式,输出一个数字作为结果,正如上一节所示。
(define calc
(lambda (exp)
(match exp匹配表达式的两种情况
[(? number? x) x] 是数字,直接返回
[`(,op ,e1 ,e2) 匹配并且提取出 *** 作符 op 和两个 *** 作数 e1, e2
(let ([v1 (calc e1)] 递归调用 calc 自己,得到 e1 的值
[v2 (calc e2)]) 递归调用 calc 自己,得到 e2 的值
(match op分支:处理 *** 作符 op 的 4 种情况
['+ (+ v1 v2)] 如果是加号,输出结果为 (+ v1 v2)
['- (- v1 v2)] 如果是减号,乘号,除号,相似的处理
['* (* v1 v2)]
['/ (/ v1 v2)]))])))
这里的 match 语句是一个模式匹配。它的形式是这样:
(match exp
[模式 结果]
[模式 结果]
... ...
)
它根据表达式 exp 的“结构”来进行“分支” *** 作。每一个分支由两部分组成,左边的是一个“模式”,右边的是一个结果。左边的模式在匹配之后可能会绑定一些变量,它们可以在右边的表达式里面使用。
一般说来,数据的“定义”有多少种情况,用来处理它的“模式”就有多少情况。比如算术表达式有两种情况,数字或者 (op e1 e2)。所以用来处理它的 match 语句就有两种模式。“你所有的情况,我都能处理”,这就是“穷举法”。穷举的思想非常重要,你漏掉的任何一种情况,都非常有可能带来麻烦。所谓的“数学归纳法”,就是这种穷举法在自然数的递归定义上面的表现。因为你穷举了所有的自然数可能被构造的两种形式,所以你能确保定理对“任意自然数”成立。
那么模式是如何工作的呢?比如 '(,op ,e1 ,e2) 就是一个模式(pattern),它被用来匹配输入的 exp。模式匹配基本的原理就是匹配与它“结构相同”的数据。比如,如果 exp 是 '(+ 1 2),那么 '(,op ,e1 ,e2) 就会把 op 绑定到 '+,把 e1 绑定到 '1,把 e2 绑定到 '2。这是因为它们结构相同:
'(,op ,e1 ,e2)
'( + 1 2)
说白了,模式就是一个可以含有“名字”(像 op, e1 和 e2)的“数据结构”,像 '(,op ,e1 ,e2)。我们拿这个带有名字的结构去“匹配”实际的数据(像 '(+ 1 2))。当它们一一对应之后,这些名字就自动被绑定到实际数据里相应位置的值。模式里面不但可以含有名字,也可以含有具体的数据。比如你可以构造一个模式 '(,op ,e1 42),用来匹配第二个 *** 作数固定为 42 的那些表达式。
看见左边的模式,你就像直接“看见”了输入数据的形态,然后对里面的元素进行 *** 作。它可以让我们一次性的“拆散”(destruct) 数据结构,把各个部件(域)的值绑定到多个变量,而不需要使用多个访问函数。所以模式匹配是非常直观的编程方式,值得每种语言借鉴。很多函数式语言里都有类似的功能,比如 ML 和 Haskell。
注意这里 e1 和 e2 里面的 *** 作数还不是值,它们是表达式。我们递归的调用 interp1 自己,分别得到 e1 和 e2 的值 v1 和 v2。它们应该是数字。
你注意到我们在什么地方使用了递归吗?如果你再看一下“算术表达式”的定义:
“算术表达式”有两种形式:
1) 一个数
2) 一个 '(op e1 e2) 这样的结构(其中 e1 和 e2 是两个“算术表达式”)
你就会发现这个定义里面“递归”的地方就是 e1 和 e2,所以 calc 在 e1 和 e2 上面递归的调用自己。如果你在数据定义的每个递归处都进行递归,那么你的递归程序就会穷举所有的情况。
之后,我们根据 *** 作符 op 的不同,对这两个值 v1 和 v2 分别进行 *** 作。如果 op 是加号 '+,我们就调用 Scheme 的加法 *** 作,作用于 v1 和 v2,并且返回运算所得的值。如果是减号,乘号,除号,我们也进行相应的 *** 作,返回它们的值。
所以你就可以得到如下的测试结果:
(calc '(+ 1 2))
=>3
(calc '(* 2 3))
=>6
(calc '(* (+ 1 2) (+ 3 4)))
=>21
一个计算器就是这么简单。你可以试试这些例子,然后自己再做一些新的例子。
什么是 lambda calculus?
现在让我们过渡到一种更强大的语言:lambda calculus。它虽然名字看起来很吓人,但是其实非常简单。它的三个元素分别是是:变量,函数,调用。用传统的表达法,它们看起来就是:
变量:x
函数:λx.t
调用:t1 t2
每个程序语言里面都有这三个元素,只不过具体的语法不同,所以你其实每天都在使用 lambda calculus。用 Scheme 作为例子,这三个元素看起来就像:
变量:x
函数:(lambda (x) e)
调用:(e1 e2)
一般的程序语言还有很多其它的结构,可是这三个元素却是缺一不可的。所以构建解释器的最关键步骤就是把这三个东西搞清楚。构造任何一个语言的解释器一般都是从这三个元素开始,在确保它们完全正确之后才慢慢加入其它的元素。
有一个很简单的思维方式可以让你直接看到这三元素的本质。记得我说过,每个程序都是一个“机器的描述”吗?所以每个 lambda calculus 的表达式也是一个机器的描述。这种机器跟电子线路非常相似。lambda calculus 的程序和机器有这样的一一对应关系:一个变量就是一根导线。一个函数就是某种电子器件的“样板”,有它自己的输入和输出端子,自己的逻辑。一个调用都是在设计中插入一个电子器件的“实例”,把它的输入端子连接到某些已有的导线,这些导线被叫做“参数”。所以一个 lambda calculus 的解释器实际上就是一个电子线路的模拟器。所以如果你听说有些芯片公司开始用类似 Haskell 的语言(比如 Bluespec System Verilog)来设计硬件,也就不奇怪了。
需要注意的是,跟一般语言不同,lambda calculus 的函数只有一个参数。这其实不是一个严重的限制,因为 lambda calculus 的函数可以被作为值传递 (这叫 first-class function),所以你可以用嵌套的函数定义来表示两个以上参数的函数。比如,(lambda (x) (lambda (y) y)) 就可以表示一个两个参数的函数,它返回第二个参数。不过当它被调用的时候,你需要两层调用,就像这样:
(((lambda (x) (lambda (y) y)) 1) 2)
=>2
虽然看起来丑一点,但是它让我们的解释器达到终极的简单。简单对于设计程序语言的人是至关重要的。一开头就追求复杂的设计,往往导致一堆纠缠不清的问题。
lambda calculus 不同于普通语言的另外一个特点就是它没有数字等基本的数据类型,所以你不能直接用 lambda calculus 来计算像 (+ 1 2) 这样的表达式。但是有意思的是,数字却可以被 lambda calculus 的三个基本元素“编码”(encoding) 出来。这种编码可以用来表示自然数,布尔类型,pair,list,以至于所有的数据结构。它还可以表示 if 条件语句等复杂的语法结构。常见的一种这样的编码叫做 Church encoding。所以 lambda calculus 其实可以产生出几乎所有程序语言的功能。中国的古话“三生万物”,也许就是这个意思。
求值顺序,call-by-name, call-by-value
当解释一个程序的时候,我们可以有好几种不同的“求值顺序”(evaluation order)。这有点像遍历二叉树有好几种不同的顺序一样(中序,前序,后序)。只不过这里的顺序更加复杂一些。比如下面的程序:
((lambda (x) (* x x)) (+ 1 2))
我们可以先执行最外层的调用,把 (+ 1 2) 传递进入函数,得到 (* (+ 1 2) (+ 1 2))。所以求值顺序是:
((lambda (x) (* x x)) (+ 1 2))
=>(* (+ 1 2) (+ 1 2))
=>(* 3 (+ 1 2))
=>(* 3 3)
=>9
但是我们也可以先算出 (+ 1 2) 的结果,然后再把它传进这个函数。所以求值顺序是:
((lambda (x) (* x x)) (+ 1 2))
=>((lambda (x) (* x x)) 3)
=>(* 3 3)
=>9
我们把第一种方式叫做 call-by-name (CBN),因为它把参数的“名字”(也就是表达式自己)传进函数。我们把第二种方式叫做 call-by-value (CBV),因为它先把参数的名字进行解释,得到它们的“值”之后,才把它们传进函数。
这两种解释方式的效率是不一样的。从上面的例子,你可以看出 CBN 比 CBV 多出了一步。为什么呢?因为函数 (lambda (x) (* x x)) 里面有两个 x,所以 (+ 1 2) 被传进函数的时候被复制了一份。之后我们需要对它的每一拷贝都进行一次解释,所以 (+ 1 2) 被计算了两次!
鉴于这个原因,几乎所有的程序语言都采用 CBV,而不是 CBN。CBV 常常被叫做“strict”或者“applicative order”。虽然 CBN 效率低下,与它等价的一种顺序 call-by-need 却没有这个问题。call-by-need 的基本原理是对 CBN 中被拷贝的表达式进行“共享”和“记忆”。当一个表达式的一个拷贝被计算过了之后,其它的拷贝自动得到它的值,从而避免重复求值。call-by-need 也叫“lazy evaluation”,它是 Haskell 语言所用的语义。
求值顺序不只停留于 call-by-name, call-by-value, call-by-need。人们还设计了很多种其它的求值顺序,虽然它们大部分都不能像 call-by-value 和 call-by-need 这么实用。
完整的 lambda calculus 解释器
下面是我们今天要完成的解释器,它只有39行(不包括空行和注释)。你可以先留意一下各个部分的注释,它们标注各个部件的名称,并且有少许讲解。这个解释器实现的是 CBV 顺序的 lambda calculus,外加基本的算术。加入基本算术的原因是为了可以让初学者写出比较有趣一点的程序,不至于一开头就被迫去学 Church encoding。
以下三个定义 env0, ent-env, lookup 是对环境(environment)的基本 *** 作:
空环境
(define env0 '())
扩展。对环境 env 进行扩展,把 x 映射到 v,得到一个新的环境
(define ext-env
(lambda (x v env)
(cons `(,x . ,v) env)))
查找。在环境中 env 中查找 x 的值
(define lookup
(lambda (x env)
(let ([p (assq x env)])
(cond
[(not p) x]
[else (cdr p)]))))
闭包的数据结构定义,包含一个函数定义 f 和它定义时所在的环境
(struct Closure (f env))
解释器的递归定义(接受两个参数,表达式 exp 和环境 env)
共 5 种情况(变量,函数,调用,数字,算术表达式)
(define interp1
(lambda (exp env)
(match exp 模式匹配 exp 的以下情况(分支)
[(? symbol? x) (lookup x env)]变量
[(? number? x) x] 数字
[`(lambda (,x) ,e)函数
(Closure exp env)]
[`(,e1 ,e2) 调用
(let ([v1 (interp1 e1 env)]
[v2 (interp1 e2 env)])
(match v1
[(Closure `(lambda (,x) ,e) env1)
(interp1 e (ext-env x v2 env1))]))]
[`(,op ,e1 ,e2) 算术表达式
(let ([v1 (interp1 e1 env)]
[v2 (interp1 e2 env)])
(match op
['+ (+ v1 v2)]
['- (- v1 v2)]
['* (* v1 v2)]
['/ (/ v1 v2)]))])))
解释器的“用户界面”函数。它把 interp1 包装起来,掩盖第二个参数,初始值为 env0
(define interp
(lambda (exp)
(interp1 exp env0)))
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)