Orodje za gramatike LL(1)

diplomsko delo

Tim Čas (Author), Janez Brest (Mentor), Borko Bošković (Co-mentor)

Abstract

V diplomskemu delu je predstavljeno orodje za delo z gramatikami tipa LL(1). Orodje omogoča preverjanje pravilnosti podane gramatike ter izračun lastnosti gramatike oz. posameznih pravil, kot sta množici FIRST in FOLLOW. Za izračun smo uporabili pristop, pri katerem se relacije med posameznimi pravili zapišejo v obliki matrik. Nad temi matrikami se nato izvedejo operacije, kot so množenje matrik ali pa tranzitivno zaprtje. Rezultat so matrike, iz katerih lahko direktno razberemo množice FIRST in FOLLOW ter preverimo pravilnost gramatike. Orodje omogoča tudi vnos testnih stavkov jezika, ki ga gramatika opisuje, izvoz tabele za skladovne razpoznavalnike in izvoz diagramov za orodje Graphviz: diagram odvisnoti med pravili in sintaktični diagram za testni stavek.

Keywords

računalniška gramatika;gramatike LL(1);sintaksa;sintaktična analiza;

Data

Language:	Slovenian
Year of publishing:	2014
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	[T. Čas]
UDC:	004.4'413:004.424.3(043.2)
COBISS:	18389270
Views:	1242
Downloads:	112
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	LL(1) Grammar Tool
Secondary abstract:	The thesis presents a tool for working with LL(1) grammars. The tool enables verification of the given grammar's correctness and computation of properties of said grammar or its individual productions, like the FIRST and FOLLOW sets. For the computations, we have used an approach where the relations between individual productions are written in the form of matrices. Operations like matrix multiplication or transitive closure are then executed upon these matrices. The result of these operations is matrices, from which the FIRST and FOLLOW sets can be directly inferred, and the correctness of the grammar verified. The tool also allows the input of a test string of the language described by the grammar, export of a table for stack-based parsers, and export of Graphviz diagrams: a dependency diagram and a syntax diagram for the test input.
Secondary keywords:	computer grammars;DLL(1) grammars;syntax;syntactic analysis;
URN:	URN:SI:UM:
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages:	IX, 37 f.
ID:	8730133