Code For Fun, Not For Food

简介

这两天开始用WebGL做一个星图App,需要处理各种星表数据。

Yale Bright Star Catalogue (BSC, 亮星星表)包含了所有视星等6.5以上的恒星(9000+枚),基本上就是人类狗眼能看到的所有恒星了。

写了这个转换脚本,可以将星表数据转换为任意格式,只需要创建对应格式的underscore template就行了。

下载

Markdown格式化后的BSC 5th Edition Readme: Bright Star Catalogue, 5th Revised Ed.

转换脚本: Generic Convertor For Bright Star Catalogue

安装

  • Node.Js
  • 在脚本目录中npm install如下包:
    • coffee-script
    • async
    • underscore
  • 下载星表数据文件,解压bsc5.datnotes文件,放到和脚本相同目录
  • 和脚本一起的有一个简单的json模板(underscore template),也可以根据需要自己创建,放到和脚本相同目录

运行

命令格式:

1
$ coffee convert template_file_name output_file_name

例:

1
$ coffee convert json bsc5.json

创建模板

参考:

介绍

2048这游戏已经被玩坏了,有人把它和Flappy Bird杂交,玩不过不能忍,于是写了个AI玩之。

游戏源码修改

首先需要对游戏进行适当的修改,便于AI获取游戏状态,并输出控制量。

修改application.js,将几个关键的对象放到windows命名空间中便于访问:

1
2
3
4
5
6
window.requestAnimationFrame(function () {
	window.input = KeyboardInputManager;
	window.actuator = HTMLActuator;
  window.score = LocalScoreManager;
  window.game = new GameManager(4, KeyboardInputManager, HTMLActuator, LocalScoreManager);
});

游戏的逻辑主要在game_manager.js中实现:

游戏中的“鸟”的css class是tile-bird,障碍物的css class是tile-block,在本文中分别简称为birdblock

  • 使用game.jump()跳跃
  • bird的状态:
变量名 说明
game.birdpos 顶端的y坐标,$[0, 1]$之间,0为顶端
game.birdspd y方向速度,向下为正
  • 在任意时刻,只有4个block分别称为a, b, cdab,cd成组,有相同的水平坐标,两组block之间一直保持2个tile的距离。每组block只有3种可能状态:全在上、全在下以及一上一下,因此block的状态由两个0~2之间的数字game.ab, game.cd确定。

游戏由一个timer驱动,每一帧计算游戏状态的变化,最后调用window.actuator.actuate()方法计算元素位置,重绘游戏。

在游戏计算出元素位置并重绘后获取状态,并由AI注入控制量是最为便捷的方式。

修改html_actuator.js:

1
2
3
4
5
6
HTMLActuator.prototype.actuate = function (grid, metadata) {
  //.. Other stuff

  // Call AI
  window.AI.play(this);
}

这样对原游戏的改动就完成了,接下来只需要实现AI类,并把类对象赋值到window.AI即可。

Q-Learning

Q-Learning是一种强化学习算法,能用于寻找Markov决策过程(MDP, Markov decision process)的最优解。 MDP问题模型由一个agent,状态$S$以及每个状态对应动作(action)集合$A$构成。Agent通过完成一个动作,从一个状态$S$跳转到另一个状态$S'$,获得一定的奖励。Agent的目标就是使奖励最大化,通过学习在每个状态下最优的动作,达到这个目的。

算法的核心是矩阵$Q$,记录状态-动作对的奖励:

$$Q: S \times A \rightarrow \mathbb{R}$$

算法初始时,$Q$取设计好的值,随后agent每执行一次动作,观察新状态以及获得的奖励,通过如下公式迭代更新:

$$Q_{t+1}(s_t, a_t) = Q_{t}(s_t, a_t) + \alpha_{t}(s_t, a_t) \times [ R_{t+1} + \gamma \max Q_{t}(s_{t+1}, a) - Q_{t}(s_t, a_t) ]$$

其中:

  • $Q_{t+1}(s_t, a_t)$: 新的$Q$值
  • $Q_{t}(s_t, a_t)$: 上一时刻$Q$值
  • $R_{t+1}$: 在$s_t$时执行$a_t$后获得的奖励
  • $\alpha \in [0, 1]$: learning rate
  • $\gamma$: 折扣率

算法设计

  • 状态:

    • $\Delta y$: bird到能安全通过当前block最高点的垂直距离
    • $\Delta x$: bird到下一个block的水平方向距离
  • 动作:

    • jump: 跳跃
    • idle: 不动作
  • 奖励:

    • 死亡:-100
    • 存活:1
  • $Q$的初始化

虽然可以简单的把$Q$全初始化为0,但这样会延长学习时间。并且在很多情况下,会导致bird一直跳跃直到跳出顶端掉不下来,这样不管是jump还是idle都会被惩罚,这样永远无法学习到正确行为。另外在底部也会有同样的问题。

实际实现时,加入了先验知识:

  • 对所有$\Delta y < y_{min}$的$s$,初始化jump的reward为-100。即在上端时禁止跳跃
  • 对所有$\Delta y > n * BirdHeight$的$s$,初始化idle的reward为-5n接近1。即离最高点的距离小于bird自己高度的时候,倾向于跳跃。注意这里的reward值较小,是因为在某些组合下(如当前block在下,下一个block在上),跳跃会挂掉,值如果过大,$Q$值无法及时对惩罚做出反馈。

  • 不定状态时的随机参数

jumpaction的reward相等时,无法通过$Q$做出决策,这个时候需要随机决定采取何种行为。

实际实现时,同样没有简单的将这个概率设为0.5,而是让不跳跃的概率远大于跳跃。道理很简单,游戏的操作方式是不平衡的,玩家只能干预下落,而不能干预上升,掉得太低跳一下就行了,跳得太高就只有等死。

效果

目前实现的版本在未学习的情况下,可以一次跳跃到700+分,学习一小时后可以到1000分,到后面出错都是遇到比较极端的组合差之毫厘,重现概率不高,所以学习速度会变慢。

玩:Q Learning Flappy 2048

代码:GitHub

介绍

今天把博客从blog.catx.me迁移到了catx.me,并关闭了原来的wordpress博客,算是完成了迁移的工作。 由于在过渡期也有若干个项目引用了博客的URL,所以迁移最后需要解决的问题是改变域名过后的重定向。 重定向包括两个方面:

  • 通过原URL的访客不会死链,会自动跳转到新URL
  • 搜索引擎能自动重新索引,不会降低页面排名

实现的原理就是在每个页面的<head>部分添加两个标签:

1
2
<meta http-equiv="refresh" content="0; url=http://new.domain.com/same/relative/url/of/old/site/">
<link rel="canonical" href="http://new.domain.com/same/relative/url/of/old/site/" />

第一个是给人看的,第二个是给机器看的。

前者会自动让浏览器跳转到新的域名,后者在搜索引擎的bot下次抓取页面的时候读取,重新索引到新的URL。

对于较大的站点,人肉在每个页面的标签很是麻烦,于是做了一个hexo的主题来实现这样一个功能(当然也有其他方式,不过主题是最简单的)。这并不是一个真正的主题,因为没有任何内容会被访问者看到。这个主题唯一的用途就是生成一个结构完全相同的站点,把每个页面重定向到一个新的域名上。

使用

以把在blog.catx.me上的站点迁移到catx.me上为例,创建repo、修改DNS、修改CNAME这些部署上的细节大同小异而又千变万化,不在此说明,过程如下:

  • 创建一个hexo博客文件夹的副本
  • 在副本文件夹中安装这个主题:
1
$ git clone https://github.com/akfish/hexo-theme-redirect.git themes/redirect
  • 修改副本站点的_config.yml文件,使用主题:
1
theme: redirect
  • 修改副本站点的_config.yml文件,添加如下行指定新域名:
1
new_domain: catx.me
  • 修改副本站点的部署配置,部署到blog.catx.me(老域名)
  • 修改原站点的部署配置,部署到catx.me(新域名)

这样就完成了迁移工作,比如访问http://blog.catx.me就会自动跳转到http://catx.me

其它

如果你的站点部署在GitHub Pages上,老域名恰好在yourname.github.io repo的CNAME绑定过,那么你其它项目的GitHub Pages的URL也需要设置跳转。

比如有个项目foo,原有的gh-pages地址就是http://blog.catx.me/foo,那么就可以在副本站点中运行:

1
$ hexo new page foo

部署后就能实现跳转。需要注意的是,hexo生成的页面路径全是小写,如果服务器是区分大小写的,就需要手动在source里修改成正确的形式。

源代码

hexo-theme-redirect

介绍

技术类博客总是不可避免的要插入各种UML图,昨天偶然发现一个有意思的Javascript库Jumly,用于渲染UML sequence diagram和robustness diagram。于是制作了一个hexo插件,便于在博客中插入。

Sequence Diagram

Robustness Diagram

安装

1
$ npm install hexo-tag-uml --save

初始化

在blog文件夹中执行:

1
$ hexo uml install

_config.yml文件中添加:

1
2
plugins:
- hexo-tag-uml

在主题的.ejs文件的合适位置插入:

1
<%- partial('jumly') %>

一般而言可以放在<head>一节里,需要注意的是Jumly依赖于jQuery,如果主题里引用了其它位置的jQuery,会导致冲突。 比如hexo的默认主题landscape就在after-footer.ejs中插入了jQuery,需要将相应行去掉,替换为上面语句。 也是因为实际主题的实现哥又不同,这个插件没能实现自动修改theme layout文件。

语法

1
2
{% uml [diagram_type] %}
{% uml %}

diagram_type可以取的值为:

  • sequence
  • robustness

如果留空,默认为sequence。

示例

1
2
3
4
5
6
7
8
9
10
11
12
{% uml %}
@found "Browser", ->
  @alt {
    "[200]": -> @message "GET href resources", "HTTP Server"
    "[301]": -> @ref "GET the moved page"
    "[404]": -> @ref "show NOT FOUND"
  }
@find(".ref").css(width:256, "padding-bottom":4)
  .find(".tag").css float:"left"
get_the_moved_page.css "background-color":"#80c080"
show_not_found.css "background-color":"#f0b0b0"
{% enduml %}

效果

Jumly的表达式规则详见:Jumly Reference Manual

在线编辑器:Try Jumly

Sequence Diagram

Robustness Diagram

背景

虚拟HID驱动用于虚拟一个或多个人机交互设备,如键盘、鼠标、摇杆等,作用都懂的。 经过搜索发现一个开源项目vmulti,实现了虚拟的多点触控、鼠标、键盘、摇杆以及数位笔,省去了自己写驱动的麻烦。

编译vmulti

  1. 安装WDK
  2. 运行以管理员权限WDK build environment
  3. 进入vmulti工程文件夹,运行
1
build -wgc
  1. 把编译生成的vmulti.sysmulti.infhidkmdf.sys文件放到同一个文件夹
  2. 把WDK中的WdfCoInstaller01009.dll, devcon.exe也放到这个文件夹

驱动签名

Windows x64系统上无法安装无签名的驱动,需要进行self sign。所有操作需要在管理员权限的WDK build environment中执行。

打开Windows测试模式

要加载self sign的内核代码,需要打开windows的测试模式:

1
bcdedit /set testsigning on

重启。

创建证书

1
2
3
makecert -r -pe -ss "CatX" -n "CN=CatX Test Certificate" catx.cer
certmgr -add catx.cer /s /r localMachine root
certmgr -add catx.cer /s /r localMachine trustedpublisher

验证证书是否正确安装,运行:

1
certmgr

签名

驱动中的如下文件需要签名:

  • *.sys文件
  • *.inf中引用的*.cat文件

如果*.cat文件不存在,需要运行inf2cat创建:

1
inf2cat /driver:%driver_folder% /os:7_x64

vmulti需要签名的文件有vmulti.sys、hidkmdf.sys和kmdfsamples.cat,运行:

1
signtool sign /v /s "CatX" /n "CatX Test Certificate" /t http://timestamp.verisign.com/scripts/timestamp.dll %file_name%

验证签名:

1
signtool verify /pa /v *.cat *.sys

安装vmulti

运行:

1
devcon install vmulti.inf djpnewton\vmulti

测试

vmulti工程中包含了一个测试程序testvmulti.exe,用于测试驱动功能:

1
2
3
testvmulti.exe /multitouch
testvmulti.exe /mouse
testvmulti.exe /digitizer

介绍

Hexo不支持数学公式,网上可以找到很多人肉修改theme使其支持用MathJax渲染公式的方法,主要分为两个步骤:

  • 在theme的header中插入对MathJax CDN script的引用,并配置inline math
  • 在文章中用inline math插入公式

这个方法有两个明显的缺点:

  • 需要人肉进行的工作太多
  • 遇到特殊符号需要人肉escape,否则会被markdown parser吃掉

于是开发了一个插件,实现:

  • 自动部署MathJax
  • 添加MathJax Tag

安装

1
$ npm install hexo-math --save

初始化

在blog文件夹中执行:

1
$ hexo math install

_config.yml文件中添加:

1
2
plugins:
- hexo-math

使用

对于不含特殊符号的公式,可以直接使用MathJax的inline math表达式. 如果含有特殊符号,则需要人肉escape,如\之类的特殊符号在LaTex表达式中出现频率很高,这样就很麻烦,使用tag能够省不少事。

MathJax Inline:

1
Simple inline $a = b + c$.

效果:

Simple inline $a = b + c$.

MathJax Block:

1
2
3
4
$$\frac{\partial u}{\partial t}
= h^2 \left( \frac{\partial^2 u}{\partial x^2} +
\frac{\partial^2 u}{\partial y^2} +
\frac{\partial^2 u}{\partial z^2}\right)$$

效果:

$$\frac{\partial u}{\partial t} = h^2 \left( \frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} + \frac{\partial^2 u}{\partial z^2}\right)$$

Tag inline:

1
This equation {% math \cos 2\theta = \cos^2 \theta - \sin^2 \theta =  2 \cos^2 \theta - 1 %} is inline.

效果:

This equation $\cos 2\theta = \cos^2 \theta - \sin^2 \theta = 2 \cos^2 \theta - 1$ is inline.

Tag Block:

1
2
3
4
5
6
7
{% math-block %}
\begin{aligned}
\dot{x} & = \sigma(y-x) \\
\dot{y} & = \rho x - y - xz \\
\dot{z} & = -\beta z + xy
\end{aligned}
{% endmath-block %}

效果:

$$\begin{aligned} \dot{x} & = \sigma(y-x) \\ \dot{y} & = \rho x - y - xz \\ \dot{z} & = -\beta z + xy \end{aligned}$$

源代码

GitHub

这两天打算把博客从Wordpress迁移到GitHub Page上,主要原因还是Wordpress的编辑不如Markdown来得爽,这个主机也不如GitHub服务器的速度和可访问性高。

GitHub Pages的博客框架有很多选择,最终决定用基于Node.Js的Hexo,速度比官方的Jekyll系框架要快,并且不用折腾ruby。在使用hexo-migrator-wordpress迁移文章后,发现所有图片依然是保持外链。翻了下Hexo的文档,自己写了个migrator迁移所有外链图片,流程很简单:

  • 打开所有.md文件
  • 扫描并解析Markdown插入图片的tag
  • 下载所有非本站的图片(包括本地图片)到images目录
  • 更新所有引用的url

迁移前简单的通过对url做SHA1 hash可以避免部分图片重复,目前懒得对文件内容做对比,暂时是够用了。

有了这个工具不仅能够完成迁移,以后写文章的时候也不用人肉拷贝图片算链接,只需要直接引用,发布前跑一次就行了。

安装:

1
$ npm install hexo-migrator-image

使用:

1
$ hexo migrate image

源代码:hexo-migrator-image

问题描述

C#中经常会遇到通过单一入口动态调用对象或服务的情况,形如:

1
2
3
4
public abstract class ProxyBase
{
  protected abstract object Invoke(object someMethodRelatedInfo, object[] arguments);
}

比如Reflection,远程服务,Host动态脚本引擎时从C#调用引擎context内的方法等等情况都可以归类于这样的模型。

一种较好的工程实现就是把这些服务方法用接口定义,获得强类型的校验,避免出现不必要的bug,并便于维护。如:

1
2
3
4
5
public interface IFooService
{
  void MethodWithNoReturn();
  int MethodTakeParameterAndReturn(int a, int b);
}

对于不同的后端,需要有具体的调用实现:

1
2
3
4
5
6
7
8
9
public class FooProxyBase : ProxyBase 
{
  protected override object Invoke(object someMethodRelatedInfo, object[] arguments)
  {
    // Pack to JSON and send via http
    // Or adapte and call other classes
    // Or whatever
  }
}

最终的Proxy类通过继承调用实现类,同时实现服务约定接口实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class FooService : FooProxyBase, IFooService
{
  #region Implement IFooService
  public void MethodWithNoReturn() 
  {
    Invoke("MethodWithNoReturn", new object[0]);
  }

  public int MethodTakeParameterAndReturn(int a, int b)
  {
    return Invoke("MethodTakeParameterAndReturn", new object[] { a, b });
  }
  #endregion
}

这样一来有一个显然的问题,Proxy类包含大量重复的代码,方法越多实现起来越费劲。这个问题的point of interest就在于Proxy类的动态生成,实现以后只需要一行代码就能替代人肉实现一个巨大的Proxy类:

1
IFooService proxy = ProxyEmitter.CreateProxy<FooProxyBase, IFooService>(/*Constructor parameters are supported*/);

要动态生成Proxy类有很多种方法(如生成源代码然后编译),这里采用在运行时通过Reflection获取服务接口的方法,动态生成Proxy类,最后用ILGenerator.Emit用.Net IL实现代码逻辑。

实现要点

如何动态创建Assembly, Module, Type的框架性代码MSDN有详尽的walkthrough,不在本文讨论重点,具体实现可参考源代码。

这一节记录在实现这个项目中几处逻辑的IL代码生成,有几点是必须要知道的:

  • .Net CLR是基于栈的虚拟机
  • .Net CLR(在生成C#类时)是强类型的
  • 参数顺序入栈
  • 非static method的第一个参数总是this指针

1. 有参数的constructor

在C#中很多涉及自动生成的情况(如serialization)都要求无参数的constructor,在有的情况下很让人忧桑,其实要支持有参数的constructor也是可行的。

如果父类只有一个有参数的constructor,子类的constructor实现必须用足够的参数构造:

1
2
3
4
class Derived: Base
{
    public Derived(int may, string para, object[] meters): base(may, para, meters) {} 
}

用IL实现上述代码,需要将参数重新压栈,然后call base的ctor指针:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private static void EmitCtor(TypeBuilder tBuilder, ConstructorInfo ctor)
{
    var pTypes = ctor.GetParameters().Select(p => p.ParameterType).ToArray();
    var builder = Emitter.GetConstructor(
        tBuilder,
        MethodAttributes.Public |
        MethodAttributes.HideBySig |
        MethodAttributes.SpecialName |
        MethodAttributes.RTSpecialName,
        pTypes
        );
    var ilGen = builder.GetILGenerator();

    // No locals

    // Load all args, note arg 0 is this pointer, so must emit one more
    for (int i = 0; i <= pTypes.Length; i++)
    {
        DoEmit(ilGen, OpCodes.Ldarg_S, i);
    }
    // Call base ctor
    DoEmit(ilGen, OpCodes.Call, ctor);

    // Return
    DoEmit(ilGen, OpCodes.Ret);
}

生成的IL形如:

1
2
3
4
5
6
IL_0000: ldarg.0
IL_0001: ldarg.1
IL_0002: ldarg.2
IL_0003: ldarg.3
IL_0004: call instance void Base::.ctor(int32, string, object)
IL_0009: ret

2. Array的初始化 由于Invoke的长相,决定了这个生成器中需要大量的生成object[]对象,并把参数装进去。 创建一个local variable,首先需要declare:

1
ilGen.DeclareLocal(typeof(object[]))

每个method的运行环境里维护了一个local列表,IL代码通过index把local入栈和出栈。 创建Array对象,并设置到local:

1
2
3
4
5
6
7
// Initialize array
// IL_0006:  ldc.i4.x
DoEmit(ilGen, OpCodes.Ldc_I4_S, pTypes.Length);
// IL_0007:  newarr     [mscorlib]System.Object
DoEmit(ilGen, OpCodes.Newarr, typeof(Object));
// IL_000c:  stloc.1
DoEmit(ilGen, OpCodes.Stloc_0);

对Array元素的逐条赋值由4~5条机器指令完成:

  • ldloc.?将array入栈
  • ldci4?将当前元素的index入栈
  • 将需要赋给元素的值入栈(本例中为参数用ldarg_s,注意参数0为this指针)
  • 如果是value type需要box
  • stelem.ref指令完成赋值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Now fill the array
for (int i = 0; i < pTypes.Length; i++)
{
    // Load the array first
    // IL_000X + 00: ldloc.0
    DoEmit(ilGen, OpCodes.Ldloc_0);

    // Push the index
    // IL_000X + 01: ldc_i4_x
    DoEmit(ilGen, OpCodes.Ldc_I4_S, i);
    // Load argument i + 1 (note that argument 0 is this pointer(?))
    // IL_000X + 02: ldarg_X
    DoEmit(ilGen, OpCodes.Ldarg_S, i + 1);
    // Box value type
    if (pTypes[i].IsValueType)
    {
        // IL_000X + 03: box pTypes[i]
        DoEmit(ilGen, OpCodes.Box, pTypes[i]);
    }
    // Set arrary element
    // IL_00X + ??: stelem.ref
    DoEmit(ilGen, OpCodes.Stelem_Ref);
}

源代码及使用方法

GitHub

In part 1 we discussed the design goals of Sarcasm and devised a grammar specification that covers most of Irony's features.

Continuing from commit 15c9e6, in which I implemented the grammar specs by hand with Irony, we will discuss the following topics:

  • Construction of abstract syntax tree
  • Generator workflow
  • MarkDown generator
  • Having some fun with visualization

AST Overview

After grammar class is implemented, the first thing you are going to do is to create a parser instance:

1
2
3
var language = new LanguageData(new SarcasmGrammar());
var parser = new Irony.Parsing.Parser(_language);

With the Parser instance, we can parse source code by simply:

1
2
3
var parseTree = parser.Parse(sourceCode);
var parseRoot = parseTree.Root;
var astRoot = ParseRoot.AstNode;

If something is wrong with the grammar or source code, parseRoot and astRoot will be null. For now I will not go into error handling.

Two kinds of trees are generated when Irony parses the source code: parsing tree and optional abstract syntax tree. To create an AST, you must do the following:

1. Set language flag in grammar class's constructor

1
LanguageFlags |= LanguageFlags.CreateAst;

2. Create a bunch of AST node class deriving from Irony.Interpreter.Ast (also remember to add reference to assembly Irony.Interpreter.dll).

1
2
3
4
5
6
// Make your own base class will make life eaiser
public abstract class SarcasmNode : AstNode {/*...*/}
// For other nodes
public class Document : SarcasmNode {/*...*/}
public class IdNode : SarcasmNode {/*...*/}
/*...*/

3. Assign AST node class to each Terminal/NonTerminal instances.

1
2
3
4
5
// For terminals
var ID = new IdentifierTerminal("ID");
ID.AstConfig.NodeType = typeof (IdNode);
// For non-terminals
var Directive = new NonTerminal("Directive", typeof(DirectiveNode));

4. Override AST node's Init method to handle initialization.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// In AST node class
        public AstNode ChildNode;

        public override void Init(AstContext context, ParseTreeNode treeNode)
        {
            // Keep this
            base.Init(context, treeNode);
            // treeNode is the corresponding node in parse tree, contains information like:
            // Token
            var token = treeNode.Token;
            // Term
            var term = treeNode.Term;
            // Child nodes
            var nodes = treeNode.GetMappedChildNodes();

            // Set AsString to a human readable format. It will be used to display AST in Irony.GrammarExplorer
            AsString = "Id: " + token.Text;
            // Use AddChild to build tree structure, it returns an AstNode instance of child's AST node 
            ChildNode = AddChild(string.Empty, nodes[0]);
        }

That's almost all you need to know about how to construct an AST. However, if you mess it up, things can get ugly since the debug information is extremely not helpful. The most common exception on can get is:

System.NullReferenceException: Object reference not set to an instance of an object. at Irony.Ast.AstBuilder.BuildAst(ParseTreeNode parseNode) in f:\Dev\Tool\Irony_2013_12_12\Irony\Ast\AstBuilder.cs:line 97 This will not help you at all. But I will tell you that this always has to do with forgetting to set AST node type to one of your Terminals/Non-Terminals.

Here are some tips I learned in the hard way (the only way mostly, since Irony's documentation is poor):

  • Assign AST node type to all Terminals/NonTerminals, including any intermediate/temporary ones.
  • Except the ones marked as transient. They will not be created at all.
  • CommentTerminals will NOT be mapped to AST at all. You will get the above error regardless the AST node type is set or not.

Generator Workflow

AST marks the watershed between compiler's front end and back end. Although there're still some work (e.g. type validation and semantic analysis) left to be done, we can already generate something with this AST now. The most commonly used method here is the visitor pattern:

1. Declare a interface for Visitor, one overload for each AST node

1
2
3
4
5
6
7
    public interface ISarcasmVisitor
    {
        void Visit(IdNode node);
        void Visit(Document node);
        void Visit(StringValueNode node);
        // others
    }

2. Add virtual/abstract method to AST base class and implement in all derived class

1
2
3
4
5
6
7
8
9
10
11
12
    public abstract class SarcasmNode : AstNode
    {
        public abstract void Accept(ISarcasmVisitor visitor);
    }

    public class Document : SarcasmNode
    {
        public override void Accept(ISarcasmVisitor visitor)
        {
            visitor.Visit(this);
        }
    }

3. Then we can create a generator by implement specific ISarcasmVisitor for different workflow, not only for target code generation but also outlining, semantic analysis.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
    public abstract class TargetGenerator
    {
        public SarcasmParser Parser { get; set; }

        protected TargetGenerator(SarcasmParser parser)
        {
            Parser = parser;
        }

        protected virtual void BeforeVisitor(StreamWriter writer, ISarcasmVisitor visitor) { }
        protected abstract ISarcasmVisitor MakeVisitor(StreamWriter writer);
        protected virtual void AfterVisitor(StreamWriter writer, ISarcasmVisitor visitor) { }
        public bool Generate(StreamReader sourceStream, StreamWriter targetStream)
        {
            // Parse first
            Parser.Parse(sourceStream);
            if (Parser.IsValid)
            {
                var visitor = MakeVisitor(targetStream);
                BeforeVisitor(targetStream, visitor);
                // Visit AST
                Parser.Document.Accept(visitor);
                AfterVisitor(targetStream, visitor);
            }
            targetStream.Flush();
            return Parser.IsValid;
        }
    }

MarkDown Generation

MarkDown generation for Sarcasm is very straight forward, since the syntax is in MarkDown. All I need to do is remove comment delimiters, add correct amount of line endings, format grammar rule into block and escape some special characters.

Again I won't bother with the details here. Just see the code for yourself.

Something Fun with Visualization

The original plan was to start generate C# parser class from here. Then I found an interesting project arbor.js (especially its halfviz demo) and decided to do something fun with it. The idea is to make a better tool for debug. What debug information is better than a visualized one?

The halfviz demo converts a simple language called HalfTone to a node network. With the generator framework in place, it took me less than half an hour to generate node representation from Sarcasm grammar source file. This can be used to visualize references between terminals and non-terminals:

sarcasm-vis

You can play with it live here. It looks more confusing in this form, for now. But with some interaction (filtering, folding, highlighting for example), it can help develops quickly navigate though the grammar. Here's another concept of how to visualize grammar related errors in this form (click to enlarge): sarcasm-concept

Imagine view build errors in Visual Studio with this graph and navigate to the line that is responsible by click on the node. I definitely will try to create something like that later when I begin to make tool chain for Sarcasm.