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

The Taub Faculty of Computer Science Events and Talks

Compile-Time LL(1) Parsing in Java's Typesystem
event speaker icon
Ori Roth (M.Sc. Thesis Seminar)
event date icon
Wednesday, 28.03.2018, 13:30
event location icon
Taub 401
event speaker icon
Advisor: Prof. J. Gil
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.