漫笔-341  谈论-2670  文章-0  trackbacks-0
  置顶漫笔
自我感觉良好系列代码:
    GacUI
    编程相关谈论1000人群:点击进入 
    IDE试验项目Release供给下载
    Cppblog12bet怎么样下载小程序:点击进入

语法剖析引荐书本
    我引荐的书:《Parsing Techniques》,还有它的第二版(part1.rarpart2.rar

编译原理系列文章:
   
跟vczh看实例学编译原理:系列文章(零)(一)(二)*new*
    怎样开发可装备语法剖析器:系列文章(一)(二)(三)(三点五)(四)(五)(六),(七)。
    怎样规划一门言语:系列文章(一)(二)(三)(四)(五)(六)(七)(八)(九)(十)(十一)(十二)
    浅谈面向方针言语的类型运算
    怎样手写语法剖析器《结构正则表达式引擎》和《结构可装备词法剖析器》
    运用高阶函数开发语法剖析器

运用我写的库开发语法剖析器系列文章:
    Vczh Library++语法剖析器开发攻略
    Vczh Library++3.0 12bet轻量级可装备语法剖析器,系列文章(一)188bet金博宝官网(三)(四)
    12bet轻量级可装备语法剖析器

    开发自己的IDE——Vczh Library++的IDE工程开发进程:十一十二

挖了坑却没空填上系列文章:
    手把手教你写脚本引擎(一)(二)(三)(四)(五)。Demo (一)
    12bet实用技巧:(一)(二)(三)(四)

著作及代码下载:
    JIT脚本引擎:CMinus 0.1版敞开下载 
    Vczh Library++ 2.0 GUI Framework 预览版代码以及示例程序
    Vczh Free Script 2.0 beta发布 
posted @ 2008-06-06 01:36 陈梓瀚(vczh)| 修正 保藏
  2015年1月9日
原本我都忘掉了,成果有网友提示我要写,我就来写一写。 现在的年终总结现已没什么内容了,主要是GacUI (www.gaclib.net)的开发实在太绵长。我现在在做拖控件程序GacStudio,期望在做完之后能够有Blend修正WPF的效果,在xml里边写data binding的时分不同的当地会有不同的intellisense。这当然是很难的,所以才想做。因而本年就把GacUI做到能够有Control Template、Item Template、Data Binding、XML Resource和加载,所以总算能够开端做GacStudio了。GacStudio整个会运用GacUI引荐的Data Binding来写。这有三个优点:1、查验Data Binding是否规划的好趁便抓bug;2、查验功用;3、证明GacUI是屌的,咱们都能够用。 我还在github开了一个数据库项目,在https://github.com/vczh/herodb,不过由于现在没有台式机,笔记本太烂装不了Ubuntu的虚拟机,所以暂停开发,比及我设备到了我再持续写。这个东西写完之后会集并进GacUI作为扩展的一部分,能够开许多脑洞,这个我就不讲了。 我觉得2014年最巨大的成果便是,我总算搬去西雅图了,啊哈哈哈哈。
posted @ 2015-01-09 06:58 陈梓瀚(vczh) 阅览(15410) | 谈论 (14)修正 保藏
  2014年7月15日

前次有人来要求我写一篇文章谈谈什么代码才是好代码,是谁我现已忘掉了,如同是AutoHotkey仍是啥的专栏的作者。放下那些古怪的条款不谈,靠谱的 代码有一个一同的特色,便是DRY。DRY便是Don't Repeat Yourself,其完结已被人谈了许多年了,可是简直一切人都会忘掉。

什么是DRY(Don't Repeat Yourself)

DRY 并不是指你不能仿制代码这么简略的。不能repeat的其实是信息,不是代码。要剖析一段代码里边的什么东西时信息,就跟给物理题做受力剖析相同,想每次 都做对其实不太简略。可是一份代码总是要不断的修补的,所以在这之前咱们要先做好TDD,也便是Test Driven Development。这儿我对自己的要求是覆盖率要高达95%,不论用什么办法,总归95%的代码的输出都要遭到查验。当有了足够多的测验做后台的时 候,不论你今后发作了什么,比如说你发现你Repeat了什么东西要改,你才干放心大胆的去改。并且从久远的视点来看,做好TDD能够将开宣布相同质量的代码的时刻缩短到30%左右(这是我自己的经验值) 。

什么是信息

信息这个词不太好用言语下界说,不过我能够举个比如。比如说你要把一个装备文件里边的字符串依照分隔符分解成几个字符串,你大约就会写出这样的代码:

// name;parent;description
void ReadConfig(const wchar_t* config)
{
    auto p 
= wcschr(config, L';');                            // 1
    if(!p) throw ArgumentException(L"Illegal config string"); // 2
    DoName(wstring(config, p));                               // 3
    auto q = wcschr(p + 1, L';');                             // 4
    if(!q) throw ArgumentException(L"Illegal config string"); // 5
    DoParent(wstring(p + 1, q);                               // 6
    auto r = wcschr(q + 1, L';');                             // 7
    if(r) throw ArgumentException(L"Illegal config string");  // 8
    DoDescription(q + 1);                                     // 9
}

这段短短的代码重复了多少信息?

  • 分隔符用的是分号(1、4、7)
  • 第二/三个片段的榜首个字符坐落榜首/二个分号的后边(4、6、7、9)
  • 格局检查(2、5、8)
  • 反常内容(2、5、8)

除了DRY以外还有一个问题,便是处理description的办法跟name和parent不相同,由于他后边再也没有分号了。

那这段代码要怎样改呢?有些人或许会想到,那把重复的代码抽取出一个函数就好了:

wstring Parse(const wchar_t& config, bool end)
{
    auto next 
= wcschr(config, L';');
    ArgumentException up(L
"Illegal config string");
    
if (next)
    {
        
if (end) throw up;
        wstring result(config, next);
        config 
= next + 1;
        
return result;
    }
    
else
    {
        
if (!end) throw up;
        wstring result(config);
        config 
+= result.size();
        
return result;
    }
}

// name;parent;description
void ReadConfig(const wchar_t* config)
{
    DoName(Parse(config, 
false));
    DoParent(Parse(config, 
false));
    DoDescription(Parse(config, 
true));
}

是不是看起来还很别扭,如同把代码修正了之后只把作业搞得更乱了,并且就算config对了咱们也会创立那个up变量,就仅仅是为了不 重复代码。并且这份代码还散宣布了一些欠好的滋味,由于关于Name、Parent和Description的处理办法仍是不能共同,Parse里边针对 end变量的处理看起来也是很重复,但实践上这是无法在这样规划的条件下消除的。所以这个代码也是欠好的,充其量仅仅比榜首份代码强一点点。

实 际上,代码之所以要写的好,之所以不能repeat东西,是由于产品狗总是要改需求,不改代码你就要死,改代码你就要加班,所以为了削减修正代码的苦楚, 咱们不能repeat任何信息。举个比如,有一天产品狗说,要把分隔符从分号改成空格!一会儿就要改两个当地了。description后边要加tag! 这样你处理description的办法又要改了由于他是以空格完毕不是0完毕。

因而针对这个片段,咱们需求把它改成这样:

vector<wstring> SplitString(const wchar_t* config, wchar_t delimiter)
{
    vector
<wstring> fragments;
    
while(auto next = wcschr(config, delimiter))
    {
        fragments.push_back(wstring(config, next));
        config 
= next + 1;
    }
    fragments.push_back(wstring(config));
    
return fragments; // 12bet11便是好!
}

void ReadConfig(const wchar_t* config)
{
    auto fragments 
= SplitString(config, L';');
    
if(fragments.size() != 3)
    {
        
throw ArgumentException(L"Illegal config string");
    }
    DoName(fragments[
0]);
    DoParent(fragments[
1]);
    DoDescription(fragments[
2]);
}

咱们能够发现,分号(L';')在这儿只呈现了一次,反常内容也只呈现了一次,并且处理name、parent和 description的代码也没有什么差异了,检查过错也更简略了。你在这儿还给你的Library增加了一个SplitString函数,说不定在以 后什么当地就用上了,比Parse这种专门的函数要强许多倍。

咱们能够发现,在这儿重复的东西并不只仅是仿制了代码,而是由于你把 同一个信息散播在了代码的各个部分导致了有许多附近的代码也散播在各个当地,并且还不是那么好经过抽成函数的办法来处理。由于在这种状况下,就算你把重复 的代码抽成了Parse函数,你把函数调用了几回实践上也等于重复了信息。因而正确的办法便是把做作业的办法变一下,写成SplitString。这个 SplitString函数并不是经过把重复的代码简略的抽取成函数而做出来的。去掉重复的信息会让你的代码的结构发作实质的改动

这个问题其实也有许多变体:

  • 不能有Magic Number。L';'呈现了许多遍,其实便是个Magic Number。所以咱们要给他个姓名,比如说delimiter。
  • 不要仿制代码。这个应该不必我讲了。
  • 解耦要做成正交的。SplitString尽管不是直接冲着读config来写的,可是它反映了一个在其它当地也会遇到的常见的问题。假如用Parse的那个版别,显着仅仅看起来处理了问题罢了,并没有给你带来任何额定的效益。

信息一旦被你repeat了,你的代码就会不同程度的呈现各种腐朽或许破窗,上面那三条其实仅仅我能想到的比较常见的表现方式。这件作业也告知咱们,当高手告知你什么什么不能做的时分,得想一想背面的原因,不然跟封建迷信有什么差异。

posted @ 2014-07-15 22:44 陈梓瀚(vczh) 阅览(14446) | 谈论 (9)修正 保藏
  2014年4月30日
RT
posted @ 2014-04-30 15:33 陈梓瀚(vczh) 阅览(12365) | 谈论 (5)修正 保藏
  2014年3月23日

文章中引证的代码均来自https://github.com/vczh/tinymoe

 

看了前面的三篇文章,咱们应该底子对Tinymoe的代码有一个开端的感觉了。在正确剖析"print sum from 1 to 100"之前,咱们首要得剖析"phrase sum from (lower bound) to (upper bound)"这样的声明。Tinymoe的函数声明又许多关于block和sentence的装备,不过这儿并不计划将一切细节,我会将要点放在怎样写一个针对无歧义语法的递归下降语法剖析器上。所以咱们这儿不会触及sentence和block的什么category和cps的装备。

 

尽管"print sum from 1 to 100"无法用无歧义的语法剖析的办法做出来,可是咱们能够借用对"phrase sum from (lower bound) to (upper bound)"的语法剖析的成果,动态结构能够剖析"print sum from 1 to 100"的语法剖析器。这种说法看起来如同很巨大上,可是其实并没有什么特别难的技巧。关于"结构"的问题我将鄙人一篇文章《跟vczh看实例学编译原理——三:Tinymoe与有歧义语法剖析》具体介绍。

 

在我之前的12bet怎么样里我从前写过《怎样手写语法剖析器》,这篇文章讲了一些简略的写递归下降语法剖析器的规矩,尽管许多人来信说这篇文章帮他们处理了许多问题,但实践上细节还不行丰厚,用来对编程言语做语法剖析的话,仍是会觉得杂乱性太高。这篇文章也一同作为《怎样手写语法剖析器》的弥补。好了,咱们开端进入无歧义语法剖析的主题吧。

 

咱们需求的榜首个函数是用来读token并判别其内容是不是咱们期望看到的东西。这个函数比较特别,所以独自拿出来讲。在词法剖析里边咱们现已把文件分行,每一行一个CodeToken的列表。可是由于一个函数声明独占一行,因而在这儿咱们只需求对每一行进行剖析。咱们判别这一行是否以cps、category、symbol、type、phrase、sentence或block最初,假如是那Tinymoe就以为这必定是一个声明,不然便是一般的代码。所以这儿假定咱们找到了一行代码以上面的这些token作为最初,所以咱们就要进入语法剖析的环节。作为整个剖析器的根底,咱们需求一个ConsumeToken的函数:

 

 

作为一个朴实的12bet11的项目,咱们应该运用STL的迭代器。其实在写语法剖析器的时分,依据迭代器的代码也比依据"token在数组里的下表"的代码要简略得多。这个函数所做的内容是这样的,它检查it指向的那个token,假如token的类型跟tokenType描绘的相同,他就it++然后回来true;不然便是用content和ownerToken来发作一个过错信息参加errors列表里,然后回来false。当然,假如传进去的参数it自身就等于end,那天然要发作一个过错。天然,函数体也非常简略:

 

那关于标识符和数字怎样办呢?明眼人必定一眼就看出来,这是给检查符号用的,比如左括号、右括号、冒号和要害字等。在声明里边咱们是不需求太杂乱的东西的,因而咱们还需求两外一个函数来输入标识符。Tinymoe现实上有两个针对标识符的语法剖析函数,榜首个是读入标识符,第二个不只需读入标识符还要判别是否到了行末不然报错:

 

在这儿我需求着重一个要点,在写语法剖析器的时分,函数的各式必定要整齐划一。Tinymoe的语法剖析函数有两个格局,别离是针对parse一行的一个部分,和parse一个文件的一些行的。ParseToEnd和ParseToFarest就归于parse一行的一个部分的函数。这种函数的格局如下:

  1. 回来值必定是语法树的一个节点。在这儿咱们以share_ptr<SymbolName>作为标识符的节点。一个标识符能够含有多个标识符token,比如说the Chinese people、the real Tinymoe programmer什么的。因而咱们能够简略地估测SymbolName里边有一个vector<CodeToken>。这个界说能够在TinymoeLexicalAnalyzer.h的最终一部分找到。
  2. 前两个参数别离是iterator&和指向结尾的iterator。结尾一般指"从这儿开端咱们不期望这个parser函数来读",当然这一般就意味着行末。咱们把"结尾"这个概念抽取出来,在某些状况下能够得到极大的优点。
  3. 最终一个token必定是vector<CodeError>&,用来寄存进程中遇到的过错。

 

除了函数格局以外,咱们还需求一切的函数都遵从某些前置条件和后置条件。在语法剖析里,假如你企图剖析一个结构可是不幸呈现了过错,这个时分,你有或许能够回来一个语法树的节点,你也有或许什么都回来不了。所以这儿就有两种状况:

  1. 你能够回来,那就证明尽管输入的代码有过错,可是你成功的进行了过错康复——实践上便是说,你觉得你自己能够猜想这份代码的作者实践是要表达什么意思——所以你要移动榜首个iterator,让他指向你榜首个还没读到的token,以便后续的语法剖析进程持续进行下去。
  2. 你不能回来,那就证明你康复不了,因而榜首个iterator不能动。由于这个函数有或许仅仅为了测验一下当时的输入是否满意一个什么结构。已然他不是,并且你康复不出来——也便是你猜想作者原本也不计划在这儿写某个结构——因而iterator不能动,表明你什么都没有读。

 

当你依据这样的格局写了许多语法剖析函数之后,你会发现你能够很简略用简略结构的语法剖析函数,拼凑出一个杂乱的语法剖析函数。可是由于Tinymoe的声明并没有一个编程言语那么杂乱,所以这种嵌套结构呈现的次数并不多,所以咱们这儿先越过关于嵌套的谈论,比及后边具体剖析"函数指针类型的参数"的时分天然会触及到。

 

说了这么多,我觉得也应该上ParseToEnd和ParseToFarest的代码了。首要是ParseToEnd:

 

咱们很快就能够发现,其实语法剖析器里边绝大多数篇幅的代码都是关于过错处理的,真实处理正确代码的部分其实很少。ParseToEnd做的作业不多,他便是从it开端一向读到end的方位,把一切不是标识符的token都丢掉,然后把一切遇到的标识符token都连起来作为一个完好的标识符。也便是说,ParseToEnd遇到相似"the real 100 Tinymoe programmer"的时分,他会回来"the real Tinymoe programmer",然后在"100"的当地报一个过错。

 

ParseToFarest的逻辑差不多:

 

仅仅当这个函数遇到"the real 100 Tinymoe programmer"的时分,会回来"the real",然后把光标移动到"100",可是没有报错。

 

看了这几个底子的函数之后,咱们能够进入正题了。做语法剖析器,当然仍是从文法开端。跟上一篇文章相同,咱们来测验直接结构一下文法。可是语法剖析器跟词法剖析器的文法的差异是,词法剖析其的文法能够 "界说函数"和"调用函数"。

 

首要,咱们来看symbol的文法:

SymbolName ::= <identifier> { <identifier> }

Symbol ::= "symbol" SymbolName

 

其次,便是type的声明。type是多行的,不过咱们这儿只关怀最初的相同:

Type ::= "type" SymbolName [ ":" SymbolName ]

 

在这儿,中括号代表可有可无,大括号代表重复0次或以上。现在让咱们来看函数的声明。函数的生命略为杂乱:

 

Function ::= ("phrase" | "sentence" | "block") { SymbolName | "(" Argument ")" } [ ":" SymbolName ]

Argument ::= ["list" | "expression" | "argument" | "assignable"] SymbolName

Argument ::= SymbolName

Argument ::= Function

 

Declaration ::= Symbol | Type | Function

 

在这儿咱们看到Function递归了自己,这是由于函数的参数能够是另一个函数。为了让这个参数调用起来愈加美丽一点,你能够把参数写成函数的方式,比如说:

pharse (the number) is odd : odd numbers

    return the number % 2 == 1

end

 

print all (phrase (the number) is wanted) in (numbers)

    repeat with the number in all numbers

        if the number is wanted

            print the number

        end

    end

end

 

print main

    print all odd numbers in array of (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

end

 

咱们给"(the number) is odd"这个判别一个数字是不是奇数的函数,起了一单个名叫"odd numbers",这单个名不能被调用,可是他等价于一个只读的变量保存着奇数函数的函数指针。所以咱们就能够把它传递给"print all (…) in (…)"这个函数的榜首个参数了。榜首个参数声明成函数,所以咱们能够在print函数内直接调用这个参数指向的odd numbers函数。

 

现实上Tinymoe的SymbolName是能够包含要害字的,可是我为了不让它写的太长,所以我就简略的写成了上面的那条式子。那Argument是否能够包含要害字呢?答案当然是能够的,仅仅当它以list、expression、argument、assignable、phrase、sentence、block开端的时分,咱们强行以为他有额定的含义。

 

现在一个Tinymoe的声明的榜首行都由Declaration来界说。当咱们识别出一个正确的Declaration之后,咱们就能够依据剖析的成果来对后边的行进行剖析。比如说symbol后边没有东西,所以就这么完了。type后边都是成员函数,所以咱们一向找到"end"停止。函数的函数体就更杂乱了,所以咱们会直接跳到下一个看起来像Declaration的东西——也便是以symbol、type、phrase、sentence、block、cps、category开端的行。这些进程都很简略,所以问题的要点便是,怎样依据Declaration的文法来处理输入的字符串

 

为了让文法能够真实的运转,咱们需求把它做成状况机。依据之前的描绘,这个状况及依然需求有"界说函数"和"履行函数"的才干。咱们能够先伪装他们是正则表达式,然后把整个状况机画出来。这个时分,"函数"自身咱们把它当作是一个跟标识符无关的输入,然后就能够得到下面的状况机:

 

 

这样咱们的状况机就暂时完结了。可是现在还不能直接把它转化成代码,由于当咱们遇到一个输入,而咱们能够选择调用函数,并且能够用的函数还不止一个的时分,那应该怎样办呢?答案便是要检查咱们的文法是不是有歧义。

 

文法的歧义是一个很有意思的问题。在咱们真的实践一个编译器的时分,咱们会遇到三种歧义:

  1. 文法自身便是有歧义的,比如说12bet闻名的A* B;的问题。当A是一个变量的时分,这是一个乘法表达式。当A是一个类型的时分,这是一个变量声明句子。假如咱们在语法剖析的时分不知道A究竟指向的是什么东西,那咱们底子无从得知这一句话究竟要取什么意思,所以要么回来过错,要么两个成果一同回来。这便是问法自身固有的歧义。
  2. 文法自身没有歧义,可是在剖析的进程中却无法在走每一步的时分都能够算出仅有的"下一个状况"。比如说C#闻名的A<B>C;问题。当A是一个变量的时分,这个句子是不成立的,由于C#的一个句子的根节点不能是一个操作符(这儿是">")。当A是一个类型的时分,这是一个变量声明句子。从成果来看,这并没有歧义,可是当咱们读完A<B>的时分依然不知道这个句子的结构究竟是取哪一种。实践上B作为类型参数,他也能够有B<C>这样的结构,因而这个B能够是恣意长的。也便是说咱们只需在">"完毕之后再多读几个字符才干得到正确的判别。比如说C是"(1)",那咱们知道A应该是一个模板函数。假如C是一个姓名,A八成应该是一个类型。因而咱们在做语法剖析的时分,只能两种状况一同考虑,并行处理。最终假如哪一个状况剖析不下去了,就简略的丢掉,剩余的便是咱们所需求的。
  3. 文法自身没有歧义,并且剖析的进程中只需你每一步都往后多看最多N个token,酒能够算出仅有的"下一个状况"究竟是什么。这个想必咱们都很了解,由于这个N便是LookAhead。所谓的LL(1)、SLR(1)、LR(1)、LALR(1)什么的,这个1其实便是N=1的状况。N当然纷歧定是1,他也能够是一个很大的数字,比如说8。一个文法的LookAhead是多少,这是文法自身固有的特点。一个LR(2)的状况机你非要在语法剖析的时分只LookAhead一个token,那也会遇到第二种歧义的状况。假如C言语没有typedef的话,那他便是一个带有LookAhead的没有歧义的言语了。

 

看一眼咱们方才写出来的文法,显着便是LookAhead=0的状况,并且连左递归都没有,写起来必定很简略。那接下来咱们要做的便是给"函数"算first set。一个函数的first set,望文生义便是,他的榜首个token都能够是什么。SymbolName、Symbol、Type、Function都不必看了,由于他们的文法榜首个输入都是token,那便是他们的first set。最终就剩余Argument。Argument的榜首个token除了list、expression、argument和assignable以外,还有Function。因而Argument的first set便是这些token加上Function的first set。假如文法有左递归的话,也能够用相似的办法做,只需咱们在函数A->B->C->…->A的时分,知道A正在核算所以回来空集就能够了。当然,只需左递归才会遇到这种状况。

 

然后咱们检查一下每一个状况,能够发现,任何一个状况出去的一切边,他承受的token或许函数的first set都是没有交集的。比如Argument的0状况,榜首条边承受的token、第二条边承受的SymbolName的first set,和第三条边承受的Function的first set,是没有交集的,所以咱们就能够判定,这个文法必定没有歧义。依照前次状况机到代码的写法,咱们能够机械的写出代码了。写代码的时分,咱们把每一个文法的函数,都写成一个12bet的函数。每到一个状况的时分,咱们看一下当时的token是什么,然后再决议走哪条边。假如选中的边是token边,那咱们就越过一个token。假如选中的边是函数边,那咱们不越过token,转而调用那个函数,让函数自己去跳token。《怎样手写语法剖析器》用的也是相同的办法,假如对这个进程不清楚的,能够再看一遍这个文章。

 

所以咱们到了界说语法树的时分了。走运的是,咱们能够直接从文法上看到语法树的形状,然后略微做一点微调就能够了。咱们把每一个函数都当作一个类,然后运用下面的规矩:

  1. 关于A、A B、A B C等的状况,咱们转化成class里边有若干个成员变量。
  2. 关于A | B的状况,咱们把它做成承继,A的语法树和B的语法树承继自一个基类,然后这个基类的指针就放在class里边做成员变量。
  3. 关于{ A },或许A { A }的状况,那个成员变量便是一个vector。
  4. 关于[ A ]的状况,咱们就当A看,差异仅仅,这个成员变量能够填nullptr。

 

关于每一个函数,要不要用shared_ptr来装则见仁见智。所以咱们能够直接经过上面的文法得到咱们所需求的语法树:

 

首要是SymbolName:

 

其次是Symbol:

 

然后是Type:

 

接下来是Argument:

 

最终是Function:

 

咱们能够看到,在Argument那里,一同出去的三条边就组成了三个子类,都承继自FunctionFragment。图中赤色的部分便是Tinymoe源代码里在上述的文法里呈现的那部分。至于为什么还有多出来的部分,其实是由于这儿的文法是为了叙说便利简化过的。至于Tinymoe关于函数声明的一切语法能够别离看下面的四个github的wiki page:

https://github.com/vczh/tinymoe/wiki/Phrases,-Sentences-and-Blocks

https://github.com/vczh/tinymoe/wiki/Manipulating-Functions

https://github.com/vczh/tinymoe/wiki/Category

https://github.com/vczh/tinymoe/wiki/State-and-Continuation

 

在本章的结尾,我将向咱们展现Tinymoe关于函数声明的那一个Parse函数。文章现已把一切要害的常识点都讲了,具体怎样做咱们能够上https://github.com/vczh/tinymoe 阅览源代码来学习。

 

首要是咱们的函数头:

 

回想一下咱们之前讲到的关于语法剖析函数的格局:

  1. 回来值必定是语法树的一个节点。在这儿咱们以share_ptr<SymbolName>作为标识符的节点。一个标识符能够含有多个标识符token,比如说the Chinese people、the real Tinymoe programmer什么的。因而咱们能够简略地估测SymbolName里边有一个vector<CodeToken>。这个界说能够在TinymoeLexicalAnalyzer.h的最终一部分找到。
  2. 前两个参数别离是iterator&和指向结尾的iterator。结尾一般指"从这儿开端咱们不期望这个parser函数来读",当然这一般就意味着行末。咱们把"结尾"这个概念抽取出来,在某些状况下能够得到极大的优点。
  3. 最终一个token必定是vector<CodeError>&,用来寄存进程中遇到的过错。

 

咱们能够清楚地看到这个函数满意上文提出来的三个要求。剩余来的参数有两个,榜首个是decl,假如不为空那代表调用函数的人现已帮你吧语法树给new出来了,你应该直接运用它。领一个参数ownerToken则是为了发作语法过错运用的。然后咱们看代码:

 

榜首步,咱们判别输入是否为空,然后依据需求报错:

 

第二步,依据榜首个token来确认函数的方式是phrase、sentence仍是block,并记载在成员变量type里:

 

第三步是一个循环,咱们依据当时的token(还记不记得之前说过,要先看一下token是什么,然后再决议走哪条边?)来决议咱们接下来要剖析的,是ArgumentFragment的两个子类(别离是VariableArgumentFragment和FunctionArgumentFragment),仍是一般的函数名的一部分,仍是说函数现已完毕了,遇到了一个冒号,因而开端剖析别号:

 

最终就不贴了,是检查格局是否满意语义的一些代码,比如说block的函数名有必要由参数开端啦,或许phrase的参数不能是argument和assignable等。

 

这篇文章就到此完毕了,期望咱们在看了这片文章之后,合作wiki关于语法的全面描绘,现已知道怎样对Tinymoe的声明部分进行语法剖析。紧接着便是下一篇文章——Tinymoe与带歧义语法剖析了,会让咱们了解,想对比如"print sum from 1 to 100"这样的代码做语法剖析,也不需求多杂乱的办法就能够做出来。

posted @ 2014-03-23 16:51 陈梓瀚(vczh) 阅览(7181) | 谈论 (2)修正 保藏
  2014年3月2日

文章中引证的代码均来自https://github.com/vczh/tinymoe

 

完结Tinymoe的榜首步天然是一个词法剖析器。词法剖析其所作的作业很简略,便是把一份代码切割成若干个token,记载下他们地点文件的方位,以及丢掉不必要的信息。可是Tinymoe是一个按行切割的言语,天然token列表也便是二维的,榜首维是行,第二维是每一行的token。在持续讲词法剖析器之前,先看看Tinymoe包含多少token:

  • 符号:(、)、,、:、&、+、-、*、/、\、%、<、>、<=、>=、=、<>
  • 要害字:module、using、phrase、sentence、block、symbol、type、cps、category、expression、argument、assignable、list、end、and、or、not
  • 数字:123、456.789
  • 字符串:"abc\r\ndef"
  • 标识符:tinymoe
  • 注释:-- this is a comment

 

Tinymoe关于token有一个特其他规则,便是字符串和注释都是单行的。因而假如一个字符串在没有完毕之前就遇到了换行,那么这种写法界说为你遇到了一个没有右双引号的字符串,需求报个错,然后下一行就不是这个字符串的内容了。

 

一个词法剖析器所需求做的作业,便是把一个字符串分解成描绘此法的数据结构。已然上面现已提到Tinymoe的token列表是二维的,因而数据结构必定会表现这个观念。Tinymoe的词法剖析器代码能够在这儿找到:https://github.com/vczh/tinymoe/blob/master/Development/Source/Compiler/TinymoeLexicalAnalyzer.h

 

首要是token:

CodeTokenType是一个枚举类型,符号一个token的类型。这个类型比较细化,每一个要害字有自己的类型,每一个符号也有自己的类型,剩余的按品种来分。咱们能够看到token需求记载的最要害的东西只需三个:类型、内容和代码方位。在token记载代码方位是非常重要的,正确地记载代码方位能够让你能够陈述带方位的过错、从语法树的节点还原成代码方位、甚至在调试的时分能够把指令也换成方位。

 

这儿需求提到的是,string_t是一个typedef,具体的声明能够在这儿看到:https://github.com/vczh/tinymoe/blob/master/Development/Source/TinymoeSTL.h。Tinymoe是彻底由规范的12bet11和STL写成的,可是为了习惯不同状况的需求,Tinymoe分为依靠code page的版别和Unicode版别。假如编译Tinymoe代码的时分声明晰大局的宏UNICODE_TINYMOE的话,那Tinymoe一切的字符处理将运用wchar_t,不然运用char。char的类型和Tinymoe编译器在运转的时分操作体系当时的code page是绑定的。所以这儿会有相似string_t啊、ifstream_t啊、char_t等类型,会在不同的编译选项的影响下指向不同的STL类型或许原生的12bet类型。github上的V12bet2013工程运用的是wchar_t的版别,所以string_t便是std::wstring。

 

Tinymoe的词法剖析器除了token的类型以外,必定还需求界说整个文件结构在词法剖析后的成果:

这个数据结构表现了"Tinymoe的token列表是二维的"的这个观念。一个文件会被词法剖析器处理成一个shared_ptr<CodeFIle>方针,CodeFile::lines记载了一切非空的行,CodeLine::tokens记载了该行的一切token。

 

现在让咱们来看词法剖析的具体进程。关于怎样从正则表达式结构词法剖析器能够在这儿(http://www.fometaux.com/vczh/archive/2008/05/22/50763.html)看到,不过咱们今日要讲一讲怎样人肉结构词法剖析器。办法其实是相同的,首要人肉结构状况机,然后把用状况机剖析输入的字符串的代码抄过来就能够了。可是很罕见人会解耦得那么开,由于这样写很简略看不懂,其次有或许会遇到一些极点状况是你无法用朴实的正则表达式来分词的,比如说12bet的raw string literal:R"tinymoe(这儿的字符串没有转义)tinymoe"。一个用【R"<一些字符>(】开端的字符串只能由【)<相同的字符>"】来完毕,要顺畅剖析这种状况,只能经过在状况机里边做hack才干处理。这便是为什么咱们人肉结构词法剖析器的时分,会把状况和动作都混在一同写,由于这样便于处理特别状况。

 

不过幸亏的是,Tinymoe并没有这种状况发作。所以咱们能够直接从状况机下手。为了简略起见,我鄙人面的状况机中去掉一切不是+和-的符号。首要,咱们需求一个开端状况和一个完毕状况:

 

首要咱们增加整数和标识符进去:

 

其次是加减和浮点:

 

最终把字符串和注释补全:

 

这样状况机就现已完结了。读过编译原理的或许会问,为什么完结状况都是由虚线而不是带有输入的完结指向的?由于虚线在这儿有特其他含义,也便是说它不能移动输入的字符串的指针,并且他还要担任增加一个token。当状况跳到End之后,那他就会变成Start,所以实践上Start和End是同一个状况。这个状况机也不是输入什么字符都能跳转到下一个状况的。所以当你发现输入的字符让你无路可走的时分,你便是遇到了一个词法过错

 

这样咱们的规划就算完结了,接下来便是怎样用12bet来完结它了。为了让代码更简略阅览,咱们应该给Start和1-9这么多状况起姓名,做法如下:

在这儿相似状况3这样的状况被我省掉掉了,由于这个状况仅有的出路便是虚线,所以跳到这个状况意味着你要马上履行虚线,也便是说你不需求做"跳到这个状况"这个动作。因而它不需求有一个姓名。

 

然后你只需依照下面的做法翻译这个状况机就能够了:

 

只需写到这儿,那么咱们就开端完结了词法剖析器了。其实任何体系的主要功用都是相对简略完结的,往往是非有必要的功用才需求花费许多的精力来完结,并且还很简略犯错。在这儿"非有必要的功用"便是——记载token的队伍号,还有保护CodeFile::lines避免空行的呈现!

 

尽管我现已做过了那么屡次词法剖析器,可是我依然无法趁热打铁写对,依然会出一些bug。面临编译器这种纯核算程序,debug的最好办法便是写单元测验。不过关于不了解单元测验的人来讲或许很难一会儿想到要做什么测验,在这儿我能够把我给Tinymoe谢的一部分单元测验在这儿贴一下。

 

榜首个,当然是传说中的"Hello, world!"测验了:

 

TEST_CASE和TEST_ASSERT(这儿暂时没有直接用到TEST_ASSERT)是我为了开发Tinymoe顺手撸的一个宏,能够在Tinymoe的代码里看到。为了检查咱们有没有粗枝大叶,咱们有必要检查词法剖析器的任何一个输出的数据,比如每一行有多少token,比如每一个token的行号列好内容和类型。我为了让这些单调的测验用例简略看懂,在这个文件(https://github.com/vczh/tinymoe/blob/master/Development/TinymoeUnitTest/TestLexicalAnalyzer.cpp)的最初能够看到FIRST_LINE、FIRST_TOKEN、TOKEN、LAST_TOKEN、NEXT_LINE、LAST_LINE是怎样界说的。其实吧这些宏打开,便是一个一般的遍历CodeFile::lines和CodeLine::tokens的程序,然后TEST_ASSERT一下CodeToken的每一个成员是否咱们所需求的值。我信任看到这儿许多人必定把要点放在宏和炫技上,而不是怎样规划测验用例上,这是有出路的程序员和没出路的程序员面临一份材料的反响的重要差异之一。没出路的程序员总是会把注意力放在一些不可思议的当地,其间一个比如便是"过早优化"。

 

第二个测验用例针对的是整数和浮点的输出和报错上,要点在于检查每一个token的列号是不是正确的核算了出来:

 

第三个测验用例的要点主要是-符号和—注释的剖析:

 

第四个测验用例则是测验字符串的escaping和在面临换行的时分是否正确的处理(之条件到字符串不能换行,遇到一个忽然的换行将会被当作短少双引号):

 

鉴于词法剖析原本内容也不多,所以这篇文章也不会太长。信任有出路的程序员也会在这儿得到一些编译原理以外的常识。下一篇文章将会描绘Tinymoe的函数头的语法剖析部分,将会描绘一个编译器的不带歧义的语法剖析是怎样人肉出来的。敬请期待。

posted @ 2014-03-02 23:44 陈梓瀚(vczh) 阅览(10760) | 谈论 (10)修正 保藏
  2014年3月1日

最近学习12bet11的variadic template argument,总算能够脱节用fpmacro模板来仿制一大堆代码的做法了,好开心。这个比如的main函数用lambda写了一个斐波那契数列的递归核算函数。跟以往不同的是,在Y函数的协助下,这个lambda表达是能够成功看到自己,然后递归调用。当然这依然需求用一般的12bet递归来完结,并不是λ-calculus那个巨大上的Y Combinator。

 

#include <functional>

#include <memory>

#include <iostream>

#include <string>

 

using namespace std;

 

template<typename TResult, typename ...TArgs>

class YBuilder

{

private:

    function<TResult(function<TResult(TArgs...)>, TArgs...)> partialLambda;

 

public:

    YBuilder(function<TResult(function<TResult(TArgs...)>, TArgs...)> _partialLambda)

        :partialLambda(_partialLambda)

    {

    }

 

    TResult operator()(TArgs ...args)const

    {

        return partialLambda(

            [this](TArgs ...args)

            {

                return this->operator()(args...);

            }, args...);

    }

};

 

template<typename TMethod>

struct PartialLambdaTypeRetriver

{

    typedef void FunctionType;

    typedef void LambdaType;

    typedef void YBuilderType;

};

 

template<typename TClass, typename TResult, typename ...TArgs>

struct PartialLambdaTypeRetriver<TResult(__thiscall TClass::*)(function<TResult(TArgs...)>, TArgs...)>

{

    typedef TResult FunctionType(TArgs...);

    typedef TResult LambdaType(function<TResult(TArgs...)>, TArgs...);

    typedef YBuilder<TResult, TArgs...> YBuilderType;

};

 

template<typename TClass, typename TResult, typename ...TArgs>

struct PartialLambdaTypeRetriver<TResult(__thiscall TClass::*)(function<TResult(TArgs...)>, TArgs...)const>

{

    typedef TResult FunctionType(TArgs...);

    typedef TResult LambdaType(function<TResult(TArgs...)>, TArgs...);

    typedef YBuilder<TResult, TArgs...> YBuilderType;

};

 

template<typename TLambda>

function<typename PartialLambdaTypeRetriver<decltype(&TLambda::operator())>::FunctionType> Y(TLambda partialLambda)

{

    return typename PartialLambdaTypeRetriver<decltype(&TLambda::operator())>::YBuilderType(partialLambda);

}

 

int _tmain(int argc, _TCHAR* argv[])

{

    auto fib = Y([](function<int(int)> self, int index)

    {

        return index<2

            ?1

            :self(index-1)+self(index-2);

    });

 

    for (int i = 0; i < 10; i++)

    {

        cout << fib(i) << " ";

    }

    cout << endl;

}

posted @ 2014-03-01 00:34 陈梓瀚(vczh) 阅览(9652) | 谈论 (3)修正 保藏
  2014年2月11日

自从《序》瞎说了快一个月之后,总算迎来了正片。之所以系列文章叫《看实例学编译原理》,是由于整个系列会经过带咱们一步一步完结Tinymoe的进程,来介绍编译原理的一些常识点。

 

可是榜首个系列还没到开端处理Tinymoe源代码的时分,首要的跟咱们讲一讲我规划Tinymoe的故事。为什么这种东西要比及现在才讲呢,由于之前没有文档,将了也是白讲啊。Tinymoe在github的wiki分为两部分,一部分是介绍语法的,另一部分是介绍一个最小的规范库是怎样完结出来的,地址在 https://github.com/vczh/tinymoe/wiki 不带问号的那些都是写完了的。

系列文章的方针

在介绍Tinymoe之前,先说一下这个系列文章的方针。Ideally,只需一个人看完了这个系列,他就能够鄙人面这些当地得到入门

  • 词法剖析
  • 歧义与不歧义的语法剖析
  • 语义剖析
  • 符号表
  • 全文CPS改换
  • 编译生成高效的其他言语的代码
  • 编译生成自己的指令集
  • 带GC的虚拟机
  • 类型推导(intersection type,union type,concept mapping)
  • 跨进程剖析(inter-procedural analyzing)

 

当然,这并不能让你成为一个大牛,可是至少自己做做试验,搞一点巨大上的东西骗师妹们是没有问题了。

Tinymoe规划的方针

尽管主意许多年前就现已有了,可是这次我想把它完结出来,是为了完结《怎样规划一门言语》的后续。光讲大道理是没有含义的,至少得有一个比如,让咱们知道这些作业究竟是什么姿态的。因而Tinymoe有一点教育的含义,不论是运用它仍是完结它。

 

首要,处理Tinymoe需求的常识点多,用于编译原理教育。已然是为了展现编译原理的根底常识,因而言语自身不或许是那种烂大街的C系列的东西。当然除了常识点以外,还会让咱们深入的了解到,难完结和难用,是彻底没有联系的!Tinymoe用起来可爽了,啊哈哈哈哈哈。

 

其次,Tinymoe简略嵌入其他言语的程序,作为DSL运用,能够调用宿主程序供给的功用。这严厉的来讲不算言语自身的功用,而是完结自身的功用。就算是12bet也能够规划为嵌入式,lua也能够被规划为编译成exe的。一个言语自身的规划并不会对怎样运用它有多大的约束。为了让咱们看了这个系列之后,能够写出至少可用的东西,而不只仅是写玩具,因而这也是规划的方针之一。

 

第三,Tinymoe语法优化于描绘杂乱的逻辑,而不是优化与杂乱的数据结构和算法(尽管也能够)。Tinymoe自身是不存在任何细粒度操控内存的才干的,并且尽管能够完结杂乱的数据结构和算法,可是自身描绘这些东西最多也就跟JavaScript相同简略——其实便是不简略。可是Tinymoe规划的时分,是为了让咱们把Tinymoe当成是一门能够规划DSL的言语,因而对杂乱逻辑的描绘才干特别强。仅有的条件便是,你懂得怎样给Tinymoe写库。很好的运用和很好地完结一个东西是相得益彰的。我在规划Tinymoe之初,许多pattern我也不知道,仅仅由于规划Tinymoe遵从了科学的办法,因而最终我发现Tinymoe居然具有如此强壮的描绘才干。当然关于读者们自身,也会在阅览系列文章的有相似的感觉。

 

最终,Tinymoe是一个动态类型言语。这朴实是我的个人爱好了。对一门动态类型言语做静态剖析那该多风趣啊,啊哈哈哈哈哈哈。

Tinymoe的规划哲学

当然我并不会为了写文章就无线进步Tinymoe的完结难度的。为了把他操控在一个正常水平,因而规划Tinymoe的榜首条便是:

 

一、小规模的言语中心+大规模的规范库

 

其实这跟12bet差不多。可是12bet由于想做的作业实在是太多了,比如说视图包容一切范式等等,因而就算这么做,依然让12bet自身包含的东西过于巨大(其实我仍是觉得12bet不难怎样办)。

 

言语中心小,完结起来当然简略。可是你并不能为了让言语中心小就献身什么功用。因而精心规划一个中心是有必要的,由于一切你想要可是不想参加言语的功用,从此就能够用库来完结了。

 

比如说,Tinymoe经过有条件地露出continuation,要求编译器在编译Tinymoe的时分做一次全文CPS改换。这个东西说简略也不是那么简略,可是至少比你做分支循环反常处理什么的悉数加起来要简略多了吧。所以我只供给continuation,剩余的操控流悉数用库来做。这样有三个优点:

  1. 言语简略,完结难度下降
  2. 为了让库能够发挥应有的效果,言语的功用的选择非常的正交化。不过这依然在必定的程度上进步了学习的难度。可是并不是一切人都需求写库对吧,许多人只需求会用库就够了。经过一点点的献身,正交化能够充分发挥程序员的幻想才干。这关于以DSL为意图的言语来说是不可或缺的。
  3. 规范库自身能够作为编译器的测验用例。你只需求预备足够多的测验用例来运转规范库,那么你只需用12bet(假定你用12bet来完结Tinymoe)来跑他们,那一切的规范库都会得到运转。运转成果假如对,那你对编译器的完结也就有决心了。为什么呢,由于规范库许多的运用了言语的各种功用,并且是无节操的运用。假如这样都能过,那一般的程序就更能过了。

 

说了这么多,那究竟什么是小规模的言语中心呢?这在Tinymoe上有两点表现。

 

榜首点,便是Tinymoe的语法元素少。一个Tinymoe表达式无非就只需三类:函数调用、字面量和变量、操作符。字面量便是那些数字字符串什么的。当Tinymoe的函数的某一个参数指定为不定个数的时分你还得供给一个tuple。托付(在这儿是函数指针和闭包的总称)和数组尽管也是Tinymoe的原生功用之一,可是对他们的操作都是经过函数调用来完结的,没有特其他语法。

 

简略地讲,便是除了下面这些东西以外你不会见到其他品种的表达式了:

1

"text"

sum from 1 to 100

sum of (1, 2, 3, 4, 5)

(1+2)*(3+4)

true

 

一个Tinymoe句子的品种就更少了,要么是一个函数调用,要么是block,要么是连在一同的几个block:

do something bad

 

repeat with x from 1 to 100

    do something bad with x

end

 

try

    do something bad

catch exception

    do something worse

end

 

有人或许会说,那repeat和try-catch就不是语法元素吗?这个真不是,他们是规范库界说好的函数,跟你自己声明的函数没有任何特其他当地。

 

这儿其实还有一个有意思的当地:"repeat with x from 1 to 100"的x其实是循环体的参数。Tinymoe是怎样给你自界说的block开洞的呢?不只如此,Tinymoe的函数还能够声明"引证参数",也便是说调用这个函数的时分你只能把一个变量放进去,函数里边能够读写这个变量。这些都是怎样完结的呢?学下去就知道了,啊哈哈哈哈。

 

Tinymoe的声明也只需两种,榜首种是函数,第二种是符号。函数的声明或许会略微杂乱一点,不过除了函数头以外,其他的都是相似装备相同的东西,简直都是用来界说"catch函数在运用的时分有必要是连在try函数后边"啊,"break只能在repeat里边用"啊,比如此类的信息。

 

Tinymoe的符号非常简略,比如说你要界说一年四季的符号,只需求这么写:

symbol spring

symbol summer

symbol autumn

symbol winter

 

symbol是一个"异乎寻常的值",也便是说你在两个module下面界说同名的symbol他们也是不相同的。一切symbol之间都是不相同的,能够用=和<>来判别。symbol便是靠"不相同"来界说其自身的。

 

至于说,那为什么不必enum呢?由于Tinymoe是动态类型言语,enum的类型自身是底子没有用武之地的,所以爽性就规划成了symbol。

 

第二点,Tinymoe除了continuation和select-case以外,没有其他原生的操控流支撑

 

这底子上归功于前辈发明continuation passing style transformation的劳绩,细节在今后的系列里边会讲。心急的人能够先看 https://github.com/vczh/tinymoe/blob/master/Development/Library/StandardLibrary.txt 。这个文件暂时包含了Tinymoe的整个规范库,里边界说了许多if-else/repeat/try-catch-finally等操控流,甚至连coroutine都能够用continuation、select-case和递归来做。

 

这也是小规模的言语中心+大规模的规范库所要表达的意思。假如能够供给一个feature A,经过他来完结其他必要的feature B0, B1, B2…的一同,将来说不定还有人能够出于自己的需求,开发DSL的时分界说feature C,那么只需A需求保存下来,一切的B和C都将运用库的办法来完结。

 

这么做并不是彻底有益无害的,仅仅害处很小,在"Tinymoe的完结难点"里边会具体阐明。

 

二、扩展后的东西跟原生的东西外观共同

 

这是很重要的。假如扩展出来的东西跟原生的东西长得不相同,用起来就觉得很傻逼。Java的string不能用==来判别内容便是这样的一个比如。尽管他们有的是理由证明==的反直觉规划是对的——可是反直觉便是反直觉,便是一个大坑。

 

这种比如还有许多,比如说go的数组和表的类型啦,go自身假如不要数组和表的话,是写不出长得跟原生数组和表相同的数组和表的。其实这也不是一个大问题,问题是go给数组和表的姿态搞特别化,还有那个反直觉的slice的赋值问题(会集法溢出!),相似的东西实在是太多了。一个东西特例太多,坑就无法避免。所以其实在我看来,go还不如给C言语加上erlang的actor功用完事。

 

反而12bet在这件作业上就做得很好。假如你对12bet不了解的话,有时分底子分不清什么是编译器干的,什么是规范库干的。比如说static_cast和dynamic_cast长得像一个模板函数,因而boost就能够用相似的办法参加lexical_cast和针对shared_ptr的static_pointer_cast和dynamic_pointer_cast,整个规范库和言语自身天衣无缝。这姿态做的优点是,当你在培育对言语自身的直觉的时分,你也在培育对规范库的直觉,培育直觉这件作业你不必做两次。你对一个东西的直觉越准,学习新东西的速度就越快。所以12bet的规划刚好能够让你在熬过榜首个阶段的学习之后,后边都觉得无比的轻松。

 

不过具体到Tinymoe,由于Tinymoe自身的语法元素太少了,所以这个做法在Tinymoe身上表现得不显着。

Tinymoe的完结难点

首要,语法剖析需求对Tinymoe程序处理三遍。Tinymoe关于句子规划使得对一个Tinymoe程序做语法剖析不是那么直接(尽管比12bet什么的仍是简略多了)。举个比如:

module hello world

 

phrase sum from (lower bound) to (upper bound)

end

 

sentence print (message)

end

 

phrase main

    print sum from 1 to 100

end

 

榜首遍剖析是词法剖析,这个时分得把每一个token的行号记住。第二遍剖析是不带歧义的语法剖析,方针是把一切的函数头抽取出来,然后组成一个大局符号表。第三遍剖析便是对函数体里边的句子做带歧义的语法剖析了。由于Tinymoe答应你界说变量,所以符号表必定是一边剖析一边修正的。所以关于"print sum from 1 to 100"这一句,假如你没有发现"phrase sum from (lower bound) to (upper bound)"和"sentence print (message)",那底子无从下手。

 

还有另一个比如:

module exception handling

 

 

phrase main

    try

        do something bad

    catch

        print "bad thing happened"

    end

end

 

当语法剖析做到"try"的时分,由于发现存在try函数的界说,所以Tinymoe知道接下来的"do something bad"归于调用try这个块函数所需供给的代码块里边的代码。接下来是"catch",Tinymoe怎样知道catch是接在try后边,而不是放在try里边的呢?这依然是由于catch函数的界说告知咱们的。关于这方面的语法常识能够点击这儿检查

 

正由于如此,咱们需求首要知道函数的界说,然后才干剖析函数体里边的代码。尽管这在必定程度上形成了Tinymoe的语法剖析杂乱度的提高,可是其杂乱度自身并不高。比12bet简略就不说了,就算是C、C#和Java,由于其语法元素太多,导致不需求屡次剖析所下降的杂乱度被彻底的抵消,成果跟完结Tinymoe的语法剖析器的难度平起平坐。

 

其次,CPS改换后的代码需求特别处理,不然直接履行简略导致call stack堆集的没用的东西过多。由于Tinymoe能够自界说操作符,所以操作符跟12bet相同在编译的时分被转化成了函数调用。每一个函数调用都是会被CPS改换的。尽管每一行的函数调用次数不多,可是假如你的程序油循环,循环是经过递归来描绘(而不是完结,由于CPS改换后Tinymoe做了优化,所以不存在实践上的递归)的,假如直接履行CPS改换后的代码,算一个1加到1000都会导致stack overflow。可见其call stack里边堆积的closure数量之巨大。

 

我在做Tinymoe代码生成的试验的时分,为了简略我在单元测验里边直接发作了对应的C#代码。一开端没有处理CPS而直接调用,程序不只慢,并且简略stack overflow。可是咱们知道(其实你们今后才会知道),CPS改换后的代码里边简直一切的call stack项都是糟蹋的,因而我把整个在生成C#代码的时分修正成,假如需求调用continuation,就回来调用continuation的句子组成的lambda表达式,在最外层用一个循环去驱动他直到回来null停止。这样做了之后,就算Tinymoe的代码有递归,call stack里边也不会由于递归而堆集call stack item了。所以生成的C#代码履行飞快,并且不管你怎样递归也永久不会形成stack overflow了。这个美好的特性简直一切言语都做不到,啊哈哈哈哈哈。

 

当然这也是有价值的,由于实质上我仅仅把保存在stack上的context转移到heap上。不过多亏了.net 4.0的强壮的background GC,这样做一点点没有剩余的功用上的损耗。当然这也意味着,一个高功用的Tinymoe虚拟机,需求一个牛逼的废物搜集器作为靠山。context发作的closure在函数体真的被履行完之后就会被很快地搜集,所以CPS加上这种做法并不会对GC发作额定的压力,一切的压力依然来源于你自己所创立的数据结构。

 

第三,Tinymoe需求动态类型言语的类型推导。当然你不这么做而把Tinymoe的程序当JavaScript那样的程序处理也没有问题。可是咱们知道,正是由于V8对JavaScript的代码进行了类型推导,才发作了那么优异的功用。因而这算是一个优化上的办法。

 

最终,Tinymoe还需求跨进程剖析和对程序的操控流的化简(比如continuation转状况机等)。现在具体怎样做我还在学习傍边。不过咱们想,已然repeat函数是经过递归来描绘的,那咱们能不能经过对一切代码进行inter-procedural analyzing,然后发现比如

repeat 3 times

    do something good

end

便是一个循环,然后生成用真实的循环指令(比如说goto)呢?这个问题是个很有意思的问题,我觉得我假如能够经过学习静态剖析然后处理它,不进我的才干会得到提高,我对你们的科普也会做得更好。

跋文

尽管还不到五千字,可是总觉得写了许多的姿态。总归我期望读者在看完《零》和《一》之后,对接下来需求学习的东西有一个较为明晰的知道。

posted @ 2014-02-11 12:53 陈梓瀚(vczh) 阅览(13957) | 谈论 (11)修正 保藏
  2014年1月19日

在《怎样规划一门言语》里边,我讲了一些言语方面的东西,还有爽快的喷了一些XX粉什么的。不过单纯讲这个也是很无聊的,所以我开了这个《跟vczh看实例学编译原理》系列,意在科普一些编译原理的常识,尽量让咱们能够在发明言语之后,自己写一个原型。在这儿我拿我发明的一门很风趣的言语 https://github.com/vczh/tinymoe/ 作为实例。

 

商业编译器对功用和质量的要求都是很高的,里边许多的东西其实都跟编译原理不要紧。一个典型的编译原理的原型有什么特征呢?

  1. 功用低
  2. 过错信息丑陋
  3. 没有检查一切状况就生成代码
  4. 优化做得烂
  5. 简直没有编译选项

 

等等。Tinymoe就满意了上面的5种状况,由于我的方针也仅仅想做一个原型,向咱们介绍编译原理的根底常识。当然,我对语法的规划仍是尽量接近工业质量的,仅仅完结没有花太多心思。

 

为什么我要用Tinymoe来作为实例呢?由于Tinymoe是罕见的一种用起来简略,并且库能够有多杂乱写多杂乱的言语,就跟12bet相同。12bet11额规范库在一同用简直是愉快啊,Tinymoe的代码也是这么写的。可是这并不阻碍你能够在写12bet库的时分发挥你的幻想力。Tinymoe也是相同的。为什么呢,我来举个比如。

 

Hello, world!

Tinymoe的hello world程序是很简略的:

 

module hello world

using standard library

 

sentence print (message)

    redirect to "printf"

end

 

phrase main

    print "Hello, world!"

end

 

module指的是模块的姓名,一般的程序也是一个模块。using指的是你要引证的模块——standard library便是Tinymoe的STL了——当然这个程序并没有用到任何standard library的东西。提到这儿咱们或许认识到了,Tinymoe的姓名能够是不定长的token组成的!没错,后边咱们会渐渐认识到这种做法有多么的强壮。

 

后边是print函数和main函数。Tinymoe是严厉区别句子和表达式的,只需sentence和block最初的函数才干作为句子,并且一同只需phrase最初的函数才干作为表达式。所以下面的程序是不合法的:

 

phrase main

    (print "Hello, world!") + 1

end

 

原因便是,print是sentence,不能作为表达式运用,因而他不能被+1。

 

Tinymoe的函数参数都被写在括号里边,一个参数需求一个括号。到了这儿咱们或许会觉得很古怪,不过很快就会有回答了。为什么要这么做,下一个比如就会告知咱们。

 

print函数用的redirect to是Tinymoe声明FFI(Foreign Function Interface)的办法,也便是说,当你运转了print,他就会去host里边找一个叫做printf的函数来运转。不过咱们不要误解,Tinymoe并没有被规划成能够直接调用C函数,所以这个姓名其实是随意写的,只需host供给了一个叫做printf的函数完结printf该做的作业就行了。main函数就不必解说了,很直白。

1加到100等于5050

这个比如能够在Tinymoe的主页(https://github.com/vczh/tinymoe/)上面看到:

 

module hello world

using standard library

 

sentence print (message)

redirect to "printf"

end

 

phrase sum from (start) to (end)

set the result to 0

repeat with the current number from start to end

add the current number to the result

end

end

 

phrase main

print "1+ ... +100 = " & sum from 1 to 100

end

 

为什么姓名能够是多个token?为什么每一个参数都要一个括号?看加粗的部分就知道了!正是由于Tinymoe想让每一行代码都能够被念出来,所以才这么规划的。当然,咱们必定都知道怎样算start + (start+1) + … + (end-1) + end了,所以应该很简略就能够看懂这个函数里边的代码具体是什么意思。

 

在这儿能够略微多做一下解说。the result是一个预界说的变量,代表函数的回来值。只需你往the result里边写东西,只需函数一完毕,他就变成函数的回来值了。Tinymoe的括号没有什么特别意思,便是改动优先级,所以那一句循环则能够经过增加括号的办法写成这样:

 

repeat with (the current number) from (start) to (end)

 

咱们或许会想,repeat with是不是要害字?当然不是!repeat with是standard library里边界说的一个block函数。咱们知道block函数的意思了吧,便是这个函数能够带一个block。block有一些特功用够让你写出相似try-catch那样的几个block连在一同的大block,特别适合写库。

 

到了这儿咱们心中或许会有疑问,循环为什么能够做成库呢?还有愈加令人震惊的是,break和continue也不是要害字,是sentence!由于repeat with是有代码的:

 

category

    start REPEAT

    closable

block (sentence deal with (item)) repeat with (argument item) from (lower bound) to (upper bound)

    set the current number to lower bound

    repeat while the current number <= upper bound

        deal with the current number

        add 1 to the current number

    end

end

 

前面的category是用来界说一些block的次序和围住结构什么的。repeat with是归于REPEAT的,而break和continue声明晰自己只能直接或许直接方在REPEAT里边,因而假如你在一个没有循环的当地调用break或许continue,编译器就会报错了。这是一个花边功用,用来避免手误的。

 

咱们或许会注意到一个新东西:(argument item)。argument的意思指的是,后边的item是block里边的代码的一个参数,关于repeat with函数自身他不是一个参数。这就经过一个很天然的办法给block增加参数了。假如你用ruby的话就得写成这个悲催的姿态:

 

repeat_with(1, 10) do |item|

    xxxx

end

 

而用12bet写起来就更悲催了:

 

repeat_with(1, 10, [](int item)

{

    xxxx

});

 

block的榜首个参数sentence deal with (item)便是一个引证了block中心的代码的托付。所以你会看到代码里边会调用它。

 

好了,那repeat while总是要害字了吧——不是!后边咱们还会知道,就连

 

if xxx

    yyy

else if zzz

    www

else if aaa

    bbb

else

    ccc

end

 

也仅仅你调用了if、else if和else的一系列函数然后让他们串起来罢了。

 

那Tinymoe究竟供给了什么根底设施呢?其实只需select-case和递归。用这两个东西,加上内置的数组,就图灵齐备了。图灵齐备便是这么简略啊。

 

多重分配(Multiple Dispatch)

讲到这儿,我不得不说,Tinymoe也能够写类,也能够承继,不过他跟传统的言语不相同的,类是没有结构函数、析构函数和其他成员函数的。Tinymoe一切的函数都是大局函数,可是你能够运用多重分配来"选择"类型。这就需求第三个比如了(也能够在主页上找到):

 

module geometry

using standard library

 

phrase square root of (number)

    redirect to "Sqrt"

end

 

sentence print (message)

    redirect to "Print"

end

 

type rectangle

    width

    height

end

 

type triangle

    a

    b

    c

end

 

type circle

    radius

end

 

phrase area of (shape)

    raise "This is not a shape."

end

 

phrase area of (shape : rectangle)

    set the result to field width of shape * field height of shape

end

 

phrase area of (shape : triangle)

    set a to field a of shape

    set b to field b of shape

    set c to field c of shape

    set p to (a + b + c) / 2

    set the result to square root of (p * (p - a) * (p - b) * (p - c))

end

 

phrase area of (shape : circle)

    set r to field radius of shape

    set the result to r * r * 3.14

end

 

phrase (a) and (b) are the same shape

    set the result to false

end

 

phrase (a : rectangle) and (b : rectangle) are the same shape

    set the result to true

end

 

phrase (a : triangle) and (b : triangle) are the same shape

    set the result to true

end

 

phrase (a : circle) and (b : circle) are the same shape

    set the result to true

end

 

phrase main

    set shape one to new triangle of (2, 3, 4)

    set shape two to new rectangle of (1, 2)

    if shape one and shape two are the same shape

        print "This world is mad!"

    else

        print "Triangle and rectangle are not the same shape!"

    end

end

 

这个比如略微长了一点点,不过咱们能够很清楚的看到我是怎样界说一个类型、创立他们和拜访成员变量的。area of函数能够核算一个平面几何图形的面积,并且会依据你传给他的不同的几何图形而运用不同的公式。当一切的类型判别都失利的时分,就会掉进那个没有任何类型声明的函数,然后引发一场。嗯,其实try/catch/finally/raise都是函数来的——Tinymoe对操控流的操控便是如此强壮,啊哈哈哈哈。就连return都能够自己做,所以Tinymoe也不供给预界说的return。

 

那phrase (a) and (b) are the same shape怎样办呢?没问题,Tinymoe能够一同指定多个参数的类型。并且Tinymoe的完结具有跟12bet虚函数相同的性质——不管你有多少个参数符号了类型,我都能够O(n)跳转到一个你需求的函数。这儿的n指的是符号了类型的参数的个数,而不是函数实例的个数,所以跟12bet的状况是相同的——由于this只能有一个,所以便是O(1)。至于Tinymoe究竟是怎样完结的,只需求看《怎样规划一门言语》第五篇(http://www.fometaux.com/vczh/archive/2013/05/25/200580.html)就有答案了。

Continuation Passing Style

为什么Tinymoe的操控流都能够自己做呢?由于Tinymoe的函数都是写成了CPS这种风格的。其实CPS咱们都很了解,当你用jquery做动画,用node.js做IO的时分,那些嵌套的一个一个的lambda表达式,就有点CPS的滋味。不过在这儿咱们并没有看到嵌套的lambda,这是由于Tinymoe供给的语法,让Tinymoe的编译器能够把同一个层次的代码,转成嵌套的lambda那样的代码。这个进程就叫CPS改换。Tinymoe尽管用了许多函数式编程的办法,可是他并不是一门函数是言语,仅仅一门一般的进程式言语。可是这跟C言语不相同,由于它连C#的yield return都能够写成函数!这个比如就更长了,咱们能够到Tinymoe的主页上看。我这儿只贴一小段代码:

 

module enumerable

using standard library

 

symbol yielding return

symbol yielding break

 

type enumerable collection

    body

end

 

type collection enumerator

    current yielding result

    body

    continuation

end

 

略(这儿完结了跟enumerable相关的函数,包含yield return)

 

block (sentence deal with (item)) repeat with (argument item) in (items : enumerable collection)

    set enumerator to new enumerator from items

    repeat

        move enumerator to the next

        deal with current value of enumerator

    end

end

 

sentence print (message)

    redirect to "Print"

end

 

phrase main

    create enumerable to numbers

        repeat with i from 1 to 10

            print "Enumerating " & i

            yield return i

        end

    end

 

    repeat with number in numbers

        if number >= 5

            break

        end

        print "Printing " & number

    end

end

 

什么叫仿照C#的yield return呢?便是连慵懒核算也一同仿照!在main函数的榜首部分,我创立了一个enumerable(iterator),包含1到10十个数字,并且每发作一个数字还会打印出一句话。可是接下来我在循环里边只取前5个,打印前4个,因而履行成果便是

当!

 

CPS风格的函数的威力在于,每一个函数都能够操控他怎样履行函数完毕之后写在后边的代码。也便是说,你能够依据你的需求,爽性选择保护现场,然后今后再回复。是不是听起来很像lua的coroutine呢?在Tinymoe,coroutine也能够自己做!

 

尽管函数最终被转化成了CPS风格的ast,并且测验用的生成C#代码确实也是原封不动的输出了出来,所以运转这个程序耗费了许多的函数调用。但这并不意味着Tinymoe的虚拟机也要这么做。咱们要记住,一个言语也好,类库也好,给你的接口的概念,跟完结的概念,有或许彻底不同。yield return写出来确实要花费点心思,所以《序文》我也不讲这么多了,后续的文章会具体介绍这方面的常识,当然了,还会告知你怎样完结的。

 

结尾

这儿我选择了四个比如来展现Tinymoe最重要的一些概念。一门言语,要运用用起来简略,库写起来能够发挥幻想力,才是有出路的。yield return比如里边的main函数相同,用的时分多清新,清新到让你彻底忘掉yield return完结的时分里边的各种费事的细节。

 

所以为什么我要选择Tinymoe作为实例来科普编译原理呢?有两个原因。榜首个原因是,想要完结Tinymoe,需求许多的常识。所以已然这个系列想让咱们能够看完完结一个Tinymoe的低质量原型,当然会讲许多常识的。第二个原因是,我想经过这个比如向咱们将一个道理,便是库和运用 、编译器和语法、完结和接口,彻底能够做到阻隔杂乱,只留给最终用户简略的部分。你看到的杂乱的接口,并不意味着他的完结是臃肿的。你看到的简略的接口,也不意味着他的完结就很简练

 

Tinymoe现在现已能够输出C#代码来履行了。后边我还会给Tinymoe加上静态剖析和类型推导。关于这类言语做静态剖析和类型推导又许多费事,我现在还没有彻底搞了解。比如说这种能够自己操控continuation的函数要怎样编译成状况机才干避免掉许多的函数调用,就不是一个简略的问题。所以在系列一边做的时分,我还会一边研讨这个作业。假如到时分系列把编译部分写完的一同,这些问题我也搞了解的话,那我就会让这个系列扩展到包含静态剖析和类型推导,持续往下讲。

posted @ 2014-01-19 01:21 陈梓瀚(vczh) 阅览(43120) | 谈论 (4)修正 保藏
  2014年1月4日

2013年我就干了两件作业。榜首件是gaclib,第二件是tinymoe

 

Gaclib总算做到安全的支撑12bet的反射、从XML加载窗口和控件了。现在在完结的东西则是一个给gaclib用的workflow小脚本,用来写一些简略的view的逻辑、界说viewmodel接口,还有跟WPF差不多的data binding。

 

Tinymoe是我大二的时分就规划出来的东西,无法曾经对核算机的理论根底了解的太少,以至于无法完结,直到现在才干做出来。总的来说tinymoe是一个仿照英语语法的严厉的编程言语——也便是说它是不依据NLP的,语法是严厉的,写错一个单词也会编译不过。因而一切的函数都要写成短语,包含操控流句子也是。所以我就想了一想,能不能让分支、循环、反常处理和异步处理等等其他言语的内置的功用在我这儿都变成库?这当然是能够的,只需做全文的cps改换,然后要求这些操控流函数也写成cps的风格就能够了。

 

现在的榜首个主意是,等搞好了之后先生成javascript或许C#的代码,不太想写自己的VM了,然后就出一个系列文章叫做《看实例跟大牛学编译原理》,就以这个tinymoe作为比如,来把《怎样规划一门言语》延续下去,啊哈哈哈哈哈。

 

写12bet怎么样是一件很难的作业。我大三开端运营这个cppblog/cnblogs的12bet怎么样的时分,一天都能够写一篇,底子上是在记载我学到的东西和我造的轮子。现在都比较懒了,觉得整天说自己在开发什么也没意思了,所以想写一些其他,居然不知怎样下手,所以就出了各种没填完的系列。

 

我觉得我学编程这13年来也是学到了不少东西的,除了朴实的api和言语的常识以外,许多办法论都给我起到了非常重要的效果。一开端是面向方针,然后是数据结构算法,然后是面向方面编程,然后是函数式编程,后来还触摸了各种跟函数式编程有关的概念,比如说reactive programming啊,actor啊,异步啊,continuation等等。脑子里充满了各式各样的办法论和模型之后,现在不管写什么程序,简直都能够拿这些东西往上套,然后做出一个保护也很简略(条件是有这些常识),代码也很简练的程序了。

 

作业的这四年半里,让我学习到了文档和自动化测验的重要性,所以运用这几年我把文档和测验的才干也训练的差不多了。现在我觉得,技能的话作业敷衍起来是超级简略,可是自己对技能的热心仍是促进我不断的研讨下去。2014年应该研讨的技能便是嘴炮了。

posted @ 2014-01-04 21:52 陈梓瀚(vczh) 阅览(9061) | 谈论 (9)修正 保藏
  2013年11月10日
     摘要: 在考虑怎样写这一篇文章的时分,我又想到了曾经谈论正交概念的作业。假如一个别系被规划成正交的,他的功用扩展起来也能够很简略的坚持质量这是没错的,可是关于每一个独自给他扩展功用的个别来说,这个系共同点都欠好用。所以我觉得现在的言语被规划成这样也是有那么点道理的。就算是规划Java的那谁,他也不是傻逼,那为什么Java会被规划成这样?我觉得这跟他刚开端想让金字塔的底层程序员也能够顺畅运用Java是有联系...  阅览全文
posted @ 2013-11-10 17:06 陈梓瀚(vczh) 阅览(8903) | 谈论 (6)修正 保藏
仅列出标题  下一页