基于关系代数的语法—语义分析单元设计

发布时间：2018-09-13 16:59

【摘要】：句法分析是结构模式识别系统的重要组成部分之一。然而,传统上句法分析单元的实现方式是通过编写专门的过程语言的代码。当应用领域需要识别的文法规模十分庞大时,编写出能够快速对样本进行识别的程序,并不容易。本文尝试通过将句法分析算法与关系代数模型紧密集成,利用关系数据库系统能够组织和快速检索海量数据的特点,增强句法分析单元处理复杂文法样本的能力,同时减轻用户的编码负担。我们给出了Earley (?)(?)法分析算法的扩展关系模型。在此框架中,任意部分推导树集合可对应表示为关系代数中一个关系；部分推导树之间的运算被表示为关系代数运算；语法分析算法被对应表示为一条递归查询语句；过程语言描述的运算过程与递归查询的查询执行在单个运算、控制结构、数据结构三个方面存在对应关系。依据此框架,我们给出一种新的Earley语法分析关系代数算法,及其公用表表达式(CTE)实现和存储过程的实现。并通过原型系统验证了该方法的可行性。属性文法兼有决策理论方法和结构方法两者的特点,所以在模式识别领域中受到广泛的注意。因此进一步本文尝试将基于关系代数的方法推广应用于属性文法的语义分析问题,给出一种基于关系代数的Earley综合属性语法制导翻译算法。将其应用于一个基本的综合属性计算问题——算术表达式求值问题,算法可在读入表达式词法分析结果的同时,计算出表达式的值。从而验证了该方法的可行性。已知了Earley语法分析算法与关系数据库间存在的这些对应关系,在今后的算法设计中就可以全部或部分地利用这些关系,有选择地将句法分析问题全部或部分转化为数据库查询问题,借助关系数据库系统处理海量数据的优势,增强句法分析单元处理复杂文法样本的能力。此外,借助本文给出的扩展关系代数运算,可以方便地表达Earley语法分析算法运算过程中产生的语法分析项目或部分推导树之间的关系。理论方面,由于已知这些对应关系,对于一个领域的某些问题,通过类比,有可能从另一个领域获得启发。例如,我们可以通过比较二者,发现相对查询执行而言,过程语言所描述的算法在某些方面具有更高执行效率的原因。这些无疑是数据库查询处理可以借鉴的。
[Abstract]:Syntactic analysis is one of the important components of structural pattern recognition system. Traditionally, however, syntactic parsing units are implemented by writing specific procedural language codes. When the scale of grammar recognition in application field is very large, it is not easy to write a program that can recognize samples quickly. This paper attempts to integrate the syntactic parsing algorithm with the relational algebra model, and make use of the characteristics of the relational database system to organize and quickly retrieve the massive data, so as to enhance the ability of the syntactic analysis unit to deal with complex grammar samples. At the same time reduce the user's coding burden. We gave Earley (?) The extended relational model of the algorithm is analyzed by the method. In this framework, any set of partial derivation trees can be represented as a relation in relational algebra, the operations between partial derivation trees can be represented as relational algebraic operations, and the syntax analysis algorithm can be represented as a recursive query statement. The operation process described by the procedure language has corresponding relations with the query of recursive query in three aspects: single operation, control structure and data structure. According to this framework, we present a new Earley syntax parsing relational algebra algorithm, and the realization of common table expression (CTE) and stored procedure. The feasibility of the method is verified by the prototype system. Attribute grammar has both the characteristics of decision theory and structural method, so it has been paid more and more attention in the field of pattern recognition. Therefore, this paper attempts to extend the relational algebraic approach to the semantic analysis of attribute grammars, and presents a Earley Synthetical attribute Grammar guidance Translation algorithm based on relational algebra. It is applied to a basic comprehensive attribute evaluation problem, the arithmetic expression evaluation problem. The algorithm can calculate the expression value while reading the result of the expression lexical analysis. The feasibility of the method is verified. These corresponding relations between Earley parsing algorithm and relational database are known, which can be fully or partially utilized in future algorithm design. The syntactic parsing problem is transformed into database query problem in whole or in part selectively, and the ability of syntactic analysis unit to deal with complex grammar samples is enhanced by using the advantage of relational database system to deal with massive data. In addition, with the help of the extended relational algebraic operation presented in this paper, it is easy to express the relationship between the parse items or partial derivation trees produced in the operation of the Earley parsing algorithm. Theoretically, because these corresponding relations are known, it is possible to draw inspiration from another domain for some problems in one domain by analogy. For example, by comparing the two, we can find the reason why the algorithms described in the procedure language are more efficient in some aspects than query execution. These are undoubtedly database query processing can be used for reference.
【学位授予单位】：大连交通大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：H043

【共引文献】