PA10之开始:由PA6的Parser想到的一些问题

最近打算着实地开始将两年前结束的 CPPGM 的 PA6 解析器重新用起来,用于解析(文曲星上的)GVMaker 文件。选择 GVMaker 主要还是想要完成以前的一个愿望,而利用 PA6 的解析器则是为了让 CPPGM 这个课的参与能稍微再完整一些(虽然已经结束两年多了,)能够在一个比较完整但是整体规模(不光是语法,还包括之后的代码生成和运行时之类的)也不是很大的语言上做一个相对完整的编译器流程。而取名为 PA10 ,只是因为它在 PA9 之后而已。

这次主要是想清楚了两件事情:

  1. 意识到一次解析的过程和结果都能用来表示,过程是「决策树」,结果是「语法树」,而结果是过程的一个子集;
  2. 用了一个类来维护在遍历和修改这棵树时的各种状态,减少代码累赘。

现在分别说以上两点。

※ 决策树与语法树 ※

决策树的建立方法是这样的:在解析到一个规则时,每根据这条规则右边的产生式产生一个新的非终结符,就给当前结点添加一个子结点。也就是说一个结点可以有N个子结点。这决策树是在解析器试探输入文件时的调用栈所扫过的痕迹。

而相比之下,语法树和决策树一模一样,但是只是只在成功的情况下才保留子结点,否则则删除子结点。另外语法树的结点中还包括终结符,不像决策树的结点中只包括非终结符。

所以如果给了以下输入:

int a;

这个文件的全部内容就是声明一个全局变量 int a。它最后解出来的语法树也反映了这一点:

Parse Tree of

树中,“int”是一个“simple_type_specifier”,“a”是一个“id_expression”,加上分号,三者构成了一个“simple_declaration”,最后组成了一个“translation_unit”。

这个语法树所对应的决策树是这样的(其中绿色的结点对应着语法树中的结点):

Decision tree generated while parsing

可见在解析时,解析器进行了两次“declaration”的试探。其中第一次试探发现了“int a;”的声明,而第二次试探完成后发现并没有更多的声明,就结束了。

整个 parsing 的过程,也就是根据每次解析的结果成功与否不断对决策树进行调整,直到找到符合语法规则且吃掉了所有 token 决策树时将树输出的过程。

※ 记录(bookkeeping)的事情 ※

记录的事情有以下这些:

  • 表示当前这个非终结符走到了第几个分岔(即是决策树中的分岔),例如
    noptr-declarator-root:
        declarator-id attribute-specifier*      
    
  • 每个分支成功与否
  • 当前的 Token 的位置。
  • 当前的递归深度。递归深度并不一定等于分岔的位置,就是因为在一个非终结符所对应的一条规则中,如果出现了加号或是星号,就可能进行多次尝试。
  • 当前所正在生成的语法树结点以及父结点。

这几点在 PA6 的解析器中,都直接以变量的形式存在。这样每次新增一条语法规则时都太容易出错了。为了减少出错,这回把这些信息都存在一个称为 ParseState 的表示解析状态的类中。它与其它部分的联系是:

  • 从「整个解析器」的角度看,在进入最外一层(translation_unit)时:
    第一种可能是刚进入,此时的「决策树」是空的;或者
    第二种可能是接续上一次失败或成功的解析,将「决策树」前进一格,然后再进行尝试;
  • 从「非终结符」的角度看,在进入一个非终结符的这条规则时,相应地也有两种可能:
    第一种可能、刚进入时,需要往「决策树」中新加入这次尝试所走的分岔;
    而在第二种可能、也就是因循上一次解析时,需要从「决策树」中读出这回应该尝试的岔路;而在「因循上一次的决策」结束时,又要回到第一种情况,向决策树中添加新的结点;
    所以,就有两个地方会对「决策树」进行修改:第一个地方是完成一次解析后的「进一格」,第二个地方就是在非终结符中新增新和结点。
  • 从「一条规则」的角度看,在需要解析一个非终结符时:
    如果是首次出现的非终结符,那就需要将语法树中深入一层;
    而如果不是首次出现的非终结符,那就保持语法树的层次。
    也就是类似于在深度优先搜索时需要记下每一次访问到了第几个子结点那样的。
    而这个地方的处理也要和分岔的进位一起考虑起来。

因为在解析的过程中 ParseState 会一直被改变,比如他的 Token 位置会一直前进和后退,分岔和递归深度需要一直更新或回退。所以在设计时就有了以下函数:

ParseState::OnFirstNT() 此条规则中,所遇到第一个非终结符时的拷贝构造
ParseState::OnNextNT() 这条规则中,所遇到的其后的非结结符时的拷贝构造
ParseState::NextChoiceFrom() 是在这一条分岔走完时用的拷贝构造函数

PA10Parser::ConsumeToken() 是搭配 OnFirstNT 所使用的
PA10Parser::ConsumeTokenToParent() 是搭配 OnNextNT 的。(*)

PA10Parser::OnEntry() 在进入一个非终结符时需要做的事情
PA10Parser::OnExit() 在离开一个非终结符时需要做的事情

(*):这两个 ConsumeToken 的存在是因为一条规则中所沿用的 ParseState 有数据依赖关系,在而这些相依赖的 ParseState 会因为某时调用了 OnFirstNT() 而使得 AST 向下进了一层。对于非终结符来说,一定要进一层;但是对于 Token 来说,并不一定要进一层。所以才会有「对于 Token,在进一层之前,调用 ConsumeToken ,而在进一层之后,调用 ConsumeTokenToParent 」的现象。

以上这些,还要搭配正确的赋值,并且将每个非终结符中的不同分岔以一个 switch 语句括起来,才能正确地处理解析中的其它情况,比如说带有星号、加号、问号的规则。

总结起来

这个 parser 目前尝试过的最大的输入是 yan 的编译器,算上所有的包含命令,一共有大约 81000 个 token 。每次 parse 用时大约 20 秒。

发表在 Uncategorized | 留下评论

给逸珑8089安装JWM窗口管理器&一些其它事情

前几个星期把逸珑8089上面的Debian 8弄得启动不了图形界面了,同时也发现更新过的Iceweasel不能在8089上运行(每次一打开就说非法指令),于是就重新装了GNewSense 3,希望能进入图形界面以及启动旧版的Iceweasel。安装的过程和先前Debian的网络安装是一样的,为了方便也用了大笔记本(Precision M4400)充当路由器来分享WiFi。安装完成后的默认图形界面是Gnome 2,有WiFi,有电源,挺好用的。不过有一些性能问题,就是Gnome 2用起来有点慢,且命令行打开时会需要等待约2秒的时间。以下描述上面两个问题的解决方法,再描述一些其它的事宜。

这些事宜的解决是为了让龙芯笔记本不要处于闲置的状态,而要去达成一个有意义的目的。目前这个目的就设定为按照《Ray Tracing from the Ground Up》撰写光线追踪程序,体验一下在龙芯笔记本上编写程序的感觉。

  • 把Gnome 2换成更轻量级的JWM
    Gnome 2在8089上光是打开菜单这么简单的操作都会让屏幕一闪一闪的,给人感觉要费老大力气才把屏幕刷新好。真是不好用。所以考虑把窗口管理器换成Puppy Linux中用的JWM。(为什么不换i3之类的平铺窗口管理器呢?主要是平铺会强行改变OpenGL程序的窗口大小,让编写OpenGL程序时不方便。)更换的过程好简单的,从JWM的主页上下载最新的源代码,然后装上所有的依赖项(GNewSense 3里面都有的),然后编译安装,就有了执行程序。但是有了执行程序还不够,还要进行系统方面的设定,也就是更换 /usr/share/xsessions/Jwm.desktop 之类的文件。我不太会进行这方面的设定,所以是先安装了源里的JWM(是旧版),让系统自己完成设定,然后把 /usr/bin/jwm 换成自己编译完成的新版JWM,这样就能在欢迎界面中选择JWM了。在安装完JWM之后,还需要费心进行一些设置。进行设置的过程,其实各种桌面环境都差不多吧,都是一些麻烦的事。只不过有的像XFCE这样能够通过图形界面进行设置,有的只能像JWM这样通过改配置文件进行设置了。磨合一段时间后,就会越来越好用。JWM在龙芯上用比较好用,在大笔记本Precision M4400上和Gimp按上画图板一起用时会有些小的问题,有时候画图板会失去响应甚至造成整个桌面没有响应,所以在大笔记本上还是用XFCE。(XFCE对龙芯来说也太重量级了。)
  • 减小Bash启动时的等待时间
    对于在龙芯上的GNewSense 3,Bash启动时的等待时间是由于 /etc/bash_completion 这个脚本造成的。这个脚本有“第一版”和“第二版”之分。在新近的系统中,都是第二版的。但是在龙芯上的GNewSense 3它还是第一版的。第一版比第二版速度慢,如果换成了第二版的,速度就能快很多。第二版bash-completion以deb包的形式存在,安装Debian Wheezy所配的DEB是可以的。安装完以后打开终端所需要等待的时间就从2秒减小到半秒左右了。在安装时,会有以下画面。
    Screenshot
  • 其它事情
  • 以下几条是在折腾龙芯电脑时在大笔记本上也遇到了的事。

    • 编译安装Conky
      在编译Conky时,如果想要显示NVidia显卡的状态或查看WiFi的信号强度,需要分别启用USE_NVIDIA和WLAN这两个变量。(Todo: 详情
    • 鼠标消失
      鼠标消失是因为启动了gnome-settings-daemon。如果把它砍掉,指针就会回来。
  • 以下几条是在Macbook上安装过Linux之后遇到的一些事。
    • 模仿Mac OS中的缩放模式,设置高分辩率显示屏 + 普通显示屏的双输出

      这一条讲的是如何设定 X Server ,使得在笔记本上有高DPI的显示屏、又外接了一个普通DPI的显示屏时,不会出现普通显示屏上的文字过大的情况。具体而言,就是在Macbook Pro上面安装了Linux以后如何配置外接显示屏。
      首先,我们知道,普通显示屏上的文字过大是因为屏幕缓冲区不经缩放直接点对点显示在所有显示器上。所以,一个290像素高的字,在290PPI的显示屏上高度就是1英寸,到了145PPI的显示屏上就变成2英寸了,就是比正常情况大了一倍。根据这个现象,只要把对应着普通显示屏那部分的缓冲区在显示时用普通显示屏上的1个像素显示缓冲区中的4个象素,就能使得在145PPI的屏幕上显示的290像素高的字还是1英寸高了。

      因为1个普通显示屏上的像素对应着4个缓冲区中的像素,所以缓冲区的像素数也是普通屏幕的像素数的4倍。这个4倍,会在X的设定中用到。具体而言,就是“输入的Viewport”的像素是“输出的Viewport”的像素的4倍。

      (Todo)

  • Ray Tracing from the Ground Up
    搭框架时发现用glut创建窗口是会segfault的。像NeHe的教程中就没有用到glut,而是用了glfw。用了NeHe的创建窗口的方法,就能在龙芯上正常运行了。
    有了Ray Tracer,就能对龙芯的性能有一个更好的了解,这个龙芯本就能逐渐地完成它的历史使命了。
    Screenshot-Untitled Window

 

发表在 Uncategorized | 留下评论

字幕君

字幕君(字幕君只是一个代号,其窗口名字还是「Fluid Demo」)是用于在舞台上显示歌词烘托演出气氛的一个小程序,最近的一次亮相是……在俺们的「胶囊乐队」第一次演出时登台,用于显示歌名和歌词。

mmexport1416941092981–>Screenshot - 11292014 - 05:02:09 AM

 

(对的,在现场那天,连FPS Counter都没有拿掉。因为俺感觉跳动的示数看起来就会让人觉得兴奋哈哈)

字幕君是以[1]为蓝本修改的。原先的程序模拟了一个热源、一个密度源作用下带有障碍物的网格中流体流动的现象。字幕君以[1]为蓝本修改的过程中,增加了以下内容:

  1. 将文字输出到密度场中参与流体相关计算、以及配套的非常非常简陋的设置歌词、颜色、转场时间的脚本。
  2. 经由boost::shared_memory_object来使得通过ssh遥控字幕君成为可能。

这两项功能是独立的、不互相依赖的。同时,在制作字幕君的过程中,还略微对Gauss-Seidel法和Jacobi法有了一些了解。

【Gauss-Seidel、Jacobi法和共轭梯度法】

这三种方法的用处都是为了解以下方程,亦即Navier-Stokes方程中的Diffuse项:

Diffuse项的连续形式:
Diffuse Term Continuous Form
将其转换成网格上的离散形式,就能看出 Jacobi 法和 Gauss-Seidel 法的端倪:
Diffuse Term Discrete Form
式子右边的是上一时刻的u场中的值,左边的是欲求的本时刻的u场中的值。经过多次迭代以后,上一时刻的u场就变成了本时刻的u场。

 

这个程序中解线性方程使用的是Jacobi法,[2]中用的是Gauss-Seidel法。Jacobi法与Gauss-Seidel法的区别在于在一次迭代中,是否使用已经在这次迭代中覆写过的元素。对应到程序中就是在最内层循环中的赋值语句的左侧写入到哪里: Jacobi法是在每一次循环结束时才统一将x场覆写一次,但是 Gauss-Seidel 法在循环过程中就将 x 覆写一次:

// Gauss-Seidel
for(int i=1; i<=w; i++) {
    for(int j=1; j<=h; j++) {         
       x[IX(i, j)] = (a*(x[IX(i-1,j)] + 
                         x[IX(i+1,j)] +
                         x[IX(i,j-1)] + 
                         x[IX(i,j+1)]) +                                x0[IX(i,j)]) / c;
   }
}
// Jacobian 
for(int i=1; i<=w; i++) {
    for(int j=1; j<=h; j++) {
      aux[IX(i, j)] = (a*(x[IX(i-1,j)] + 
                          x[IX(i+1,j)] +
                          x[IX(i,j-1)] + 
                          x[IX(i,j+1)]) +
                       x0[IX(i,j)]) / c;
    } 
} 
memcpy(x, aux, sizeof(float)*(w+2)*(h+2));

至共轭梯度法的实现则和这两者不太相同。[4]在讲述共轭梯度法时将问题描述为了一个线性系统Ax=b。一开始费了一番力气才明白其中的A、x和b分别是什么。虽然花了一番力气,但是有了这样的一般化描述,以后面对类似问题时就更容易明白了吧。在具体实现过程中,矩阵A是以一个函数FluidSolver::multiplyASolver存在的(对于N*N的网格来说,A矩阵的大小是N^2 * N^2,但是它是一个稀疏矩阵,大量的元素是0),x是下一时时刻的x场,b是这一时刻的x场。将展开后的离散形式中的下一时刻的x全部移到左边,这一时间的x全部移到右边,即可得到A的撰写方法。

// Conjugate Gradient (来自[4])
0. 设置A和b
1. r <- b - Ax
2. p = r
3. rho = dot(r, r)
4. rho0 = rho
5. for(iter=0; iter

Jacobi法的好处是每个格子之间没有相互依赖,适合GPU实现。Gauss-Seidel法的好处是收敛速度快一些。共轭梯度法的收敛速度更快,如下图所示:

收敛速度

以我自身的使用情况看来,[1]所提供的GPU实现可以在320x320的格子上达到60fps的更新速度,但是[2]的CPU实现只要超过300x90就会迟滞了。不过字幕君一开始的想法是在[2]上试验的,因为[2]中流体参与运算的所有过程都是在CPU上进行,不涉及帧缓冲对象和贴图对象之类的OpenGL Clinet和Host之间的数据交换,比较简单。

[4]说,共轭梯度法在GPU上的表现比红+黑的Gauss-Seidel法和Jacobi法都慢。至于为何尚不可知,但是若是在CPU上,凭借其高速收敛的特性,共轭梯度法应当是最快的。

【将文字内容与流体模拟连起来】

将文字输出到密度场中借用了freetype-gl的范例。freeglut-gl完成了读入TTF字形、将矢量字形转为顶点缓冲并将文字输出到一张贴图的工作。在这之后只需将含有文字的贴图以Shader写入[1]中的循环,既可做成一个以字形为形状的密度源。

目前的脚本支持三个不同的贴图同时在屏幕上出现,而这套脚本就是用于管理这三个不同的贴图,使其能在{不可见、淡入、可见、淡出}这四种状态间转换,另外控制每个状态中所对应的参数({淡入/出时间、处于可见状态时每帧向密度场添加的流量})。与以上截图相对应的脚本如下所示:

CapsuleBegin
Pen Color(1,1,1) Delay(1000)
Silo0 Text Pos(35,190) Delay(0) Weights(0.01,0.01) " 啦啦啦 啦啦啦 啦"
Brush0 Rect Velocity Pos(480,0,460,270) Value(-30,0,0,1) Frames(200000)
Silo0 FadeIn Duration(1000)
Silo1 Text Pos(35,90) Delay(1000) Weights(0.01,0.01) " 在生命中\n 最美丽的一天 "
Silo1 FadeIn Duration(1000)
CapsuleEnd

CapsuleBegin
Silo0 FadeOut Duration(1000) Impulse(0)
Silo1 FadeOut Duration(1000) Impulse(0)
Brush0 Stop
CapsuleEnd

从中可见在脚本是由一些位于CapsuleBegin和CapsuleEnd之间的命令组成的,若干连续执行的命令构成一个动作,在实际上台演出时,按一下空格键就会执行一个动作,即是包含在此动作中的所有命令。CapsuleBegin命令可以有标签,若有的话,则可通过B与N键来定位。在这回使用的脚本中,标签全部位于17首曲子各自的开始处。这样在遇到意外需要重来一曲或是字幕放映出错时,就可以及时调回到正确的位置了。

【远程控制】

若想在表演场地显示字幕君,必须将参与计算的电脑连接至调音台上的VGA Port上。由于调音台离舞台很远,所以人在舞台上时就不能直接操作参与计算的电脑。由于表演场地有Wi-Fi覆盖,所以通过Wi-Fi进行远程操控就成为一种可行方案。所以,将另外一台电脑相连之后,就有了以下的拓扑图:

逸珑8089D  XPS M1330 舞台上的银幕

这台逸珑8089D是去年团购时买的,重装了Debian 7。鉴于龙芯笔记本图形性能有限且无线网络带宽可能有限的问题,带图形的远程桌面不是好选择,所以只考虑了以文字界面的SSH登录这种方式。

SSH登录以后,还剩下的问题就是如何将正在运行中的程序的状态告知用户和如何响应用户的输入。这两个问题都可以通过为字幕君再编写一个配套的控制程序来解决。通过参照[3]的范例,达成了字幕君与字幕君的控制程序之间以boost::shared_memory_object通信的功能。在以上的画面呈现时,字幕君控制器所在的控制台中会显示如下内容:

Received: Heart Beat
Silo 0: [  KEEP      ]  啦啦啦 啦啦啦 啦
Silo 1: [  KEEP      ]  在生命中\n 最美丽的一天 
Silo 2: [  KEEP      ] 10.
Action -1/215, Line1005/1455

这样字幕君的功能就差不多齐全了。

【杂项】

※ 因为歌词有中文,所以在程序中有很多地方都需要使用wchar_t*,所以相应的字串处理函数也需要使用宽字符的对应版,如strcmp的对应即是wcscmp(Wide Character String Comparison)。有一个例,即是在printf时,可以不像其它与char*对应的函数那样使用wchar_t的对应版wprintf,而是只需使用printf("%ls")。其原因是wprintf与printf是不推荐混用的。另外,读取中文文本目前还不清楚除了使用C++ STL中的以外的方法,因此也只能将CPP文件宣告为extern "C"以后在C文件中使用。

※ 表演场地的舞台的VGA接口支持的分辨率有很多,当时选定的是960x540,可是实际测量之后,发现只有正中间的大小约为720x480的区域是可见的,周围全被裁剪掉了。为了照顾不同的屏幕大小,字幕君可将整个窗口的内容缩放,而相应的渲染流程也从直接渲染到窗口的帧缓存修改为先渲染到某贴图,然后将各个贴图贴到窗口上。这样做的原因是有些Shader依赖窗口位置和大小,而若直接从Clip Space的坐标(-1, 1),就可避免绝对窗口大小带来的问题。

【接下来的打算】

接下来我还打算将字幕君用作自己想翻唱的一首歌里,可是目前的状态是我唱功很不行,大概还需要多爬爬关于唱歌方法的文章和播客内容才能知晓如何突破吧。

【参考】

[1] Simple Fluid Simulation at The Little Grasshopper
[2] Stable Fluids at Caltech Multi-Res Modelling Group - Stam's Stable Fluids
[3] Create two C++ programms using the Boost library for a shared memory example
[4] Goncalo Amador, A. G. (2009). Linear Solvers for Stable Fluids: GPU vs CPU. In 17th Encontro Portugues de Computacao Grafica (EPCG’09).

发表在 Programming, Uncategorized | 留下评论

Thoughts on MidiSheetMusicMemo

最近我觉得《MidiSheetMusicMemo》有一个问题:在“问答模式”中玩一次的时间对于正常的谱子而言太冗长,以至于坚持到最后是一件很辛苦的事情。这本身并不是很大的问题,但是因为以现在的程序的状况,如果不坚持到最后,统计数据就不会更新,就不会有成就感,那就会让用户体验很不好。目前连俺作为开发者自身都没法认真玩完,对于其它用户可想而知。
就拿最近的《二部创意曲8》和《二部创意曲13》来说,虽然小节数不是很多,各有35个小节和25个小节,但是却要至少五分钟甚至是十分钟才能完成。即使这样的小曲子时间都如此之长,其原因之一可能是因为选项的个数太多:八选一从绝对数量来看是很多的,俺自己在使用时都会有一种“即使我能背下这个谱子,也不能很快地从八个选项中找到正确的选项,因为错误选项的干扰效应太强了。”的感觉。应该试试看三选一、四选一和六选一,不应该就从一开始就吊死在八选一这棵树上。
话说最近想尝试一种新的转场效果,并修复一些bug。希望年底之前有空做完吧。

发表在 Uncategorized | 留下评论

Cangjie input method mini game

It's here —> http://edgeofmap.com/cj
It's still under development.
I would want to gamify the learning process, creating a fun and rewarding experience. When I started learning 倉頡 in February I used a Win3.1 program (which was 16-bit!) called 「倉頡教室」.
It's first exercise was about the parts-keys. The purpose was to help remember which parts are on which [a-z] keys. The parts in Cangjie were divided into groups (Group 1=日月金木水火土, group 2=竹戈十大中一弓, group 3=人心手口, group 4=尸廿山女田卜) and so was the first exercise.
The second exercise teaches simple compound characters. Example: 明=日+月.
The web game has so far replicated the first exercise and part of the second exercise.
I was wondering this may be useful for not only those who're learning the input method, but also those who are learning Chinese characters, even without prior exposure to those characters.
Still this web app has a long way to go, either to becoming a fully usable Cangjie tutorial or a complete introduction to Chinese characters.

发表在 Uncategorized | 留下评论