Primerjava sintaksne analize vrste LLLR in LL(*)

magistrsko delo

Klemen Košir (Avtor), Boštjan Slivnik (Mentor)

Povzetek

Sintaksna analiza se na področju računalništva uporablja v prevajalnikih za preverjanje veljavnosti prevajanega programa glede na izbrano gramatiko oziroma programski jezik. Novi in izboljšani pristopi ter algoritmi omogočajo hitrejšo sintaksno analizo ter dovoljujejo uporabo zahtevnejših razredov gramatik in programskih jezikov. V tem magistrskem delu smo implementirali metodo LLLR, ki združuje lastnosti metod LL in LR. Tako lahko sintaksno analizo izvedemo v linearnem času, v primeru konflikta v sintaksni tabeli pa izvajanje nadaljujemo z vgrajenim analizatorjem po metodi LR. Implementirano metodo smo najprej primerjali z metodo LL(k). Čeprav sta metodi na gramatikah brez konfliktov v sintaksni tabeli enako hitri, na praktičnih primerih opazimo, da lahko metoda LLLR sintaksno analizo izvede ne glede na število konfliktov in rekurzivnost produkcij. Zatem smo metodo primerjali še z metodo LL(*), ki konflikte razrešuje z determinističnimi končnimi avtomati. Metoda LL(*) je zaradi uporabe avtomatov v splošnem hitrejša, vendar ne podpira leve rekurzije. Za take gramatike je primernejša uporaba metode LLLR.

Ključne besede

sintaksna analiza;gramatika;jeziki;vgrajeni analizator;računalništvo;računalništvo in informatika;magisteriji;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2019
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[K. Košir]
UDK:	004(043.2)
COBISS:	1538452675
Št. ogledov:	651
Št. prenosov:	170
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	LLLR vs LL(*) parsing
Sekundarni povzetek:	Syntax analysis is a process used in compilers to determine the validity of a program source code according to the chosen programming language grammar. New and improved approaches and algorithms enable faster analysis and allow the use of more sophisticated grammars and programming languages. In this thesis, we implemented the LLLR method, which combines the features of the LL and LR methods. Thus, the syntax analysis can be performed in linear time, while conflicts in the parse table are resolved with the embedded parser using the LR method. We first compared the implemented method to the LL(k) method. Although the methods are equally fast when applied to grammars without conflicts in the parse table, practical examples have shown us that the LLLR method can perform the analysis regardless of the number of conflicts and recursiveness of productions. We then compared the method to LL(), which resolves conflicts with deterministic finite automata. The LL() method is generally faster due to the use of automata but does not support left recursion. For such grammars, the use of the LLLR method is more appropriate.
Sekundarne ključne besede:	syntax analysis;grammar;languages;embedded parser;computer science;computer and information science;master's degree;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Študijski program:	1000471
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	75 str.
ID:	11295713