5 ms·

Probably the first article Ive ever read about lexical parsing with code that i have actually understood - and I dont even program in golang. Great job.

throwlaplace 7y ago
Lexical analysis using these bespoke methods (writing the finite state machine) is so tedious and error prone. I don't have that much experience but I just went through crafting interpreters and replaced this same module with https://github.com/J-F-Liu/pom https://github.com/J-F-Liu/pom, which is a parser combinator library, and it was way easier.
- gpetukhov 7y ago
  I guess it's relevant. Here is a great set of videos from "Low Level Javascript" channel explaining how to write parser combinators from scratch. - https://www.youtube.com/watch?v=6oQLRhw5Ah0&list=PLP29wDx6QmW5yfO1LAgO8kU3aQEj8SIrU https://www.youtube.com/watch?v=6oQLRhw5Ah0&list=PLP29wDx6Qm...
- arcticbull 7y ago
  Parser combinators are neat. nom is my go-to now in Rust, it's nice not have to separate your lexer and parser in simpler grammars.
  - dilap 7y ago
    (it’s actually also straightforward to write a recursive descent parser directly on the char stream w/o a lexing step.)
    - throwlaplace 7y ago
      how? it's not like you can magically skip the actual tokenization. you're basically saying you can do lexical analysis and semantic analysis in the same function. sure but that makes the code that much hairier - there's a reason why they're typically factored into a lexer and a parser.
      - dilap 7y ago
        > you're basically saying you can do lexical analysis and semantic analysis in the same function. yes > that makes the code that much hairier true, but it does save you the rigamarole of the lexer. func parseDeclaration(s string, i0 Pos) (n Node, i Pos, err error) { i = i0 i = skipSpace(s, i) if word(s, i, "var") { v := &ast.VarDecl{VarPos: i} i += 3 i = skipSpace(s, i) if v.Ident, i, err = parseIdent(s, i); err != nil { return } i = skipSpace(s, i) if is(s, i, "=") { i += 1 i = skipSpace(s, i) if v.Value, i, err = parseExpr(s, i); err != nil { return } } if !is(s, i, ";") { return nil, i, fmt.Errorf(`unexpected input or EOF (expected ";")`) } ⋮
    - arcticbull 7y ago
      Possible sure, but without a combinator framework, you have to do a ton of the rote work yourself.
- papaf 7y ago
  which is a parser combinator library, and it was way easier I like parser combinators but a word of warning. A lot of parser combinators (not all) have problems with recursive grammar such as Json and SQL [1]. For instance, a JSON map can contain a JSON map and this can lead to stack overflows when defining the grammar. [1] https://fsharpforfunandprofit.com/posts/understanding-parser-combinators-4/#5-parsing-array https://fsharpforfunandprofit.com/posts/understanding-parser...
  - throwlaplace 7y ago
    thanks for the link will take a look. like i said i don't have that much experience.
userbinator 7y ago
It's recursive-descent --- a pretty common and intuitive way to write a parser in general.

throwlaplace 7y ago

Lexical analysis using these bespoke methods (writing the finite state machine) is so tedious and error prone. I don't have that much experience but I just went through crafting interpreters and replaced this same module with https://github.com/J-F-Liu/pom https://github.com/J-F-Liu/pom, which is a parser combinator library, and it was way easier.

gpetukhov 7y ago
I guess it's relevant. Here is a great set of videos from "Low Level Javascript" channel explaining how to write parser combinators from scratch. - https://www.youtube.com/watch?v=6oQLRhw5Ah0&list=PLP29wDx6QmW5yfO1LAgO8kU3aQEj8SIrU https://www.youtube.com/watch?v=6oQLRhw5Ah0&list=PLP29wDx6Qm...
arcticbull 7y ago
Parser combinators are neat. nom is my go-to now in Rust, it's nice not have to separate your lexer and parser in simpler grammars.
- dilap 7y ago
  (it’s actually also straightforward to write a recursive descent parser directly on the char stream w/o a lexing step.)
  - throwlaplace 7y ago
    how? it's not like you can magically skip the actual tokenization. you're basically saying you can do lexical analysis and semantic analysis in the same function. sure but that makes the code that much hairier - there's a reason why they're typically factored into a lexer and a parser.
    - dilap 7y ago
      > you're basically saying you can do lexical analysis and semantic analysis in the same function. yes > that makes the code that much hairier true, but it does save you the rigamarole of the lexer. func parseDeclaration(s string, i0 Pos) (n Node, i Pos, err error) { i = i0 i = skipSpace(s, i) if word(s, i, "var") { v := &ast.VarDecl{VarPos: i} i += 3 i = skipSpace(s, i) if v.Ident, i, err = parseIdent(s, i); err != nil { return } i = skipSpace(s, i) if is(s, i, "=") { i += 1 i = skipSpace(s, i) if v.Value, i, err = parseExpr(s, i); err != nil { return } } if !is(s, i, ";") { return nil, i, fmt.Errorf(`unexpected input or EOF (expected ";")`) } ⋮
  - arcticbull 7y ago
    Possible sure, but without a combinator framework, you have to do a ton of the rote work yourself.
papaf 7y ago
which is a parser combinator library, and it was way easier I like parser combinators but a word of warning. A lot of parser combinators (not all) have problems with recursive grammar such as Json and SQL [1]. For instance, a JSON map can contain a JSON map and this can lead to stack overflows when defining the grammar. [1] https://fsharpforfunandprofit.com/posts/understanding-parser-combinators-4/#5-parsing-array https://fsharpforfunandprofit.com/posts/understanding-parser...
- throwlaplace 7y ago
  thanks for the link will take a look. like i said i don't have that much experience.

userbinator 7y ago

It's recursive-descent --- a pretty common and intuitive way to write a parser in general.