Equivalent Transformations and Regularization in Context-Free Grammars
Cybernetics and Information Technologies · 2015
DOI: 10.1515/cait-2014-0003 ↗Kurz gefasst
Fachartikel in der Zeitschrift Cybernetics and Information Technologies, 2015. Verfasst von Ludmila Fedorchenko und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 3.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Fedorchenko, L., & Baranov, S. (2015). Equivalent Transformations and Regularization in Context-Free Grammars. Cybernetics and Information Technologies. https://doi.org/10.1515/cait-2014-0003
Vancouver
Fedorchenko L, Baranov S. Equivalent Transformations and Regularization in Context-Free Grammars. Cybernetics and Information Technologies. 2015. doi:10.1515/cait-2014-0003
BibTeX
@article{Fedorchenko2015,
author = {Fedorchenko, Ludmila and Baranov, Sergey},
title = {Equivalent Transformations and Regularization in Context-Free Grammars},
journal = {Cybernetics and Information Technologies},
year = {2015},
doi = {10.1515/cait-2014-0003}
}
EUVIMED