2
$\begingroup$

Often I use sed 's/match/replacement/' in places where I would rather have a more formal tool, just because sed is what I know.

As an example, lets say I want to translate markdown to html. In sed I would start doing something like:

s/# (.*)/<h1>\1</h1>/
s/## (.*)/<h2>\1</h2>/
s/### (.*)/<h3>\1</h3>/
s/#### (.*)/<h4>\1</h4>/
s/`(.*)`/<pre><code>\1</pre></code>/
# etc...

Now for arguments sake, lets say that I had the grammars of markdown and html (or whatever two languages are the best for this example) defined in BNF.

Then instead of creating an ad-hoc parser for both markdown and html, I would just have to find a tool to translate from grammar A to grammar B. Is there any such framework?

  • For example, I know pandoc can translate from several markup languages to each-other.
  • Also a lot of languages now-a-days translate to javascript (eg: typescript, elm, purescript, coffeescript).
  • I took a look at string-rewriting/semi-Thue systems on wikipedia.

I'm guessing that most of these tools do the translation by hand, rather than taking as an input two grammars and some mapping from one to the other. Is this even possible?

Improve this question
$\endgroup$
1
  • $\begingroup$ In theory, if the two languages have the same compute competence.they can translate from one to another. $\endgroup$
    – Hamilton
    Jun 20, 2021 at 1:59

1 Answer 1

Reset to default
1
$\begingroup$

The language $$EQ_{CFG} = \{\langle G_1,G_2 \rangle ~|~ G_1,G_2 \text{ are context free and } L(G_1) = L(G_2)\}$$ is known to be undecidable.

Suppose you had some algorithm which on input of two grammars, would give you a way to tranform one into the other. Then this process should only succeed if they produce the same language, and fail if they don't. So you could decide this undecidable set.

There are some catches. Maybe your grammars are not context free, or maybe you already know they are equivalent and just want the conversion, things where this would not apply.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How about transpilation or source-to-source compilation? $\endgroup$
    – user16237393
    Jul 6, 2021 at 10:09
  • $\begingroup$ @user16237393 I guess it depends on how phrased. Equality between two turing machines is also an undecidable problem. $\endgroup$
    – abrahimladha
    Jul 19, 2021 at 16:35

Your Answer

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

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