获取源代码
Stekinscript 的项目地址在 https://github.com/neuront/stekinscript, 获取最新版代码$ git clone git://github.com/neuront/stekinscript.git
$ cd stekinscript
$ git reset --hard 9b756ad111fa3cf1d78a89e050a1adf38fa5e0b6
外围模块概述
下面内容中, 凡是首次提到某个类或函数时, 会在括弧中用文件路径: 行号的方式给出它所声明或定义的位置, 如main 函数 (stekin.cpp: 11); 上下文很明显有说明哪个文件时, 以 L 行号 说明在哪一行.对 C++11 的使用
既然是用 C++ 实现那么内存管理Stekinscript 的内存管理大量依赖于 C++11 中的
std::unique_ptr 跟 move semantic, 并且对 std::unique_ptr 自有一套封装, 包括如下的几个类型util::sptr(util/pointer.h: 94) 是直接对std::unique_ptr的封装, 但不允许通过get()方法直接取得其中的裸指针, 也不允许通过单目 * 操作符获取对象的引用, 单目型号操作符获取的是util::sref类型对象util::sref(util/pointer.h: 23) 是共享引用类型, 几乎等价于一般对象引用类型, 只是不可以通过单目 & 操作符取引用, 另外使用 -> 操作符使用其内部的对象而不是直接使用 . 操作符
C++11 的基础知识可以参考这些文章.
错误处理
需要安装有 Python 2.7 版本, 在源码目录下执行$ make code-gen
report/errors.h 包括了所有编译报错函数, 凡是源代码中出现
error:: 名字空间中的调用均声明于此. (虽然生成的代码格式上寒碜了点, 勉强可读)Lex/Yacc
既然是讲 C++ 程序, 本该从main 函数入手, 但 Stekinscript 有一些依赖在初始化环境 (stekin::initEnv env.h: 9) 之后, 立即调用了 Yacc 中的 yyparse() 函数, 所以这时要去看 Lex/Yacc 文件了.grammar/lexica.l 文件定义了词法单元, 其中行首空格 (L 19) 不可被忽略 (否则哪来的缩进语法), 而行首不能有制表符否则报错 (L 24). 缩进层次将被缓存在全局变量
grammar::last_indent 中 (grammar/yy-misc.h: 23). 其它的词法单元看看便罢.Analysis然后小的重头在 grammar/syntacticall.y 这个文件中, 它实现了部分简单的语法规则. 去掉其中的语句, 开头的一些产生式如下 (L 42)
root:
stmt_list
;
indent: ... /* 这是缩进 */
eol: ... /* 行尾 */
stmt_list:
stmt_list stmt
|
stmt_list clue
|
;
stmt:
arithmetics
|
func_return
|
import
|
export
;
...
root 是整个语法产生式的根节点, 每个 Stekinscript 源文件是由语句列表构成, 而语句列表就是任意多条语句, 语句包括算术语句 (arithmetics), 返回语句 (func_return) 等等. 下面再看看这样的语句又是如何构成的 (L 93)arithmetics:
indent expr_sequence eol { ... }
;
func_return:
indent KW_RETURN expr_sequence eol { ... }
|
indent KW_RETURN eol { ... }
;
expr_sequence 的这个构成部分, 想必这肯定是非常重要的东西了, 那么它的定义又是 (L 150)expr_sequence:
expr_sequence expr_token { ... }
|
expr_token { ... }
;
expr_token:
'.' { ... }
|
'!' { ... }
|
AND { ... }
|
...
|
INT_LITERAL { ... }
|
DOUBLE_LITERAL { ... }
|
...
|
'(' { ... }
|
...
expr_sequence 这玩意儿没任何机关陷阱, 就是单纯一连串的词法单元序列而已. 现在的问题是- 缩进级别如何决定了语句所属的代码块
- 如何实现折行
stmt_list: stmt_list stmt 除了归约什么都不干, 而语句本身归约时, 所有的内容都直接送到 grammar::builder (grammar/yy-misc.h: 22) 这东西里去了arithmetics:
indent expr_sequence eol
{
grammar::builder.addArith($1, misc::position($3), $2->deliver());
}
;
插播一个编译原理知识, 正如正则表达式无法处理括号配对一样, Yacc 或任何其它的语法规则解释程序都无法完美地处理缩进语法, 因为它们所能解决的是文法模型中的 II 型文法, 或称为上下文无关文法, 而缩进语法的语言每个子句却是上下文相关的, 它之前的其它子句的缩进便是这个 "上下文".
当然也不是说上下文无关文法一定无法描述缩进语法, 其实也可以用下面这种无赖手法来写产生式
program:
level_0_block
|
level_1_block
|
level_2_block
|
...
;
level_0_block:
level_0_block level_0_statement
|
level_0_statement
;
...
level_0_statement:
line_begin statement_content
;
level_1_statement:
line_begin ' ' statement_content
;
level_2_statement:
line_begin ' ' ' ' statement_content
;
...
言归正传, 因为上面这个硬伤, 而又不能把代码写得太难看, 所以语法分析必须借助一些更复杂的手法来完成. 既然如此, 那么 Yacc 文件索性就简单一点拉倒. 产生式中用到的下列类型
%union {
// ...
grammar::OpImage* op_type;
grammar::Ident* ident_type;
grammar::NameList* names_type;
grammar::TokenSequence* expr_seq_type;
grammar::Token* expr_token_type;
}
grammar::Token 声明在 grammar/automation-base.h: 16, 其余声明在 grammar/syntax-types.h 中.grammar::Token 表示一个词法节点, 其实现子类声明在 grammar/expr-nodes.h 中. 而 grammar::TokenSequence 则是对 std::vector<util::sptr<grammar::Token>> 的包装, 因为 C++ 不允许 union 里面放对象而只能放指针, 因此在 Yacc 里面将就着用这个. 而在 grammar/syntacticall.y: 28%type <expr_seq_type> expr_sequence
expr_sequence 会用到此类型. 调用这对象的 deliver() (grammar/syntax-types.cpp: 48) 就获取其中的 std::vector<util::sptr<grammar::Token>> 以上供到 grammar::builder 那里去, 它的使命就完成了.总体看来, Yacc 这部分可以说这就是个坑, 除了把一个个词法单元打包, 几乎什么事情都没有做嘛. 那么
grammar::builder 这个神秘的幕后对象究竟是谁, 它是怎么把缩进相同的语句组织在一起的, 又是如何解决折行问题呢?语法分析中的缩进解析
解决缩进语法所需的数据结构
在调用grammar::builder 的类似 addArith (grammar/clause-builder.h: 23, grammar/clause-builder.cpp: 30) 这样的方法时, 缩进长度也作为参数一同传入, 因此很明显如何根据缩进组织语句块会在 ClauseBuilder 类中处理.在每个
ClauseBuilder 对象中包含有一个栈 _clauses (grammar/clause-builder.h: 72), 栈中每个元素是个 ClauseBase (grammar/automation-base.h: 78) 对象. 每个 ClauseBase 指的是一个语句块, 或如分支语句那样的一个复合语句, 如全局空间下的全部语句console.log(0)
console.log(1)
console.log(2)
ClauseBase 对象, 而下面这个分支console.log(0)
if x > y
console.log(1)
console.log(2)
ClauseBase 对象, 更准确地说, 其子类 IfClause (grammar/clauses.h: 14) 的对象. 每个 ClauseBase 有一个固有的缩进属性 indent (grammar/automation-base.h: 87), 这表示它本身的缩进层次 (而不是其成员的), 比如上面例子中的分支, 它的 indent 属性值为 0, 而下面例子中func fib(n)
if (n < 2)
return 1
return fib(n - 1) + fib(n - 2)
fib 函数定义的 indent 属性为 0, 而 if 分支的 indent 属性为 4. 一个 ClauseBase 的自身缩进值须区分与它的成员子句的缩进值 _member_indent (grammar/automation-base.h: 106), 如上例中函数本身的缩进值为 0 而成员子句缩进值为 4.在
ClauseBuilder::_clauses 这个栈中, indent 属性越大的越靠近栈顶, 而栈底 ClauseBase 对象则是一个固定的 indent 属性为 -1 的特殊 ClauseOfPack 对象 (grammar/clause-builder.h: 56). (而其 _member_indent 不一定为 0, Stekinscript 支持所有全局空间中的语句有一个相同的不为 0 的缩进, 这点与 Python 不同.)根据缩进组句
以下面这段代码为例if x > y
console.log(0)
console.log(1)
console.log(2)
indent 值为 0 的) ClauseBase 对象持续遇到缩进 4 的语句 (前两个 console.log) 就将它们加入到自己麾下, 而此后遇到同样缩进为 0 的语句时, if 分支对应的 ClauseBase 对象就需要先连同它的子块中所有的语句一起变身成一个普通语句插入到全局语句块中, 此后 console.log(2) 这条语句才被插入到全局语句块中.下面的图示给出更详细的情况, 当
console.log(2) 被放入 ClauseBuilder 时, 栈中有两个 ClauseBase 对象+--------------------------+ <- bottom
| ClauseOfPack (indent:-1) |
+--------------------------+
| IfClause (indent:0) |
+--------------------------+ <- top
| |
ClauseBuilder 会尝试依次弹出栈中的 ClauseBase 对象, 告诉它们现在需要归约了, 然后它们会乖乖地成为一个普通语句 (或者函数定义). 其具体做法实现于 IfClause::deliverTo (grammar/clauses.cpp: 31). (if 分支语句的定义以及其它各种语句定义参见 grammar/stmt-nodes.h grammar/stmt-nodes.cpp)另一方面,
ClauseOfPack 对象会长期霸占栈底, 由于它的固有缩进是 -1, 因此永远不会自然从栈中出来. 当然在文件结束后会手动弹它的.当新语句 (或语句的一个部分) 被添加到
ClauseBuilder 对象时, 都会直接或通过 _prepareLevel 函数 (grammar/clause-builder.cpp: 147) 间接调用 _shrinkTo (grammar/clause-builder.cpp: 134) 函数. 这个函数会试图依次从 _clauses 栈中弹出所有缩进不大于指定缩进的全部 ClauseBase 对象 (的确是 "试图", 因为 ClauseBase::tryEol 方法可能会闹个别扭. 此函数后面会详细分析), 顺利的话, 新添加的语句就会与所有与之缩进相同的语句会师.如果需要通过输出日志调试这部分代码, 可以插入类似这样的输出
/* grammar/clause-builder.cpp */
/* 30 */
void ClauseBuilder::addArith(int indent_len
, misc::position const& pos
, std::vector<util::sptr<Token>> const& sequence)
{
std::cerr << " + LOG Arithmetic of indent=" << indent_len << " at pos=" << pos.str() << std::endl;
if (_shrinkTo(indent_len, pos)) {
_clauses.back()->setMemberIndent(indent_len, pos);
_clauses.back()->prepareArith();
}
_pushSequence(pos, sequence);
}
/* L 85 */
void ClauseBuilder::addIf(int indent_len
, misc::position const& pos
, std::vector<util::sptr<Token>> const& sequence)
{
std::cerr << " + LOG If branch of indent=" << indent_len << " at pos=" << pos.str() << std::endl;
if (!_prepareLevel(indent_len, pos, "if")) {
return;
}
_clauses.push_back(util::mkptr(new IfClause(indent_len, pos)));
_pushSequence(pos, sequence);
}
/* L 134 */
bool ClauseBuilder::_shrinkTo(int level, misc::position const& pos)
{
std::cerr << " + LOG Try shrinking to indent=" << level << " at pos=" << pos.str() << std::endl;
while (level <= _clauses.back()->indent) {
if (!_clauses.back()->tryEol(pos, _clauses)) {
return false;
}
std::cerr << " + LOG Deliver clause whose indent=" << _clauses.back()->indent << " at pos=" << pos.str() << std::endl;
util::sptr<ClauseBase> deliverer(std::move(_clauses.back()));
_clauses.pop_back();
deliverer->deliverTo(*_clauses.back());
}
return _clauses.back()->tryEol(pos, _clauses);
}
