高效扩增式LL语法分析并行化扩充

摘要

随着并行技术和并行语言的发展，处理并行语言的并行编译技术，将串行程序转换成并行程序的自动并行编译技术正在深入研究之中。语法分析是编译系统设计最重要的内容之一，而扩增式语法分析广泛的用于基于语言编辑器，扩增式编辑和译码环境中。在这些环境中，最经常执行的操作是对改进输入串的重新语法分析，它的效率能极大的影响这些环境的成功。 本文描述了对应用于支持最小化LL(1)重新语法分析的语法分析树中线性链接和LL预测分析表中附加距离入口的简介。随后，线索化语法分析树和扩增式LL预测分析表被用于生成一个高效的扩增式LL语法分析。然后又具体讨论了在并行化环境下对这个高效的扩增式语法分析的分析和改进，给出一个改进的并行化扩增式LL语法分析算法，并用一个实例进行详细分析。文章的最后还针对该并行算法在数学表达式分析过程中局部树的相同变换重复替换问题进行了探讨，并给出了该并行算法在数学表达式语法分析过程的特殊作用的相关结论。 本文通过在并行环境下对构建高效扩增式LL语法分析的详细分析和讨论，对提高扩增式LL语法分析效能有其实践意义，从而也为进一步讨论在并行环境下的数学表达式分析打下了良好的理论基础。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景与发展现状

1.1.1编译技术的发展

1.1.2编译的概念

1.1.3编译的阶段

1.1.4文法和语言

1.2论文研究内容

1.2.1本课题研究的目的与意义

1.2.2本文的主要工作

1.3论文的组织结构

第二章扩增式LL预测分析表和线索化分析树

2.1语法分析

2.2语法分析树

2.3自顶向下分析法构造FIRST、FOLLOW及SELECT集合

2.3.1基本概念

2.3.2算法设计

2.4 LL(1)文法

2.4.1基本概念

2.4.2非LL(1)文法的等价变换

2.4.3 LL(1)文法分析方法

2.5 LL预测分析表和语法分析树

2.6扩增式LL预测分析表的构造算法

2.7本章小结

第三章扩增式LL语法分析

3.1语法分析树的重用

3.2扩增式语法分析算法

3.3一个实例

3.4实例分析过程中引出的思考

3.5在并行环境下的推广

3.5.1在并行环境下改进的算法

3.5.2算法的正确性和有效性

3.6本章小结

第四章数学表达式问题

4.1传统数学表达式处理算法简介

4.2数学表达式在并行环境下的扩增式语法分析

4.3数学表达式中局部树相同变换的重复替换问题

4.4本章小结

第五章总结和展望

5.1总结

5.2展望

参考文献

附录

致谢

攻读学位期间的科研成果