12
$\begingroup$

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:

  • KEYWORDs cannot be used as IDENTIFIERs
  • Difficult to parse List<List<T>>, 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?

$\endgroup$
9
  • $\begingroup$ For my language my lexer only separates numbers and identifiers, and whitespace. All symbols are left unchanged since too many symbols are context dependent $\endgroup$
    – mousetail
    Mar 28 at 15:09
  • $\begingroup$ Is this about parser generators or just about two-phase parsers generally? $\endgroup$
    – Michael Homer
    Mar 28 at 19:10
  • 4
    $\begingroup$ You don't need to separate them, it just usually makes the design easier. $\endgroup$
    – Barmar
    Mar 28 at 19:54
  • $\begingroup$ tratt.net/laurie/blog/2023/… $\endgroup$
    – apropos
    Mar 28 at 21:20
  • $\begingroup$ @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. $\endgroup$
    – Aster
    Mar 29 at 5:39

4 Answers 4

8
$\begingroup$

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)<z else 6, 7)

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)<z else 6, 7)

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Mar 28 at 15:56
  • $\begingroup$ @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. $\endgroup$
    – kaya3
    Mar 28 at 16:01
  • $\begingroup$ If tokenization is distinct from parsing, it is usually not done with lookahead that is comparable to the concept in parsers. $\endgroup$
    – feldentm
    Mar 29 at 6:54
  • $\begingroup$ 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. $\endgroup$ Mar 29 at 11:14
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 29 at 11:17
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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