About LL(1)-grammars, algorithms on them and methods of their analysis in programming

S.V. Kozlov, A. V. Svetlakov

Abstract


The article discusses the theoretical foundations of parsing, namely, the definition of LL(1)-grammars and proves the key positions associated with them for practice. The authors demonstrate the impracticality of the proof by definition that context-free grammar is an LL(1)-grammar. In view of this, a theorem is formulated and proved that sets the criterion of LL(1)-grammar. First and follow sets are constructed, which determine the necessary and sufficient conditions for the existence of LL(1)-grammar. Examples show the application of the formulated criterion. The central point of the article is the question of finding grammars equivalent to LL(1)-grammar. A number of statements are considered to reveal that the grammar being analyzed is not an LL(1)-grammar. In particular, two necessary conditions for the existence of LL(1)-grammar are analyzed. Namely, theorems that if a grammar contains a left recursion or a right branching, then it is not an LL(1)-grammar. The example shows that these conditions are not sufficient. Two methods for analyzing LL(1)-grammars used in practice are discussed and compared: the recursive descent method and the emission-transfer method. For each of the methods, its meaningful description and implementation in pseudocode is given. All the provisions of the article are accompanied by the necessary examples. The relevance of the article is associated with the search and study of parsing algorithms for grammars of natural and artificial languages, which are successfully used as tools for writing pattern recognition systems in the field of artificial intelligence.

Full Text:

PDF (Russian)

References


Bazhenov R. I., Lopatin D. K. O primenenii sovremennyh tehnologij v razrabotke intellektual'nyh sistem // Zhurnal nauchnyh publikacij aspirantov i doktorantov. – 2014. – # 3 (93). – S. 263-264.

Kozlov S. V. Konceptual'nye vozmozhnosti ispol'zovanija cifrovyh tehnologij v sfere obrazovanija // Cifrovoj region: opyt, kompetencii, proekty: sbornik statej III Mezhdunarodnoj nauchno-prakticheskoj konferencii, posvjashhennoj 90-letiju Brjanskogo gosudarstvennogo inzhenerno-tehnologicheskogo universiteta. – Brjansk, 2020. – S. 396-402.

Munerman V. I. Realizacija parallel'noj obrabotki dannyh v oblachnyh sistemah // Sovremennye informacionnye tehnologii i IT-obrazovanie. – 2017. T. 13. # 2. – S. 57-63.

Kozlov S. V., Svetlakov A.V. Teorija formal'nyh grammatik i ee primenenie // Sistemy komp'juternoj matematiki i ih prilozhenija. – 2021. # 22. – S. 358-364.

Muha V. S. Matematicheskie modeli mnogomernyh dannyh // Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radiojelektroniki. – 2014. – # 2 (80). – S. 143-158.

Kiseleva O.M., Timofeeva N.M. Postroenie konceptual'noj modeli uchebnyh slovarej po pedagogicheskim disciplinam // Nauchno-metodicheskij jelektronnyj zhurnal «Koncept». – 2013. – T. 3. – S. 3216-3220.

Vtjurin M. V. Primenenie formal'nyh grammatik dlja sokrashhenija ob"ema tekstovoj informacii // Innovacionnoe razvitie: tehnicheskij i tehnologicheskij aspekty. Sbornik statej mezhdunarodnoj nauchno-prakticheskoj konferencii. – 2019. – S. 22-25.

Kagirov I. A., Leont'eva A. B. Avtomaticheskij sintaksicheskij analiz russkih tekstov na osnove grammatiki sostavljajushhih // Izvestija vysshih uchebnyh zavedenij. Priborostroenie. – 2008. – T. 51. # 11. – S. 47-51.

Volkova I. A., Vylitok A. A., Rudenko T. V. Formal'nye grammatiki i jazyki. Jelementy teorii transljacii: uchebnoe posobie dlja studentov II kursa. – M., 2009 – 115 s.

Kompiljatory. Principy, tehnologii, instrumentarij / A. V. Aho, M. S. Lam, R. Seti, D. D. Ul'man. – M., 2008. – 1184 s.

Virt N. Postroenie kompiljatorov. – M., 2013. – 192 c.

Borisenkova A. V., Kozlov S. V. Ispol'zovanie metoda kaskadov Haara pri raspoznavanii obrazov na izobrazhenijah // Razvitie nauchno-tehnicheskogo tvorchestva detej i molodezhi: Sbornik materialov III Vserossijskoj nauchno-prakticheskoj konferencii s mezhdunarodnym uchastiem. – 2019. – S. 28-33.

Favorskaja M. N. K voprosu ob ispol'zovanii formal'nyh grammatik pri raspoznavanii ob"ektov v slozhnyh scenah // Reshetnevskie chtenija. – 2009. – T. 2. – S. 540-541.

Janchenko E. V. Ispol'zovanie formal'nyh grammatik v kriptografii // Sovremennye problemy telekommunikacij: materialy mezhdunarodnoj nauchno-tehnicheskoj konferencii. – Novosibirsk, 2021. – S. 155-158.

Kozlov S. V. Intellektual'naja sistema podderzhki prinjatija reshenij «Advanced Tester» // Komp'juternaja integracija proizvodstva i IPI-tehnologii: sbornik materialov X Vserossijskoj konferencii. – Orenburg, 2021. – S. 127-131.

Maljavko A.A. Formal'nye jazyki i kompiljatory: uchebnoe posobie dlja vuzov. – M.: Izdatel'stvo Jurajt, 2020. – 429 s.

Pentus A. E., Pentus M. R. Teorija formal'nyh jazykov: uchebnoe posobie. – M: Izd-vo CPI pri mehaniko-matematicheskom f-te MGU, 2004. — 80 s.

Hopkroft Dzh. Je., Motvani R., Ul'man Dzh. D.. Vvedenie v teoriju avtomatov, jazykov i vychislenij. – M., 2008. – 528 s.

Skripov A. V. Opisanie kontekstnyh uslovij formal'nyh jazykov grammatiki s kontekstual'nymi argumentami // Vestnik Ural'skogo instituta jekonomiki, upravlenija i prava. – 2013. # 1 (22). – S. 111-116.

Martynenko B. K. Reguljarnye jazyki i KS-grammatiki // Komp'juternye instrumenty v obrazovanii. – 2012. # 1. – S. 14-20.

Kozlov S.V., Svetlakov A.V. Primenenie teorii formal'nyh grammatik v informatike. Distancionnye obrazovatel'nye tehnologii. Sbornik trudov VI Mezhdunarodnoj nauchno-prakticheskoj konferencii. – Simferopol', 2021. – S. 255-259.

Kristofides N. Teorija grafov. Algoritmicheskij podhod. – M.: Mir, 1978. – 432 s.

Kozlov S. V. Cifrovoe modelirovanie processov upravlenija social'no-jekonomicheskimi sistemami s primeneniem metodov funkcional'nogo analiza // Vyzovy cifrovoj jekonomiki: itogi i novye trendy: sbornik statej II Vserossijskoj nauchno-prakticheskoj konferencii (g. Brjansk, 07 ijunja 2019 g.) [Jelektronnyj resurs]. – Brjansk: Brjan. gos. inzhenerno-tehnol. un-t., 2019. – S. 233-239.

Bajdarmanova B. N. Nekotorye sposoby nahozhdenija jekvivalentnyh preobrazovanij v kontekste svobodnyh grammatik // Theoretical & Applied Science. – 2013. – # 5 (1). – S. 5-11.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162