随笔-341  评论-2670  文章-0  trackbacks-0

    大概一年前曾经用C++开发了一个可以在C++中直接写上下文无关文法的上下文无关文法分析器。这玩意儿叫Syngram。Syngram曾经做了两次,第一次做成了用一个类去读文法文件,后来不爽就改成了直接在C++里面写的。我弄了一个叫Term的类,重载了一些操作符,于是你可以搞分支、可选、错误处理等复杂的文法推导式。现在打算做一个周边工具。

    这个周边工具的由来是这样的。后来我用Syngram开发了一个支持namespace、class和函数的动态语言Vczh Free Script 2.0 beta,这个动态语言支持面向对象、泛型以及函数式等若干范式,语言可以调用编译器编译一个字符串并操作。虚拟机被我做成了两个dll,一个是给native c++调用的,另一个是给C# 3.0调用的。编译器我用了Syngram,在上面那个链接所提供的代码里就有一个文件,布满了文法推导式以及每一个式子的语义函数。旁边的一个文件写了一个很大的语法树数据结构,是一组C++类。

    这门脚本语言的第一个版本的编译器开发长达三天,因为我要花一天时间做文法,一天时间做语法树,一天时间生成指令。第一版只支持闭包和数组。这么小的语言写一个编译器花了三天实在是浪费的太多了,因为后来我发现语法树是一个很有规律的东西。我就在想,能不能我就写一点点东西,然后有一个工具就帮我把这些代码写出来呢?前几天洗澡的时候想到了一个解决方案。

    我可以用一种很简便的方法写一个可以被转换成C++的类、列表、字典和枚举类型的语法树模型,然后将一点点东西添加在推导式里面告诉推导式创建什么样的对象、如何修改对象、列表和字典等。错误信息的产生以及错误恢复已经在Syngram里面实现了,很容易支持进去。于是现在又变成了类似读文法文件产生代码的东西了,不过跟Syngram第一版有很大区别。

    首先,Syngram作为一个C++的类库,仍然可以支持在C++里直接写文法、错误处理以及语义函数。
    第二,这个新的工具读入文法文件之后,产生的并不是一个完整的语法分析器,而是一些基于Syngram类库的代码。
    第三,这个新的工具的最大好处在于可以在自己写的语义函数(将分析结果转换成自己想要的语法树)中和自己写语法树的数据结构(特别是相应的一些虚函数族)这两个没有挑战性而且很烦的工作中解放出来。工具将根据输入的文件生成用于表达数据结构的一堆类(通常是几十个),根据需求自动分成几个继承的组,为他们添加一两个使用了Visitor模式的接口。于是虚函数的方便被转移到了Visitor模式的产物中,自己的代码跟生成的代码完全隔离。
    最后,说不定这个工具有GUI。

    前几天完成了Syngram所属的Vczh Library ++ 2.0中的GUI Framework预览版。这个东西的初衷是写给我自己用的,因为我很不喜欢MFC等有BEGIN_MESSAGE_MAP或者需要我处理WPARAM和LPARAM的界面库,于是自己弄了一个。不过GUI Framework实在是庞大,一个人做起来也是比较吃力的。如果我心情好GUI 1.0 beta比这个Syngram Helper早完成的话,那么Syngram Helper就会有GUI用了。今天写了个简单的语法文件的文法,贴出来先。里面的注释用英语仅仅是因为我懒的来回切换输入法,估计有一堆语法错误,不要计较。

KEYWORD  ->class
  ->bool
  ->int
  ->double
  ->string
  ->list
  ->map
  ->term
  ->infer
OPERATOR ->[
  ->]
  -><
  ->>
  ->,
  ->=
  ->|
  ->:
  ->#
  ->@

IDENT  ->[a-zA-Z_]\w*
REGEX  ->[^\r\n]+\r\n
COMMENT  ->'[^\r\n]*\r\n
STRING  ->"([^\\"]|\\\.)*"

CLASS   ->class IDENT [: IDENT] "{" MEMBERS "}"
ENUM  ->enum IDENT "{" IDENTS "}"
MEMBER  ->TYPE IDENT
  ->STRING IDENT //external member, treat STRING as type, can not be accessed in semantic rule
TYPE  ->bool
  ->int
  ->double
  ->string
  ->token  //store a token
  ->list<TYPE>
  ->map<TYPE,TYPE>
  ->multimap<TYPE,TYPE>

LEXICAL  ->term IDENT REGEX
SYNTAX  ->infer TYPE IDENT RULE_EXP
RULE_EXP ->[ RULE_EXP "|" ]RULE_SERIES
RULE_SERIES ->[ RULE_SERIES ]RULE_UNIT
RULE_UNIT ->RULE_TERM
  ->"[" RULE_EXP "]"
RULE_TERM ->IDENT [ "[" SEMANTICS "]" ]

SEMANTIC ->SEMANTIC_TARGET [ "=" SEMANTIC_SOURCE ]
SEMANTIC_TARGET ->:IDENT // Field of result, new map item or new list item
SEMANTIC_TARGET ->#key  // add item in result map using this key
SEMANTIC_TARGET ->#value // add item in result map using this value
SEMANTIC_TARGET ->#item  // add item in result list using this value
SEMANTIC_TARGET ->#result // treat this value as the result, result map or result list
    // new item in a path is not required if there is at least a #result term in the same path
SEMANTIC_TARGET ->#alias // name this value as SEMANTIC_SOURCE
SEMANTIC_TARGET ->#error // treat SEMANTIC_SOURCE as error message
SEMANTIC_TARGET ->#keyerror // treat SEMANTIC_SOURCE as error message and raise an error if the specified key exists
SEMANTIC_TARGET ->#past  // past this term when error occurs
SEMANTIC_TARGET ->#read  // read a token when error occurs
SEMANTIC_TARGET ->#exit  // terminate parsing when error occurs
SEMANTIC_SOURCE ->IDENT  // value of alias or enumeration item
SEMANTIC_SOURCE ->STRING // value of error message
SEMANTIC_SOURCE ->@IDENT // value of external string
/*
#key, #value, #item, #result : can only appears once in a path
#alias    : can not be conflict in a path
#error, #past, #read, #exit : can only appears once in a term
#alias, #error   : must be used with SEMANTIC_SOURCE
#keyerror   : can only appears once in a term, must be used with #key
:IDENT    : can not be conflict in a path
*/

IDENTS  ->IDENT [IDENTS]
MEMBER  ->MEMBER [MEMBERS]
SEMANTICS ->SEMANTIC ["," SEMANTICS]
TYPES  ->( CLASS | ENUM )[TYPES]
LEXICALS ->LEXICAL[LEXICALS]
SYNTAXES ->SYNTAX[SYNTAXES]

PROGRAM  ->TYPES LEXICALS SYNTAXES

posted on 2008-08-27 05:11 陈梓瀚(vczh) 阅读(1845) 评论(5)  编辑 收藏 引用 所属分类: 脚本技术

评论:
# re: Syngram Helper开始设计:一个能用来写编译器的工具 2008-08-27 06:25 | Lnn
super!  回复  更多评论
  
# re: Syngram Helper开始设计:一个能用来写编译器的工具 2008-08-27 09:13 | Michel
是否可以公布一下你的学习曲线?
读过哪些读物能够达到现在的程度?需要做哪些努力,关注哪些方面?
如果您的饮食对您的能力有所提高的话,也可以公布一下~  回复  更多评论
  
# re: Syngram Helper开始设计:一个能用来写编译器的工具 2008-08-27 09:25 | 陈梓瀚(vczh)
事实上我以前是做图形的,后来中途改方向,反正现在看起来以前走的路还真是乱七八糟。罢了。  回复  更多评论
  
# re: Syngram Helper开始设计:一个能用来写编译器的工具 2008-08-27 17:01 | foxtail
谁都说不清自己学习的路 摸爬滚打过来的  回复  更多评论
  
# re: Syngram Helper开始设计:一个能用来写编译器的工具 2008-08-27 19:19 | 空明流转
这个 Demo 倒是挺简洁的。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理