Earleyev parser

diplomski rad

• Naslov (engleski): Earley's parser
• Autor: Luka Lončar
• Mentor: Vedran Čačić (mentor)
• Član povjerenstva: Vedran Čačić (predsjednik povjerenstva)
• Član povjerenstva: Pavle Pandžić (član povjerenstva)
• Član povjerenstva: Nenad Antonić (član povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2021-09-22, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U početku rada smo definirali osnovne pojmove teorije formalnih jezika. Zatim smo definirali regularne izraze i uveli opću definiciju gramatika kako bismo mogli definirati klasu regularnih jezika. Zatim smo definirali beskontekstne gramatike i jezike koje one generiraju. Zatim smo uveli pojmove problema i parsiranja, te objasnili algoritam CYK koji ima teorijsku značajnost. U drugom poglavlju smo protumačili algoritam i implementaciju Earleyevog parsera. Prvo smo objasnili implementaciju strukture podataka. Zatim smo objasnili konstrukciju skupova stanja Earleyevih stavki. Naposljetku smo objasnili konstrukciju stabla parsiranja.

Sažetak (engleski)

In the beginning of this thesis we defined basic terms of formal language theory. Then we defined regular expressions and introduced the universal definition of grammars so we could define the class of regular languages. Then we defined context-free grammars and languages they generate. Then we introduced concepts of problems and parsing, and explained the CYK algorithm which has theoretical significance. In the second chapter, we explained the algorithm and implementation of the Earley parser. First we explained the implementation of the used data structures. Then we explained the construction of state sets which consist of Earley items. In the end, we explained the construction of the parse tree.

• Ključne riječi: teorija formalnih jezika; klasa regularnih jezika; beskontekstne gramatike; parsiranje; algoritam CYK
• Ključne riječi (engleski): formal language theory; class of regular languages; context-free grammars; parsing; CYK algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:827568
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-10-29 06:55:48