Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Compile-Time LL(1) Parsing in Java's Typesystem
event speaker icon
Ori Roth, M.Sc. Thesis Seminar
event date icon
Wednesday, 28.3.2018, 13:30
event location icon
Taub 401
A recent result shows that the Java type system and its type-checker are mighty enough to emulate deterministic pushdown automata (DPDAs), and hence, capable (disregarding cost) to recognize deterministic context free languages (DCFGs). The problem is of concrete practical value, since, as it turns out, this recognition is essential for automatic generation of fluent APIs from their specification. This work advances the state of knowledge, in presenting, for the first, an efficient (specif- ically linear time) algorithm for generating an automaton, implementable within the framework of compile time computation of Java, which recognizes a given LL(1) language. The generated automaton is time efficient, spending a constant amount of time on each symbol of the “input”. Space requirement is also polynomially bounded. We implement the algorithm in a prototypical tool to convert a (fluent API) specifi- cation of a certain fluent API design, into an actual implementation.
[Back to the index of events]