5 ms·

It's a pain and not something you really keep touching again and again once you've got it baked. I've done it a number of times and I've had to relearn ANTLR e

• FeepingCreature 10y ago
  I don't understand why people use FSMs or parser tools. I wrote the parser for my script language, jerboa ( https://github.com/FeepingCreature/jerboa https://github.com/FeepingCreature/jerboa ) over a few days; it's (I thought) entirely standard recursive descent single-pass. This is how I've always written parsers. Where would you even use FSMs for parsers?
  • wolfgke 10y ago
    > Where would you use FSMs for parsers? For the lexing (lexical analysis) stage of the parser. I know that the alternative to using a lexer (for which the tokens are specified by regular languages, thus lexed by FSMs) is to use so-called scannerless parsing (this is possible since every regular-language is context-free, thus the tokens can also be specified by the original context-free grammar). But using this alternative is usually much more painful since you usually want the grammar to have a nice property that allows linear-time parsing and a unique parse tree. LR(k), LL(k) etc. are such properties. Such properties are much more difficult to ensure for scannerless parsing.
    • jblow 10y ago
      Except no, lexing is trivial; it is by far the easiest part of writing a compiler. You don't need anything fancy, you just type in the code.
      • wolfgke 10y ago
        If you want to write a lexer from scratch, this is IMHO not trivial. If you use a generator it is much easier, but so is also using a parser generator for the CFG parsing stage.
        • SamReidHughes 10y ago
          Hand-rolling a lexer seems pretty trivial to me. The code writes itself. A generator is a tool whose limitations you have to work around, be it for a lexer or a parser.
        • jblow 10y ago
          If you can't write a lexer by hand, just forget trying to write a compiler that does anything interesting, because the lexer is MUCH easier than any other part of the compiler. There are a lot of reasons for this, but one of the basic ones is that the lexer does not need to interact in a complex way with the compiler's state. It is a relatively simple pipeline where characters go in one end and tokens come out the other.
      • programLyrique 10y ago
        When you add unicode, it can become more complicated (or rather, cumbersome)...
        • jblow 10y ago
          Well, you just need to call unicode_next_character all the time instead of saying s++, similarly for whitespace, similarly for asking whether a character can initiate or continue an identifier, etc. It does not change the basic nature of the task at all.
          • programLyrique 10y ago
            Sure, but if you are using a language without support for unicode, and you don't use a dedicated library (which would be already using a kind of lexer, wouldn't it?), you have also to parse these unicode characters yourself.
    • SamReidHughes 10y ago
      The only actual increase in difficulty from scannerless parsing is having to janitor whether a function will always slurp up whitespace before it finishes. Linear-time is easy, questions of unique parse tree are irrelevant because the only ambiguity is who owns a piece of whitespace that gets discarded anyway.
  • ci5er 10y ago
    What wolfgke said. I (personally) use FSMs as my swiss-army chainsaw a lot. I realize that this isn't common practice, but I came from silicon, so what are ya gonna do?
• joe_the_user 10y ago
  Sure, All of the parser-generator tools are really opaque and not something that can be easily used for simple things. On the other hand, recursive descent parsers are something that can be whipped easily if you have a little project. And the problem is that a lot programmers both can't produce a recursive descent parser AND don't know when their problem domain is moving into a place where such a thing is needed.
  • ci5er 10y ago
    Fair enough. They're not rocket science conceptually - but I have to relearn the tools each time. Not a huge deal - a couple of hours - but I was thinking that you were claiming I needed to have it down as cold as when I got out of CS 202 (or whatever that thing was).