Syntactic Analysis And Syntax-directed Translation Based On Extended Relational Model

Syntactic analysis is an essential ingredient for for syntactic pattern recognition and algebraic dynamic programming. Currently, these applications arc typically supported by application-level code that uses the underlying database as a dumb data store.In this paper, we discuss a method for implementing parsing algorithm as standard relational queries on an relational database management system. In this framework, each set of partial derivation trees is represented as a relation in the relational database. Partial derivation tree operations are represented as extended relational operators. An parsing algorithm can be expressed as a recursive query. We construct a new Earley parsing system based on the extended relational data model. Finally, we present our prototype implementation that demonstrates the feasibility of parsing using our system.Naturally, all query optimization techniques can be directly applied to processing this query. Thus, these transformations allow us to take full advantage of the query optimizer and other performance enhancement capabilities available in traditional relational databases.Syntactic analysis algorithms can be natively supported by a database system. Thus, we are spared the arduous task of designing and implementing our own syntactic analysis system and the associated costs. The framework provides a unified approach for other related chart parsing algorithms.This method is extended to syntax-directed translation of synthesized attributes.And we have evaluated our algorithm on an expression evaluation calculator problem, a simple semantic analysis problem, to demonstrates the feasibility of our system.