A Generator of Incremental Divide-and-Conquer Lexers A Tool to Generate an Incremental Lexer from a Lexical Specification

Visa enkel post
dc.contributor.authorHansson, Kristofer
dc.contributor.authorHugo, Jonas
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.date.accessioned2019-07-03T13:42:30Z
dc.date.available2019-07-03T13:42:30Z
dc.date.issued2015
dc.description.abstractThis report aims to present a way to do lexical analysis incrementally instead of the present norm: sequential analysis. In a text editor, where updates are common, an incremental lexer together with an incremental parser could be used to give users real time parsing feedback. Previous work has proven that regular expressions can be implemented incrementally [11], we make use of these findings in order to show that it can be expanded to a lexical analyzer. The results in this report shows that an incremental lexer is efficient, it can do an update in log n time which makes it suitable when updates are common. In order for an incremental lexer to be applicable it has to be precise, only correctly lexed tokens are relevant. It is required that an incremental lexer is robust, a lexical error for a partial result must be handled gracefully since it may not propagate to the final result. To achieve incrementality a divide and conquer tree structure, fingertrees, is used that stores the intermediate lexical results of all the partial trees. When an update to the tree is made only the effected node and its parents are updated. The state machine in the implementation is generated by Alex since it is efficient and enables support for lexical analysis of different languages. The report finishes with giving suggestions for improvements to the drawbacks found during the work, The suggestions given are mainly for improving space complexity. This report shows that an implementation of an incremental lexer can be precise, efficient and robust.
dc.identifier.urihttps://hdl.handle.net/20.500.12380/219083
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectData- och informationsvetenskap
dc.subjectInformations- och kommunikationsteknik
dc.subjectComputer and Information Science
dc.subjectInformation & Communication Technology
dc.titleA Generator of Incremental Divide-and-Conquer Lexers A Tool to Generate an Incremental Lexer from a Lexical Specification
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
local.programmeComputer science – algorithms, languages and logic (MPALG), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
219083.pdf
Storlek:
726.78 KB
Format:
Adobe Portable Document Format
Beskrivning:
Fulltext
Ladda ner
Samling
Examensarbeten för masterexamen