<p>Assume you are tasked with writing a compiler for a language that <em>can</em> be parsed in a single pass, like C, but does not necessarily <em>have to be</em>. What are the pros and cons for doing this? Would you do this in a compiler for a language meant to be used <em>in production</em>, or would you make the parser multi-pass? Why?</p>
<p><strong>To clarify</strong>: what I mean by &quot;single pass&quot; is <em>not</em> to smash the usual passes (parsing, type-checking, optimization, and code gen) together into one mess. That question is <a href="https://langdev.stackexchange.com/q/1899/134">here</a>.</p>
<p>What I mean is a language where the <em>parser</em> can be a single pass, and no extra name resolution pass is needed, because forward declarations are required.</p>
<p>(Yes, I know, the name resolution pass probably wouldn't be implemented by the parser.)</p>
<p>Also, I consider the lexer and parser to be one pass together in this context.</p>
<p>In addition, by &quot;in production,&quot; I mean for a compiler that companies might use in critical code, including safety-critical code. While I am doing this in my spare time, I still don't want to do this halfway.</p>
<p>Note: This question was inspired by <a href="https://langdev.stackexchange.com/questions/915/how-would-you-design-a-compiler-upfront-to-be-both-a-compiler-and-a-lsp-server#comment2838_925">an exchange</a> I had with <a href="https://langdev.stackexchange.com/users/861/alexis-king">@AlexisKing</a>, but I have made the question more general because <strong>I also want other people to chime in</strong> about this fascinating subtopic of compiler design.</p>

<compilers><implementation><parsing>
What are the pros and cons of a compiler with a single-pass parser?
CC BY-SA 4.0
2023-07-02T22:06:33.320Z
Correct me if I'm wrong, but most parsers are single-pass, unless you count lexing as a separate stage. Some parsers might have to backtrack, in which case you might say they aren't single-pass. But name resolution (the kind of thing you need forward declarations for) isn't part of parsing.
kaya3
CC BY-SA 4.0
2023-07-02T22:08:06.650Z
@kaya3-supportthestrike I'll clarify that I mean something without a resolution pass. This is just the wording that was (accidentally) hashed out with Alexis King.
Gavin D. Howard
CC BY-SA 4.0
2023-07-02T22:10:03.737Z
I'm responding to this: *"What I mean is a language where the parser can be a single pass because forward declarations are required."*. I don't see how requiring forward declarations could matter to whether the parser is single-pass, since forward declarations are needed for things that happen after parsing. (Except in the very specific case of parsing C, which parses differently based on semantic information about names.)
kaya3
CC BY-SA 4.0
2023-07-02T22:10:56.343Z
@GavinD.Howard I think the question was good as-written, prior to your edit, though I think the “unnecessary background” is (unsurprisingly) unnecessary and doesn’t add much to the question. But if your question is *specifically about* having a separate name-resolution pass, then I agree that it would be good to say that explicitly rather than talk about “single- versus multi-pass parsers” at all (which is much broader).
Alexis King
CC BY-SA 4.0
2023-07-02T22:12:21.933Z
@AlexisKing I'm okay with the broader question too. After all, these questions are meant to be useful to more than just one person.
Gavin D. Howard
CC BY-SA 4.0
2023-07-02T22:33:09.337Z
I think I understand the question better after the edit. Would it be fair to summarise this as: "what are the pros and cons of doing name resolution in the same pass as the parser"? There is potential overlap with [this question](https://langdev.stackexchange.com/q/153/89) but I don't think it's a duplicate.
kaya3
CC BY-SA 4.0
2023-07-02T22:43:03.930Z
@kaya3-supportthestrike I think that's a good summary. I also don't think this is a duplicate because this is an *implementation* question while the other is a *design* question.
Gavin D. Howard
CC BY-SA 4.0
2023-07-13T19:03:30.583Z
Are you intending to use Yao to produce C that is destined for Web Assembly? Or is it microcontrollers? What is the deployment environment?
MicroservicesOnDDD
CC BY-SA 4.0
2023-07-14T03:46:39.747Z
@MicroservicesOnDDD all of the above. I want my software to meet the DO-178C standard, but I also want it to be usable by anyone on just about anything.
Gavin D. Howard
<p>A long time ago when computers didn't have massive amounts of memory and very fast SSDs, data was stored on punch cards and tape. While doing multiple passes over the data stored in those storage media was possible, it was definitely very slow. By ensuring the programming language could be parsed in a single pass, you'd have greatly optimized the speed of the compiler.</p>
<p>You make a point about just the parser being single-pass. You can view the parser as a stage in a pipeline. If each stage is single-pass, then you don't have to store all of the intermediate results. For example, if you had separate programs to tokenenize, parse, compile and assemble, then you could write it like so on a UNIX command line:</p>
<pre><code>cat program.c | tokenize | parse | compile | assemble &gt; program.o
</code></pre>
<p>Each pipe between commands is just a small buffer. This saves storage space (which was expensive and slow), and at the same time allows for parallelism.</p>
<p>(Apologies for the useless-use-of-cat.)</p>

CC BY-SA 4.0
2023-07-12T12:06:11.210Z
2023-07-12T12:13:48.110Z
2023-07-12T12:13:48.110Z
G. Sliepen
CC BY-SA 4.0
2023-07-12T13:20:38.753Z
Upvoted for style and for useless-use-of-cat.
Gavin D. Howard
CC BY-SA 4.0
2024-11-26T22:15:54.547Z
Ironically, the first FORTRAN compiler subjected program code to more than a dozen processing stages, which transformed its in-memory representation in a variety of ways.  This required that any information about the source code that was going to be used by any downstream stage would need to be kept in memory by all upstream stages, but meant that the code for the different compiler stages could be loaded into memory separately.
supercat
<p>Con: You have to design for very lightweight split-declaration to support co-referential definitions.</p>
<p>If you've got definitions of co-recursive functions or co-referencing types, then there's no declaration order that allows all uses of a name to follow the declaration.</p>
<pre><code>fn isOdd (x: Int): Bool { return x != 0 &amp;&amp; isEven(x - sign(x)) }
fn isEven(x: Int): Bool { return x == 0 || isOdd (x - sign(x)) }
// Each function uses the other.
</code></pre>
<p>Since uses of the other function typically occur within the body, you could allow for separating the function signature from the body.</p>
<pre><code>// Declarations
fn isOdd:  Int -&gt; Bool;
fn isEven: Int -&gt; Bool;
// Definitions
isOdd (x) does { return ... }
isEven(x) does { return ... }
</code></pre>
<p>That way you don't have duplicative definitions which a programmer has to keep in sync.</p>
<p>But that approach doesn't work as well for co-referencing type definitions.  Consider two types that each may embed an instance of the other.</p>
<pre><code>// A ZebraList is like a ConsList except that its
// elements are striped.
class WhiteStripe&lt;T&gt; {
  head: T;
  tail: BlackStripe&lt;T&gt; | Nil;
}
class BlackStripe&lt;T&gt; {
  head: T;
  tail: WhiteStripe&lt;T&gt; | Nil;
}
</code></pre>
<p>You can predeclare that WhiteStripe and BlackStripe are type definitions.
That's sufficient to resolve the C ambiguity.</p>
<pre><code>#ifdef FOO
typedef struct {} T;
# else
int T = 3;
#endif

T * x;  // pointer variable definition ifdef FOO else multiplication
</code></pre>
<p>But there's not a lot of substantial signature information that you can pull entirely out of a type definition.</p>
<p>Even type parameters cannot be pulled out.  Generic types can be surprisingly self-referential: <code>Comparable&lt;T extends Comparable&lt;T&gt;&gt;</code> and I can imagine co-reference via type parameters.</p>
<pre><code>// Each node points at its graph.
class AbstractGraph&lt;NODE_TYPE extends Node&lt;AbstractGraph&lt;NODE_TYPE&gt;&gt; { ... }
class Node&lt;GRAPH_TYPE extends AbstractGraph&lt;Node&lt;GRAPH_TYPE&gt;&gt;&gt; { ... }
</code></pre>

CC BY-SA 4.0
2023-07-05T16:39:46.897Z
2023-07-05T16:39:46.897Z
Mike Samuel
CC BY-SA 4.0
2024-11-26T22:22:24.743Z
It's not possible for two types to hold actual instances of each other.  If types merely hold pointers or references to each other, that poses no problem in C.  A compiler can let code work with type `struct foo*` without having to care about where if anywhere  `struct foo` is defined, unless or until code would declare an object of, produce an lvalue of,  or invoke `sizeof` upon, the actual type `struct foo`.
supercat
<p>In order to have actual pro's for single pass compilers, you'd need to provide a definition of what a compiler really is. If a compiler has optimization and code generation phases, you simply can't provide a competitive product with adequate cost. Simply, because the only way to get it to be a &quot;single pass&quot; is by pushing unevaluated lambdas through your parse tree. Humans aren't good at that.</p>
<p>So, here's a list of cons, i.e. points in favor of an architecture with multiple passes and phases:</p>
<p>Deterministic serializable and mostly generated AST generation saves a lot of time when it comes to debugging and maintaining the compiler. This causes AST generation to be a distinct pass.</p>
<p>Deterministic serializable and separate passes for semantic analysis and code generation can save a lot of time spent on debugging and maintaining the compiler.</p>
<p>Code optimizations are usually multiple passes.</p>
<p>Code analysis for errors and warnings are usually multiple passes. High-quality warnings often require an analysis at the end semantic analysis which would be another pass at least in the pass concept I know.</p>
<p>The language needs to support such compiler architecture and it does not make sense to do so, because it reduces expressiveness or requires programmers to do pointless manual work like forward declarations or checking ODR violations themselves.</p>
<p>Note: If this discussion is input for a lecture or something similar, you should also discuss if the linker is part of the compiler. Some of the stages are fundamentally link time passes. It is even more interesting, if you have a JIT or similar. If you think about it, you'll notice that one gets competitive results by moving passes to non-observed components which isn't necessarily a good choice in practice.</p>

CC BY-SA 4.0
2023-07-12T07:46:43.383Z
2023-07-12T07:46:43.383Z
feldentm
<p>Alternative: single-passiness-ish via redundant grammatical constructs</p>
<p>Java manages to almost resolve names early despite some odd properties of its frontend but it does that via <em>cover grammars</em>: by adding extra AST types to suspend decisions.</p>
<p>In Java</p>
<pre><code> package com.example;
 class C extends D {
   Foo x;
 }
</code></pre>
<p>To resolve <code>Foo</code>, Java has to:</p>
<ol>
<li>Resolve super-types (<code>D</code>) and look for non-private nested types (<code>D.Foo</code>), or if that's not found</li>
<li>Resolve in the same package by looking for a file <code>com/example/Foo.java</code> relative to the source path or <code>com/example/Foo.class</code> relative to the class path, or if that's not found</li>
<li>Resolve in the empty package by looking for a file <code>Foo.java</code> relative to the source path, or a file <code>Foo.class</code> relative to the class path.</li>
</ol>
<p>But to be able to answer question (1) for <code>Foo</code>, we need to have parsed the file defining <em>D</em> and resolved its (raw) super-types and identified its nested types.</p>
<p>If there are <code>import</code> statements, the story gets even more complicated.</p>
<p>Java handles this complicated dance by using <em>cover grammars</em> to parse each file to an AST, single pass, and then rewriting the AST to convert <a href="https://docs.oracle.com/javase/specs/jls/se8/html/jls-6.html#jls-6.5" rel="nofollow noreferrer">AST nodes like <em>PackageOrTypeName</em></a> to more specific node types.</p>
<p>So there's a spectrum of choices in single pass compilers that lets you resolve names early, but it means having to represent ambiguous names explicitly in the AST.</p>

CC BY-SA 4.0
2023-07-05T17:04:35.237Z
2023-07-05T17:04:35.237Z
Mike Samuel
CC BY-SA 4.0
2023-07-12T07:51:18.317Z
This is just the AST-variant of an unevaluated lambda.
feldentm
CC BY-SA 4.0
2023-07-13T17:02:48.240Z
@feldentm Cover grammars are a useful trick but, unlike thunking, they do mean that you need to have two AST definitions, one with and one without, if you want post resolution passes to not have to include useless cases for AST node types they shouldn't encounter.
Mike Samuel
CC BY-SA 4.0
2023-07-13T19:50:22.057Z
Agreed. They are the same approach on a very high level, but have different implications on low level. Also, I wouldn't restrict the concept of unevaluated lambdas to the functional domain despite that being its origin and the easiest way to implement them.
feldentm
<h2>What constitutes a single-pass parser?</h2>
<p>Where you draw the line is somewhat arbitrary. Most programming languages tokenize their input and then parse the token stream; arguably this is already a multi-pass parser. More generally, the line where parsing ends and everything else begins is often difficult to draw in many compilers. They often massage the AST in various ways as it percolates through the frontend—to resolve names and parse import-dependent structure, for example—and it’s not always clear which of these are parsing and which of them are something more:</p>
<ul>
<li><p>Your question mentions name resolution, and I think it’s quite reasonable to consider name resolution an extension of parsing. Really, a program is a graph, not a tree, and resolving the names is the last step in parsing that graph. But plenty of people would say it is not part of parsing.</p>
</li>
<li><p>The grammar of C is famously context-sensitive. Rather than actually keep track of all that context, lots of C parsers choose to just parse the ambiguous productions in a generic, context-free way, then sort them out afterwards.</p>
</li>
<li><p>In Haskell, the grammar of expressions, types, and patterns has many overlapping cases, and sorting out which is which ahead of time is quite challenging. So GHC just parses all of them into one common datatype that contains the union of all the expression, type, and pattern productions, then uses a second pass to restrict the parsed terms as appropriate.</p>
</li>
<li><p>In Lisps, the program is “read” as an s-expression, but this doesn’t actually parse very much structure. The process of macroexpansion is essentially what actually parses the loose tree of tokens into the AST (abstract syntax tree), so in a sense, parsing involves arbitrarily many passes!</p>
</li>
</ul>
<p>There are many more examples, but these are a few. Which of these constitute multi-pass parsing and which don’t is a matter of debate. But let’s assume for the sake of argument that we’re willing to call all of these multi-pass parsers.</p>
<h2>Sometimes multi-pass parsing is necessary</h2>
<p>In some of the above cases, multiple passes are really not optional: there’s no way to parse a Lisp program without expanding it. This suggests one potential cop-out answer, “Parse using as many passes as you need, but no more,” in which case there is no choice and thus no pros or cons.</p>
<p>Of course, there <em>is</em> technically one alternative, namely somehow altering the language to make it possible to parse in a single pass. But given the somewhat nebulous benefits of single-pass parsers (you don’t gain much aside from a modicum of performance, and parsing is almost always the cheapest part of an AOT compiler), this seems like probably the wrong reason to change the design of a language.</p>
<h2>The costs and benefits are a bit of a wash</h2>
<p>Let’s therefore restrict ourselves to consider the cases where it <em>is</em> optional, like in the case of C and Haskell—both <em>can</em> be implemented in a single pass with sufficient context or lookahead. In those cases, I think the pros and cons are roughly as follows:</p>
<ul>
<li><p><strong>Implementation simplicity: multi-pass parsers win.</strong> Multi-pass parsers are often a matter of separation of concerns. It’s easier to focus on the simplest parsing task first, then hash out the complicated things afterwards.</p>
</li>
<li><p><strong>Error messages: no clear winner.</strong> Sometimes a multi-pass parser can actually produce <em>better</em> errors than a single-pass one because more information is available when reporting an error in a later pass. However, in other cases, deferring the error until later may result in the parse failing somewhere else in the first pass, which might be unhelpful. Which is better really depends on the details.</p>
</li>
<li><p><strong>Efficiency: no clear winner.</strong> Sometimes a multi-pass parser can avoid needing to do inefficient lookahead and backtracking, in which case it can provide better performance than a single-pass equivalent. However, in other cases, there might be a single-pass strategy that doesn’t need lookahead, in which case the multi-pass strategy pays for additionally traversing the parse tree.</p>
</li>
<li><p><strong>Mechanized reference: single-pass parsers win.</strong> One advantage of single-pass parsers—<em>if</em> you’re using a parser generator—is that they serve as a complete, mechanized specification of the language’s grammar. This is almost certainly not the case for most multi-pass parsing schemes.</p>
</li>
</ul>
<p>Really, the tradeoffs are pretty specific to the grammar you’re trying to parse and the way you choose to architect your compiler. Picking one over the other doesn’t preclude you from anything, so it’s all just a matter of implementation technique.</p>

CC BY-SA 4.0
2023-07-02T23:11:38.200Z
2023-07-12T05:32:43.300Z
2023-07-12T05:32:43.300Z
Alexis King
CC BY-SA 4.0
2023-07-05T16:06:11.413Z
Apologies if this is nitpicky, re "there’s no way to parse a Lisp program without expanding it" wouldn't a staged compiler provide a way to get the benefits of Lisp-style meta-programming while still allowing the parser to be single-stage?  Lisp macros can introduce variable declarations, so the distinction between lvalues and rvalues isn't apparent during parsing, but if that problem were solved, perhaps by requiring names destined for declaration to be marked as such, could you have the parser symbolize names.
Mike Samuel
CC BY-SA 4.0
2023-07-05T16:10:52.823Z
@MikeSamuel Sure, it’s possible. See, for example, [Inferring scope through syntactic sugar](https://dl.acm.org/doi/abs/10.1145/3110288). But such systems are usually quite restrictive, so I know of no real implementations that mandate them.
Alexis King
CC BY-SA 4.0
2023-07-05T16:48:54.857Z
Thanks for the pointer.  Looks like that may have value re macro hygiene and maybe have nice knock-on effects for things like simplifying IDE go-to-definition affordances but probably overkill if your goal is quick name resolution.
Mike Samuel
CC BY-SA 4.0
2024-11-26T22:25:32.043Z
Some old single-pass parsers could map machine-code locations to source-code constructs more accurately than modern ones, even without needing to produce any "debug" information.  If Turbo Pascal 2.0 and 3.0 encountered a run-time error, it would output an address.  Typing that address into the IDE would result in the compiler triggering an error at the location in the source code that produced the offending executable code.
supercat
CC BY-SA 4.0
2024-12-05T14:58:45.970Z
@supercat That is much easier to do if the compiler is much less sophisticated and therefore does far less rearranging of code!
Alexis King
CC BY-SA 4.0
2024-12-05T15:36:21.037Z
@AlexisKing: It only works if output code addresses are assigned while the source code is being scanned, but it avoids the need for generating metadata and maintaining it through the build chain.
supercat
# What are the pros and cons of a compiler with a single-pass parser?
Posted by: username_0 on 2023-07-02
Assume you are tasked with writing a compiler for a language that *can* be parsed in a single pass, like C, but does not necessarily *have to be*. What are the pros and cons for doing this? Would you do this in a compiler for a language meant to be used *in production*, or would you make the parser multi-pass? Why?

**To clarify**: what I mean by "single pass" is *not* to smash the usual passes (parsing, type-checking, optimization, and code gen) together into one mess. That question is [here](https://langdev.stackexchange.com/q/1899/134).

What I mean is a language where the *parser* can be a single pass, and no extra name resolution pass is needed, because forward declarations are required.

(Yes, I know, the name resolution pass probably wouldn't be implemented by the parser.)

Also, I consider the lexer and parser to be one pass together in this context.

In addition, by "in production," I mean for a compiler that companies might use in critical code, including safety-critical code. While I am doing this in my spare time, I still don't want to do this halfway.

Note: This question was inspired by [an exchange](https://langdev.stackexchange.com/questions/915/how-would-you-design-a-compiler-upfront-to-be-both-a-compiler-and-a-lsp-server#comment2838_925) I had with [@AlexisKing](https://langdev.stackexchange.com/users/861/alexis-king), but I have made the question more general because **I also want other people to chime in** about this fascinating subtopic of compiler design.
**Tags:** compilers implementation parsing
> **Comments:**
> **username_1**: Correct me if I'm wrong, but most parsers are single-pass, unless you count lexing as a separate stage. Some parsers might have to backtrack, in which case you might say they aren't single-pass. But name resolution (the kind of thing you need forward declarations for) isn't part of parsing.  
> **username_0**: @kaya3-supportthestrike I'll clarify that I mean something without a resolution pass. This is just the wording that was (accidentally) hashed out with Alexis King.  
> **username_1**: I'm responding to this: *"What I mean is a language where the parser can be a single pass because forward declarations are required."*. I don't see how requiring forward declarations could matter to whether the parser is single-pass, since forward declarations are needed for things that happen after parsing. (Except in the very specific case of parsing C, which parses differently based on semantic information about names.)  
> **username_2**: @GavinD.Howard I think the question was good as-written, prior to your edit, though I think the “unnecessary background” is (unsurprisingly) unnecessary and doesn’t add much to the question. But if your question is *specifically about* having a separate name-resolution pass, then I agree that it would be good to say that explicitly rather than talk about “single- versus multi-pass parsers” at all (which is much broader).  
> **username_0**: @AlexisKing I'm okay with the broader question too. After all, these questions are meant to be useful to more than just one person.  
> **username_1**: I think I understand the question better after the edit. Would it be fair to summarise this as: "what are the pros and cons of doing name resolution in the same pass as the parser"? There is potential overlap with [this question](https://langdev.stackexchange.com/q/153/89) but I don't think it's a duplicate.  
> **username_0**: @kaya3-supportthestrike I think that's a good summary. I also don't think this is a duplicate because this is an *implementation* question while the other is a *design* question.  
> **username_3**: Are you intending to use Yao to produce C that is destined for Web Assembly? Or is it microcontrollers? What is the deployment environment?  
> **username_0**: @MicroservicesOnDDD all of the above. I want my software to meet the DO-178C standard, but I also want it to be usable by anyone on just about anything.  
---
## 5 answers
### Answer by username_2 on 2023-07-02. Score: 15 | Accepted answer
## What constitutes a single-pass parser?

Where you draw the line is somewhat arbitrary. Most programming languages tokenize their input and then parse the token stream; arguably this is already a multi-pass parser. More generally, the line where parsing ends and everything else begins is often difficult to draw in many compilers. They often massage the AST in various ways as it percolates through the frontend—to resolve names and parse import-dependent structure, for example—and it’s not always clear which of these are parsing and which of them are something more:

* Your question mentions name resolution, and I think it’s quite reasonable to consider name resolution an extension of parsing. Really, a program is a graph, not a tree, and resolving the names is the last step in parsing that graph. But plenty of people would say it is not part of parsing.
* The grammar of C is famously context-sensitive. Rather than actually keep track of all that context, lots of C parsers choose to just parse the ambiguous productions in a generic, context-free way, then sort them out afterwards.
* In Haskell, the grammar of expressions, types, and patterns has many overlapping cases, and sorting out which is which ahead of time is quite challenging. So GHC just parses all of them into one common datatype that contains the union of all the expression, type, and pattern productions, then uses a second pass to restrict the parsed terms as appropriate.
* In Lisps, the program is “read” as an s-expression, but this doesn’t actually parse very much structure. The process of macroexpansion is essentially what actually parses the loose tree of tokens into the AST (abstract syntax tree), so in a sense, parsing involves arbitrarily many passes!

There are many more examples, but these are a few. Which of these constitute multi-pass parsing and which don’t is a matter of debate. But let’s assume for the sake of argument that we’re willing to call all of these multi-pass parsers.

## Sometimes multi-pass parsing is necessary

In some of the above cases, multiple passes are really not optional: there’s no way to parse a Lisp program without expanding it. This suggests one potential cop-out answer, “Parse using as many passes as you need, but no more,” in which case there is no choice and thus no pros or cons.

Of course, there *is* technically one alternative, namely somehow altering the language to make it possible to parse in a single pass. But given the somewhat nebulous benefits of single-pass parsers (you don’t gain much aside from a modicum of performance, and parsing is almost always the cheapest part of an AOT compiler), this seems like probably the wrong reason to change the design of a language.

## The costs and benefits are a bit of a wash

Let’s therefore restrict ourselves to consider the cases where it *is* optional, like in the case of C and Haskell—both *can* be implemented in a single pass with sufficient context or lookahead. In those cases, I think the pros and cons are roughly as follows:

* **Implementation simplicity: multi-pass parsers win.** Multi-pass parsers are often a matter of separation of concerns. It’s easier to focus on the simplest parsing task first, then hash out the complicated things afterwards.
* **Error messages: no clear winner.** Sometimes a multi-pass parser can actually produce *better* errors than a single-pass one because more information is available when reporting an error in a later pass. However, in other cases, deferring the error until later may result in the parse failing somewhere else in the first pass, which might be unhelpful. Which is better really depends on the details.
* **Efficiency: no clear winner.** Sometimes a multi-pass parser can avoid needing to do inefficient lookahead and backtracking, in which case it can provide better performance than a single-pass equivalent. However, in other cases, there might be a single-pass strategy that doesn’t need lookahead, in which case the multi-pass strategy pays for additionally traversing the parse tree.
* **Mechanized reference: single-pass parsers win.** One advantage of single-pass parsers—*if* you’re using a parser generator—is that they serve as a complete, mechanized specification of the language’s grammar. This is almost certainly not the case for most multi-pass parsing schemes.

Really, the tradeoffs are pretty specific to the grammar you’re trying to parse and the way you choose to architect your compiler. Picking one over the other doesn’t preclude you from anything, so it’s all just a matter of implementation technique.
> **Comments:**
> **username_6** (2023-07-05): Apologies if this is nitpicky, re "there’s no way to parse a Lisp program without expanding it" wouldn't a staged compiler provide a way to get the benefits of Lisp-style meta-programming while still allowing the parser to be single-stage?  Lisp macros can introduce variable declarations, so the distinction between lvalues and rvalues isn't apparent during parsing, but if that problem were solved, perhaps by requiring names destined for declaration to be marked as such, could you have the parser symbolize names.  
> **username_2** (2023-07-05): @MikeSamuel Sure, it’s possible. See, for example, [Inferring scope through syntactic sugar](https://dl.acm.org/doi/abs/10.1145/3110288). But such systems are usually quite restrictive, so I know of no real implementations that mandate them.  
> **username_6** (2023-07-05): Thanks for the pointer.  Looks like that may have value re macro hygiene and maybe have nice knock-on effects for things like simplifying IDE go-to-definition affordances but probably overkill if your goal is quick name resolution.  
> **username_5** (2024-11-26): Some old single-pass parsers could map machine-code locations to source-code constructs more accurately than modern ones, even without needing to produce any "debug" information.  If Turbo Pascal 2.0 and 3.0 encountered a run-time error, it would output an address.  Typing that address into the IDE would result in the compiler triggering an error at the location in the source code that produced the offending executable code.  
> **username_2** (2024-12-05): @supercat That is much easier to do if the compiler is much less sophisticated and therefore does far less rearranging of code!  
> **username_5** (2024-12-05): @AlexisKing: It only works if output code addresses are assigned while the source code is being scanned, but it avoids the need for generating metadata and maintaining it through the build chain.  
---
### Answer by username_4 on 2023-07-12. Score: 3
A long time ago when computers didn't have massive amounts of memory and very fast SSDs, data was stored on punch cards and tape. While doing multiple passes over the data stored in those storage media was possible, it was definitely very slow. By ensuring the programming language could be parsed in a single pass, you'd have greatly optimized the speed of the compiler.
You make a point about just the parser being single-pass. You can view the parser as a stage in a pipeline. If each stage is single-pass, then you don't have to store all of the intermediate results. For example, if you had separate programs to tokenenize, parse, compile and assemble, then you could write it like so on a UNIX command line:
cat program.c | tokenize | parse | compile | assemble > program.o

Each pipe between commands is just a small buffer. This saves storage space (which was expensive and slow), and at the same time allows for parallelism.
(Apologies for the useless-use-of-cat.)
> **Comments:**
> **username_0** (2023-07-12): Upvoted for style and for useless-use-of-cat.  
> **username_5** (2024-11-26): Ironically, the first FORTRAN compiler subjected program code to more than a dozen processing stages, which transformed its in-memory representation in a variety of ways.  This required that any information about the source code that was going to be used by any downstream stage would need to be kept in memory by all upstream stages, but meant that the code for the different compiler stages could be loaded into memory separately.  
---
### Answer by username_6 on 2023-07-05. Score: 3
Alternative: single-passiness-ish via redundant grammatical constructs
Java manages to almost resolve names early despite some odd properties of its frontend but it does that via cover grammars: by adding extra AST types to suspend decisions.
In Java
 package com.example;
 class C extends D {
   Foo x;
 }

To resolve Foo, Java has to:

Resolve super-types (D) and look for non-private nested types (D.Foo), or if that's not found
Resolve in the same package by looking for a file com/example/Foo.java relative to the source path or com/example/Foo.class relative to the class path, or if that's not found
Resolve in the empty package by looking for a file Foo.java relative to the source path, or a file Foo.class relative to the class path.

But to be able to answer question (1) for Foo, we need to have parsed the file defining D and resolved its (raw) super-types and identified its nested types.
If there are import statements, the story gets even more complicated.
Java handles this complicated dance by using cover grammars to parse each file to an AST, single pass, and then rewriting the AST to convert AST nodes like PackageOrTypeName to more specific node types.
So there's a spectrum of choices in single pass compilers that lets you resolve names early, but it means having to represent ambiguous names explicitly in the AST.
> **Comments:**
> **username_7** (2023-07-12): This is just the AST-variant of an unevaluated lambda.  
> **username_6** (2023-07-13): @feldentm Cover grammars are a useful trick but, unlike thunking, they do mean that you need to have two AST definitions, one with and one without, if you want post resolution passes to not have to include useless cases for AST node types they shouldn't encounter.  
> **username_7** (2023-07-13): Agreed. They are the same approach on a very high level, but have different implications on low level. Also, I wouldn't restrict the concept of unevaluated lambdas to the functional domain despite that being its origin and the easiest way to implement them.  
---
### Answer by username_6 on 2023-07-05. Score: 2
Con: You have to design for very lightweight split-declaration to support co-referential definitions.
If you've got definitions of co-recursive functions or co-referencing types, then there's no declaration order that allows all uses of a name to follow the declaration.
fn isOdd (x: Int): Bool { return x != 0 && isEven(x - sign(x)) }
fn isEven(x: Int): Bool { return x == 0 || isOdd (x - sign(x)) }
// Each function uses the other.

Since uses of the other function typically occur within the body, you could allow for separating the function signature from the body.
// Declarations
fn isOdd:  Int -> Bool;
fn isEven: Int -> Bool;
// Definitions
isOdd (x) does { return ... }
isEven(x) does { return ... }

That way you don't have duplicative definitions which a programmer has to keep in sync.
But that approach doesn't work as well for co-referencing type definitions.  Consider two types that each may embed an instance of the other.
// A ZebraList is like a ConsList except that its
// elements are striped.
class WhiteStripe {
  head: T;
  tail: BlackStripe | Nil;
}
class BlackStripe {
  head: T;
  tail: WhiteStripe | Nil;
}

You can predeclare that WhiteStripe and BlackStripe are type definitions.
That's sufficient to resolve the C ambiguity.
#ifdef FOO
typedef struct {} T;
# else
int T = 3;
#endif

T * x;  // pointer variable definition ifdef FOO else multiplication

But there's not a lot of substantial signature information that you can pull entirely out of a type definition.
Even type parameters cannot be pulled out.  Generic types can be surprisingly self-referential: Comparable> and I can imagine co-reference via type parameters.
// Each node points at its graph.
class AbstractGraph> { ... }
class Node>> { ... }
> **Comments:**
> **username_5** (2024-11-26): It's not possible for two types to hold actual instances of each other.  If types merely hold pointers or references to each other, that poses no problem in C.  A compiler can let code work with type `struct foo*` without having to care about where if anywhere  `struct foo` is defined, unless or until code would declare an object of, produce an lvalue of,  or invoke `sizeof` upon, the actual type `struct foo`.  
---
### Answer by username_7 on 2023-07-12. Score: 2
In order to have actual pro's for single pass compilers, you'd need to provide a definition of what a compiler really is. If a compiler has optimization and code generation phases, you simply can't provide a competitive product with adequate cost. Simply, because the only way to get it to be a "single pass" is by pushing unevaluated lambdas through your parse tree. Humans aren't good at that.

So, here's a list of cons, i.e. points in favor of an architecture with multiple passes and phases:

Deterministic serializable and mostly generated AST generation saves a lot of time when it comes to debugging and maintaining the compiler. This causes AST generation to be a distinct pass.

Deterministic serializable and separate passes for semantic analysis and code generation can save a lot of time spent on debugging and maintaining the compiler.

Code optimizations are usually multiple passes.

Code analysis for errors and warnings are usually multiple passes. High-quality warnings often require an analysis at the end semantic analysis which would be another pass at least in the pass concept I know.

The language needs to support such compiler architecture and it does not make sense to do so, because it reduces expressiveness or requires programmers to do pointless manual work like forward declarations or checking ODR violations themselves.

Note: If this discussion is input for a lecture or something similar, you should also discuss if the linker is part of the compiler. Some of the stages are fundamentally link time passes. It is even more interesting, if you have a JIT or similar. If you think about it, you'll notice that one gets competitive results by moving passes to non-observed components which isn't necessarily a good choice in practice.
---
