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

摘要

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