BT

Your opinion matters! Please fill in the InfoQ Survey!

Anders Hejlsberg Explains Modern Compiler Construction

| by Pierre-Luc Maheu Follow 2 Followers on May 18, 2016. Estimated reading time: 2 minutes |

A note to our readers: As per your request we have developed a set of features that allow you to reduce the noise, while not losing sight of anything that is important. Get email and web notifications by choosing the topics you are interested in.

The main reference in compiler construction, Compiler: Principles, Techniques, and Tools, also know as the Dragon Book, was first published in 1986. Anders Hejlsberg, known for his work on Turbo Pascal, Delphi, C# and TypeScript, explains in a Channel 9 interview how compiler construction today is different from how it was done 30 years ago.

The main characteristic of a classic compiler is the sequential processing of its input. The phases can be seen as a pipeline of its main components:

Lexer -> Parser -> Type Checker -> Code Generator -> Emitter

Over the last decade, expectations have increased progressively towards IDEs and tooling to provide features such as auto-completion, refactoring, code navigation, static analysis and so forth. User studies at Microsoft have shown these features must respond to input under a delay of 100 ms, otherwise they are deemed too slow. This contrasts with the compilation time of a whole project, which can take over a minute for a mid-sized solution.

To provide quick feedback in an IDE, a compiler must limit as much as possible the processing it does in real time. This means compiling the whole program at each keystroke is not an option. Instead, the compiler builds just enough information to provide an answer to the user.

Fast response time are achieved by limiting processing but also reusing old data structures as much as possible. Each time the user types in a character, every data structure in memory is considered erased. However, to increase responsiveness, everything that wasn’t modified is reused. Abstract syntax trees (AST), for example, can be reused if the source file they represent wasn’t modified.

Reuse is also possible even if a data structure is modified. Persistent data structures. which are immutable, handle modifications by creating and returning new instances while keeping the parts underneath that weren’t modified. For an AST, that would mean modifying the current node and its ancestor nodes up to the root. The rest of the tree, however, stays the same and is reused in the construction of the new instance.

Back several years ago, the need for IDE features provided in real-time led to a duplicated code base between the C# compiler and the IDE feature implementation. This was one of the main reason behind the creation of Roslyn. Roslyn was designed from the start to be usable from an IDE as well as a command line.

Anders and Seth discusses at the end the resources available to learn more about modern compiler construction. The Roslyn and TypeScript projects are given as examples, both being open source and publicly available on GitHub.

Rate this Article

Adoption Stage
Style

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Tell us what you think

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread
Community comments

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Discuss

Login to InfoQ to interact with what matters most to you.


Recover your password...

Follow

Follow your favorite topics and editors

Quick overview of most important highlights in the industry and on the site.

Like

More signal, less noise

Build your own feed by choosing topics you want to read about and editors you want to hear from.

Notifications

Stay up-to-date

Set up your notifications and don't miss out on content that matters to you

BT