Problem Detail: There are parser generators (some of which are limited to certain classes of grammars) which, given a grammar, automatically generate a parser for that grammar. Would it be possible to make a general-purpose translator generator to automatically translate from a string in the language with production rules described by grammar $G_1$ to a string in the language with production rules described by grammar $G_2$? If so, what rules would have to be imposed? For practical purposes let’s say these grammars must both be CFGs. Would a formalization of semantic rules for the grammars also have to specified for the translator generator? An example of this hypothetical, general-purpose translator generator: the translator generator is given grammar $G_1$ (which is a CFG representing a context-insenitive adaptation of the C programming language), $G_2$ (which is a CFG representing a context-insenitive adaptation of the JavaScript programming language), and a formalization of the semantic rules of the language with production rules described by grammar $G_2$1. The translator generator is expected to produce a translator which takes as input a string in the language with production rules described by grammar $G_1$ and translates that string to a string in the language with production rules described by grammar $G_2$. 1 I am not entirely sure of what this formalization of the language’s semantic rules would look like, so if there exists some formalization which would make the existence of this general-purpose translator generator decidable, then I would also welcome suggestions on what this formalization would look like.
Asked By : Francesco Gramano
Answered By : Raphael
Every reasonable, Turing-complete programming language is (in essence) an admissible numbering of all Turing-computable functions. As such, we know that there is indeed a computable compiler from (and to) any other such numbering/language. “Computable” here means that the compiler can be expressed as Turing machine (or equivalent). It does not mean we that there is an algorithm that computes the compiler, given (representations of) both languages. Finding this program by hand may be hard, too. I guess it won’t be in practice, though, at least not for many pairs of languages. But the result need not be pretty; all we know is that we get some equivalent program. One look at uncompiled Java code tells you all you need to know.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41909 Ask a Question Download Related Notes/Documents
