EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 3.0

Equivalent Transformations and Regularization in Context-Free Grammars

Ludmila Fedorchenko, Sergey Baranov

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →