精华内容
下载资源
问答
  • 最近在看DSL的东西,对于外部DSL,写一个解释器是必不可少的。我试图归纳一下我学到的,以写一个解释器为目标,讲一下如果来实现一个可用的解释器。一个解释器通常可以分为一下几个阶段: 词法分析(Lexer) 语法分析...

    最近在看DSL的东西,对于外部DSL,写一个解释器是必不可少的。我试图归纳一下我学到的,以写一个解释器为目标,讲一下如果来实现一个可用的解释器。一个解释器通常可以分为一下几个阶段:

    1. 词法分析(Lexer)
    2. 语法分析(Parser, BNF, CFG, AST)
    3. 语义分析(AST的处理, annotated AST)
    4. 目标语言生成(stack-based)

    这里的解释器不包括目标语言的执行和运行时环境,如果需要类似于python/ruby的解析执行器的话,还需要bytecode-compiler, bytecode-interpreter和runtime。我们这里只谈解释的部分,不谈执行的部分。作为DSL我们大多都有宿主语言,通常也就我们生成的目标语言,有关执行这部分,我们交给目标语言去解决。换个说法,我们只讨论一个完整解释执行器的前端。

    当前编译技术已经得到极大发展,对于词法分析和语法分析,我们可以借助成熟的工具或库很快的完成,极大简化了写解释器的难度。对于一个解释器来说我们需要自己处理的部分基本上集中于语义的分析,即AST的处理和目标语言的生成。其实这里的AST的处理结果相当于一个与执行环境无关的中间语言表示,而目标语言的生成就是针对目标语言的特性,将annotated AST转换为目标语言以方便在目标语言的运行环境中运行。

    继续扯扯淡,Lisp语言的语法基本上就是直接写AST,直接用AST的表示法来表示程序,所以Lisp语法是最贴近于编译器的中间表示,开始可能根本就不是给一般人用的,谁知道这么多人喜欢用。Lisp之所以叫List Processer那是因为Lisp直接处理AST的数据结构表示即Nested List,所以才叫List Processor,一点都没有谦虚的意思。在数据结构里,表示树这种数据结构的,最简单直接的办法就是Nested List(通过Linked-List了来实现)。而且这种结构利于递归遍历,方便Stack-based执行或者代码的生成。

    1,词法分析

    词法分析是将源代码转换成tokens,这些tokens有些事关键字,有些是变量,有些是字面量,有些是语法结构,等等。比如:

    var s = 5;

    if(s > 0){

      print “greater than 5”

    }

    输出的tokens是[var, s, 5, ;, if, (, s, >, 0, ), {, print, “greater than 5”, }],这些tokens是有顺序的,但是没有具体的语法和语义。我们的词法分析器就是将源代码作为输入,输出就是这个tokens的序列。

    词法分析中我们会遇到一些问题,比如当我们看到whe的时候我们不知道这个是个变量名还是when关键字,这个需要看连续的4个字符才可以知道,这个就是LL(4),LL代表从左边依次读取,从最左边的w->wh-whe->when依次来推导出这个是关键字还是变量。

    这个我们这里不多讲,细节可以找本编译器的书来看看。有很多现成的工具和类库帮我们完成这样的工作,比如lex, flex, ply,等等。

    2,语法分析

    语法分析是帮我们分析这个token序列是否符合我们的语法,并且将语法分析结果用AST表示出来。既然是检查语法和按语法抽取出AST,那么我们就需要表示语法,通常我们使用Backs-Naur Format,也就是我们常说的BNF表示法。不过好笑的是BNF本身是个规范,不是具体的实现。也就是说同样BNF,不同的实现有不同的表示。比如:

    statement ::= statement | empty

    这个表示称为statement的产生式,也就是statement的语法规则,同样的有的BNF表示法是这样表示的

    statement –> statement or empty

    其中::=和->, |和or,是一样的意思。

    语法分析的结果就是符合语法的AST,也可以说是符合语法的一个实例。

    语法分析阶段我们也需要处理一些问题,比如为了解决算术的二义性,我们需要引入优先级(precedence),和结合性(associative)。

    语法分析也有现成的工具和类库可以使用比如yacc, bison, antlr, ply等等。

    3,语义分析

    符合语法的源代码不一定有意义,比如a/0,这个就是没有意义的,这个我们需要在语义处理阶段解决。

    待续…

    转载于:https://www.cnblogs.com/Jerry-Chou/p/3696370.html

    展开全文
  • 其实网上有不少人已经过类似一大把...或者还有一个更简单的,BrainFuck语言解释器,估计是最简单的了吧,感兴趣的可以做一个BF解释器出来。其实BF解释器我早做出来过一个了。也就几十行代码吧。 Scheme的解释器: ...

    其实网上有不少人已经写过类似一大把的文章了,王垠的那篇比较经典。

    我发一些比较经典的资料吧,主要以实现Lisp解释器为主,这玩意儿比较简单。或者还有一个更简单的,BrainFuck语言解释器,估计是最简单的了吧,感兴趣的可以做一个BF解释器出来。其实BF解释器我早做出来过一个了。也就几十行代码吧。

    Scheme的解释器:

    http://stackoverflow.com/questions/7526439/i-want-to-implement-a-scheme-interpreter-for-studying-sicp

    http://www.cs.utexas.edu/ftp/garbage/cs345/schintro-v14/schintro_toc.html

    还有知乎上搜索,解释器有vczh等人回答质量比较高的资料。这个坑慢慢来填。

    展开全文
  • 最近看到了一个系列文章,目前有14章,讲了如何用Python语言实现一套完整的解释器,来解释执行一个非常古老的语言——Pascal语言的源代码。 我看过以后觉得有点意义,循序渐进不疾不徐。但是原文的有点繁琐了。...

    解释器是虚拟机VM的重要组成部分,解释器其实和编译器在很多时候都是相近的概念,特别上实现过程中的概念。

    最近看到了一个系列文章,目前有14章,讲了如何用Python语言实现一套完整的解释器,来解释执行一个非常古老的语言——Pascal语言的源代码。

    我看过以后觉得有点意义,循序渐进不疾不徐。但是原文写的有点繁琐了。于是我花了几晚时间翻译和简化一下。目前共13章,后面陆续跟进。

     

    展开全文
  • 在接下来的几篇文章中,我们一起用Java写一个简单的编程语言(我称之为Lan)解释器。该语言不会有实际用处,仅仅作为演示Pratt解析算法。目标读者是对编程语言的解析感兴趣的初学者,当然我也是。先看看Lan的一些...

    在接下来的几篇文章中,我们一起用Java写一个简单的编程语言(我称之为Lan)解释器。该语言不会有实际用处,仅仅用于演示Pratt解析算法。目标读者是对编程语言的解析感兴趣的初学者,当然我也是。先看看Lan的一些代码:

    变量类型(数字,布尔值,字符串,函数,null)

    n = 123 + 1 - 23 * 21 / 3
    b = true 
    s = "hello lan"
    hello = func(name){print "hello world" + name}
    n = null

    控制流(打印乘法表)

    i = 1
    while i < 10 {
        j = 1
        while j < 10 {
            print i+"*"+j+"="+i*j
            j = j + 1
        }
        i = i + 1
    }

    函数(斐波拉契数)

    func fib(n) {
        if n == 0 {
            0
        } else if n == 1 {
            1
        } else {
            fib(n-1)+fib(n-2)
        }
    }
    foo = fib(10)
    print foo

    闭包

    makeAdder = func(numberToAdd) {
        return func(n) {
            n + numberToAdd
        }
    }
    adder = makeAdder(10)
    print adder(5)
    print makeAdder(20)(5)

    看起来还不错,实现起来也非常的简单。下一篇文章开始词法分析,也就是把源代码分解成一个个的词(Token)。

    展开全文
  • 我们也从头过了一个自己的词法分析,没有借助正则表达式或者Lex之类的工具,就生生的出来了。 在token流中,如何识别一个短语,或者说找到一个特定结构。这个过程叫解析或者句法分析。 用句法图来表...
  • //取出下一个字符,并且将索引加1 char c = code.charAt( index ++); //如果是空格,回车,制表符号直接跳过并进入下一次循环 if (c == ' ' || c == '\r' || c == '\t' ) continue ; //如果是换行...
  • 听说你想自己写一个 Lisp 解释器?欢迎入坑! Make-A-Lisp 这个项目的目标是让你更容易地实现你自己的 Lisp 解释器,使你在攀登 McCarthy (译注: 即, Lisp语言之父) 之山的过程中,避开那些需要顿悟的难题("Aha!" ...
  • 今天的目标是:搭建一个支持Pascal编程语言子集的全功能解释器。我们使用的Pascal的例子程序,可以被 Free Pascal compiler, fpc.编译通过。当然,我们希望我们的解释器可以成功解释通过。   例子程序代码如下...
  • 这种解释器叫此法导向解释器。它通常只扫描代码遍,适用于简单的语言。如果想做到分析更复杂的Pascal语言的结构,我们需要构建IR,也就是中间表示。我们的解析器负责生成IR,我们的解释器负责解释IR。 业界的经验...
  • 今天的主要话题是单目运算符。... 扩充现有的解释器,增加一个visit_UnaryOp方法,来解析单目运算农夫。 单目运算符就是只有有个操作数的操作码,优先级比+, -, *, /要高。可以简单理解为正负号就对了。   ...
  • Burger和Starbird合著过一本书《高效思考的五个要点》,里面提到Tony Plog,他是个吹喇叭的艺术家,开办了一个喇叭培训班。他班上都是成熟的喇叭演奏手。当这些演奏手吹奏复杂的歌曲的时候,吹的很精彩,但是当Tony...
  • 今天要如何解析和解释Pascal语言的定义、复合语句、赋值语句、变量。还要聊聊符号表以及存储和查找变量。   BEGIN BEGIN number := 2; a := number; b := 10 * a + 10 * number / 4; c := a - - b END; x...
  • 原创声明:这一个系列是翻译自https://ruslanspivak.com。插图是原文中自带的,同时我删除了一些没必要的解释。 “如果你不知道compiler是怎么工作的,那么你就不会清楚计算机是怎么工作的。如果你不是100%确定地...
  • 当你想弄明白一个复杂的系统,比如说interpreter或者是编译器。一开始它看起来好像是一团杂乱无章的毛球,你需要把这个毛球的线都拆出来,重新组成一个光滑的毛球。 这个过程可以是单线程的,也就是说每次你只拿一...
  • 如果一件事值得做,那就值得做过头儿. ...所以基本上,语义分析就是这样一个工作,让我们检查一个程序是不是合理,根据语言的定义,它的意义是什么。 什么样的程序是合理的?这涉及到语言的定义和语言的需求。比...
  • 过程声明是一个语言模块,定义了一个标识符(过程的名字)和对应的Pascal代码块。有点像C语言的函数。 严格定义: Pascal 过程没有返回值. Pascal 过程可以嵌套 可以有形参 这个是我们今天的测试Pascal程序:...
  • 今天将是不同寻常的一天。...上一章我们有一个factor规则,用来处理表达式中的基本单位。在我们的例子里就是整数。今天,我们将要添加另一个基本的单位——括号表达式。 这是修改过后的语法: expr和term的生...
  • 章我们讲讲多乘数法的计算,注意除法是整数的除法,比如9除以4等于2。 我还要使用种新的表达方式,上下文无关的语法书(简称为语法书),或者叫BNF(Backus Naur样式),来表示种编程语言的语句规则。多...
  • 前两章我们聊了怎么实现两整数的加和减,比如 “7 + 3” 和 “12 - 9”。 今天我们聊聊怎么实现任意多位数的加减,比如 “7 - 3 + 2 - 1”. 基本上,下面的图就是这种表达式的语法图: 什么是语法图呢?...
  • 未完待续 Table of Contents Scopes and scoped symbol tables Procedure declarations with formal parameters Procedure symbols Nested scopes Scope tree: Chaining scoped symbol tables ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 962
精华内容 384
关键字:

如何写一个解释器