אורי רוט, הרצאה סמינריונית למגיסטר
יום רביעי, 28.3.2018, 13:30
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.