3

I'm trying to find a software system that can automatically generate a source-to-source compiler, given a formal grammar and a description of the output for each rule in the grammar.

PEG.js that can do this in some cases, but it still leaves much to be desired. As a proof of concept, I've written a PEG.js grammar that can convert JavaScript arithmetic expressions into Lisp expressions:

start
  = additive

additive
  = left:multiplicative "+" right:additive { return "(+ " + left +" "+ right + ")"; }
  / multiplicative

multiplicative
  = left:primary "*" right:multiplicative { return "(* " + left +" "+ right +")"; }
  / primary

primary
  = integer
  / "(" additive:additive ")" { return additive; }

integer "integer"
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

Unfortunately, this grammar can only translate Javascript into Lisp and not vice-versa. Are there any alternatives to PEG.js that can automatically generate source-to-source compilers?

3

[OP asks in a comment if the DMS Software Reengineering Toolkit would be a good choice of code generator. I think yes, but then its my system so you need to take this answer with a very big grain of salt. What follows is some justification].

People repeatedly make the mistake of assuming that having a parser (e.g., "Peg.js") is the key to building code generators.

This is confusing "necessary" for "sufficient". The problem is what I call Life After Parsing.

What OP appears to really want is a (Source-to-Source) Program Transformation System (PTS)

These are tools that generally accept (one or more) grammars, and accept "rules" that map between structures in one grammar to another. The grammars allow the tools to parse source to compiler data structures such as abstract syntax trees. The rules allow you write, using the concrete syntax of the source and target languages,

 if you see *this syntax pattern*, replace it by *that syntax pattern*

By matching the AST for the syntax patterns against the AST from the parsed program, such rules can find where to apply the rule, and then splice it a replacement tree from the replacement pattern.

This works remarkably well for some tasks. Stratego/XT and TXL are good examples of PTS that can easily implement OP's specific example, using such rules.

However, most such systems (Stratego/XT and TXL included) are pretty weak when it comes to doing sophisticated code generation/transformation, because they don't really address "life after parsing". In fact, they often go overboard in providing a pure-rewrite system, only. If you reach back to your CS classes, these "pure rewrites" are tree-to-tree rewrites, which are a generalization of string-to-string rewrites. Such rewrites are so-called Post systems, and technically can accomplish any computation, therefore any possible transformation of the input. So such PTS are Turing capable. You can do anything. Arguably.

But they handle context (information from other parts of the program) poorly, which means that writing transforms to do serious tasks involving complex symbol tables, types, or flow analysis are impractical to implement this way.

The compiler community taught us how to build compilers; these are the essence of code generation. You ignore what the compiler community knows are the price of building weak transformation and generator tools.

DMS was designed from the beginning to be a PTS that harnesses this knowledge. One provides DMS with grammars, and various types of analyzers for each grammar ("a language front end"), to give DMS access to ASTs, control and data flow graphs, and other analyses needed to support transforms that can inspect context. DMS provides lots of machinery to support the construction of such front ends, and over the years we have built many front ends for production programming languages (e.g, many dialects of C and C++ including MS and GNU versions of C++14, Java, COBOL, ...)

Using those front ends, one can write context-dependent optimization rules like:

target domain C~GCC4;

rule simplify_conditional_assignment(v:left_hand_side,e1:expression,e2:expression,e3:expression)
    :statement->statement
 =  " if (\e1) \v=\e2; else \v=e3; " 
 -> " \v=\e1?\e2:\e3; "
 if no_side_effects(v);  -- here is the context check; without it, this transform is unsafe

and translation rules (oversimplifying a bit) like:

source domain COBOL;
target domain C~GCC4;

rule translate_add_to_self_integer(lvalue: lhs, rvalue: v): statement->statement
  =  "ADD \v TO \lhs."
  -> "\lhs+=\v"
  if IsIntegerType(lhs) /\ IsIntegerType(v); -- special case context check

rule translate_add_to_self_decimal_int(lvalue: lhs, rvalue: v): statement->statement
  =  "ADD \v TO \lhs."
  -> "decimal_add(&\lhs,&\v)"
  if IsDecimalType(lhs) /\ IsDecimalType(v); -- different special case check

To get a sense of what DMS can do, you can see how DMS is used to define high school algebra as a grammar, and then do symbolic computations on it.

Or, you can see more complex transformations applied to Wirth's Oberon programming language as an example. This page gives a lot of detail about what one can say in the rewrite rules.

A spectacular (I think) example of a source-to-source compiler built with DMS is a JOVIAL (legacy embedded programming language) to C compiler, that translated 1.5 MSLOC of JOVIAL code to C for the Air Force's B-2 Stealth Bomber mission software.

DMS can also carry out complex compositions and transformations on C++(14) code, with complete (context) and accurate support for name resolution and type inference.

If you explore our web site, you'll see (we think) a huge variety of tools. They are all implemented using DMS.

Regarding OP's original question:

  • DMS can be used to build very sophisticated code generators
  • Yes, it compiles grammars and explicit translation rules into a package forming a source-to-source compiler (using a DMSRuntime library for support).
  • It handles context well, where most PTS do not.

There's an implied question from OP about directionality of transformation. DMS translators are wired to go from A to B by rules that map A structures to B structures. Those rules don't run backwards. To get a bidirectional translator, you have to build two, each with its own set of rules (in this case, another set of rules B to A). I have seen no system anywhere that does bidirectional transformation, given one direction. I doubt I will ever see one, and I've been doing this for a long time.

DMS is a commercial product. Just so people are not surprised, it is not cheap compared to many other widely available development tools. (I get a lot of flak from people that tell me it should be free, but who didn't put 20 years of vision and personal energy into it). It is cheap if you value your time, and want to finish building a sophisticated tool.

|improve this answer|||||
  • Indeed, some bidirectional compiler generators do exist. See here for a description of a bidirectional compiler-compiler. – Anderson Green Jun 9 '15 at 19:58
  • @AndersonGreen Impressive. I was not able to scan enough of the book to understand how one can invert a many-to-one function used by a translator. The author of that work claims an invertible C to Pascal translator. – Ira Baxter Jun 9 '15 at 22:20
  • It is surprisingly easy to write a "many-to-many" translator using definite clause grammars in Prolog. Here is a proof-of-concept of this type of translator. – Anderson Green Mar 11 '16 at 4:39
  • Why should that be the case? A local translation result may be affected by context from far away based on language semantics and desire to produce good code. This costs inference time, and mental design effort to define that inference. Why should a DCG make it "surprisingly easy" to write even one translator? (I will grant that Prolog makes it easier to build symbolic computations than a conventional compiler. Regarding DMS: it isn't conventional; it has a lot of symbolic manipulation machinery built in). Proof of concepts don't count; real translators count. Details are tough. – Ira Baxter Mar 11 '16 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.