BSU Bulletin. Mathematics, Informatics
Bibliographic description:
HOMOMORPHISM OF EQUIVALENT TRANSFORMATIONS OF GRAMMARS IN PARSER GENERATION // BSU Bulletin. Mathematics, Informatics. - 2019. №2. . - С. 44-60.
Title:
HOMOMORPHISM OF EQUIVALENT TRANSFORMATIONS OF GRAMMARS IN PARSER GENERATION
Financing:
Codes:
Annotation:
When constructing a translator, as a rule, it is necessary to apply the equivalent transformations of grammar of the implemented language, which convert the syn- tactic specification of the language into a form that allows for automatic or manual implementation of the source language, and solves the problem of constraint satis- faction of the chosen parsing technique. These problems arise both because of the variety of ways of defining the implemented languages, and because of the lan- guage ambiguity or nondeterminism of the recognizing automaton. Each transfor- mation performed on translational CF-grammars can be defined as a likelihood ratio (homomorphism), determined on classes of grammars. Such relations preserve the semantic meaning of grammatical structures in equivalent syntax transformations, since the ultimate purpose of translation is to obtain a sequence of actions pre- scribed by the computing environment.
The article presents a brief overview of various types of likelihood ratio over grammars used in constructing translators since the 1970s.
A flow chart for LL parsing with use of syntactic graph scheme (SGS) is presented. We have given a formal notion of a route (path) in the SGS and an example of the automatic CFR-grammar transformation of CIAO formal language in SynGT (Syntax Graph Transformations) system of equivalent transformations.
The article presents a brief overview of various types of likelihood ratio over grammars used in constructing translators since the 1970s.
A flow chart for LL parsing with use of syntactic graph scheme (SGS) is presented. We have given a formal notion of a route (path) in the SGS and an example of the automatic CFR-grammar transformation of CIAO formal language in SynGT (Syntax Graph Transformations) system of equivalent transformations.
Keywords:
equivalent transformations of grammars; likelihood ratio; cover homo- morphism; CF-grammar in a regular form (CFR-grammar); syntactic graph scheme (flow-chart); grammar regularization.
List of references:
Fedorchenko L. Regularization of Context-Free Grammars. Saarbrucken: LAP LAMBERT Academic Publishing, 2011.
Fedorchenko L., Baranov S. Equivalent Transformations and Regularization in Context–Free Grammars. Cybernetics and Information Technologies (CIT). V. 14. No. 4. Pp.11–28.
Aho A. V., Sethi R., Ullman J. D. Compilers, Principles, Techniques, and Tools.
Addison-Wesley, 1986.
Fedorchenko L. N. Regulyarizatsiya kontekstno-svobodnykh grammatik na os- nove ekvivalentnykh preobrazovanii sintaksicheskikh graf-skhem [Regularization of Context-Free Grammars Based on Equivalent Transformations of Syntactic Graph- Schemes]. Trudy SPIIRAN. 2010. V. 4 (15). Pp. 213–230. ISSN 2078-9181.
Early J. Ambiguity and Precedence in Syntax Description. Acta Informatica.
1975. No. 4. Iss. 2. Pp. 183–192.
Fedorchenko L. N. Ekvivalentnost kak otnoshenie podobiya v translyacii yazykov [Equivalence as a Likelihood Ratio in Language Translation]. Vestnik Buryat- skogo gosudarstvennogo universiteta. 2014. No. 9–3. Pp. 49–53.
Mc Naughton R. The Development of Formal Language Theory Since 1956.
Int. J. Found. Comput. Sci. 1990. V. 1. No. 4. Pp. 355–368.
Paull M., Unger S. Structural Equivalence of Context-Free Grammars. Journal of Computer and System Sciences. 1968. Vol. 2. Pp. 427–463.
Paull M. C., Unger S. H. Structural Equivalence of LL-k Grammars. IEEE Con- ference Record of Ninth Annual Symposium on Switching and Automata Theory. 1968. Pp. 160–175.
Prather R. E. Regular Expressions for Program Computations. American Math- ematical Monthly. 1997. V. 104. No. 2.
Fedorchenko L., Baranov S. Equivalent Transformations and Regularization in Context–Free Grammars. Cybernetics and Information Technologies (CIT). V. 14. No. 4. Pp.11–28.
Aho A. V., Sethi R., Ullman J. D. Compilers, Principles, Techniques, and Tools.
Addison-Wesley, 1986.
Fedorchenko L. N. Regulyarizatsiya kontekstno-svobodnykh grammatik na os- nove ekvivalentnykh preobrazovanii sintaksicheskikh graf-skhem [Regularization of Context-Free Grammars Based on Equivalent Transformations of Syntactic Graph- Schemes]. Trudy SPIIRAN. 2010. V. 4 (15). Pp. 213–230. ISSN 2078-9181.
Early J. Ambiguity and Precedence in Syntax Description. Acta Informatica.
1975. No. 4. Iss. 2. Pp. 183–192.
Fedorchenko L. N. Ekvivalentnost kak otnoshenie podobiya v translyacii yazykov [Equivalence as a Likelihood Ratio in Language Translation]. Vestnik Buryat- skogo gosudarstvennogo universiteta. 2014. No. 9–3. Pp. 49–53.
Mc Naughton R. The Development of Formal Language Theory Since 1956.
Int. J. Found. Comput. Sci. 1990. V. 1. No. 4. Pp. 355–368.
Paull M., Unger S. Structural Equivalence of Context-Free Grammars. Journal of Computer and System Sciences. 1968. Vol. 2. Pp. 427–463.
Paull M. C., Unger S. H. Structural Equivalence of LL-k Grammars. IEEE Con- ference Record of Ninth Annual Symposium on Switching and Automata Theory. 1968. Pp. 160–175.
Prather R. E. Regular Expressions for Program Computations. American Math- ematical Monthly. 1997. V. 104. No. 2.
Article.pdf