<p>Why do many typical parsers need to have two stages: <strong>tokenization</strong> and <strong>parsing</strong>?</p>
<p>This isn't just a helping hand for manually-constructed parsers, as even generation tools do the same. For example, the common parser generator <em>bison</em> is often used in combination with <em>flex</em> for tokenization, while ANTLR has <em>lexer mode</em> and <em>parser mode</em>.</p>
<p>I felt some shortcomings during use:</p>
<ul>
<li><code>KEYWORD</code>s cannot be used as <code>IDENTIFIER</code>s</li>
<li>Difficult to parse <code>List&lt;List&lt;T&gt;&gt;</code>, because <code>&gt;&gt;</code> is <code>SHIFT_RIGHT</code>.</li>
</ul>
<p>Single-stage parsers such as parser combinators and parsing expression grammar do not have this disadvantage.</p>
<p>The advantages are</p>
<ul>
<li>We can add virtual tokens, such as <code>INDENT</code>, <code>DEDENT</code></li>
</ul>
<hr />
<p>I looked at the main implementations of most major programming languages, and they all use two-stage parsing.</p>
<p>Are there any huge advantages to splitting into two stages?</p>

<parsing>
Why do we need to divide lexing and parsing stages
CC BY-SA 4.0
2024-03-28T15:09:19.787Z
For my language my lexer only separates numbers and identifiers, and whitespace. All symbols are left unchanged since too many symbols are context dependent
mousetail 'he-him'
CC BY-SA 4.0
2024-03-28T19:10:46.107Z
Is this about parser *generators* or just about two-phase parsers generally?
Michael Homer
CC BY-SA 4.0
2024-03-28T19:54:09.553Z
You don't *need* to separate them, it just usually makes the design easier.
Barmar
CC BY-SA 4.0
2024-03-28T21:20:04.337Z
https://tratt.net/laurie/blog/2023/why_split_lexing_and_parsing_into_two_separate_phases.html
apropos
CC BY-SA 4.0
2024-03-29T05:39:05.017Z
@MichaelHomer, **two-phase parsers**, whether it is handwritten or a generator. I know that peg can be run twice to generate token stream and ast respectively. This situation is regarded as two-stage parsing.
Aster
CC BY-SA 4.0
2024-03-29T05:43:50.630Z
We don't need to -- but it does make things simpler and easier to understand if you can break them down into simpler steps.  This is true of any programming problem, or even any "process" that needs to be understood.
Chris Dodd
CC BY-SA 4.0
2024-03-29T06:22:13.633Z
It is totally possible to have a separate lexer, while simultaneously using keywords as identifiers, or treating `>>` as two tokens. The lexer simply needs to preserve enough information for the parser to make those decisions.
rpjohnst
CC BY-SA 4.0
2024-03-29T06:50:07.053Z
For me, the question cannot be answered and is partly misguiding. Parser combinators can also be used on token streams. If we reduce it to two stage vs. one stage, I would be fine.
feldentm
CC BY-SA 4.0
2024-03-29T11:45:01.243Z
The mantra of software engineering: ***Divide et impera!*** Or, avoiding the ultimate anti-pattern, now with an Academy Award: *Everything Everywhere All at Once* ;-)
Peter - Reinstate Monica
<p>For all but the simplest grammars, the parser sometimes needs to &quot;look ahead&quot; to at least the next token to decide how to parse the current one. Let's look at an example from Python:</p>
<pre class="lang-python prettyprint-override"><code>f(5 if(x+y)&lt;z else 6, 7)
</code></pre>
<p>After parsing the integer literal <code>5</code>, the parser sees a token for the keyword <code>if</code>, and therefore knows it needs to continue parsing the expression to create a conditional expression. If instead there was a comma, the parser would know it needs to not continue parsing the expression. So the parser &quot;looks ahead&quot; to see the next token before deciding whether to consume it.</p>
<p>The same lookahead logic <em>could</em> be implemented at the character level instead of the token level, but it's a bit more complicated. To know that there is a keyword <code>if</code>, the following source code must not simply start with the characters <code>i</code> and <code>f</code> ─ that would match an identifier like <code>if_this_then_that</code> ─ but there are plenty of other non-space characters which could follow <code>i</code> and <code>f</code> (in this case, <code>(</code>) that would make it a keyword <code>if</code>. Then it gets more complicated when you realise that the next two characters could be whitespace, or even <code>#</code>:</p>
<pre class="lang-python prettyprint-override"><code>f(5# a line comment here
    if(x+y)&lt;z else 6, 7)
</code></pre>
<p>So it would be possible to write a lookahead test for a keyword <code>if</code>, but this test would have to incorporate the same logic as a lexer, including the logic for recognising and discarding comments. Then all of that logic would also be needed to <em>consume</em> the <code>if</code> keyword, because that requires skipping past the comment. On the other hand, a lexer only has to see each comment once, rather than once per lookahead and then again when a token is consumed.</p>
<p>And the above is for just a single token lookahead. In a language like Java or Typescript where an expression beginning <code>a&lt;b</code> could be either a comparison or a generic function call, it may be necessary to look many more tokens ahead.</p>
<p>So lexing is a separate stage, both because tokens are a more suitable level of abstraction for a parser to work at, and also because it makes sense to recognise and discard comment tokens in a separate pass before parsing.</p>

CC BY-SA 4.0
2024-03-28T15:41:37.083Z
2024-03-28T15:50:03.233Z
2024-03-28T15:50:03.233Z
kaya3
CC BY-SA 4.0
2024-03-28T15:56:46.573Z
Doesn’t  the tokenizer equally have to solve those problems such as lookahead? Some parsers even *rely* on solving since of these themselves, e.g. a left-recursive PEG parser must memoize/cache/store parse attempts, similar to how a lexer would provide stored tokens.
MisterMiyagi
CC BY-SA 4.0
2024-03-28T16:01:19.413Z
@MisterMiyagi Not sure what you mean. A tokenizer has to look ahead at the character level, a parser has to look ahead at the token level. They are different tasks done for different reasons. The tokenizer doesn't have to solve any of the parser's lookahead problems.
kaya3
CC BY-SA 4.0
2024-03-29T06:54:21.947Z
If tokenization is distinct from parsing, it is usually not done with lookahead that is comparable to the concept in parsers.
feldentm
CC BY-SA 4.0
2024-03-29T11:14:09.767Z
Many efficient parsing algorithms like require _limited_ lookahead.  E.g. LR(_k_) which sees _k_ "terminals" ahead.  With "terminal"=character that is rather useless, because **identifiers & string literals can be arbitrarily long**!  A tokenizer (frequently expressible in regexps and generally doable in ~linear time) groups whole identifier/keyword to single token, making bounded lookahead grammars useful.
Beni Cherniavsky-Paskin
CC BY-SA 4.0
2024-03-29T11:17:52.977Z
The division of work is: parser handles recursively nestable structures, tokenizer flat.  String interpolation is famous case where that breaks down: `"string #{nested_expression("inner #{2+2} string")} outer string"`  AFAIK Ruby's tokenizer recursively calls into parser for such case.
Beni Cherniavsky-Paskin
<p>The short answer: Lexical analysers typically disambiguate, where syntax analysers typically don't.</p>
<p>Pick any modern programming language (e.g. C) and try to come up with a regular expression that matches identifiers. It's a difficult challenge, because the strict formal definition is something like this:</p>
<ul>
<li>An alphabetic character or underscore, followed by zero or more alphanumeric characters or underscores...</li>
<li>...that isn't a keyword.</li>
</ul>
<p>And therein lies the rub.</p>
<p>There was a time, a few decades ago, when programming languages were not designed this way, but since the 1970s, they are basically all designed around the same idea of the two-level syntax, with the lower level (the lexical level) handling all the disambiguation, and the higher level (the syntax level) not doing that, or only doing that in very specific circumstances (see also: the dangling else problem).</p>
<p>Specifically, the following disambiguation rules typically apply:</p>
<ol>
<li>The &quot;maximal munch&quot; rule: The &quot;correct&quot; token is the one that consumes the most possible input.</li>
<li>In the case of a tie, tokens are assigned a priority, and the highest priority one &quot;wins&quot; (e.g. keywords are a higher priority than identifiers).</li>
</ol>
<p>It's simpler to design languages this way, and programmers (as well as tools, such as syntax-highlighting IDEs) have come to expect it.</p>

CC BY-SA 4.0
2024-03-30T01:22:39.173Z
2024-03-30T01:22:39.173Z
Pseudonym
<p>Adding to the other answers, <em>you don't, really</em>. There are languages, like Scheme, where you would not need it and parsing could be done in one step. In lisp, you could parse things one word at the time, from left to right, e.g. in <code>(+ 2 3.14 x)</code> your parser notices &quot;(&quot; so it knows it would be parsing a list, then it sees &quot;2&quot; which needs to be a number, next token starts with &quot;3&quot; so it also is a number, but &quot;.&quot; at the second position hints it that the number is a float, you proceed further, &quot;x&quot; is a non-number, so a variable, and you finally hit &quot;)&quot;, so you can return those elements as a linked-list <code>(+, (2, (3.14, (x, nil))))</code>. The same applies to many other languages with simple syntax where you don't need much context for the parser to make decisions. When you are writing a one-step parser and start noticing that your code gets complicated, it is often the sign that switching to two-step parser might be a good idea. It would allow you to split character-level decisions (lexer) from token-level decisions (parser).</p>

CC BY-SA 4.0
2024-04-02T14:35:01.847Z
2024-04-02T14:35:01.847Z
Tim
<p>It makes reasoning about parsing easier than if you had to parse character by character.</p>
<p>You can make keyword context dependent. So during parsing if a IDENT is equal to the keyword then replace the token with the keyword token. Or conversely if a keyword doesn't make sense for the context but an identifier can, replace with a IDENT.</p>
<p>Mistaking a nesting &lt;&gt; for a shift operator is a issue with your grammar, you'll always have issues with that no matter the parsing method you pick. You can sidestep that by not having nesting &lt;&gt;. If you do need to tokenize, then you can do the same replacing trick from above, if the right shift doesn't make sense then retry with it replaced by 2 greater thans</p>

CC BY-SA 4.0
2024-03-28T12:57:22.897Z
2024-03-28T12:57:22.897Z
ratchet freak
# Why do we need to divide lexing and parsing stages
Posted by: username_0 on 2024-03-28
Why do many typical parsers need to have two stages: **tokenization** and **parsing**?

This isn't just a helping hand for manually-constructed parsers, as even generation tools do the same. For example, the common parser generator *bison* is often used in combination with *flex* for tokenization, while ANTLR has *lexer mode* and *parser mode*.

I felt some shortcomings during use:

* `KEYWORD`s cannot be used as `IDENTIFIER`s
* Difficult to parse `List>`, because `>>` is `SHIFT_RIGHT`.

Single-stage parsers such as parser combinators and parsing expression grammar do not have this disadvantage.

The advantages are

* We can add virtual tokens, such as `INDENT`, `DEDENT`

---

I looked at the main implementations of most major programming languages, and they all use two-stage parsing.

Are there any huge advantages to splitting into two stages?
**Tags:** parsing
> **Comments:**
> **username_1**: For my language my lexer only separates numbers and identifiers, and whitespace. All symbols are left unchanged since too many symbols are context dependent  
> **username_2**: Is this about parser *generators* or just about two-phase parsers generally?  
> **username_3**: You don't *need* to separate them, it just usually makes the design easier.  
> **username_4**: https://tratt.net/laurie/blog/2023/why_split_lexing_and_parsing_into_two_separate_phases.html  
> **username_0**: @MichaelHomer, **two-phase parsers**, whether it is handwritten or a generator. I know that peg can be run twice to generate token stream and ast respectively. This situation is regarded as two-stage parsing.  
> **username_5**: We don't need to -- but it does make things simpler and easier to understand if you can break them down into simpler steps.  This is true of any programming problem, or even any "process" that needs to be understood.  
> **username_6**: It is totally possible to have a separate lexer, while simultaneously using keywords as identifiers, or treating `>>` as two tokens. The lexer simply needs to preserve enough information for the parser to make those decisions.  
> **username_7**: For me, the question cannot be answered and is partly misguiding. Parser combinators can also be used on token streams. If we reduce it to two stage vs. one stage, I would be fine.  
> **username_8**: The mantra of software engineering: ***Divide et impera!*** Or, avoiding the ultimate anti-pattern, now with an Academy Award: *Everything Everywhere All at Once* ;-)  
---
## 4 answers
### Answer by username_9 on 2024-03-28. Score: 10
For all but the simplest grammars, the parser sometimes needs to "look ahead" to at least the next token to decide how to parse the current one. Let's look at an example from Python:
f(5 if(x+y)
After parsing the integer literal 5, the parser sees a token for the keyword if, and therefore knows it needs to continue parsing the expression to create a conditional expression. If instead there was a comma, the parser would know it needs to not continue parsing the expression. So the parser "looks ahead" to see the next token before deciding whether to consume it.
The same lookahead logic could be implemented at the character level instead of the token level, but it's a bit more complicated. To know that there is a keyword if, the following source code must not simply start with the characters i and f ─ that would match an identifier like if_this_then_that ─ but there are plenty of other non-space characters which could follow i and f (in this case, () that would make it a keyword if. Then it gets more complicated when you realise that the next two characters could be whitespace, or even #:
f(5# a line comment here
    if(x+y)
So it would be possible to write a lookahead test for a keyword if, but this test would have to incorporate the same logic as a lexer, including the logic for recognising and discarding comments. Then all of that logic would also be needed to consume the if keyword, because that requires skipping past the comment. On the other hand, a lexer only has to see each comment once, rather than once per lookahead and then again when a token is consumed.
And the above is for just a single token lookahead. In a language like Java or Typescript where an expression beginning a could be either a comparison or a generic function call, it may be necessary to look many more tokens ahead.
So lexing is a separate stage, both because tokens are a more suitable level of abstraction for a parser to work at, and also because it makes sense to recognise and discard comment tokens in a separate pass before parsing.
> **Comments:**
> **username_10** (2024-03-28): Doesn’t  the tokenizer equally have to solve those problems such as lookahead? Some parsers even *rely* on solving since of these themselves, e.g. a left-recursive PEG parser must memoize/cache/store parse attempts, similar to how a lexer would provide stored tokens.  
> **username_9** (2024-03-28): @MisterMiyagi Not sure what you mean. A tokenizer has to look ahead at the character level, a parser has to look ahead at the token level. They are different tasks done for different reasons. The tokenizer doesn't have to solve any of the parser's lookahead problems.  
> **username_7** (2024-03-29): If tokenization is distinct from parsing, it is usually not done with lookahead that is comparable to the concept in parsers.  
> **username_11** (2024-03-29): Many efficient parsing algorithms like require _limited_ lookahead.  E.g. LR(_k_) which sees _k_ "terminals" ahead.  With "terminal"=character that is rather useless, because **identifiers & string literals can be arbitrarily long**!  A tokenizer (frequently expressible in regexps and generally doable in ~linear time) groups whole identifier/keyword to single token, making bounded lookahead grammars useful.  
> **username_11** (2024-03-29): The division of work is: parser handles recursively nestable structures, tokenizer flat.  String interpolation is famous case where that breaks down: `"string #{nested_expression("inner #{2+2} string")} outer string"`  AFAIK Ruby's tokenizer recursively calls into parser for such case.  
---
### Answer by username_12 on 2024-03-30. Score: 7
The short answer: Lexical analysers typically disambiguate, where syntax analysers typically don't.

Pick any modern programming language (e.g. C) and try to come up with a regular expression that matches identifiers. It's a difficult challenge, because the strict formal definition is something like this:

* An alphabetic character or underscore, followed by zero or more alphanumeric characters or underscores...
* ...that isn't a keyword.

And therein lies the rub.

There was a time, a few decades ago, when programming languages were not designed this way, but since the 1970s, they are basically all designed around the same idea of the two-level syntax, with the lower level (the lexical level) handling all the disambiguation, and the higher level (the syntax level) not doing that, or only doing that in very specific circumstances (see also: the dangling else problem).

Specifically, the following disambiguation rules typically apply:

1. The "maximal munch" rule: The "correct" token is the one that consumes the most possible input.
2. In the case of a tie, tokens are assigned a priority, and the highest priority one "wins" (e.g. keywords are a higher priority than identifiers).

It's simpler to design languages this way, and programmers (as well as tools, such as syntax-highlighting IDEs) have come to expect it.
---
### Answer by username_13 on 2024-04-02. Score: 1
Adding to the other answers, *you don't, really*. There are languages, like Scheme, where you would not need it and parsing could be done in one step. In lisp, you could parse things one word at the time, from left to right, e.g. in `(+ 2 3.14 x)` your parser notices "(" so it knows it would be parsing a list, then it sees "2" which needs to be a number, next token starts with "3" so it also is a number, but "." at the second position hints it that the number is a float, you proceed further, "x" is a non-number, so a variable, and you finally hit ")", so you can return those elements as a linked-list `(+, (2, (3.14, (x, nil))))`. The same applies to many other languages with simple syntax where you don't need much context for the parser to make decisions. When you are writing a one-step parser and start noticing that your code gets complicated, it is often the sign that switching to two-step parser might be a good idea. It would allow you to split character-level decisions (lexer) from token-level decisions (parser).
---
### Answer by username_14 on 2024-03-28. Score: 0
It makes reasoning about parsing easier than if you had to parse character by character.

You can make keyword context dependent. So during parsing if a IDENT is equal to the keyword then replace the token with the keyword token. Or conversely if a keyword doesn't make sense for the context but an identifier can, replace with a IDENT.

Mistaking a nesting <> for a shift operator is a issue with your grammar, you'll always have issues with that no matter the parsing method you pick. You can sidestep that by not having nesting <>. If you do need to tokenize, then you can do the same replacing trick from above, if the right shift doesn't make sense then retry with it replaced by 2 greater thans
---
