<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Regularization of translational context-free grammar via equivalent transformations is a mandatory step in developing a reliable processor of a formal language defined by this grammar. In the 1970-ies, the multi-component oriented graphs with basic equivalent transformations were proposed to represent a formal grammar of ALGOL-68 in a compiler for IBM/360 compatibles. This paper describes a method of grammar regularization with the help of an algorithm of eliminating the left/right-hand side recursion of nonterminals which ultimately converts a context-free grammar into a regular one. The algorithm is based on special equivalent transformations of the grammar syntactic graph: elimination of recursions and insertion of iterations. When implemented in the system SynGT, it has demonstrated over 25% reduction of the memory size required to store the respective intermediate control tables, compared to the algorithm used in Flex/Bison parsers.</p></abstract>

Regularization of translational context-free grammar via equivalent transformations is a mandatory step in developing a reliable processor of a formal language defined by this grammar. In the 1970-ies, the multi-component oriented graphs with basic equivalent transformations were proposed to represent a formal grammar of ALGOL-68 in a compiler for IBM/360 compatibles. This paper describes a method of grammar regularization with the help of an algorithm of eliminating the left/right-hand side recursion of nonterminals which ultimately converts a context-free grammar into a regular one. The algorithm is based on special equivalent transformations of the grammar syntactic graph: elimination of recursions and insertion of iterations. When implemented in the system SynGT, it has demonstrated over 25% reduction of the memory size required to store the respective intermediate control tables, compared to the algorithm used in Flex/Bison parsers.

Equivalent Transformations and Regularization in Context-Free Grammars

St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, 14 liniya, 39, V.O. St. Petersburg, 199178, Russia

ITMO University, Av. Kronverkski, 49, St. Petersburg, Russia

Cybernetics and Information Technologies

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Equivalent Transformations and Regularization in Context-Free Grammars"}

Regularization of translational context-free grammar via equivalent transformations is a mandatory step in developing a reliable processor of a formal language...

Equivalent Transformations and Regularization in Context-Free Grammars

Publié en ligne: 31 janv. 2015

Pages: 29 - 44

DOI: https://doi.org/10.1515/cait-2014-0003

© 2015 Ludmila Fedorchenko and Sergey Baranov

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.