为啥要写post呢?
hlinzhou · 2007-08-24
<< 原来久世同学所谓的革命是这么一回事……
|
首 页
|
Don Walser >>
2007-08-24
构造一个可运行的解释器(一):Prelude
- [
编程
]
版权声明
:转载时请以超链接形式标明文章原始出处和作者信息及
本声明
http://hlinzhou.blogbus.com/logs/7899010.html
note: This series of article follows the PLAI(
Programming Languages: Application and Interpretation
) book
1.准备
PLAI这本书里的程序是构建在一个Language Level上的,要想顺利运行其中的代码,首先要安装
DrScheme
,然后在DrScheme的文件菜单下选择“安装.plt文件”,填入
http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/plai-370.plt
,安装完成后重启DrScheme,从选择语言里选择PLAI再点一下运行按钮就行了。
虽然这个plt文件是针对DrScheme V370的,不过在V371下也能正常运行。plt里的具体内容可以查看C:\Documents and Settings\Administrator\Application Data\PLT Scheme\371\collects\plai下的文件,大都是一些define-syntax,像书中所使用的define-type过程就是在这些文件中定义的。
2.语法
PLAI所使用语言采用类lisp的语法,接受合法的s表达式,不过用{}代替了scheme中的()。
采用这种带括号语法的主要原因是可以利用scheme中现成的read过程,read过程将解释器构造中tokenizing和parsing这两个最费力的过程(要是首先要完成的两个过程)变成了tokenizing,reading和parsing三个过程,而且完成了tokenizing和reading,而我们只需要编写代码做第三步的parse就够了。
parser的目的则是将具体语法(Concrete Syntax)转化为抽象语法(Abstract Syntax),比如{+ 1 2}转换成PLAI中的抽象语法就是(add (num 1) (num 2))。
我们先从一个最简单的BNF描述开始(AE代表Arthmetic Expression)完成这个解释器:
<AE> ::= <num>
| {+ <AE> <AE>}
| {- <AE> <AE>}
合法的语法示例:
1. 3
2. {+ 3 4}
3. {+ {- 3 4} 7}
3.代码
;;假设送给parser的程序语法都是合法的,
;;即read返回的要么是一个数字要么是
;;第一个元素为运算符第二和第三个元素为子表达式的一个表(list)
;;parse: sexp->AE
;;将s表达式转换成算数表达式,s表达式即合乎lisp语法的表达式
(define-type AE
(num (n number?))
(add (lhs AE?)
(rhs AE?))
(sub (lhs AE?)
(rhs AE?)))
(define (parse sexp)
(cond
((number? sexp) (num sexp)) ;;表达式为一个数字
((list? sexp)
(case (first sexp)
((+) (add (parse (second sexp))
(parse (third sexp))))
((-) (sub (parse (second sexp))
(parse (third sexp))))))))
运行示例:
欢迎使用 DrScheme, 版本 371 [3m].
语言: PLAI.
> (parse (read))
{+ {- 4 5} 1}
(add (sub (num 4) (num 5)) (num 1))
> (parse (read))
随机文章:
构造一个可运行的解释器(二):Interpreting Arithmetic
2007-09-01
Don Walser
2007-08-31
用Dev-C++编译Python扩展
2007-06-14
集动态语言之大成者
2007-06-10
用中文写注释
2007-06-06
收藏到:
Del.icio.us
Tag:
Scheme
Interpreter
引用地址:
hlinzhou
发表于
12:10:25
|
编辑
|
继续话题
|
转发
|
推荐
发表评论
原始快照:web.archive.org