zDoc 的解析自动机
优质
小牛编辑
132浏览
2023-12-01
对于每个段落的解析,依靠自动机。本文为自动机的实现者提供一些参考
自动机堆栈
头 .................... 尾
[C][C][C] # 字符缓冲栈
[T][T][T] # 数据栈
[@][@] # 操作栈
1 ']' # 指示堆栈,并联自动机当做退出字符,串联当做子机下标
四个堆栈的操作原则是:“谁压入谁弹出”
堆栈通过 {..} 来表示,可以构成级联
{..}
{..}
{..}
{..}
{..}
每个自动机都有方法
enter(AmStack, char):AmStatus # 试图进入这个自动机,如果成功将设置堆栈
eat(AmStack, char):AmStatus # 消费字符
done(AmStack):void # 将字符缓冲的内容填充到数据栈
任何一个自动机每次被执行都会返回如下四个行为之一
DROP # 丢弃当前堆栈
CONTINUE # 继续,读取下一个字符,执行栈顶自动机的 run 方法
DONE # 将弹出操作栈顶自动机,并执行它的 done 方法
DONE_BACK # 执行 DONE 操作,并重新进入下一个可能的自动机
一个堆栈的数据结构
buffer # 字符缓冲
objs # 数据栈
ams # 操作栈
qcs # 退出字符
sis # 指示堆栈
i_obj
i_am
i_qc
i_si
candidates # 候选堆栈
它应该支持的操作
enter(Am, char): bool # 是否可以让这个自动机进入堆栈
eat(char) : AmStatus # 消费字符,返回 false 表示不能消费了
done : void # 调用栈顶自动机的 done
close : T # 将对象堆栈清空
pushAm(Am)
popAm : Am
peekAm : Am
pushObj(T)
popObj : T
peekObj : T
pushQc(char)
popQc : char
qc : char
pushSi(int)
popSi : int
si : int
串联自动机
串联自动机有一个固定的进入字符
假设一个堆栈状态为:
[] # 字符缓冲是干净的
[] ... # 数据栈
[] ... # 操作栈
... # 指示堆栈
enter ...
#------------------------------------------------
如果符合进入字符
[] # 字符缓冲内容由第一个子机决定
[T] ... # 准备一个对象
[&] ... # 压入自己
-1 ... # 指示字符为自己第一个子机
eat ...
#------------------------------------------------
如果发现当前子机下标小于 0,则表示子机未被执行 enter ,那么就
将下标变成正数,并调用对应子机的 enter
(注意,这里的下标是 1 base,需要转换成 0 base 使用)
[] #
[T] ... # 还是那个对象
[&] ... # 串联自动机
1 ... # 下标变成正数,并调用子机的 enter
如果当前子机 enter 未遂,或者 eat 返回 DROP 了,那么自己也返回 DROP
如果返回的状态是 DONE 或者 DONE_BACK,
会调用当前子机的 done,并试图切换到下一个子机
[] #
[T] ... # 还是那个对象
[&] ... # 串联自动机
-2 ... # 下标指向下一个子机,并调用子机的 enter
如果没有下一个子机了,则返回 DONE | DONE_BACK
done ...
#------------------------------------------------
如果为 done 时,堆栈应该为
[C][C]... # 缓冲可能为空也可能有字符
[T] ... # 还是那个对象
[&] ... # 操作栈顶应该是最后一个子
2 ... # 下标指向最后一个子机
如果没有达到最后一个子机,那么调用当前子机的 done
然后将将自己退栈
[]
[] ... # 将 T 组合到之前的对象中
[] ... # 清除自己
... # 清除了指示下标
并联自动机
如果发现有超过一个自动机都进入了堆栈,并联自动机会依次为其构建堆栈
假设一个堆栈状态为:
[] # 字符缓冲是干净的
[] ... # 数据栈
[] ... # 操作栈
... # 指示堆栈
enter ...
#------------------------------------------------
构建新堆栈:
[]
[] # 不要准备对象
[@] # 表示有子自动机进入了
']' # 自己的退出字符
如果超过一个自动机进入了,那么将堆栈变成
{候选堆栈A} {候选堆栈B} -?- {母堆栈}
{候选堆栈C} /
...
那么就会将自身压入母堆栈,同时也要在母堆栈标识退出字符
[]
[] ...
[+]... # 仅仅在当前堆栈压入自身
']'... # 压入自己的退出字符
eat ...
#------------------------------------------------
如果没有候选堆栈,则本自动机将执行选择一个候选堆栈
如果有候选堆栈,那么它的状态应该为 :
[]
[] ...
[+]...
']'...
[?] # 子机设置
[?] # 子机设置
[@] # 某个子机
']' # 自己的退出字符
每次 eat 如果某个候选堆栈 DROP , 就移除掉它
保证每次都给所有的候选堆栈消费字符,如果某个堆栈 DONE 了,
则将这个堆栈关闭后得到对象组合到母堆栈中。
done ...
#------------------------------------------------
如果没有候选堆栈,那么就什么也不做
如果有多个候选堆栈,并联自动机会首先调用候选A的栈顶自动机的 done
{候选堆栈A}.close() => T
{self}.mergeHead(T)
{self}.pushQc({候选堆栈A}.popQc())
并将其压入自己所在堆栈,否则,就会调用自己堆栈栈顶自动机的 done,
让自己的的堆栈状态为:
[] # 字符缓冲
[] ... # 这个是自己的对象
[+] ... # 头部就只有自己
']' ... # 自己的退出字符在顶部
执行堆栈的真正弹出
[]
[] ... # 将 T 组合到之前的对象中
[] ... # 清除了自动机
... # 清除了退出字符