6
$\begingroup$

Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and you want to make some guesses on the corresponding syntactic tree.

How would you try to achieve this, and would you have any hope to make it working on some toy problems ?

To be clear, the goal isn't to make a parser for 4 or 5 different (but similar) programming languages, but really to detect -from some examples- the regularity in how the data is structured, and build from it a syntactic tree, with the hope to generate a grammar, a syntactic parser and -let's dream- a semantic parser and an interpreter.

My thoughts : a major problem is that in general the grammar needed for parsing a given source code isn't LR(1), but only locally LR(1), and globally recursive. For example HTML contains some Javascript, itself containing some HTML+Javascript hidden in a string :

<html><body><script>

   document.onLoad = (function(){ 
            document.write("<div> <input type='button' value='click'   \
                       onClick='javascript:fn();'></input> </div>   \
                     <script>   \
                           function fn() { alert('wow a language nested into another'); }    \
                    </script> ");
</scritp></body></html>

For parsing this, you need to generate a grammar for HTML and another one for Javascript, and generate a recursive grammar saying that sometimes in the syntactic tree (from one node to its child) it can jump from one language to the other.

Do you have any reference/idea on this problem?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

You might be interested in learning about grammar induction: given a set of examples of strings from a context-free language, there are algorithms to learn a context-free grammar that generates those strings.

To learn more about it, read the Wikipedia article I linked to, and Inducing a context free grammar, Is there a known method for constructing a grammar given a finite set of finite strings?, and the the Sequitur, Lempel-Ziv-Welch, and byte pair encoding algorithms.

There's no hope for automatically building an interpreter for the language, because that depends on the semantics (meaning) of the programs, and you can't determine that solely from the program source code; the most you can hope to learn is to characterize the syntax of the language, not the semantics.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks at lot. What about the hope of making it working on toy problems ? $\endgroup$
    – reuns
    Commented Oct 13, 2016 at 5:36
  • $\begingroup$ LZW works only for prefixed trees, right ? While here I have many infixed trees, so the "genetic algorithm" part of Grammar_induction looks more adapted $\endgroup$
    – reuns
    Commented Oct 13, 2016 at 5:46
  • $\begingroup$ One last comment : I know that natural language processing have a similar but completely different problem. Source code is highly structured, much more than natural language, so the problem should be much easier and much more "mechanical". Unfortunately, most work on "grammar induction" is about natural language processing, not source code. A reference I found is this grammarware.net/text/2014/rosu.pdf $\endgroup$
    – reuns
    Commented Oct 13, 2016 at 6:06
1
$\begingroup$

It may be possible to automatically generate parsers for multiple programming languages using example-based machine translation systems. These systems have been used to translate natural languages, so it is also possible that they could be used to translate and parse programming languages.

Example-based machine translation systems can be designed to "learn" the grammar of multiple languages using parallel corpora. A parallel corpus for several programming languages could be written like this:

java
    System.out.println(a)
c#
    Console.WriteLine(a)
python
    print(a)

Programming languages can also be automatically translated using unsupervised learning models: Facebook recently did this using a system called TransCoder.

Improve this answer
$\endgroup$

Your Answer

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

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