Geodesic
Minimization of syntax diagrams with multiport components
Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 85-97.

Voir la notice de l'article provenant de la source Math-Net.Ru

The minimization problem for syntax diagrams is considered. For this purpose, we transform the Wirth diagrams (WD) into syntax diagrams with multiport components (SD), which are similar to WD in their structure, but differ in the fact that the non-terminals in nonterminal nodes are replaced with the starting nodes of the corresponding components. On the set of SD nodes, we introduce a relation which possesses the equivalence property, dividing the set of nodes into equivalence classes. We prove that uniting an equivalence class into one node is an equivalence transformation. If an equivalence class includes the nodes of various components, then, as a result of uniting the class into one node, the components are united into one component, which has several inputs. The algorithms for dividing the set of nodes into equivalence classes and plotting a SD are suggested. The algorithm for dividing the set of nodes into equivalence classes is based on a serial partitioning of the set of nodes into subsets so that non-equivalent nodes fall into different subsets. After partitioning the set of nodes into equivalence classes, an SD is constructed. In the SD construction algorithm, for each equivalence class, the following actions are executed: only one node from the class is left in the SD, the remaining nodes of the class are deleted, and if some arc in the source diagram is going to the deleted node, then it is redirected to one of remaining nodes. We give an example which demonstrates that a SD plotted by the suggested algorithms is considerably smaller than the equivalent WD. The resulting SD, after minimization process, can be used to construct memory efficient programs for formal languages processing.
Keywords: formal language, syntax diagram, minimization.
Mots-clés : equivalence relation 
@article{PDM_2018_3_a8,
     author = {Yu. D. Ryazanov},
     title = {Minimization of syntax diagrams with multiport components},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {85--97},
     publisher = {mathdoc},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_3_a8/}
}
TY  - JOUR
AU  - Yu. D. Ryazanov
TI  - Minimization of syntax diagrams with multiport components
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 85
EP  - 97
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_3_a8/
LA  - ru
ID  - PDM_2018_3_a8
ER  - 
%0 Journal Article
%A Yu. D. Ryazanov
%T Minimization of syntax diagrams with multiport components
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 85-97
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_3_a8/
%G ru
%F PDM_2018_3_a8
Yu. D. Ryazanov. Minimization of syntax diagrams with multiport components. Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 85-97. http://geodesic.mathdoc.fr/item/PDM_2018_3_a8/

[1] Jensen K., Wirth N., Pascal User Manual and Report, Springer Verlag, N.Y., 1975, 167 pp. | Zbl

[2] Jensen K., Wirth N., Pascal User Manual and Report, Springer Verlag, Berlin–Heidelberg, 1974, 170 pp. | Zbl

[3] Legalov A. I., Shvets D. A., Legalov I. A., Formal Languages and Translators, Siberian Federal University, Krasnoyarsk, 2007, 213 pp. (in Russian)

[4] Karpov Yu. G., “The Theory and Technology of Programming. Fundamentals of Translators”, BHV-Petersburg Publ., Saint-Petersburg, 2005, 272 pp. (in Russian)

[5] Sverdlov S. Z., “Methods of Translation”, VSU Publ., Vologda, 2016, 235 pp. (in Russian)

[6] Sverdlov S. Z., Compiler Design, Lap Lambert, Saarbruken, 2015, 571 pp. (in Russian)

[7] Martynenko B. K., “Syntactic charts and graph-schemes in the SYNTAX-Technology”, Computer Tools in Education, 2014, no. 2, 3–19 (in Russian)

[8] Ryazanov Yu. D., Seval'neva M. N., “The analysis of syntax diagrams and automatic generation of linear-time programs recognizer”, Belgorod State University Scientific Bulletin. History. Political science. Economics. Information technologies, 2013, no. 8, 128–136 (in Russian)

[9] Polyakov V. M., Ryazanov Yu. D., “Algorithm for not recursive linear-time programs recognizer design from deterministic syntax diagrams”, Bulletin of BSTU named after V. G. Shukhov, 2013, no. 6, 194–199 (in Russian)