6 ms·

I usually love Laurence's posts. However, one thing he said in this one is wrong in my experience. > Since some parsing approaches such as recursive descent pa

• jcranmer 4y ago
  My experience is that splitting lexing and parsing is by far the norm, even in recursive descent.
  • gavinhoward 4y ago
    Oh, thank you! I was wondering if I was an outlier.
    • chris37879 4y ago
      Nah, I’ve been toying with writing a compiler and that’s where I’ve gotten to too, it seems to my inexperienced self at least, if what you’re implementing is a specified language, combining the phases makes sense since you only have one thing per language, but while making a language and experimenting, having them be separate helps reduce a lot of complexity in the parser for things like tokens that go across multiple lines. 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.
      • gavinhoward 4y ago
        Funny; my experience is the opposite. 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.
        • chris37879 4y ago
          I know right? 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.
          • gdy 4y ago
            It's buggy though
            • chris37879 4y ago
              It definitely can be, and it was mostly an illustrative example for the ‘mathematical validity’ part of my comment. When you’re just starting out, working valid code is better than nothing!
• puddingforears 4y ago
  I’ve only written lexing and parsing together in recursive descent parsers. What am I missing out on?
  • pyrale 4y ago
    I believe the point being made is that while it is possible to merge lexing and parsing with recursive descent parser, it is not essential to this style, and separating lexing and parsing while doing recursive descent parser is also a legitimate approach.
  • phpnode 4y ago
    Lexing separately is cleaner in that the lexer's only job is to produce tokens and then the parser's only job is to consume tokens and produce e.g. an AST. It also means that you can use that token stream for other things that don't require a full parse (e.g. for syntax highlighting). The disadvantage is that you're often doubling the allocations and increasing the memory footprint. I alternate between separate lexer, combined recursive descent parser and generated PEG parsers depending on what is more important: speed + maintainability, speed of execution or speed of development
  • gavinhoward 4y ago
    If you don't think you're missing out, you're not. I think it could be preference. I just prefer for a lexer to be responsible for handling characters, and a parser be responsible for handling tokens. So Single Responsibility Principle.
  • mst 4y ago
    If you find the code wants factoring out (if you don't, just leave it be, parsers are wonderful things to have written but IME writing them is generally a labour of love) then that split tends to be very natural and works well in the vast majority of cases. 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)
• kmill 4y ago
  I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand. 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).
  • deleted 4y ago
    [deleted]
  • Twisol 4y ago
    > I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand. 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).
    • beached_whale 4y ago
      This is how I am setup in the little language I am writing in C++. I put the lexer into an iterator.
  • matheusmoreira 4y ago
    > I've seen interleaved lexing and parsing, where the recursive descent parser asks for the next token, which is computed on demand. 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.
  • bazoom42 4y ago
    A Javascript parser have to do something like this. The text /a/ tokenize differently depending on where in the grammar, eg a/b/c is division (/a/) is a regex.
    • 4y ago
• vidarh 4y ago
  I think you're right that most modern recursive decent parsers have separate lexers, but I think what you'll find in many older recursive descent parsers is that when it's clear which token type may come next, the parsers will often call a specialised function that will return or throw an error if it's not that specific type. 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.
  • peterfirefly 4y ago
    That's how most of my recursive descent parsers have worked. I think the first ones I wrote did have a lexer/parser split and then I realized it was easier to use the specific calls for each expected token class.
    • vidarh 4y ago
      Most of mine too. When you're hand-writing the whole thing anyway, and the grammar makes it obvious the next token can only be an identifier it feels wasteful to call a generic function, and so I rarely add a generic function unless I get to somewhere in the grammar where there's no easy way to determine a single or small set of token types to parse. But at the same time, if you're reaching for automation the lexer side is easier to automate "cleanly" and most of the automation tools tend to provide a single entry-point.
• ltratt 4y ago
  You're quite right, I over-simplified -- mea culpa! That should have said "often unify these phases". FWIW, I've written recursive descent parsers with and without separate lexers, though my sense is that the majority opinion is that "recursive descent" implies "no separate lexer".
  • munificent 4y ago
    For what it's worth, in my little corner of the world, all of the recursive descent parsers I've seen and worked with have separate lexers. I can't recall seeing a single recursive descent parser in industry that didn't separate lexing. 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.
  • abecedarius 4y ago
    That's not my impression of the majority opinion, fwiw. (I wrote my first recursive-descent parser in the 80s and I learned from pretty standard sources like one of Wirth's textbooks.)
  • lemming 4y ago
    As another data point in addition to the sibling comments, all IntelliJ language parsers use recursive descent with a separate lexer.
• WalterBright 4y ago
  In my first C compiler, I combined the lexer and preprocessor. That was a mistake. The (much) later one I wrote, Warp, tokenized and then preprocessed. It was much easier to work with.
  • exebook 3y ago
    It is also about performance. 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.
    • WalterBright 3y ago
      Excellent summary. A couple other reasons for a separate tokenizer: 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
• mikevin 4y ago
  Can you expand on why you prefer that approach?
  • int_19h 4y ago
    It's much easier to have a grammar that is LL(1) - which also makes recursive descent that much more convenient to write - if you separate.
• kerkeslager 4y ago
  I won't say this is the explicit reason recursive descent parsers have separate lexers, but there is a major downside to folding the lexer into a recursive descent parser, which would occur when/if you make the leap to packrat parsing. If the parsed language develops far enough you'll often run into edge cases where backtracking can become pathological. One benefit to recursive descent is that you can often just fix this by memoizing the parser functions (called a packrat parser). 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).
  • seanmcdirmid 4y ago
    Incremental re-Lexing works great in IDEs where you want to preserve tokens and the state associated with them. It also helps to isolate errors by attributing them to a token that contains the change rather than somewhere far off. Incremental parsing is the same: it costs more in terms of memory and even overall time, but provides better feedback for the IDE. Batch compilation is a different beast, but I haven’t written one of those for a pint time.
• seanmcdirmid 4y ago
  I don’t think it’s an outlier, I do my lex phase before the parsing phase, it’s not concurrent. However, I find reporting bad tokens and parse errors to work well even if the phases are sequential.
• drpixie 4y ago
  I have similar compiler history and employ similar practice. 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.)