How to Create a Parser that Operates in Reverse

I’ve got my answer to this in the comment of the one I checked. Which Algorithm Approach Should I Take to Generate Lambda Expressions in Java? but I don’t exactly know where to look in terms of generating lambda expressions with Parsing in Reverse. I’m not exactly allowed to use programs like ANTLR.

The tutorials and instructions I see are the traditional parsing tutorials, I can’t seem to find anything that relates to Parsing in Reverse. Is there a more specific term for this, that I can search for? Sorry newbie.


Parsing in reverse is code generation.

Think of a compiler as a translator: first, it parses usually to an intermediate data structure (often a tree), then it walks that intermediate data structure generating code for another language, sometimes as a textual output. Essentially code generation is the reverse of parsing.

The output language of a compiler is usually more primitive (i.e. byte code, assembly, or machine code), but can just as easily be another high-level language.

See, for example, google closure compiler (JavaScript input, JavaScript output). Or TypeScript, which takes TypeScript input to JavaScript output.

So, you should try to encode your content as a tree and employ code generation techniques. Or encode as text and use translation techniques (parse the text input, generate text output).

Translation can be done for a lot of reasons. For example, in the early days, different SQL implementations actually had different operator precedence! So, compiler technology translation was employed to take SQL written for one vendor and translate to SQL fully parenthesized to use with another.


Parsing in reverse is called unparsing or pretty printing. Creating a parser that can operate in reverse (instead of simply creating separate parsers and unparsers) is for example covered in the paper Invertible syntax descriptions: Unifying parsing and pretty printing by Tillmann Rendel and Klaus Ostermann, which describes a mechanism for having a single syntax description be able to operate both as a parser and a pretty printer. In addition to the code from the paper, there is also a more recent Haskell package called syntax which implements this idea.


Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *