I am trying to build code generation and transformation tool and hence I need software for Abstract Syntax Tree manipulation for at least three languages (Coq, Haskell, Java). So far I have managed to find custom software for 2 of the languages (Haskell, Java) and I wonder - why there is no universal program that can take BNF grammar and generate manipulation tool from it? There are universal YACC parser generator and why there is no universal AST manipulation tool generator? I am considering building one myself (I have no other option), but it could be smart to consider the reason why something similar has not been done so far? Maybe I should not do it as well?

I can image the following overall design of such tool: 1) I can use YACC parser generator to arrive at some graph structure; 2) I can import this graph structure in some general graph manipulation library (I guess, there should exist some) and do manipulation there. So, one should combine existing software only here, isn't so?

I have two use cases for such tool:

  • Automatic programming or automated software development - I am considering use of cognitive architectures (http://bicasociety.org/cogarch/architectures.php) for modelling how software is designed and how the code are built and the reasoning should be done at the right level of abstraction (AST level) for this. Of course, modern software involve several programming languages - e.g. the simplest web application involves as minimum HTML/JavaScript/Sass-CSS/SQL or NoSQL.
  • Immediate used case: I have to simulate term rewriting in Coq (I have relevant SO question about this, there is no tool currently available).

But I guess that there can be many for uses cases.

  • 3
    Food for thought: (1) Syntax is comparatively easy, but what about semantics? Haskell has no concept of Java-style classes, objects, or mutability, and Java has no concept of Haskell-style typeclasses, monads, or lazy evaluation. (2) Note that YACC has its limits, for example it cannot parse Haskell's indentation-sensitive syntax. Related questions: Why different languages have different syntax, If we had an universal interpreter
    – amon
    Aug 24, 2018 at 21:02
  • 1
    I expect that tools are way more effective when they can display the concrete syntax elements. But to do that, they actually need to know what they are.
    – Telastyn
    Aug 24, 2018 at 21:25
  • 1
    There are some efforts to build ontologies of programming languages (although no important progress have been made) - there are concepts that span multiple languages (classes are in many of them), so, maybe one can annotate BNF grammars and expect that AST tool organizes the trees according to annotations.
    – TomR
    Aug 24, 2018 at 21:33
  • 1
    And kframework.org can be used for semantics.
    – TomR
    Aug 24, 2018 at 23:24
  • 1
    Antlr is fairly close to what you want. Many languages don't work well with BNF because they are actually multiple grammars and you have to use context dependent filtering to pass fragments to the correct parser. Aug 30, 2018 at 0:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.