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

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