There are parser generators (some of which are limited to certain classes of gra

Question

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 G1 to a string in the language with production rules described by grammar G2? 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 G1 (which is a CFG representing a context-insenitive adaptation of the C programming language), G2 (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 G21. The translator generator is expected to produce a translator which takes as input a string in the language with production rules described by grammar G1 and translates that string to a string in the language with production rules described by grammar G2.

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.