题目：GLR分析器自动生成及相关问题研究

软件自动生成是计算机科学家始终追求的目标。语法分析器的自动生成是软件自动生成最经典的应用领域之一。自语法分析理论建立之后，许多研究工作致力于如何自动产生分析速度快、处理能力强的语法分析程序。事实上，形式文法的开发和语法分析器的自动构造问题可以追溯到软件工程成为计算机科学中的一门独立学科之前。尽管拥有如此悠久的历史，然而在过去的二十多年里，适用于计算机语言处理的自底向上语法分析器的自动构造技术却始终没有得到明显改观。为了满足软件再(逆向)工程和实现领域专用语言对语法分析技术的需求，论文提出和实现了一个自底向上语法分析器生成系统的技术框架。论文的技术框架以Tomita的GLR分析算法为基础，这使得它有别于传统的LALR(1)或LL(1)分析器生成系统。GLR算法是通用的语法分析算法，它能够识别任意上下文无关文法，然而将其用作自动生成的语法分析器的分析算法，需要解决分析器的性能问题和运行时的用户控制问题。论文阐述了在计算机语言的语法分析中采用GLR算法的动机，提出一个多层次的优化策略，加快了GLR分析器的分析速度，并为基本的GLR算法增加了必要的运行时控制机制，使其在语法分析时调用文法规则附带的语义动作，化解输入串的二义性。实验结果表明，在分析计算机语言时，自动生成的GLR分析器的分析速度与自由软件基金会的Bison生成的LALR(1)分析器的分析速度有可比性。根据DeRemer和Pennello的LALR(1)向前看符号集计算公式，论文设计了高效的算法，实现了LALR(1)自动机和分析表的快速生成，实验结果显示，其生成速度超过了自由软件基金会的LALR(1)分析器生成器Bison。论文分析了语法分析冲突的起因和解决冲突的时机及策略，提出改写文法应遵循的3条规则，将常用的文法改写技巧总结为6个基本的文法改写模式。应用案例表明，论文描述的文法改写规则和基本文法改写模式可有效解决语法分析冲突。论文提出一种灵活、简单、有效的基于动态优先级的语法分析时消歧技术，以解决上下文相关的文法符号的语法分析问题。论文研究了文法的测试和充分性准则，定义了比已知的规则覆盖更严格的文法测试充分性准则，提出一个文法测试的充分性准则族，定义了测试充分性准则期望具有的若干正面的、直觉的性质，并利用这些性质对各条准则进行了比较和评判。论文提出的形式定义和概念，不仅是对传统软件测试充分性理论必要的、有益的补充，也为测试人员选择使用测试充分性准则提供了参考依据。论文提出的技术框架、算法已在一个原型系统VPGE中实现。该系统是一个可视化的文法开发、调试和分析器生成环境，支持断点调试，实现了灵活、有效的消歧机制。关键词：语法分析器生成，GLR算法，消歧，语法分析冲突，文法调试，文法测试，测试充分性准则，LALR(1)，YACC，Bison