Top ↑
无匹配结果,请重新输入
zDoc的解析自动机
Jul 9, 2017 11:52:32 PM
作者: zozoh

对于每个段落的解析,依靠自动机。本文为自动机的实现者提供一些参考

自动机堆栈

头 .................... 尾
[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 组合到之前的对象中
[] ...   # 清除了自动机
   ...   # 清除了退出字符

本页面的文字允许在知识共享 署名-相同方式共享 3.0协议GNU自由文档许可证下修改和再使用。