基于内存自动机与模式的动态引擎构造技术研究

论文摘要

解释是软件系统开发与构造过程中反复出现的一个主题。一个应用系统自身可被理解为针对数据的变换和解释。系统开发者为实现软件系统的适应性与扩展性,利用解释系统将开发时尚不能确定的状态留待运行时解释并执行特定动作。语言的翻译或解释引擎是各种引擎中最为复杂的一种,本文以脚本语言的定义和引擎构造为核心,总结语言中各种语法和语义现象,重点研究在内存自动机基础上的SLL(*)计算、回溯计算、LookAhead DFA构造以及文法与语义模式。论文在构造内存自动机的基础上,将SLL(*)计算、回溯计算、以及动态引擎的结构分析统一为自动机上的状态迁移操作。这些算法都已在动态解析引擎XD SLL(*) Parser中实现。为了验证算法的正确性、有效性以及相关综合性能,本文还对其进行了系统的实验研究。作者研究工作的具体内容包括:〔1〕定义基本正则表达式的元语言并构造正则元语言识别引擎正则元语言用于描述待解析目标的词法结构,而正则元语言识别引擎将元语言描述的正则表达式转化为等价语法树,在语法树基础之上构造相应的内存有限状态自动机,并在构造过程中进行冲突检测以及冲突消解,最终实现在内存有限状态自动机上的输入流匹配,为后续的文法结构分析提供输入。〔2〕提出了一种增强的SLL(*)分析计算方法动态分析引擎自身是基于下推自动机PDA进行状态迁移的,可以为结构分析提供运行时的栈信息。增强的SLL(*)分析算法以终结符号和运行时栈信息为计算依据,减少了仅采用终结符号进行预测分析时所产生的状态爆炸问题,从而加快了在内存自动机上选择下一迁移状态时的速度。〔3〕提出了一种SLL(*)分析与回溯分析相结合的分析方法SLL(*)分析不保证对所有LL文法都能够进行结构分析,回溯分析可保证对所有LL文法甚至二义文法进行分析,但其单次分析不具有完备性。当SLL(*)分析失效时,启用回溯分析以保证动态解析引擎对语法分析的完备性,同时将SLL(*)计算结果与回溯分析结果进行融合并构造LookAhead DFA以加快引擎分析速度。〔4〕实现了基于PDA的结构分析引擎与语义动作挂接机制结构分析等价于PDA中的状态迁移,直接在PDA上进行状态迁移即可完成结构分析;在进行状态迁移的同时,执行特定结构所附加的语义动作,可完成相应语义计算,同时提供基于语法树上语义动作的前置计算与后置计算,便于开发者改变语法树上的缺省计算顺序。〔5〕实现了常用的文法模式与相应的语义动作作者对语言中频繁出现的部分文法模式进行了分析,并将相应的语义动作以类库形式进行封装,既有效降低结构分析与语义动作间的耦合性,也解决了引擎构造过程中的代码冗余问题,最大限度地提高语义模块的复用程度。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究意义
• 1.1.1 语言正向构造
• 1.1.2 语言逆向分析
• 1.1.3 数据、协议的解析与分析
• 1.2 研究思路
• 1.3 项目背景与XD SLL（*） PARSER 结构
• 1.4 论文的主要工作与组织结构
• 第二章 基本概念与相关研究工作
• 2.1 形式语言与自动机
• 2.2 编译器生成工具与脚本语言
• 2.3 扩展编译技术
• 2.4 相关工作比较
• 2.5 本章小结
• 第三章 正则引擎
• 3.1 正则引擎分类与设计
• 3.2 正则元语言
• 3.3 DFA 构造引擎
• 3.4 DFA 引擎
• 3.5 本章小结
• 第四章 动态分析引擎
• 4.1 文法描述与识别
• 4.2 LL（K）分析
• 4.3 动态分析引擎
• 4.3.1 内存自动机的构造
• 4.3.2 SLL（*）计算
• 4.3.3 基于文法状态转换图的分析引擎
• 4.3.4 增强SLL（*）计算
• 4.3.5 回溯计算与LookAheadDFA
• 4.4 本章小结
• 第五章 文法模式与动作
• 5.1 基于自动机的语义动作
• 5.2 基于语法树的语义动作
• 5.3 文法模式及语法树动作
• 5.3.1 类型与变量定义模式
• 5.3.2 函数模式
• 5.3.3 表达式模式
• 5.3.4 循环、条件选择与跳转模式
• 5.3.5 命令模式与对象模式
• 5.4 本章小结
• 第六章 实验研究
• 6.1 引言
• 6.2 ICSL 脚本解释引擎
• 6.2.1 ICSL 文法分析
• 6.2.2 实例运行结果
• 6.2.3 效率与有效性分析
• 6.3 MDL 与SQL 数据抽取引擎
• 6.3.1 MDL 分析
• 6.3.2 SQL 分析
• 6.4 Lua 与 Java 分析引擎
• 6.5 本章小结
• 第七章 工作总结与进一步的研究
• 7.1 工作总结
• 7.2 进一步的研究
• 致谢
• 参考文献
• 攻读博士学位期间完成的论文
• 攻读博士学位期间参加的科研
• 附录A
• ICSL 脚本样例
• 附录B
• 增强ICSL 文法结构
• 增强ICSL 脚本样例
• 附录C
• 测试MDL 文本样例
• 附录D
• 测试SQL 文本样例