2016-09-21 编译器 go

开了个新坑。正在写一个使用 PEG (Parsing Expression Grammar (Wikipedia)) 的 parser generator,类似于 PEG.js

PEG 在 2004 年由 Bryan Ford 提出,不同于传统的 CFG,类似于以前的自顶向下解析。主要不同在于选择运算符,PEG 中,如果第一个选项成功匹配了,之后的都将被忽略。

项目已经开源在 github: PEG.go

进展

  • Scanner: 完成。
    • 要支持 escaped character: "\t\n",字符串里问题不大,看一下前一个字符就行了。
    • 有一个比较纠结的地方是我希望能支持 utf-8,但是 utf-8 是可变长的,一个字符可能在多个 byte 里。现在的方案是在一开始把整个文件读到一个字节数组,然后转换成字符数组。
      Scanner 接受一个 reader 并维护了一个 buffer (一个字节数组)。每次需要下一个字符的时候,先从 buffer 里取,当 buffer 里内容太少的时候重新填满 buffer。
    • 还有一个没解决的问题就是,peg 文件里有可能出现一段用户写的,用花括号围起来的代码。但是这段代码里可能出现花括号。如果是一对花括号是没有问题的。但是有不匹配的单个左/右花括号的时候,就不能正确处理了。
  • Parser: 完成。
    • 手写了一个递归下降的 Parser。
  • Code generation: 基本完成,仍需改进。
    • 函数返回的都是 interface{},之后用起来很麻烦。
    • 当函数返回 nil 的时候,认为解析失败。但是真正的情况中有可能不需要返回。
      现在函数有两个返回值,第一个是实际返回的内容,第二个是 error 类型。有个小问题就是用户写的代码中 return 时需要返回两个值,似乎有点麻烦(?)。以后可以把返回的变量名指定,这样返回的时候只需要 return 就行了。
      提供了返回变量,ret 和 err。只需要赋值就行了,不需要手动写 return。
    • 最近看到 parser combinator,似乎有点意思。
    • 错误提示和处理还没有。

未来

这部分是在现在的问题都解决后的一些方向。

  • 实现 Packrat parser。它能够保证线性的运行时间,但是会消耗更多的内存。
  • 处理左递归。

参考资料