In English

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

Kristofer Hansson ; Jonas Hugo
Göteborg : Chalmers tekniska högskola, 2015. 65 s.
[Examensarbete på avancerad nivå]

This 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.

Publikationen registrerades 2015-06-29. Den ändrades senast 2019-05-21

CPL ID: 219083

Detta är en tjänst från Chalmers bibliotek