http://gist.github.com/1277224 从 8 行到 17259 行。从一个侧面也证明了把静态语言“编译”成动态语言有多困难。Dart 注定是个笑话。 ps. 今天 Eisa 的总行数只有 4643 行。
Tag Archives: compiler
自己动手开发编译器(十):miniSharp语法分析器
经过前面四篇的铺垫,我们终于拥有了编写语法分析器的强大工具,现在可以正式开发一门编程语言的语法分析器了。我们先来定义 miniSharp 的语法规则,然后根据 LL 文法的特点进行一些调整,最后借助解析器组合子生成完整的语法分析器。
自己动手开发编译器(九)CPS风格的解析器组合子
上回我们用函数式编程的方法,结合 Linq 语法,建立了一套解析器组合子方案,并能成功解析自定义文法的输入字符串。但是,上次做成的解析器组合子有个重要的功能没有完成——错误报告。作为编程语言的语法分析器,不能在遇到语法错误的时候简单地返回 null ,那样程序员就很难修复代码中的语法错误。我们需要的是准确报告语法错误的位置,更进一步,是程序中所有的语法错误,而不仅仅是头一个。后者要求解析器具有错误恢复的能力,即在遇到语法错误之后,还能恢复到正常状态继续解析。错误恢复不仅仅可以用在检测出所有的语法错误,还可以在存在语法错误的时候仍然提供有意义的解析结果,从而用于 IDE 的智能感知和重构等功能。手写的递归下降语法分析器可以很容易地加入错误恢复,但需要针对每一处错误手工编写代码来恢复。像 C#官方编译器,给出的语法错误信息非常全面、精确、智能,全都是手工编写的功劳。又回到我们是懒人这个残酷的事实,能不能在让解析器组合子生成的解析器自动具有错误恢复能力呢?
自己动手开发编译器(八)用Linq编写解析器组合子
上回我们说到手写递归下降语法分析器。手写递归下降的方式是目前很多编译器采用的方式,如果你想写一个商业质量的编译器,这是首选的方法。但是,一个完善的递归下降解析器需要的代码量也不少,如果要进行错误报告、错误恢复等等那代码量就更大了。作为懒人,我们有时想要一些小型语言的解析器,最好写起来像直接写文法的产生式一样,最好连错误报告和错误恢复也一并自动解决,可能吗?在过去很长一段时间,人们采用的方法是使用解析器生成器(parser generator)。因为不管是 LL 递归下降解析还是 LR 的移进归约解析,都可以很容易地用计算机来生成所需的规则。这样的著名工具有 yacc、 ANTLR 等。他们的特点是要用一种专门的语法格式来编写文法产生式,然后经过一个翻译程序生成解析器的代码。在函数式语言发展起来之后,有些人发现函数式语言的抽象能力非常强,甚至能够直接用函数式语言的代码来表达文法的产生式,并将解析器“组合”出来,这称作解析器组合子(parser combinator)。如今 C# 和 VB 语言也具有函数式语言相当的特征,特别是还有 Linq 助阵,以至于在 C# 和 VB 中也能享受组合子带来的方式。今天我们就来看看怎么做解析器的组合子。这一篇文字描述可能比较模糊,大家一定要认真地看代码,动手实验。
自己动手开发编译器(七)递归下降的语法分析器
上回我们说到语法分析使用的上下文无关语言,以及描述上下文无关文法的产生式、产生式推导和语法分析树等概念。今天我们就来讨论实际编写语法分析器的方法。今天介绍的这种方法叫做递归下降(recursive descent)法,这是一种适合手写语法编译器的方法,且非常简单。递归下降法对语言所用的文法有一些限制,但递归下降是现阶段主流的语法分析方法,因为它可以由开发人员高度控制,在提供错误信息方面也很有优势。就连微软C#官方的编译器也是手写而成的递归下降语法分析器。
自己动手开发编译器(六)上下文无关语言和文法
上回我们已经学习了语法分析第一阶段——词法分析的原理和工具,介绍了正则表达式、正则语言和DFA等工具。今次我们要开始涉及编译器前端最重要的阶段——语法分析。简单而言,这一步就要完整地分析整个编程语言的语法结构。上回说到词法分析的结果是将输入的字符串分解成一个个的单词流,也就是诸如关键字、标识符这样有特定意义的单词。一种完整的编程语言,必须在此基础上定义出各种声明、语句和表达式的语法规则。观察我们所熟悉的编程语言,其语法大都有某种递归的性质。例如四则运算与括号的表达式,其每个运算符的两边,都可以是任意的表达式。比如1+a是表达式,(1+a)*(2 – c)也是表达式,((a+b) + c) * (d – e)也是表达式。再比如if语句,其if的块和else的块中还可以再嵌套if语句。我们在词法分析中引入的正则表达式和正则语言无法描述这种结构,如果用DFA来解释,DFA只有有限个状态,它没有办法追溯这种无限递归。所以,编程语言的表达式,并不是正则语言。我们要引入一种表现能力更强的语言——上下文无关语言。
自己动手开发编译器(五)miniSharp语言的词法分析器
原文地址:http://www.cnblogs.com/Ninputer/archive/2011/06/13/2080094.html 多谢各位的一直以来的支持,我们今天总算走到了实践的一步。今天我们要用 VBF.Compilers 的词法分析库来开发一个小型语言——miniSharp 的词法分析。 miniSharp 是 C# 语言的子集, miniSharp 程序的语义就等于把它当做 C# 的语义。但是 miniSharp 只支持很少的语言特性,以降低制作编译器的难度。简单来说 miniSharp 有如下特征:
自己动手开发编译器(四)利用 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。因此,它的四个接受状态分别代表遇到了四种不同的单词。
自己动手开发编译器(三)有穷自动机 — 注记
说 NFA 是在“猜”实在不是什么好的比喻。如果说 DFA 只能一次有一个活跃状态的话,那么 NFA 一次则可以有多个活跃状态,每次转换的过程是:A’ ← A 读入字符 c 对所有 j ∈ A 对所有 s, 如果转换 (j, s) = c A’ ← A’ ∪ { s } 设置新的活跃状态为 A’ 在正则表达式的领域,如果是做字符串匹配的话, DFA 还真的不常用。因为对于规模为 n 的正则表达式,生成的 DFA 规模为 O(2n) ,生成时间也是这个渐进量级。因此,在需要进行字符串匹配这种场合下如此长的生成时间并非好主意。而 Ninputer 翻译正则到 NFA 的算法则是 Θ(n) 的量级,生成十分迅速。 而且更重要的是, NFA 方法可以很方便的扩展支持非正则语言(比如著名的反向引用),因为转换好的 NFA 里还包含着原始正则表达式的“结构”信息。但通常 DFA 转换完的形式就和正则表达式大相径庭,毫无相似点了。 正则表达式直接转 DFA [...]
自己动手开发编译器(三)有穷自动机
原文地址: http://www.cnblogs.com/Ninputer/archive/2011/06/10/2077991.html 上回我们说到用正则表达式来表示词法分析中的单词规则。正则表达式的规则很容易理解,但是正则表达式并不能直接用来解析字符串,我们还要引入一种适合转化为计算机程序的模型。今天我们引入的这种模型就叫做 有穷自动机(finite automation, FA),有时也叫有穷状态机(finite state machine)。有穷自动机首先包含一个有限状态 的集合,还包含了从一个状态到另外一个状态的转换。有穷自动机看上去就像是一个有向图,其中状态是图的节点,而状态转换则是图的边。此外这些状态中还必须有一个初始状态 和至少一个接受状态。下面的图展示了一个有穷自动机,有根从外边来的箭头指向的状态表示初始状态,有个黑圈的状态是接受状态: