采用预测策略的Earley算法

在自然语言处理中,句法分析主要有基于统计的方法和基于规则的方法。Earley算法是一种基于规则的方法,可以分析任意上下文无关文法(CFG),而不需要对文法进行修改。详细分析了Earley算法的特点。在通常的Earley算法中增加了多种预测机制,这些预测机制借鉴了LL,LR以及SLR等确定性分析算法的一些思想,并对这几种不同的预测机制及其组合在相同条件下进行了中文句法分析实验。结果显示,引入这些预测机制通常可以减少产生项目的数量,从而节省存储空间,减少运行时间。

基于扩展Viterbi路径的概率Earley算法

概率Earley句法分析算法采用Viterbi路径构造输入序列的句法树,由于文法限制,存在空树问题。提出了扩展启始状态、省略未覆盖句首和补充未覆盖子树等方法来对Viterbi路径进行扩展,解决了绝大多数空树问题,并有效提高了Earley算法的整体性能。

基于Earley算法的多功能雷达文法概率快速学习算法

针对基于随机上下文无关文法(SCFG)建模的多功能雷达(MFR)概率学习问题,在传统Inside-Outside(IO)算法和Viterbi-Score(VS)算法的基础上,提出一种基于Earley算法的多功能雷达文法概率快速学习算法。该算法通过对截获的雷达数据进行预处理,构造可以反映派生过程的Earley剖析表,并且基于最大子树概率原则从剖析表中提取出最优剖析树,利用改进的IO算法和改进的VS算法对文法概率进行学习,实现MFR参数估计,得到文法参数后,再利用Viterbi算法对MFR状态进行估计。理论分析和实验仿真表明,与IO算法和VS算法相比,改进算法在保持估计精度的同时,可以有效降低计算复杂度和减少运行时间,验证了Earley算法能够提高文法概率的学习速度。

两个真歧义句的Earley算法演示

从两个真歧义句的组合谈起,借以抽象出"vp ap的np"格式,该格式可以有若干种定界模式,可以举出包括以上两个真歧义句的许多实例;同时介绍了Earley算法的基本操作,构造了一个初步的CFG文法,尝试讨论了歧义的消解策略,并试图通过对以上两个真歧义句的Earley算法的演示表明该算法也可以推广到其他实例的分析中去。

基于Earley算法的英语句法剖析系统

首先,介绍上下文无关语法系统,指出基于上下文无关语法的各种算法,具体分析Earley算法的实现过程。然后,建立词库和产生式规则库,结合实际例句,运用Earley算法完成一个英语句法剖析系统的全过程。利用该句法剖析系统,能对结构比较常用的英语句子进行剖析,并得到句子可能的句法结构。当然,本系统还存在规模不大和消歧等问题,有待进一步深入研究。

Earley算法的改进策略

在自然语言的处理中,主要通过基于统计的方法和基于规则的方法来进行句法分析。Earley算法可以不需要对文法进行修改的基础上分析任意上下文无关文法,是一种基于规则的方法。通过几种预测机制来改进Earley算法,从而减少无用项目的产生。在通常的Farley算法中增加了多种预测规则,并对这几种不同的预测机制及其组合在相同条件下进行了中文句法分析实验。结果显示,引入这些预测机制通常可以减少产生项目的数量,从而节省存储空间,减少运行时间。

编译器前端构造工具及JLUCC的实现

针对多种典型的编译器构造工具存在对文法有限制、嵌入式语义动作有负面影响,目标语言单一和调试维护困难等一些问题,设计并实现了一种新的编译器构造工具———JLUCC(JilinUniversityCompilerCompil-er)。JLUCC使用Earley分析方法,结合反射、面向对象和设计模式等技术,具有词法分析器、语法分析器、抽象语法树和遍历工具等编译器模块的自动生成功能,可以支持任意上下文无关文法、多遍处理和对目标语言的扩展。其功能强大、使用方便、便于维护和扩展,具有广阔的应用前景。展望了未来编译器构造工具的发展趋势。

基于关系代数的结构模式识别系统句法分析单元设计

介绍了一种基于关系代数的句法分析单元设计.尝试通过与关系代数模型紧密集成,利用关系数据库系统能够组织和快速检索海量数据的特点,提高句法分析单元的处理复杂文法样本的能力,同时减轻用户的编码负担.在此框架中,部分推导树集合被表示为关系;推理规则集被表示为扩展的关系代数运算.给出了算法实现所需的数据结构和控制结构.从而将句法分析算法完全表示为数据库系统中的一个关系运算过程.最后通过原型系统验证了该方法的可行性.