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

自动机堆栈

  1. 头 .................... 尾
  2. [C][C][C]      # 字符缓冲栈
  3. [T][T][T]      # 数据栈
  4. [@][@]         # 操作栈
  5.  1 ']'         # 指示堆栈，并联自动机当做退出字符，串联当做子机下标
  7. 四个堆栈的操作原则是：“谁压入谁弹出”
  9. 堆栈通过 {..} 来表示，可以构成级联
  11. {..}
  12.     {..}
  13.         {..}
  14.         {..}
  15.     {..}
  17. 每个自动机都有方法
  18. enter(AmStack, char):AmStatus  # 试图进入这个自动机，如果成功将设置堆栈
  19. eat(AmStack, char):AmStatus    # 消费字符
  20. done(AmStack):void             # 将字符缓冲的内容填充到数据栈
  22. 任何一个自动机每次被执行都会返回如下四个行为之一
  23. DROP       # 丢弃当前堆栈
  24. CONTINUE   # 继续，读取下一个字符，执行栈顶自动机的 run 方法
  25. DONE       # 将弹出操作栈顶自动机，并执行它的 done 方法
  26. DONE_BACK  # 执行 DONE 操作，并重新进入下一个可能的自动机

一个堆栈的数据结构

  1. buffer  # 字符缓冲
  2. objs    # 数据栈
  3. ams     # 操作栈
  4. qcs     # 退出字符 
  5. sis     # 指示堆栈
  7. i_obj
  8. i_am
  9. i_qc
  10. i_si
  12. candidates  # 候选堆栈
  13.  

它应该支持的操作

  1. enter(Am, char): bool       # 是否可以让这个自动机进入堆栈
  2. eat(char)      : AmStatus   # 消费字符，返回 false 表示不能消费了
  3. done           : void       # 调用栈顶自动机的 done
  4. close          : T          # 将对象堆栈清空
  6. pushAm(Am)
  7. popAm   : Am
  8. peekAm  : Am
  9. pushObj(T)
  10. popObj  : T
  11. peekObj : T
  12. pushQc(char)
  13. popQc   : char
  14. qc      : char
  15. pushSi(int)
  16. popSi   : int
  17. si      : int
  19.  

串联自动机

串联自动机有一个固定的进入字符

  1. 假设一个堆栈状态为:
  2. []       # 字符缓冲是干净的
  3. [] ...   # 数据栈
  4. [] ...   # 操作栈
  5.    ...   # 指示堆栈
  7. enter ...
  8. #------------------------------------------------
  9. 如果符合进入字符
  11.     []          # 字符缓冲内容由第一个子机决定
  12.     [T] ...     # 准备一个对象
  13.     [&] ...     # 压入自己
  14.     -1  ...     # 指示字符为自己第一个子机
  16. eat ...
  17. #------------------------------------------------
  18. 如果发现当前子机下标小于 0，则表示子机未被执行 enter ，那么就
  19. 将下标变成正数，并调用对应子机的 enter 
  20. （注意，这里的下标是 1 base，需要转换成 0 base 使用）
  22.     []          #
  23.     [T] ...     # 还是那个对象
  24.     [&] ...     # 串联自动机
  25.      1  ...     # 下标变成正数，并调用子机的 enter
  27. 如果当前子机 enter 未遂，或者 eat 返回 DROP 了，那么自己也返回 DROP
  28. 如果返回的状态是 DONE 或者 DONE_BACK, 
  29. 会调用当前子机的 done，并试图切换到下一个子机
  31.     []          #
  32.     [T] ...     # 还是那个对象
  33.     [&] ...     # 串联自动机
  34.     -2  ...     # 下标指向下一个子机，并调用子机的 enter
  36. 如果没有下一个子机了，则返回 DONE | DONE_BACK
  39. done ...
  40. #------------------------------------------------
  41. 如果为 done 时，堆栈应该为     
  43.     [C][C]...   # 缓冲可能为空也可能有字符
  44.     [T] ...     # 还是那个对象
  45.     [&] ...     # 操作栈顶应该是最后一个子
  46.      2  ...     # 下标指向最后一个子机
  48. 如果没有达到最后一个子机，那么调用当前子机的 done
  49. 然后将将自己退栈
  51.     []
  52.     [] ...   # 将 T 组合到之前的对象中
  53.     [] ...   # 清除自己
  54.        ...   # 清除了指示下标
  56.  

并联自动机

如果发现有超过一个自动机都进入了堆栈，并联自动机会依次为其构建堆栈

  1. 假设一个堆栈状态为:
  2. []       # 字符缓冲是干净的
  3. [] ...   # 数据栈
  4. [] ...   # 操作栈
  5.    ...   # 指示堆栈
  1. enter ...
  2. #------------------------------------------------
  3. 构建新堆栈:
  4. []
  5. []       # 不要准备对象
  6. [@]      # 表示有子自动机进入了
  7. ']'      # 自己的退出字符
  9. 如果超过一个自动机进入了，那么将堆栈变成
  11.     {候选堆栈A}         {候选堆栈B} -?- {母堆栈}
  12.     {候选堆栈C} /
  13.     ... 
  1. 那么就会将自身压入母堆栈，同时也要在母堆栈标识退出字符
  2. []
  3. [] ...
  4. [+]...  # 仅仅在当前堆栈压入自身
  5. ']'...  # 压入自己的退出字符
  1. eat ...
  2. #------------------------------------------------
  3. 如果没有候选堆栈，则本自动机将执行选择一个候选堆栈
  4. 如果有候选堆栈，那么它的状态应该为 :
  5. []
  6. [] ...
  7. [+]...
  8. ']'...
  9.     [?]      # 子机设置
  10.     [?]      # 子机设置
  11.     [@]      # 某个子机
  12.     ']'      # 自己的退出字符
  13. 每次 eat 如果某个候选堆栈 DROP , 就移除掉它
  14. 保证每次都给所有的候选堆栈消费字符，如果某个堆栈 DONE 了，
  15. 则将这个堆栈关闭后得到对象组合到母堆栈中。
  18. done ...
  19. #------------------------------------------------
  20. 如果没有候选堆栈，那么就什么也不做
  21. 如果有多个候选堆栈，并联自动机会首先调用候选A的栈顶自动机的 done
  23.     {候选堆栈A}.close() => T
  24.     {self}.mergeHead(T)
  25.     {self}.pushQc({候选堆栈A}.popQc())
  27. 并将其压入自己所在堆栈，否则，就会调用自己堆栈栈顶自动机的 done，
  28. 让自己的的堆栈状态为:
  29. []          # 字符缓冲
  30. [] ...      # 这个是自己的对象
  31. [+] ...     # 头部就只有自己
  32. ']' ...     # 自己的退出字符在顶部
  34. 执行堆栈的真正弹出
  35. []
  36. [] ...   # 将 T 组合到之前的对象中
  37. [] ...   # 清除了自动机
  38.    ...   # 清除了退出字符

原文:

http://nutzam.com/zdoc/parsing_am.html