11
$\begingroup$

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.

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 I had with @AlexisKing, but I have made the question more general because I also want other people to chime in about this fascinating subtopic of compiler design.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – kaya3
    Jul 2, 2023 at 22:06
  • $\begingroup$ @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. $\endgroup$ Jul 2, 2023 at 22:08
  • $\begingroup$ 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.) $\endgroup$
    – kaya3
    Jul 2, 2023 at 22:10
  • 1
    $\begingroup$ @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). $\endgroup$
    – Alexis King
    Jul 2, 2023 at 22:10
  • $\begingroup$ @AlexisKing I'm okay with the broader question too. After all, these questions are meant to be useful to more than just one person. $\endgroup$ Jul 2, 2023 at 22:12

5 Answers 5

15
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jul 5, 2023 at 16:06
  • 1
    $\begingroup$ @MikeSamuel Sure, it’s possible. See, for example, Inferring scope through syntactic sugar. But such systems are usually quite restrictive, so I know of no real implementations that mandate them. $\endgroup$
    – Alexis King
    Jul 5, 2023 at 16:10
  • $\begingroup$ 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. $\endgroup$ Jul 5, 2023 at 16:48
3
$\begingroup$

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:

  1. Resolve super-types (D) and look for non-private nested types (D.Foo), or if that's not found
  2. 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
  3. 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.

$\endgroup$
3
  • $\begingroup$ This is just the AST-variant of an unevaluated lambda. $\endgroup$
    – feldentm
    Jul 12, 2023 at 7:51
  • $\begingroup$ @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. $\endgroup$ Jul 13, 2023 at 17:02
  • $\begingroup$ 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. $\endgroup$
    – feldentm
    Jul 13, 2023 at 19:50
3
$\begingroup$

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.)

$\endgroup$
1
  • 1
    $\begingroup$ Upvoted for style and for useless-use-of-cat. $\endgroup$ Jul 12, 2023 at 13:20
2
$\begingroup$

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<T> {
  head: T;
  tail: BlackStripe<T> | Nil;
}
class BlackStripe<T> {
  head: T;
  tail: WhiteStripe<T> | 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<T extends Comparable<T>> and I can imagine co-reference via type parameters.

// Each node points at its graph.
class AbstractGraph<NODE_TYPE extends Node<AbstractGraph<NODE_TYPE>> { ... }
class Node<GRAPH_TYPE extends AbstractGraph<Node<GRAPH_TYPE>>> { ... }
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .