oriroth / fling Goto Github PK

A fluent API generator

Home Page: http://drops.dagstuhl.de/opus/volltexte/2019/10805/

Java 99.96% GAP 0.04%

fling's Introduction

Fling is the first general and practical solution of the fluent API problem. The implementation includes an algorithm that takes a deterministic context free language (equivalently, LR(k), k≥0 language) and encodes it in an unbounded parametric polymorphism type system employing only a polynomial number of types. The theoretical result is employed in an actual tool Fling—a fluent API compiler-compiler in the venue of YACC, tailored for embedding DSLs in polymorphic, object-oriented languages.

Fling

Fling (fluent interfaces generator) is a parser generator. Instead of generating the code of a real-time parser, Fling generates Java fluent interfaces, which implement a compile-time parser of the given language. Fling accepts either LL(1) grammar or DPDA specifications; If a grammar is given, Fling also generates the AST class definitions used to compile a fluent API INVOCATION into an abstract parse tree at run-time.

Download jar

Full release (includes examples)

Documentation

Example

Let us define the Datalog grammar, in Java, using Fling's interface:

// Datalog grammar defined in BNF
BNF bnf = bnf().
      start(Program).
      derive(Program).to(oneOrMore(Statement)).
      specialize(Statement).into(Fact, Rule, Query).
      derive(Fact).to(fact.with(S), of.many(S)).
      derive(Query).to(query.with(S), of.many(Term)).
      specialize(Rule).into(Bodyless, WithBody).
      derive(Bodyless).to(always.with(S), of.many(Term)).
      derive(WithBody).to(RuleHead, RuleBody).
      derive(RuleHead).to(infer.with(S), of.many(Term)).
      derive(RuleBody).to(FirstClause, noneOrMore(AdditionalClause)).
      derive(FirstClause).to(when.with(S), of.many(Term)).
      derive(AdditionalClause).to(and.with(S), of.many(Term)).
      derive(Term).to(l.with(S)).or(v.with(S)).
      build();

After Fling has created the fluent interfaces supporting Datalog, a simple Datalog program...

parent(john, bob)
parent(bob, donald)
ancestor(A, B) := parent(A, B)
ancestor(A, B) := parent(A, C), ancestor(C, B)
ancestor(john, X)?

...can be written in Java by method-chaining, as follows:

Program program =
  fact("parent").of("john", "bob").
  fact("parent").of("bob", "donald").
  always("ancestor").of(l("adam"), v("X")).
  infer("ancestor").of(v("A"), v("B")).
    when("parent").of(v("A"), v("B")).
  infer("ancestor").of(v("A"), v("B")).
    when("parent").of(v("A"), v("C")).
    and("ancestor").of(v("C"), v("B")).
  query("ancestor").of(l("john"), v("X")).$();

The produced program is represented in Java as an abstract syntax tree (AST) that can be traversed and analyzed by the client library.

fling's People

Contributors

Stargazers

Watchers

Forkers

lorenzleutgeb metormaon homedirectory

fling's Issues

Output for C#

Global renaming: OneOrMore->many; ZeroOrMore->any

Re paramater types.

Rename Collections to As

As.set
As.list
etc.

Rename CompilationScript.java

Place it in fling.examples, and name it:
ExamplesMainRunMeFirst.java

Create package-info files

and update the docs.

LR Grammar Generator

Requires importing new library

Traverse function

Chagne it to return a String. Do not print from this function

Use decorator design pattern

on fanyEBNF.
nullable, get first, follow, etc. should be in decorator(s)

Rename package to il.ac.technion.cs.fling

Rename package to fling instead of ori.roth

Write the LL(1) grammar with itself

Create package fling.intenral

Move into there all files that should not be user visible.
User visible classes are the ones you need to use the tools: BNF, adapters, Grammar, LL1, etc.

Output for Scala

Output for C++

Accepting a broader a range of grammars and generating an AST with closely resembling structure

I've spent some time familiarising myself with Fling and I am positively impressed by your work. Naturally, I am starting to hit some limitations as I explore further. So the goal of this issue is to discuss one particular limitation. I'd like to know what you think and whether it is possible to overcome this limitation in Fling.

The limitation comes from the restriction on the class of accepted grammars, which must be LL. Here are some challenges that stem from it:

Any sophisticated grammar needs to be rewritten to fit the class of LL grammars. This is mostly a matter of programming ergonomics, and I can see how the translation could be implemented.
Generated ASTs directly correspond to their LL grammars. This challenge is the most significant one as it makes the generated AST difficult to work with: it is hard to reason about in the same way as LL grammars are hard to read. Moreover, there is an issue of evolvability. Certain changes that induce little semantic variation, such as operator precedence, might require significant changes to the LL grammar resulting in proportionate changes to the resulting AST.

For example, let's consider a context-free grammar for a language that has predicates and means of combining them:

Condition = Predicate | Condition 'and' Condition | Condition 'or' Condition | '(' Condition ')'
Predicate = ...

Notably, this grammar is not LL as it involves left recursion.
To provide this grammar to Fling, it has first to be transformed:

Condition = Predicate Condition$$ | CompoundCondition
CompoundCondition = '(' Condition ')' Condition$$
Condition$ = 'or' Condition | 'and' Condition
Condition$$ = Condition$ Condition$$ | ε

Now in Fling:

derive(Condition).to(Predicate, Condition$$).or(CompoundCondition).
derive(CompoundCondition).to(begin, Condition, end, Condition$$).
derive(Condition$).to(or, Condition).or(and, Condition).
derive(Condition$$).to(Condition$, Condition$$).orNone().

And the resulting AST:

interface Condition {}
record Condition1(Predicate predicate, Condition$$ condition$$) implements Condition {}
record CompoundCondition(Condition condition, Condition$$ condition$$) implements Condition {}

interface Condition$ {}
record Condition$1(Condition condition) implements Condition$ {}
record Condition$2(Condition condition) implements Condition$ {}

interface Condition$$ {}
record Condition$$1(Condition$ condition$, Condition$$ condition$$) implements Condition$$ {}
record Condition$$2 implements Condition$$ {}

Clearly, such an AST is difficult to reason about because this is the level of LL grammars.

Ideally, an AST corresponding to the original grammar would have the following form:

interface Condition {}
record AndCondition(Condition left, Condition right) implements Condition {}
record OrCondition(Condition left, Condition right) implements Condition {}
record CompoundCondition(Condition cond) implements Condition {}
record Predicate(...) implements Condition {}

And the original grammar would be specified as follows:

specialize(Condition).into(AndCondition, OrCondition, CompoundCondition, Predicate)
derive(AndCondition).to(Condition, and, Condition).
derive(OrCondition).to(Condition, or, Condition).
derive(CompoundCondition).to(begin, Condition, end).
derive(Predicate).to(...).

Overall, it would be great to be able to:

Specify a context-free grammar as input to Fling (given that it can be transformed into LL).
Have the generated AST resemble the input grammar as closely as possible.

As I already mentioned, I know that CFG to LL translation is possible, so point 1 could be achieved.
The requirement outlined in point 2, however, seems vastly more difficult to achieve. It would
probably also require changes to the parsing algorithm. A mapping between the original and
transformed grammars would need to be maintained and used to construct the desirable AST. I can only
guess at possible approaches, so I strongly wish to hear what the authors of Fling think.

returning terminals
-returning variables
-returning grammar
-returning start symbol

On this, create a function that that takes FluentLanguageAPI and
creates Java file/mediator.

E  -> T E'
E' -> + T E' | -TE' |epsilon
T  -> F T'
T' -> * F T' | /FT' |epsilon
F  -> (E) | int

e.g., by

start(Expression). 
derive(Expression).to(Summands).
derive(Summands).to(DegenerateSummands).
derive(Summands).to(Summand,SummandsList).
derive(Summand).to(sum(oneOrMore(Expression)).
derive(SummandsList).to(plus,Summand)