语法分析中基于集合冲突的ε-NFA的构造及其分析策略

构造识别句型的ε-NFA是自下而上语法分析的重要环节.传统的构造过程中要根据文法建立项目集,在项目集的基础上根据集合间的转换函数建立项目集之间的转移动作.然而这种传统的构造方法在分析过程中项目集中会出现集合中项目间的移进-归约冲突或者归约-归约冲突,因而识别活前缀的ε-NFA无法决定下一步的动作,导致分析失败.基于集合冲突的ε-NFA的构造及其分析策略能够对各类冲突进行分析与处理,可以解决分析冲突,使得语法分析方法适用于绝大多数文法的句型的分析.

形式语言与自动机中关于ε的一些问题

讨论了形式语言与自动机理论中关于空串ε的一些问题。分析了ε产生式对文法和语言分类的影响;从文法和有限状态自动机的角度讨论了开始符号S和开始状态q0的作用;提出了语言增加或减少ε句子的简单方法;研究了ε-NFA的ε状态转换函数的本质;提出了ε-NFA转换为NFA的新方法,即先将ε-NFA转换为文法形式,消除ε产生式和单产生式后得到正则文法,再将正则文法转换为NFA。并用实际例子进行了验证。