Regularization of context free grammars on the base of equivalent transformations of syntax graph-schemes

L. N. Fedorchenko

St. Petersburg Institute for Informatics and Automation of RAS

Abstract: In the article we validate the urgency of the problem rapid tuning a syntactic definition of language that implemented by applying the method of regularization of a translational context-free grammar using the equivalent transformations of their syntactic graph-scheme to optimize the built parser. In the paper we handle the method of regularization of a translational context-free grammar using the equivalent transformations of their syntactic graph-scheme to optimize the built parser. The notion “regularization of a CF grammar” is introduced. We consider a CF grammar in a regular form (CFR-grammar) supplied with extended set of operations in regular expressions in the right hand side of rules. The algorithm of extracting left (right) recursion nonterminals has been shown for CFR-grammar case. It is implemented in the system SynGT (Syntax Graph Transformations).

Keywords: CFR-grammar, syntax graph-scheme, grammars equivalent transformations.

UDC: 519.766.23

Received: 27.12.2010