<p>Okay, we all know the standard compiler architecture: a batch program with multiple passes for parsing, optimizing, and generating code.</p>
<p>Suppose you wanted to go all Turbo Pascal and implement a compiler in one pass.</p>
<p>What are the pros and cons of doing that? Is that even feasible in this day and age?</p>
<p><strong>Note</strong>: This is not a duplicate of the <a href="https://langdev.stackexchange.com/questions/1905/what-are-the-pros-and-cons-of-a-compiler-with-a-single-pass-parser">question about single-pass <em>parsers</em></a> for languages that require forward declarations. That one is about parsers only; this one is about architecting a compiler without multiple passes, even for optimization and code gen.</p>

<compilers><implementation><parsing>
What are the pros and cons of single-pass compilers?
CC BY-SA 4.0
2023-07-02T20:40:57.387Z
They're faster in general.
CPlus
CC BY-SA 4.0
2023-07-02T20:45:29.060Z
You might want to use the `<details>` tag for the unnecessary background bit, because it does make the question a bit long
user
CC BY-SA 4.0
2023-07-02T20:52:33.437Z
Oh, how do you do that? Does it hide the stuff by default?
Gavin D. Howard
CC BY-SA 4.0
2023-07-03T12:46:59.010Z
Might be a good idea to reference your other question https://langdev.stackexchange.com/questions/1905/what-are-the-pros-and-cons-of-a-compiler-with-a-single-pass-parser and explain the differences between them otherwise there will be a temptation to close one as a duplicate.
Bruce Adams
<p>When we wrote a single pass compiler, and we wanted to add more language features, the code got super convoluted, and we had this logical &quot;cycle&quot; where we had to so something before AND after something else. This basically halted the development of the language and a rewrite had to be done.</p>
<p>Things like syntax desugaring, type information, optimizations, inlining. Some of the steps mutate the program globally, instead of locally, which is really the downside of single pass compilers.</p>
<p>Another major drawback is that it's hard reusing code for a language server, which does not care to pass the entire codebase on each keystroke.</p>
<p>Modern compilers use a query system. Here's a link: <a href="https://ollef.github.io/blog/posts/query-based-compilers.html" rel="nofollow noreferrer">https://ollef.github.io/blog/posts/query-based-compilers.html</a></p>
<p>I take inspiration from C# (roselyn) and rist-analyzer.</p>

CC BY-SA 4.0
2023-07-03T05:00:37.513Z
2023-07-03T05:00:37.513Z
Spiritus Pap
CC BY-SA 4.0
2023-07-03T08:24:02.267Z
Do you mean `rust-analyzer`?
mousetail 'he-him'
<p>You can't just decide that you want a single pass compiler. A single pass compiler must be able to read a compilation unit line by line, and compile it using the information it has gathered so far, and nothing else. Pascal was a language that could easily be processed that way.</p>
<p>Now if you have a language like Swift, you have absolutely zero chance to compile that with a one pass compiler, so there are no pro's and con's to discuss at all. For example, you need to parse all files, especially the standard library files, for &quot;operator&quot; declarations to even know that + - * / are operators, and whether they are left or right associative or neither, and what their precedence is, and without that you cannot even compile 1 + 2 * 3 because you don't even know whether it is (1 + 2) * 3 or 1 + (2 * 3) or whether it is an error because there are no binary operators + or *.</p>
<p>Personally, I would use a multi-pass compiler even for a language like Pascal today, where you can calmly collect information from your source files, find out things about the program structure, find out more things, after some time figure out what code you want to produce, apply simplifications and optimisations to that code and so on, and finally generate code. Note that modern multi-pass compilers will also store information from the compilation process along with the source code, so if you change one of 50 functions in a source file, there is a good chance that 49 of the functions require very little work, and only the changed one actually requires the full work.</p>

CC BY-SA 4.0
2023-07-03T11:09:43.037Z
2023-07-03T11:09:43.037Z
gnasher729
CC BY-SA 4.0
2023-07-16T02:34:28.187Z
Since this site is "Programming Language Design and Implementation", should you not assume that "What are the pros and cons of single-pass compilers?" is asked in that context?  So then, can we assume that if having a single-pass compiler is important, then the question asker will design (or inherit from) a language (like Pascal) that facilitates making a single-pass compiler? Especially for the "critical code" he wants to produce?
MicroservicesOnDDD
<p>I’m going to assume this question is about ahead-of-time compilers; JIT compilers are a different story altogether. With that in mind…</p>
<h2>The performance benefits of single-pass compilers are overstated</h2>
<p>For starters, there is essentially no longer any benefit to implementing a single-pass compiler: they are a relic of an era in which memory was extraordinarily scarce, and compilers simply could not afford to fit the entire program in memory; this has not been true for 30 years. This is really a crucial point: single-pass compilers were developed to save on <em>memory</em>, not <em>time</em>. Fundamentally, they do all the same work as an equally-simple multi-pass compiler (modulo some marginal translation costs), they just run the whole pipeline on one statement or definition at a time rather than on entire compilation units.</p>
<p>Perhaps you feel that memory usage is nothing to sneeze at. After all, compilers—and especially optimizing compilers—can use quite a lot of memory, and though memory may be much cheaper than it once was, it’s still not free. But this is something of a red herring: compilers that do things that need lots of memory <em>cannot</em> be implemented as single-pass compilers because…</p>
<h2>Single-pass compilers just can’t do the job</h2>
<p>Modern compilers have features and perform analyses that require considering much more context than a single definition at a time. At least some of these features are present in essentially all modern programming languages. Let’s consider some examples (though this list is not by any means exhaustive).</p>
<h3>Forward references</h3>
<p>Forward references without separate forward declarations are almost universally supported by modern programming languages. There is essentially no reason to statically forbid forward references in general.</p>
<h3>Error reporting</h3>
<p>Parse errors and typechecking failures can be made significantly more helpful if the compiler has access to the entire module when generating them. For example, suppose the user has written a correct definition, but given it the wrong type. A naïve compiler would trust the type declaration and report several type mismatches: one at the definition and another at every use site.</p>
<p>However, if the compiler has access to the use sites, it could note that all the uses reflect the actual type rather than the expected one. It can therefore include a suggestion in the error message that perhaps the type signature ought to be changed.</p>
<h3>Type inference</h3>
<p>Different languages perform differing amounts of type inference, but some languages, like Haskell, have type inference that is quite global. In Haskell, a definition’s type is determined by both its body and <em>all</em> of its uses, so computing the type of a top-level definition may require typechecking all other definitions in the module.</p>
<p>GHC (the Haskell compiler) does break up modules into <em>declaration groups</em> very early in the pipeline, immediately after resolving names, based on dependency analysis between declarations (which is very cheap). This allows the definition groups to be typechecked independently, so users don’t pay a cost for this feature if they don’t use it.</p>
<h3>Inlining</h3>
<p>Essentially all ahead-of-time compilers worth their salt perform some very basic optimizations, even if they don’t do enough to warrant the name “optimizing compiler”. For example, most compilers will do constant folding and constant propagation, reducing constant expressions like <code>5 * 2</code> to <code>10</code>. And once <em>any</em> optimizations are at play, a crucial part of the process is <a href="https://en.wikipedia.org/wiki/Inline_expansion" rel="noreferrer">inlining</a>.</p>
<p>In order to inline a function, its body must be known to the compiler while optimizing its call site. This is naturally impossible if the compiler has already processed its code and promptly unloaded it from memory. So compilers generally want to keep the definitions of functions from the same module in memory, anyway, and many even perform cross-module inlining for sufficiently small functions, which requires keeping them in memory, too.</p>
<h3>Interprocedural analysis</h3>
<p>More sophisticated optimizing compilers also perform a battery of optimizations that are explicitly <em>interprocedural</em>, which is to say they cross function boundaries. For example, a compiler might notice that a program boxes some values and passes them to a function that immediately unboxes them, in which case it could remove the unnnecessary boxing. It might also keep track of what side-effects a function performs so that it can reorder calls to it if the compiler deems that will improve performance.</p>
<p>These sorts of optimizations fundamentally depend on considering much more than a single function at a time. In theory, some of them could be done by analyzing each function as it is compiled and saving the results of those analyses for downstream calls (and indeed this is how some cross-module interprocedural analysis works), but even where this is possible, it would miss out on some useful optimizations. This is because these optimizers are usually <em>iterative</em>: they perform an analysis, use it to make some improvements, then analyze the program again, since the previous step might have uncovered new opportunities for further optimization. This iterative process benefits greatly from larger compilation units where more information is available.</p>
<h3>Common subexpression elimination</h3>
<p>Optimizing compilers also perform <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination" rel="noreferrer">common subexpression elimination</a> (CSE), which essentially deduplicates code. Obviously, the more code the compiler is able to consider at once, the greater likelihood that it will find duplicate occurrences of the same thing.</p>
<h2>Multi-pass compilers are much easier to write</h2>
<p>As the above examples hopefully demonstrate, modern compilers do a lot of things. They must handle complex languages with lots of features, they must detect misuses and mistakes and report them to users in a comprehensible fashion, and they must somehow translate the language into another (usually much simpler) one while preserving its semantics. Ultimately, compilers are written by humans, so they must be organized in a way that allows them to flexibly grow and evolve.</p>
<p>For this reason, modern compilers of general-purpose programming languages near-universally translate the program into some intermediate representation that is easier to work with. Optimizing compilers use <em>several</em> intermediate representations, each progressively lower level than the last. These intermediate representations are much smaller and more uniform languages than the ones written by humans, which dramatically cuts down on the number of cases the compiler must consider.</p>
<p>In theory, this approach is not incompatible with processing a single definition at a time: a compiler could each single definition through the entire pipeline before moving onto the next one. But, as alluded to in the first paragraph of this answer, this would not save anything that wouldn’t also be saved by writing a simpler compiler! Sure, it would avoid needing to store the whole compilation unit in memory at once, but even an extraordinarily inefficient AST is not going to take up much more memory to store than the text file containing its source code. The real costs come from all the work the compiler is doing.</p>
<p>So unless you’re either writing a compiler for an exceptionally simple language or a compiler that must, for some reason, run on embedded systems, single-pass compilers are a relic of the past. Multi-pass compilers can do much more while remaining easier to understand, easier to maintain, easier to extend, and easier to debug. They’re a nearly universal compiler technique, and for good reason.</p>

CC BY-SA 4.0
2023-07-02T20:49:56.460Z
2023-07-03T12:48:05.857Z
2023-07-03T12:48:05.857Z
Alexis King
CC BY-SA 4.0
2023-07-02T21:20:56.347Z
Unfortunately, I think you still misunderstand. My compiler does have all of those passes. What it doesn't do is parse the file, build up a list of all declarations, and parse it again, solely to prevent the need to forward declarations.
Gavin D. Howard
CC BY-SA 4.0
2023-07-02T21:32:49.270Z
@GavinD.Howard No real compiler works by running the parser twice on the input text. Perhaps you are referring to a multi-pass *parser*, not a multi-pass *compiler*? What you’ve written sounds like a multi-pass compiler to me.
Alexis King
CC BY-SA 4.0
2023-07-02T21:38:50.857Z
I do know what a multi-pass compiler is, and yes, I'm implementing one, and yes, I mean a multi-pass parser. That's what the question text says. The question is about whether someone would implement a language like C with one parser pass. C is famously multi-pass (it requires a preprocessor pass, a parser pass and all the rest), but because it requires everything to be declared before use, it can run the parser and not do an extra resolution pass on the AST. That extra resolution pass, which may not actually use the file text is what I refer to as a second parser pass.
Gavin D. Howard
CC BY-SA 4.0
2023-07-02T21:40:47.583Z
@GavinD.Howard Okay, that makes more sense, but can you ask that as a separate question? Both answers and at least one comment interpreted your question as referring to a multi-pass compiler because that is what the question said before you edited it.
Alexis King
CC BY-SA 4.0
2023-07-02T21:46:47.093Z
I will ask a separate question, but to do that, I'm actually going to copy out this question into a separate one and rewrite this one because despite your claim, this question always referred to parsing, especially in the body.
Gavin D. Howard
CC BY-SA 4.0
2023-07-02T21:49:43.070Z
@GavinD.Howard Yes, I understand in retrospect. But I genuinely did not understand what you were talking about until after I wrote my answer (and apparently others did not either), because “single-pass compiler” means a pretty specific thing. My best guess was that you meant you were running the whole pipeline once per definition.
Alexis King
CC BY-SA 4.0
2023-07-03T09:44:39.793Z
@GavinD.Howard if you're talking about the quirks of C and C++ specifically, there's a way to parse such languages  in just one go - GLR. See Elkhound, for example. Every time there's an ambiguity you just branch and parse all possible interpretations.
SK-logic
CC BY-SA 4.0
2023-07-03T21:01:26.420Z
Since the comparison is Turbo Pascal--while it was one-pass I do not believe it wrote out the code for a method until it was done.  I managed to break the compiler with a big method (configuration file parser--one massive case statement.)  Some resource was certainly consumed over the course of a method.
Loren Pechtel
CC BY-SA 4.0
2023-10-24T20:55:14.077Z
@LorenPechtel: It knew the address of the machine code responsible for processing each piece of machine code at the moment it was encountered.  It might have held off on writing code for a function to disk until it had applied all of the necessary back-patches, so as to avoid having to patch the file on disk after it was written, but the "Find error location" operation, given a machine code address, would only scan through the source file up to the part which would generate code at that address.
supercat
# What are the pros and cons of single-pass compilers?
Posted by: username_0 on 2023-07-02
Okay, we all know the standard compiler architecture: a batch program with multiple passes for parsing, optimizing, and generating code.

Suppose you wanted to go all Turbo Pascal and implement a compiler in one pass.

What are the pros and cons of doing that? Is that even feasible in this day and age?

**Note**: This is not a duplicate of the [question about single-pass *parsers*](https://langdev.stackexchange.com/questions/1905/what-are-the-pros-and-cons-of-a-compiler-with-a-single-pass-parser) for languages that require forward declarations. That one is about parsers only; this one is about architecting a compiler without multiple passes, even for optimization and code gen.
**Tags:** compilers implementation parsing
> **Comments:**
> **username_1**: They're faster in general.  
> **username_2**: You might want to use the `<details>` tag for the unnecessary background bit, because it does make the question a bit long  
> **username_0**: Oh, how do you do that? Does it hide the stuff by default?  
> **username_3**: Might be a good idea to reference your other question https://langdev.stackexchange.com/questions/1905/what-are-the-pros-and-cons-of-a-compiler-with-a-single-pass-parser and explain the differences between them otherwise there will be a temptation to close one as a duplicate.  
---
## 3 answers
### Answer by username_8 on 2023-07-02. Score: 31
I’m going to assume this question is about ahead-of-time compilers; JIT compilers are a different story altogether. With that in mind…

## The performance benefits of single-pass compilers are overstated

For starters, there is essentially no longer any benefit to implementing a single-pass compiler: they are a relic of an era in which memory was extraordinarily scarce, and compilers simply could not afford to fit the entire program in memory; this has not been true for 30 years. This is really a crucial point: single-pass compilers were developed to save on *memory*, not *time*. Fundamentally, they do all the same work as an equally-simple multi-pass compiler (modulo some marginal translation costs), they just run the whole pipeline on one statement or definition at a time rather than on entire compilation units.

Perhaps you feel that memory usage is nothing to sneeze at. After all, compilers—and especially optimizing compilers—can use quite a lot of memory, and though memory may be much cheaper than it once was, it’s still not free. But this is something of a red herring: compilers that do things that need lots of memory *cannot* be implemented as single-pass compilers because…

## Single-pass compilers just can’t do the job

Modern compilers have features and perform analyses that require considering much more context than a single definition at a time. At least some of these features are present in essentially all modern programming languages. Let’s consider some examples (though this list is not by any means exhaustive).

### Forward references

Forward references without separate forward declarations are almost universally supported by modern programming languages. There is essentially no reason to statically forbid forward references in general.

### Error reporting

Parse errors and typechecking failures can be made significantly more helpful if the compiler has access to the entire module when generating them. For example, suppose the user has written a correct definition, but given it the wrong type. A naïve compiler would trust the type declaration and report several type mismatches: one at the definition and another at every use site.

However, if the compiler has access to the use sites, it could note that all the uses reflect the actual type rather than the expected one. It can therefore include a suggestion in the error message that perhaps the type signature ought to be changed.

### Type inference

Different languages perform differing amounts of type inference, but some languages, like Haskell, have type inference that is quite global. In Haskell, a definition’s type is determined by both its body and *all* of its uses, so computing the type of a top-level definition may require typechecking all other definitions in the module.

GHC (the Haskell compiler) does break up modules into *declaration groups* very early in the pipeline, immediately after resolving names, based on dependency analysis between declarations (which is very cheap). This allows the definition groups to be typechecked independently, so users don’t pay a cost for this feature if they don’t use it.

### Inlining

Essentially all ahead-of-time compilers worth their salt perform some very basic optimizations, even if they don’t do enough to warrant the name “optimizing compiler”. For example, most compilers will do constant folding and constant propagation, reducing constant expressions like `5 * 2` to `10`. And once *any* optimizations are at play, a crucial part of the process is [inlining](https://en.wikipedia.org/wiki/Inline_expansion).

In order to inline a function, its body must be known to the compiler while optimizing its call site. This is naturally impossible if the compiler has already processed its code and promptly unloaded it from memory. So compilers generally want to keep the definitions of functions from the same module in memory, anyway, and many even perform cross-module inlining for sufficiently small functions, which requires keeping them in memory, too.

### Interprocedural analysis

More sophisticated optimizing compilers also perform a battery of optimizations that are explicitly *interprocedural*, which is to say they cross function boundaries. For example, a compiler might notice that a program boxes some values and passes them to a function that immediately unboxes them, in which case it could remove the unnnecessary boxing. It might also keep track of what side-effects a function performs so that it can reorder calls to it if the compiler deems that will improve performance.

These sorts of optimizations fundamentally depend on considering much more than a single function at a time. In theory, some of them could be done by analyzing each function as it is compiled and saving the results of those analyses for downstream calls (and indeed this is how some cross-module interprocedural analysis works), but even where this is possible, it would miss out on some useful optimizations. This is because these optimizers are usually *iterative*: they perform an analysis, use it to make some improvements, then analyze the program again, since the previous step might have uncovered new opportunities for further optimization. This iterative process benefits greatly from larger compilation units where more information is available.

### Common subexpression elimination

Optimizing compilers also perform [common subexpression elimination](https://en.wikipedia.org/wiki/Common_subexpression_elimination) (CSE), which essentially deduplicates code. Obviously, the more code the compiler is able to consider at once, the greater likelihood that it will find duplicate occurrences of the same thing.

## Multi-pass compilers are much easier to write

As the above examples hopefully demonstrate, modern compilers do a lot of things. They must handle complex languages with lots of features, they must detect misuses and mistakes and report them to users in a comprehensible fashion, and they must somehow translate the language into another (usually much simpler) one while preserving its semantics. Ultimately, compilers are written by humans, so they must be organized in a way that allows them to flexibly grow and evolve.

For this reason, modern compilers of general-purpose programming languages near-universally translate the program into some intermediate representation that is easier to work with. Optimizing compilers use *several* intermediate representations, each progressively lower level than the last. These intermediate representations are much smaller and more uniform languages than the ones written by humans, which dramatically cuts down on the number of cases the compiler must consider.

In theory, this approach is not incompatible with processing a single definition at a time: a compiler could each single definition through the entire pipeline before moving onto the next one. But, as alluded to in the first paragraph of this answer, this would not save anything that wouldn’t also be saved by writing a simpler compiler! Sure, it would avoid needing to store the whole compilation unit in memory at once, but even an extraordinarily inefficient AST is not going to take up much more memory to store than the text file containing its source code. The real costs come from all the work the compiler is doing.

So unless you’re either writing a compiler for an exceptionally simple language or a compiler that must, for some reason, run on embedded systems, single-pass compilers are a relic of the past. Multi-pass compilers can do much more while remaining easier to understand, easier to maintain, easier to extend, and easier to debug. They’re a nearly universal compiler technique, and for good reason.
> **Comments:**
> **username_0** (2023-07-02): Unfortunately, I think you still misunderstand. My compiler does have all of those passes. What it doesn't do is parse the file, build up a list of all declarations, and parse it again, solely to prevent the need to forward declarations.  
> **username_8** (2023-07-02): @GavinD.Howard No real compiler works by running the parser twice on the input text. Perhaps you are referring to a multi-pass *parser*, not a multi-pass *compiler*? What you’ve written sounds like a multi-pass compiler to me.  
> **username_0** (2023-07-02): I do know what a multi-pass compiler is, and yes, I'm implementing one, and yes, I mean a multi-pass parser. That's what the question text says. The question is about whether someone would implement a language like C with one parser pass. C is famously multi-pass (it requires a preprocessor pass, a parser pass and all the rest), but because it requires everything to be declared before use, it can run the parser and not do an extra resolution pass on the AST. That extra resolution pass, which may not actually use the file text is what I refer to as a second parser pass.  
> **username_8** (2023-07-02): @GavinD.Howard Okay, that makes more sense, but can you ask that as a separate question? Both answers and at least one comment interpreted your question as referring to a multi-pass compiler because that is what the question said before you edited it.  
> **username_0** (2023-07-02): I will ask a separate question, but to do that, I'm actually going to copy out this question into a separate one and rewrite this one because despite your claim, this question always referred to parsing, especially in the body.  
> **username_8** (2023-07-02): @GavinD.Howard Yes, I understand in retrospect. But I genuinely did not understand what you were talking about until after I wrote my answer (and apparently others did not either), because “single-pass compiler” means a pretty specific thing. My best guess was that you meant you were running the whole pipeline once per definition.  
> **username_9** (2023-07-03): @GavinD.Howard if you're talking about the quirks of C and C++ specifically, there's a way to parse such languages  in just one go - GLR. See Elkhound, for example. Every time there's an ambiguity you just branch and parse all possible interpretations.  
> **username_10** (2023-07-03): Since the comparison is Turbo Pascal--while it was one-pass I do not believe it wrote out the code for a method until it was done.  I managed to break the compiler with a big method (configuration file parser--one massive case statement.)  Some resource was certainly consumed over the course of a method.  
> **username_11** (2023-10-24): @LorenPechtel: It knew the address of the machine code responsible for processing each piece of machine code at the moment it was encountered.  It might have held off on writing code for a function to disk until it had applied all of the necessary back-patches, so as to avoid having to patch the file on disk after it was written, but the "Find error location" operation, given a machine code address, would only scan through the source file up to the part which would generate code at that address.  
---
### Answer by username_4 on 2023-07-03. Score: 2
When we wrote a single pass compiler, and we wanted to add more language features, the code got super convoluted, and we had this logical "cycle" where we had to so something before AND after something else. This basically halted the development of the language and a rewrite had to be done.

Things like syntax desugaring, type information, optimizations, inlining. Some of the steps mutate the program globally, instead of locally, which is really the downside of single pass compilers.

Another major drawback is that it's hard reusing code for a language server, which does not care to pass the entire codebase on each keystroke.

Modern compilers use a query system. Here's a link: <https://ollef.github.io/blog/posts/query-based-compilers.html>

I take inspiration from C# (roselyn) and rist-analyzer.
> **Comments:**
> **username_5** (2023-07-03): Do you mean `rust-analyzer`?  
---
### Answer by username_6 on 2023-07-03. Score: 1
You can't just decide that you want a single pass compiler. A single pass compiler must be able to read a compilation unit line by line, and compile it using the information it has gathered so far, and nothing else. Pascal was a language that could easily be processed that way.

Now if you have a language like Swift, you have absolutely zero chance to compile that with a one pass compiler, so there are no pro's and con's to discuss at all. For example, you need to parse all files, especially the standard library files, for "operator" declarations to even know that + - \* / are operators, and whether they are left or right associative or neither, and what their precedence is, and without that you cannot even compile 1 + 2 \* 3 because you don't even know whether it is (1 + 2) \* 3 or 1 + (2 \* 3) or whether it is an error because there are no binary operators + or \*.

Personally, I would use a multi-pass compiler even for a language like Pascal today, where you can calmly collect information from your source files, find out things about the program structure, find out more things, after some time figure out what code you want to produce, apply simplifications and optimisations to that code and so on, and finally generate code. Note that modern multi-pass compilers will also store information from the compilation process along with the source code, so if you change one of 50 functions in a source file, there is a good chance that 49 of the functions require very little work, and only the changed one actually requires the full work.
> **Comments:**
> **username_7** (2023-07-16): Since this site is "Programming Language Design and Implementation", should you not assume that "What are the pros and cons of single-pass compilers?" is asked in that context?  So then, can we assume that if having a single-pass compiler is important, then the question asker will design (or inherit from) a language (like Pascal) that facilitates making a single-pass compiler? Especially for the "critical code" he wants to produce?  
---
