Why split lexing and parsing into two separate phases?
tratt.net
tratt.net
First memory was very limited by todays standards, say 30 to 60kb. By making lexing a separate pass, the source could be discarded before the parser started and the tokenized intermediate file written by the lexer could be read during the parsing pass. Typically, the compiler might keep the name table of all identifiers in memory between these passes.
Around the mid 70s, languages that could be compiled in a single pass were investigated. Pascal was one of these. Pascal didn’t support separate compilation either so the linking step was eliminated. Nevertheless, the early Pascal compilers still did lexing separate from parsing; I learned Pascal by studying the source for Wirth’s compiler (it had crazy inconsistent indenting).
The second reason lexing was done separately was performance. Touching every character of the input source file was a major bottleneck for compilers back then, so optimizing the lexer was perceived to be very important. By doing the lexing in a tight loop rather than being called once for ever token lots of overhead associated with these calls was eliminated.
Also, there was a questionable attraction to bottom up parsing. Knuth had shown how LR (left to right) shift-reduce parsers could parse a very large family of grammars efficiently around 1965. Everyone was enamored with them. I even wrote a set of FORTRAN programs that would construct the SLR tables suitable for a subset of LR parsable grammars. When lex and yacc applications came along, everyone thought that every compiler should be built this way (to be fair, Wirth and Per Brinch Hansen were both designing languages that could easily be parsed by recursive descent because their grammars were LL(1) a smaller family of grammars than LR(n)). I’ve never seen anyone try to use only a LR parser at the lexical level combined with the normal grammar parsing.
I went back to University for another graduate degree in 1984, and I was surprised to hear the professor that taught the compiler class say that everyone should be using lex and yacc for any compiler development. By then, in the real world, people had discovered that much more meaningful error messages were possible with LL or recursive descent (i.e. top down) parsing.
Now, performance and memory considerations are different. It’s practical for compilers to read an entire source file in a single read (or memory map the entire source file), saving all the round trips to the OS for reading input. Top down parsing provides better error messages and it fits well with parsing all the way down to the lexiems.
This is largely orthogonal to whether you separate lexing out, though - it's perfectly possible (and very pleasant) to use recursive descent parsing over a token stream rather than a character stream.
Recursive descent over a character stream might have a negative performance impact, but I’m not sure of this considering the simple grammar involved in the lexical portion of the overall grammar and the ability of today’s tools to optimize function calls via inclining etc. If I was writing a compiler today for modern hardware, I would like to try using recursive descent on a single grammar that went all the down to the characters.
The error messages complaint is the one I always see. I rarely see other, specific complaints.
Question: Is this "error messages" complaint referring to error messages for lex, yacc or both. Does the complaint apply evenly to both programs. As a flex user, generally, I rarely if ever see error messages.
I like flex because it does not require as much memory as the alternatives. Ideally, I want scanners to perform roughly same from computer to computer and from input to input, irrespective of the amount of memory available or the size of the input. I like UNIX utilties that read files line by line.
> Since some parsing approaches such as recursive descent parsing unify these phases, why do lex and yacc split them apart?
I have written two recursive descent parsers for one small, but production quality compiler. I am in the middle of writing another two, which will also be production quality and much bigger. And I have written various small parsers.
I always use recursive descent, and I always split the lexing and parsing phases.
Now, I fully acknowledge that my experience could be an outlier, but I believe the benefits of lexing are so big that most recursive descent parsers have separate lexers.
I have no idea if the above observations are generally true, but that’s been my experience with the handful of parsers I’ve thrown away because they get too unwieldy for what I want.
My first production-quality parser was for the `bc` language, which is specified in a standard.
But your experience is just as valid as mine.
I had a friend in college who nearly always solved problems 'backwards' to everyone else cause it's just how her brain worked, like we'd do a standard for(int i = 0; i < length; i++) and she'd have for(int i = length; i >=0; i--) kinda backwards.
I don't question it at this point anymore and just marvel at the mathematical validity of it all.
I just prefer for a lexer to be responsible for handling characters, and a parser be responsible for handling tokens. So Single Responsibility Principle.
It's also worth having a poke around at some of the Racket community's Language Oriented Programming efforts, they usually have a split they call 'reader' versus 'expander' that I found helped me get my head around how the dividing line can be drawn and why you'd want to.
(Racket's approach isn't quite lexer vs. parser AFAICT but while I at least -think- I've understood it well enough to use ideas, I'm not going to pretend I understand it well enough to provide a correct explanation, let alone a well written one)
They're still separate modules. You just don't have to run lexing to completion ahead of time (and as a consequence, it's natural to let lexing be context-sensitive where needed).
You even get this for free in a lazy language like Haskell, where your parser can accept a list of tokens `[Token]` whilst the list itself is only computed on-demand whenever the parser tries to get the next one.
Well, except for the context-sensitive option:
> (and as a consequence, it's natural to let lexing be context-sensitive where needed).
This is how I implemented it in my language. Evaluator asks parser for a value, parser asks lexer for one or more tokens, lexer asks the I/O layer for characters. It's nice.
In JavaScript the following give wildly differently shaped ASTs since the / character initiates RegEx parsing when in a _value position_ that has different lexing than the division operator that _only_ appears as a potential binary operator, consider the following:
a = b + /c.y/+d
a = b /c.y/+d
(Given b=1 , c={y:2} and d=3 )
The first assigns a as add b to the RegExp matching c.y added to +d giving us the string "1/c.y/3" (JS converts most types to string on addition and strings are dominant during addition as concatenations), this is correct since the + operator before the / character forces the parser to look for a value.
The second reads as assign a to b divided by property y of c then divided by d (ie the numeric computation (1/2)/3 = 0.166666.... ), this is because the parser is looking for binary operators after the b identifier and when the / character appears it becomes an operator.
So, without knowing the parsing context (operator or value position) the lexer decision is ambigious.
This is somewhat how A<B<C>> is ambigious when parsing C++/Java/C# templates/generics VS the <, > and >> operators but that case is usually easier since the parser could include a hack in the generic parsing code that mutates the token stream if it encounters >> when closing a generic. (The JS ambiguity is worse though since RegEx lexing rules are totally different from regular JS)
I don't know how JS (implementations) actually does it, but this is what I meant by the line being a bit arbitrary, in my limited experience - you can just lex 'forward slash token' or whatever and keep your lexer/parser separation even with this ambiguity.
It's not so bad in practice, since you only need to look at the previous token to decide whether a / should be parsed as a division or regular expression, once you've excluded the possibility for // and /* comments.
Comments are also why the empty regular expression in JavaScript must be written as /(?:)/
( x ) / b / a
var x = (x) / b / a;
if (x) /b/a.test(z)
I suspect the only real solution is to intertwine lexing and parsing, so the parser asks for the next token with a flag indicating context. But this constrains what parsing algorithm can be used.
The issue with JavaScript is that say /a+”/ tokenize differently based on the position in the grammar, so you can’t tokenize in a seperate pass before parsing.
E.g. you might be calling a "getIdentifier()" function instead of a generic "getToken()".
In practical terms you sort-of have a lexer separation anyway - you will have a set of functions that each lexes one type of token. You just call them directly instead of letting a generic function discriminate between the token types.
But a generic separation works also for grammars where a scannerless approach is awkward. It's always possible; worst case you add support for backtracking and/or add helpers for more generic parses, but if you need to jump through hoops like that it quickly gets silly. And if you're first used to the separation there's little reason to write parsers in two different ways depending on the grammar.
Ultimately I think that's the reason why scannerless parsers are relatively rare.
However, I do often see a little fudging the two together for funny corners of the language. Often that just means handling ">>" as right-shift in some contexts and nested generics in others.
I've watched a video recently from a guy who compiled entire Linux kernel in under 1 second I believe, he used TinyC and also noticed that something like 90% of compilation is tokenization of headers that are included many times, like there are headers that are included thousands of times in almost every C file, so he ended up caching tokens. So a big reason to have a separate tokenizer is that tokenization is a simpler task and can be optimized with all low level approaches, like perfect hashes, crafted nested switch/if tries, branchless algs, compiler intrinsics etc.
The good tokenizer is about as fast as a speed of writing the output array of records into memory. Which means it is important to choose right memory layout for your tokenized data so that when parser reads tokens it has as little cache misses and indirect memory access as possible. Tokenization can be thought of as a sort of in memory compression.
1. Sometimes all you need is a tokenizer - such as for highlighting in a code editor
2. D has a construct called a token string - where a string literal consists of tokens
3. A separate tokenizer means the lexer and parser can run in separate threads
However, you really don't want to memoize calls to lexer-y parser functions because it's almost always faster and less memory-intensive to simply re-lex the source string. This gets more complicated if you're parsing a stream (but if your language is being parsed from a stream you should definitely be giving strong preference to language constructs which don't require backtracking).
Batch compilation is a different beast, but I haven’t written one of those for a pint time.
Keep things where they logically belong - the parser is for mapping tokens onto syntax, for that it needs tokens! It doesn't matter if lexing is done in a separate pass, or "interleaved" in time. What matters is that the each "pass" is logically distinct.
Most languages are designed so that it's easy to produce tokens from text, without knowing where you are in the syntax tree - that makes it easy to read code fragments.
(There are languages where the same string can have very distinct structure & meaning depending on context. They tend to cause much swearing and confusion.)
- It's completely possible
- BUT the bits that would normally be handled elegantly in the lexing phase are now strewn into every single grammatical element's parser, and it's surprisingly hard to formulate composable solutions that don't lead to undesirable resolutions to ambiguous situations (or rejecting desired grammar, or accepting undesired grammar, etc.)
I think it's possible that with differently defined grammars, it would be fine. For example, JSON should be completely trivial just because of how few tokens there are and how little ambiguity there is; I tend to write JSON parsers directly against the codepoints for this reason, in the odd event I have to write a JSON parser. (Yes, it comes up. Yes, I am aware JSON has some weird edge cases and I shouldn't do this.)
In my experience, another reason to split is to be able to manipulate the AST independently from parsing. For example, you may have multiple dialects or representations (such as a serialized form) for which you don't require the lexer, which is typical for non-toy or trivial parsers.
Even if tokenization happens during parsing, there is almost always still some separation. Often times it's just semantics, where the lexer doesn't strictly emit tokens, but simply represents the token in-place.
Another (more historic) reason the phases are typically separate is that it allows you to reason about them and the finite state machine. For example, you could write the state transitions by hand in the traditional form and reduce as you go, just like in the dragon book.
If you want to reason about grammars then it behoves you to wield the traditional form.
I'm sure some modern compilers blur the stages nowadays.
That said, I have not read a lot of compiler source code to back this thought up. I have read some, but mostly in the C++ backend side, usually to resolve curiosities about vtable implementation details.
Isn't that why #line exists in the first place? A lot of online literature, including the clang and GCC manuals, are worded in a way that makes it seem like the purpose is for consumption by the preprocessor, but I'd be surprised if the original purpose wasn't to communicate line numbers from the preprocessor to the compiler. The #line directive isn't mentioned in K&R; not even in the "ANSI C" second edition, despite C89 standardizing #line.
Of course, it's a preprocessor directive, but leveraging the syntax this way is a nice hack:
1) It's very simple to identify C preprocessor directives (see #2), and cheap to add a pre-pass to a C compiler to identify directives, accepting #line but throwing an error (or complaining about and discarding) any other directive.
2) There's no way to generate valid, non-preprocessor C code that might look like a directive. '#' is not and never will be an operator in C or have any other lexical role; it can only exist within comments, character literals, or string literals.
3) You can gainfully feed #line to the preprocessor, for example from the output of a different transformer like M4.
The Lexer's output alphabet (a set of tokens) which is an input for a Parser is up to a few tens of symbols at worst. The smaller alphabet the easier it is to make efficient recursive decent parser.
Regular expressions are Finite-State Machines under the hood. There exist one single minimal deterministic FSM per any Regex. And that model is the best in performance. In contrast, for context-free grammars we don't have such unique computation model that would be best in performance. Because of this it is reasonable to separate a Regex-based part of the grammar (the Lexing part) and treat it independently.
Also, when parsing, perhaps it would be easier to recover from input syntax errors from the Token-based input rather than Unicode-based input.
Finally, my personal opinion is that if you write a recursive-descend parser manually, it would be really easier to reason about just the limited number of token classes rather than the entire Unicode alphabet.
There's not really any difference between tokens and grammar rules, in my experience. They're just terminal and non-terminal symbols yeah? Doing these things in one place doesn't get in the way of writing a nice LL recursive-descent parser.
I'm sure it will depend on what you're doing but for me at least splitting into lex and parse has a much higher bar now. I've done it both ways many times and at least for my applications adding a separate lexer has historically been the wrong abstraction in retrospect.
I used to use combinators-based approach without Lex/Syn separation (aka PEGs) for a long time. But then I came up to understanding that the separation approach is actually better in performance. And also that working and debugging of the Token sequences while writing parser manually is just more handy (at least for me).
But this is my personal experience of course. I do believe too that it all depends on the goal, and parsers micro-optimizations is not that much critical in many cases, and that combinators approach actually works quite well too.
As of Nom, I can say that it works quite well. But I think that the it's performance gains stem from the fact that Rust is a systems-based PL, and it optimizes function combinations just better than, let say, JavaScript or Python.
In my incremental parsers library Lady Deirdre I utilize Lex/Syn separation, and the LL(1) recursive-descend parsing, and it shows much better performance than in Tree-Sitter at least on relatively big files [1].
[1] https://github.com/Eliah-Lakhin/lady-deirdre/tree/master/wor...
Rust has pretty exact mapping from syntax errors to lexical placement. Couldn't a similar approach be used if you have a potential recovery path?
During the lexical scanning stage you can persist the token's source code sites, and later reuse them to indicate syntax or similar errors.
For example, in Rust when you parse the syntax from the TokenStream of a procedural macro input, you can bind custom errors to any spans of input tokens, and it works just fine.
Huh?
How did you come up with this number?
Also, the artifact (Docker image + some guides, CC BY 4.0) for the OCaml library: https://zenodo.org/record/7824835.
Edit: The opam file actually says the license is MIT. I'd be more inclined to believe that over CC BY 4.0 as far as source code licensing goes.
I'll have to read about flap, as it seems to utilize a lexer based on derivatives.
https://matt.might.net/articles/nonblocking-lexing-toolkit-b...
The general rule seems to be: lexer is for parsing linear structures like numbers and symbols while parsers are for recursive nested structures like lists and objects.
If I recall correctly, the original historical reason for separating them was due to memory limitations on early mainframe computers. Actual source code would be fed into the 'lexer' and a stream of 'tokens' would come out the other end and then be saved to a file, which would then be fed into the next stage.
Having said this, you can ask "In practice, is there currently an advantage to separating the lexer and the parser with the tools we use now?" The answer is 'yes', but I claim that this is just a limitation of the tools we have available to us today. Tokens are usually described using a simple regular expression, whereas the parsing rules are 'context free', so worst-case complexity of parsing the two is not the same. If you pull tokens into the parser and just parse them as naive 'single-character parser items', then you end up doing more work than you would have otherwise since your parser is going to try all kinds of unlikely and impossible chopped up token combinations. The other big issue is memory savings. Turning every token into a (small) parse tree is going to increase memory usage 10-20x (depending on the length of your tokens).
Personally, I think there is a substantial need for more advanced ways of describing language grammars. The ideal model would be to have various kinds of annotations or modifiers that you could attach to grammar rules, and then the parser generator would do all sorts optimizations based on the constraints that these annotations imply. Technically, we already do this. It's called putting the lexer in one file, and the parser in another file. There is no good reason why we can't specify both using a more unified grammar model and let the parser generator figure out what to do about each rule to be as efficient as possible.
The computer science theory behind grammars seems to have peaked in the 1980s, and there doesn't seem to have been many new innovations that have made it into daily programming life since then.
If it was looking at tokens instead of characters this would go a lot faster, because examining characters is O(n) in the number of characters.
I wonder however: would it be possible to combine lexers and parsers into a single logical construct, but rely on caching to get the same effect?
To those knowledgeable in lexing and parsing, I pose a question: How do you determine what should be part of the lexing phase and what should be part of the parsing phase? Do you choose arbitrarily and move things from one phase to another if it's simpler one way or another? Or is there a better way?
The benefit is that this keeps each stage much simpler: lexing doesn't have to do much if any lookaround, and parsing mostly doesn't have to do anything character-wise.
The example of using the same tokens but for different purposes makes it clear that the lexer shouldn't be in the business of assigning meaning (semantics) to the tokens, and the parser shouldn't be in the business of fiddling with characters when it's something the lexer can do.
The parser groups the tokens into meaningful statements, it implements the grammar. If the parser sees an "if", it expects some condition next (depending on the grammar of course). If the parser detects statements that are not consistent with the grammar of the language, it should reject the program.
Tldr they work on different levels, lexers just finds the individual building blocks, the parser builds the program
Recursion. If your thing can contain other things, it requires a full parser. Otherwise a lexer can handle it.
In other words, use a lexer when a regular language is sufficient to describe the input and a parser when it's not.
Lexer:
12345
[123 [45]]This way, your parser tests are then about covering the different symbol transitions in the grammar, making them much more manageable.
It is possible to have more complex lexers -- typically state-based lexers -- that switch state on given input. You can do this when tokenizing comments, strings, or other constructs so the lexer can emit the correct symbol for things like string interpolation. This can be useful when syntax highlighting or other token-based tasks are separate to parsing.
I can see how a state-based lexer and a parser can be combined to avoid managing the state in the lexer -- that is because the parser will know what the current state is due to where it is in the grammar, so can call the appropriate method on the lexer, or pass the corresponding state information. I've not yet experimented with this approach, but it could be useful in some contexts.
Note: I've written a lexer and parser for a language plugin for IntelliJ which has separate lexer and parser steps, and uses the lexer for syntax highlighting. I'm investigating support for the language server protocol (LSP), so may also experiment with a directed/orchestrated lexer as described above.
yacc is ancient. Even its replacement, bison, is ancient at this point.
I have seen "lexing" done on the parsing level in the past. The same way you can say "a sum expression is a subexpression, a plus sign and another expression" you can say "an identifier is 1 letter followed by 0 or more letters or digits". It was a bit cute, but awkward.
It's very convenient to have two passes. The first one removes unnecessary stuff like superfluous spaces or comments, so that the actual parsing can operate over a simplified space (not having to take into account things like "an expression 0 or more spaces, the plus sign, 0 or more spaces and another expression"). At that point, you might as well just use a Lexer for phase 1.
In addition, most languages are not CFG and require nested contexts.
"#{"\tThis is some #{'damn'} string".to_upper_case + " hello"}\n"
In my opinion, a lot of the need for separate lexing was historical, due to the weak optimisations in the compilers of the era. With modern languages like C++ or Rust on top of LLVM, the lexing steps can be inlined efficiently.
Your IDE will do type checking as well. Yes, the lexer stage will parse all identifiers into 'ID', but to provide a contrived counter-example, what if I do want to allow 'pi' to be assigned based on something that can only be processed in a later stage (perhaps an annotation, or a result of compile time function evaluation, etc). It will push the logic of handling 'ID' to later stages anyway. Now you're handling IDs in at least 2 places - that's strictly worse than the status quo.
Part of our jobs is to be able to reason about trade-offs when making decisions. Pointing out that the lexer has a limitation does not necessarily justify removing that limitation for an edge case because it might be due to that limitation that it can be kept simple for the general case.
Adding complexity to the lexer without simplifying the later stages is a net negative in my opinion, which would make this trade-off not worth it.
Is it an interesting approach? Sure. Is it worth it? Maybe in some very specific use cases, but it doesn't seem like a convincing argument to me to combine the lexing and parsing phases.
Typechecking and access control are clearly semantic analysis considerations, which are better handled in a separate pass on an explicit AST. In particular, they may require a symbol table (i.e. an environment of names) that is not possible to compute during the parsing phase.
I’ll add my own at https://jmmv.dev/2023/01/endbasic-parsing-difficulties.html where I described some difficulties I encountered while trying to apply these more “modern” techniques on a language that was designed before them.
Scannerless parser grammars, especially with GLR, are extremely flexible and a pleasure to write. They are the "DWIM" of parsers. But you pay a high price in performance for that flexibility.
Since programming language grammars don't tend to change much, by the time you have a production compiler it's usually worth your time to switch to a split lexer/scanner in order to get that extra performance.
Recursive decent, where the parser asks the 'scanner' to accept a certain symbol at a certain location in the input stream, resolves most of these problems, such as for example the fact that in HTML the tags are case insensitive while JavaScript the keywords are case sensitive.
If you try to develop a parser that is user-friendly, but maybe not the most efficient (if you allow back-tracking) the whole problem of parsing become far less complicated. (There a good methods to counter performance problems due to back-tracking.)
Generally, whenever I write a parser+checker, I try to have a very relaxing parser and then all the checks in the checker.
An interesting lesson from it was that the argument about differences between compiled programming languages and scripts (which also arose during the course) is ultimately pointless. You can write a compiler to compile a scripting language, and you can write an interpreter to interpret and run something like C. So its not the language which matters but the compiling or interpreting.
For most languages, the tokens are a regular language and a simple regex lexer is enough. Regular expressions used by a lexer end up as a state machine.
It does not make much sense to use a full recursive descent parser just to do lexing, as it will be less efficient and use more memory. Consider that the amount of characters ingested by the lexer is far greater than the tokens ingested by the parser.
Mostly efficiency. Lexer-specific code can be significantly faster on input with large tokens.
It also makes it easier for some tools to only use the lexer, which makes them more likely to work even if code is not syntactically correct or written for a newer language revision than the tool.
In this case there's a fairly natural split, as you mention, so it's natural to use composition to handle this as well.
1. history (scanner, lexer, parser all would not fit on one tape/cassette/disk back then)
2. performance (each component can benefit from specialized optimization techniques without affecting the other)
The output of the 7th stage was an intermediate code; my guess is that part of the reason there were so many stages was to enable most of the compiler to be language-independant. If you renamed the executable for the 8th pass, you could hack on the intermediate code with an editor, and make COBOL programs that could do illegal things, like access IO directly.
I suspect a lot of the passes were common to the ALGOL compiler.