4 ms·

This is really interesting for me personally because I just completed writing an interpreter in Golang and it's great to compare and contrast. One thing I noti

by throwaway2016a 9y ago

This is really interesting for me personally because I just completed writing an interpreter in Golang and it's great to compare and contrast. One thing I noticed is that the parser is hand written. Which is interesting. I always preferred to write my parsers in Yacc and Go actually has Yacc as a built in tool (although know Lex). Edit: I went through the list someone else posted and only one of the implementations actually has a Yacc grammar file in it.

villedepommes 9y ago
> Go actually has Yacc as a built in tool (although know Lex). Interesting. Did they combine both a lexer and a parser into one tool? lex,flex, and re2c are typically standalone tools (lexers) that tokenize input, whereas yacc and bison are parsers that parse those tokens into ASTs (usually).
- throwaway2016a 9y ago
  > Did they combine both a lexer and a parser into one tool? No. They give you an interface definition for the lexer and you can implement the methods however you see fit as long as it matches the interface. Which I found annoying as there are some tedious parts to writing a lexer as soon as you have a language requiring multi-rune tokens with common prefixes.[1] Apparently the back story is that go needed a parser generator but they didn't need a lexer so they only built just the one out of necessity. I read some places that they would welcome pull requests for a lex/flex equivalent. [1] A `rune` in GoLang is like a `char` in C only it stores multi-byte characters where as in C it is more analogous to a single `byte`
  - hnlmorg 9y ago
    For clarity (I know you know what a rune is but your description felt a little misleading imo): A rune is just an alias for int32. But it's context usually means unicode chars which are indeed multi-byte. You can still use byte arrays (or "slice" if you're writing idiomatic Go, but that's another tangent again) too though. Also "byte" in Go is another alias, but for int8. But that shouldn't come as a surprise to anyone :)
    - throwaway2016a 9y ago
      Thank you for the clarification. Your explanation will be helpful to people. I wasn't planning on going into that technical detail, I was focused more on typical usage.
rufius 9y ago
For my own toy compilers/interpreters, I basically always hand-roll my parsers. The only exception to that is when the purpose of building the compiler in the first place is to use a library like Parsec or FParsec. That said - many languages I dabble in are variants on Forths or Lisps where parsing is easy comparatively.
userbinator 9y ago
Recursive descent is easy to reason about, debug, and generate useful error messages with, and doesn't require learning another DSL and its accompanying theory. While LL parsing is theoretically less powerful than LR, one only has to look at the parsers used for complex languages like C++ and Perl to see that this isn't a problem in practice.
pebers 9y ago
It's not actually a built-in tool any more: https://beta.golang.org/doc/go1.8#tool_yacc https://beta.golang.org/doc/go1.8#tool_yacc For posterity, it's moved to https://godoc.org/golang.org/x/tools/cmd/goyacc https://godoc.org/golang.org/x/tools/cmd/goyacc

villedepommes 9y ago

> Go actually has Yacc as a built in tool (although know Lex). Interesting. Did they combine both a lexer and a parser into one tool? lex,flex, and re2c are typically standalone tools (lexers) that tokenize input, whereas yacc and bison are parsers that parse those tokens into ASTs (usually).

throwaway2016a 9y ago
> Did they combine both a lexer and a parser into one tool? No. They give you an interface definition for the lexer and you can implement the methods however you see fit as long as it matches the interface. Which I found annoying as there are some tedious parts to writing a lexer as soon as you have a language requiring multi-rune tokens with common prefixes.[1] Apparently the back story is that go needed a parser generator but they didn't need a lexer so they only built just the one out of necessity. I read some places that they would welcome pull requests for a lex/flex equivalent. [1] A `rune` in GoLang is like a `char` in C only it stores multi-byte characters where as in C it is more analogous to a single `byte`
- hnlmorg 9y ago
  For clarity (I know you know what a rune is but your description felt a little misleading imo): A rune is just an alias for int32. But it's context usually means unicode chars which are indeed multi-byte. You can still use byte arrays (or "slice" if you're writing idiomatic Go, but that's another tangent again) too though. Also "byte" in Go is another alias, but for int8. But that shouldn't come as a surprise to anyone :)
  - throwaway2016a 9y ago
    Thank you for the clarification. Your explanation will be helpful to people. I wasn't planning on going into that technical detail, I was focused more on typical usage.

rufius 9y ago

For my own toy compilers/interpreters, I basically always hand-roll my parsers. The only exception to that is when the purpose of building the compiler in the first place is to use a library like Parsec or FParsec. That said - many languages I dabble in are variants on Forths or Lisps where parsing is easy comparatively.

userbinator 9y ago

Recursive descent is easy to reason about, debug, and generate useful error messages with, and doesn't require learning another DSL and its accompanying theory. While LL parsing is theoretically less powerful than LR, one only has to look at the parsers used for complex languages like C++ and Perl to see that this isn't a problem in practice.

pebers 9y ago

It's not actually a built-in tool any more: https://beta.golang.org/doc/go1.8#tool_yacc https://beta.golang.org/doc/go1.8#tool_yacc For posterity, it's moved to https://godoc.org/golang.org/x/tools/cmd/goyacc https://godoc.org/golang.org/x/tools/cmd/goyacc