自动机与表达式折行语法分析
概述
在分析折行实现前, 先说说对基本的算术结构的分析.自动机基类
grammar::AutomationBase (grammar/automation-base.h: 30) 能够处理所有没有在 Yacc 语法规则中给出的细节, 比如将因子与算符组成算式, 分析括号配对, 还有对逗号, 冒号等分隔符的处理.自动机对可以处理的项目作了基本的分类, 对应于其中各名为
pushXxx 的函数和 matchClosing 函数. 而 matchClosing 函数相当于将 pushCloseParen, pushCloseBracket 等三种不同的结束括号合并成一个函数了, 因为大部分自动机自身不处理三种结束括号, 而将它们派发给其它的自动机处理.什么, 自动机还有很多种? 没错, 在 Stekinscript 语法模块设计中, 用来分析表达式的自动机有多种, 不同的自动机互相利用使得代码复杂度能够大大降低. 举个例子, 算术运算自动机
grammar::ArithAutomation (grammar/expr-automations.h: 9) 本身不处理大括号配对, 但表达式里面终归是可以出现大括号裹起来的字典的; 当这种情况发生时, 算术自动机会创建一个字典识别自动机 grammar::DictAutomation (grammar/expr-automations.h: 132), 让它顶替自己处理接下来的部分; 而这个字典自动机自己又是很懒的, 它才不会自己动手去识别用表达式描述的字典的键跟值, 怎么办呢? 与是它再新建一些算术自动机来识别表达式, 而自己只坐等逗号冒号等分隔符, 或者花括号结束.无论哪一种自动机, 都只会对特定的一些种类的
Token 感兴趣, 而基类 grammar::AutomationBase 对任何项目的实现都是一句话 (grammar/automation-base.cpp: 58-97)error::unexpectedToken(pos, image);
Token 并报错. 除了这种粗暴的对待方式, 大致上来说每个函数还有如下方式对待 Token- 接受并记录, 比如
ArithAutomation对象在正确的时候遇到运算符或者因子 - 接受并丢弃, 这个说法有点语死早的感觉, 例子就是上面
ArithAutomation与DictAutomation的故事, 在ArithAutomation对象遇到开始的大括号时, 它会创建一个DictAutomation对象, 然后丢弃大括号 (留着也没用) - 将自身归约并移交, 比如刚才提到,
DictAutomation会委托ArithAutomation为它识别键值表达式, 那么此时如果ArithAutomation遇到一个冒号, 那么它自身不会处理, 而是首先将自己归约成一个表达式grammar::Expression(grammar/node-base.h: 24) 对象, 并传递给它的委托者, 然后将这个冒号也一并移交给其委托者处理 - 将自身归约并丢弃, 比如
DictAutomation遇到结束的大括号时, 它会将自己归约成一个字典grammar::Dictionary(grammar/expr-nodes.h: 228) 对象, 完成使命, 然后弃掉结束大括号
自动机栈
刚才提到, 各种不同的自动机会相互委托, 一起完成表达式语法分析过程, 这个过程无可避免地要用到栈结构, 此栈名字毫无亮点地称之为自动机栈grammar::AutomationStack (grammar/automation-base.h: 67).引入自动机栈之后, 重新描述刚才
ArithAutomation 与 DictAutomation 的基情应该这么说, 当 ArithAutomation 对象遇到大括号时, 新建一个 DictAutomation 对象压进栈中; 而当 DictAutomation 分析完字典后, 将自己从栈中弹出, 然后将归约得到的 Dictionary 表达式对象交给栈顶的自动机.自动机栈自然拥有栈基本的功能如
push, pop 等等, 此外它还支持其它一些函数, 如 reduced 的两个重载 (grammar/automation-base.cpp: 31-43), 当位于栈顶的自动机完成使命之后, 通过这两个函数传入自己归约得到的表达式或表达式列表, 自动机栈这时会弹出栈顶的自动机, 然后将传入的结果传给当时的次栈顶.折行判定
在自动机栈运作的过程中, 如果遇到行尾, 这时需要判定折行是否为语句结束.每个自动机类型的对象有其固有的判定法, 比如,
ArithAutomation 刚刚才吃掉一个 * 符号, 之后遇到换行, 当然不会认为这是语句结束, 它还等着二元运算后面的项呢, 如读入代码进行到 a * 这里时遇到折行x: a *
b
ArithAutomation 自身已经完结, 它并不能直接决定语句是否结束, 因为它有可能在某个没有关闭的实参列表中, 如f(0, a + b
* c)
a * b 时, 栈顶的 ArithAutomation 可以认为语句结束了, 可是如果此时贸然归约当前内容 (a + b) 为一个表达式却是错误的, 因此它要去询问一下次栈顶, 也就是它下面的那个自动机是否应该结束语句. 如此一来, 只有整个自动机栈都表示折行是语句结束, 那么才会结束语句.几个典型的
eolAsBreak 重写实现如下ArithAutomation::eolAsBreak(bool) const(grammar/expr-automations.cpp: 340) 如刚才所描述的那样DictAutomation::eolAsBreak(bool) const(grammar/expr-automations.cpp: 692) 现在搞字典正搞一半呢, 一票否决ExprStmtAutomation::eolAsBreak(bool) const(grammar/expr-automations.cpp: 383) 哟, 少年们收工了么? 直接给true(这个自动机是分析表达式语句的自动机, 一直会垫在自动机栈底部, 因此轮到它来决定是否结束时, 它肯定表示该结束了)
lambda 冒号后的折行
有典型的当然有非典型的, 它便是grammar::NestedOrParamsAutomation (grammar/expr-automations.h: 96).是想一下, 如果一个
ArithAutomation 在等待因子时, 来了一个括号该怎么处理? 更一般地, 如下面这种情况x: (
这时以下两种情况都有可能
x: (a + b) * c
x: (a, b): c
而对于下面这两种情况则区分更加麻烦
x: (a) * c
x: (a): c
(a) 表示什么都是未知的, 可以是一个无聊程序员忘记擦掉的括号, 或者某个代码生成程序额外生成的括号, 括起一个常量什么的, 又有可能是正常的 lambda 形参. 因此与其它自动机对待括号的方式不同, NestedOrParamsAutomation::matchClosing (grammar/expr-automations.cpp: 491) 在结束括号头一次出现时 (即成员变量 _waiting_for_closing 还为 true 时), 对其的处理是 "接受并丢弃" 而不是 "将自身归约并丢弃", 并且在丢弃这个圆括号后, 开始痴心等冒号 (置 _wait_for_colon = true).如果这时果真来了冒号 (
NestedOrParamsAutomation::pushColon L 511), 那么自动机会向栈里面再压入一个 ArithAutomation 对象, 这个对象开始接收行间 lambda 的返回值表达式.问题来了, 如果这时马上来了个换行呢? 也就是说, 这个新上的
ArithAutomation 还没接到任何 Token 就迎来了折行, 该怎么做?回顾
ArithAutomation::eolAsBreak, 对于 ArithAutomation 来说, 如果它自己是空的, 那么它会允许此时折行, 并询问次栈顶该如何做; 此时它会向次栈顶传入一个 bool 参数, 告诉次栈顶自己是不是空的bool ArithAutomation::eolAsBreak(bool) const
{
if (_need_factor && !_empty()) { // _need_factor: 当前是否正在等因子, 比如在二元运算符后该值为 true
// _empty(): 当前已经接受的内容是否为空
return false;
}
return _previous->eolAsBreak(_empty());
}
NestedOrParamsAutomation::eolAsBreak (L 578) 则会在冒号之后并且 lambda 返回值为空表达式时表示一定能折行bool NestedOrParamsAutomation::eolAsBreak(bool sub_empty) const
{
if (_afterColon() && sub_empty) {
return true;
}
if (_wait_for_closing) {
return false;
}
return _previous->eolAsBreak(false);
}
自动机栈与 ClauseBase 对象
自动机栈归约语句
讲了这么一通, 下面该讲讲自动机栈是如何与ClauseBase 对象合体了.在每个
ClauseBase 对象中都有个自动机栈对象 _stack (grammar/automation-base.h: 105), 如果正在解析的这一句与表达式有关系 (比如表达式语句, 或 if 分支), 那么这个栈就是非空的, 并且此栈正在解析表达式. 当折行要发生时, ClauseBase::tryEol 被调用 (上篇中最后就说到这里停下), 而这个函数实现先看看一下栈是不是空的, 如果不是, 则看看当前能不能结束语句, 如果能, 就调用自动机的 eol 函数结束语句, 否则就续行.而在送入表达式
Token 序列之前, ClauseBuilder 对象会调用 ClauseBase 的 prepareXxx 函数 (grammar/automation-base.cpp: 132-145), 这些函数中会构造特殊的自动机, 并且构造时将 ClauseBase 对象自身传入. 以 grammar::ReturnAutomation (grammar/expr-automation.h: 174) 为例, 其 eol 函数实现为/* grammar/expr-automation.cpp: 723 */
void ReturnAutomation::eol(ClauseStackWrapper&, AutomationStack& stack, misc::position const&)
{
if (_expr->empty()) {
_clause->acceptStmt(util::mkptr(new ReturnNothing(_expr->pos)));
} else {
_clause->acceptStmt(util::mkptr(new Return(_expr->pos, std::move(_expr))));
}
stack.pop();
}
Return 语句 (grammar/stmt-nodes.h: 73) 对象或 ReturnNothing 语句 (grammar/stmt-nodes.h: 86) 对象.自动机栈处理多行 lambda
之前说到, lambda 在其形参列表及冒号后遇到折行时, 会将该折行视为语句结束, 但问题在于此时语句并没有真正结束, 如setTimeout(():
console.log('Aki Misawa')
, 2000)
, 2000) 处, 那么这个问题如何处理呢?来看看
eol 函数中的第一个参数类型 grammar::ClauseStackWrapper (grammar/automation-base.h: 109) 在 eol 函数中是如何被使用到的. 在自动机实现文件 grammar/expr-automations.cpp 中检索「ClauseStackWrapper&,」会发现大部分自动机在实现时根本没有理睬这个参数; 少部分将此参数直接传递给其它自动机, 自身并没有使用, 唯一只用了该参数的只有 NestedOrParamsAutomation::eol (L 589).它对此参数的使用并不复杂, 如果当前自动机正处理到冒号之后, 并且返回值为空 (也就是正好在
(): 这样的情况下), 那么就调用 ClauseStackWrapper::pushBlockReceiver 函数 (grammar/automation-base.cpp: 196). 这个函数会向该 wrapper 所持有的 ClauseBase 栈 (就是 ClauseBuilder 对象里面那个) 压入一个 ClauseBase (其子类的 L 160) 对象, 这个对象会使得新进的语句成为语句块, 也就是多行 lambda 函数体中的一员, 而不是后续的平级语句, 直到出现一个缩进较低的语句, 终止多行 lambda 的函数体. 多行 lambda 相关的折行也就藉由这个方式解决了.(全文完)
