Primerjava sintaksne analize vrste LLLR in LL(*)

magistrsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2019
Typology:	2.09 - Master's Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[K. Košir]
UDC:	004(043.2)
COBISS:	1538452675
Views:	651
Downloads:	170
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	LLLR vs LL(*) parsing
Secondary abstract:	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.
Secondary keywords:	syntax analysis;grammar;languages;embedded parser;computer science;computer and information science;master's degree;
Type (COBISS):	Master's thesis/paper
Study programme:	1000471
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	75 str.
ID:	11295713