程序设计语言原理课程设计-语言Mucha的

VIP免费

2025-01-13 8 0 408.7KB 20 页 5.9玖币

程序设计语言原理课程设计-语言Mucha的设计与实现
总体设计
语法设计
词法
语法
语义设计
形式语义
描述
实现方法
repl
宏定义
样例与结果
更进一步
与Scheme的差异
可行的计划
参考
- Mucha
SY206312
时间：2022-12-7
为了初探函数式领域，我希望设计并实现一个简单基础的函数式编程语言，或者更进一
步，Lisp方言。我对它的要求首先是 ，其次是 ，可读性高和成为
DSL。在本次作业，我大致实现了前2点。好在可读性可以通过强制要求编码规范实
现，然而DSL我着实没有想到合适的应用场景，也没有时间将本语言和某个特定的领域
结合。
我管这个语言叫Mucha，作为Scheme的子集。
我考虑了两种设计与实现思路：

第一种思路受启发于无意中看到的Lisp最简化BNF，只有短短9行，或许可以先实现这个

最小化的Lisp，再在其基础上自举，自己解析自己的S-expression，并定义新的行为。

不过这种思路很快就被否决，原因是自举的难度较大。

第二种思路是设计好语言，定义好诸多S-expression的行为，让解释器直接实现。

最后我对两个思路进行了折衷：先设计一个Scheme ，并予以实

现，让我叫它 mucha_core；后在该核心的基础上，通过自举一些辅助功能，从而达到

一定程度的易用。这里我使用了Scheme等语言的一个特点：其数据结构（list）与程序

的抽象语法树（AST）形式一致，这赋予了Scheme等语言编译时运行，运行时编译的

能力（不显式调用 evaluate）。

本语言为动态类型+强类型（与Python保持一致）。

本语言核心解释器使用Python编码，整个过程参考了Peter Norvig的文章 An ((Even

Better) Lisp) Interpreter，以及SICP的前五章。

我的解释器是传统的REPL，即Read-Evaluate-Print Loop。其中Read是分词阶段，它

将Token依次读出，交由Evaluate阶段进行s-expression的解析。通常认为，类Lisp语言

有两类语法，即Reader语法和Evaluate语法，前者决定那哪些字符串是合法的Token，

后者决定哪些s-expression是有意义的。

考虑到词法的完整性，我这里同时给出reader的行为以及若干保留字，尽管这些保留字

在reader眼中只是同质化的符号。同时，这些保留字的意义是可以在运行中覆盖的。

Reader可以识别的符号有：

left_par = (

right_par = )

unquote = ,

sp_unquote = ,@

str = "[<any character other than " or >| " | \]*"

quote = '

quasi-quote = `

comment = ;

number = [-+]?[0-9]*.?[0-9]+

constant = {number, str}

boolean = {#t, #f}

identifier = .* (剩下的都是标识符，或叫它Symbol)

上述Reader可由正则表达式实现，因此可转化为BNF进行形式化的展示，这里略过。正

则表达式:

tokenizers =

r'''\s*(,@|[('`,)]|"(?:[\\].|[^\\"])*"|;.*|[^\s('"`,;)]*)(.*)'''

在 other_symbol中，包含我们常用的运算符与Lisp（Scheme）常有的保留字。

other_symbol:

operator = {+, -, *, /, >, <, >=, <=, =}

math_op = {abs, expt, length, max, min, round} + (python)math.items

convention_scheme = {

define, define-macro,

car, cdr, append, apply, begin, cons, eq?, pair?, port?,

map, reduce, filter, lambda,

list, list?, not, number, symbol?, boolean?, procedure,

eval, load, read, call/cc, write, display, set!, dpset!,

open-input-port, close-input-port, open-output-file, close-output-file

}

为保持简便，我j将用保留字的原符号指代该符号。此外，我让数值类型和Python保持一

致。

我使用占用了以下保留字(可覆盖)：

macro = {

when, and, or, let*, let, unless, while, for,

inc, cadr, first, second, third, pop,

slot-enumerate, position?, get-position, combine,

zip, merge, scope({-})

}

Mucha的类型系统如下，实行动态类型（一个变量可绑定不同类型值）和强类型（不相

容类型间的计算会报错，行为与Python保持一致）：

class Symbol(str): pass

Number = (int, float)

Atom = (Symbol, Number)

List = list

Expression = (Atom, List)

class Procedure(object):

def __init__(self, params, body, env):

self.params, self.body, self.env = params, body, env

def __call__(self, *args):

local_env = Env(params=self.params, args=args, outer=self.env)

return eval(self.body, local_env, 'called by Proc(*Args);')

class PortInStream(object):

tokenizers = r'''\s*(,@|[('`,)]|"(?:[\\].|[^\\"])*"|;.*|[^\s('"`,;)]*)(.*)'''

def __init__(self, fp):

self.fp = fp

self.line = ''

self.regc = re.compile(PortInStream.tokenizers)

#...

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

程序设计语言原理课程设计-语言Mucha的设计与实现总体设计语法设计词法语法语义设计形式语义描述实现方法repl宏定义样例与结果更进一步与Scheme的差异可行的计划参考程序设计语言原理课程设计-语言Mucha的设计与实现SY206312朱思延时间：2022-12-7总体设计为了初探函数式领域，我希望设计并实现一个简单基础的函数式编程语言，或者更进一步，Lisp方言。我对它的要求首先是可以运行，其次是功能完整，可读性高和成为DSL。在本次作业，我大致实现了前2点。好在可读性可以通过强制要求编码规范实现，然而DSL我着实没有想到合适的应用场景，也没有时间将本语言和某个特定的领域结合。我管这个语言...

展开>> 收起<<

程序设计语言原理课程设计-语言Mucha的.pdf

共20页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

程序设计语言原理课程设计-语言Mucha的

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: