4 ms·

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://g

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.
        yoklov 10y ago
        A unicode_next_character function is very simple to write regardless of unicode support in your language. I usually write it as a small (256 byte) lookup table where each entry tells you how many characters to skip next. If you don't use a lookup table, its 4 single-line `if` statements (and if you do it's a one liner, plus however many lines the table takes).
        jblow 10y ago
        There's free source code for basic Unicode operations all over the internet.
    - nulltype 10y ago
      Here's a video of Rob Pike, developer of Go, talking about a lexer he built for the Go text/template package: https://www.youtube.com/watch?v=HxaD_trXwRE https://www.youtube.com/watch?v=HxaD_trXwRE It supports unicode.
- 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?

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.
      - yoklov 10y ago
        A unicode_next_character function is very simple to write regardless of unicode support in your language. I usually write it as a small (256 byte) lookup table where each entry tells you how many characters to skip next. If you don't use a lookup table, its 4 single-line `if` statements (and if you do it's a one liner, plus however many lines the table takes).
      - jblow 10y ago
        There's free source code for basic Unicode operations all over the internet.
  - nulltype 10y ago
    Here's a video of Rob Pike, developer of Go, talking about a lexer he built for the Go text/template package: https://www.youtube.com/watch?v=HxaD_trXwRE https://www.youtube.com/watch?v=HxaD_trXwRE It supports unicode.
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?