4 ms·

Very interested in seeing how he'll deal with lexing Haskell. It's a major pain, tools like Parsec are very good out of the box with whitespace insensitivity, b

by rtpg 12y ago

Very interested in seeing how he'll deal with lexing Haskell. It's a major pain, tools like Parsec are very good out of the box with whitespace insensitivity, but not whitespace sensitive stuff.

dllthomas 12y ago
I suppose using haskell-src-exts is cheating...
- rtpg 12y ago
  "I will build haskell by taking the source code and running it" I jest, but this is an issue I've thought about idly for a while. Maybe it's possible to write a two-step parser: one that turns chars into tokens (and cheat a little bit by stripping spaces in some contexts to make it context free), and then you have a nice CFG that you can do easily.
  - eru 12y ago
    See eg http://michaeldadams.org/papers/layout_parsing/ http://michaeldadams.org/papers/layout_parsing/
  - dllthomas 12y ago
    I once took a compiler design course where the instructor said we could use whatever language we wanted (it was a tiny class - I think there were 8 of us?). I asked whether I could use bash, and consider gcc a feature of the language. I was informed that would be cheating.
cfallin 12y ago
IIRC, Haskell has a well-defined mapping of whitespace to explicit braces and semicolons -- I suppose one could perform that transform first to desugar, then parse the resulting token stream normally...
- cardiffspaceman 12y ago
  If you think of well-defined as combining the most subtle aspects of Javascript semicolons and Python braces, I agree. As hobby projects, I have coded a significant fraction of a Haskell parser and a majority of a Python parser. It was good I did the Python one first. The Haskell rules include a clause which says if you don't yet have a syntax error from your tokens, and you have a syntax error by adding the next token, and you would not have a syntax error if you added first a closing brace and then the next token, then insert the corrective closing brace. So you can't just tokenize, infer what's missing, then parse the tokens.
orbifold 12y ago
Its not that hard to implement some form of whitespace sensitive parsing, you need to maintain explicit state, essentially a stack and a number of combinators. See for example https://github.com/purescript/purescript/blob/master/src/Language/PureScript/Parser/Common.hs https://github.com/purescript/purescript/blob/master/src/Lan... The state is defined in https://github.com/purescript/purescript/blob/master/src/Language/PureScript/Parser/State.hs https://github.com/purescript/purescript/blob/master/src/Lan... (its just the column number). I believe the whitespace rules for Haskell are somewhat subtle, but shouldn't be much harder.
- purescript 12y ago
  I tried to change the whitespace rules in the PureScript parser to match Haskell recently (to support explicit braces), and it proved to be very difficult. The "L" function which is defined in the Haskell 98 Report depends heavily on an interaction between the lexer and parser, in which a failed parse causes the indenter to behave differently in the lexer. For this reason, I stayed with the simpler rules that we have now, and I plan to support explicit braces in the parser instead.

by rtpg 12y ago

Very interested in seeing how he'll deal with lexing Haskell. It's a major pain, tools like Parsec are very good out of the box with whitespace insensitivity, but not whitespace sensitive stuff.

dllthomas 12y ago

I suppose using haskell-src-exts is cheating...

rtpg 12y ago
"I will build haskell by taking the source code and running it" I jest, but this is an issue I've thought about idly for a while. Maybe it's possible to write a two-step parser: one that turns chars into tokens (and cheat a little bit by stripping spaces in some contexts to make it context free), and then you have a nice CFG that you can do easily.
- eru 12y ago
  See eg http://michaeldadams.org/papers/layout_parsing/ http://michaeldadams.org/papers/layout_parsing/
- dllthomas 12y ago
  I once took a compiler design course where the instructor said we could use whatever language we wanted (it was a tiny class - I think there were 8 of us?). I asked whether I could use bash, and consider gcc a feature of the language. I was informed that would be cheating.

cfallin 12y ago

IIRC, Haskell has a well-defined mapping of whitespace to explicit braces and semicolons -- I suppose one could perform that transform first to desugar, then parse the resulting token stream normally...

cardiffspaceman 12y ago
If you think of well-defined as combining the most subtle aspects of Javascript semicolons and Python braces, I agree. As hobby projects, I have coded a significant fraction of a Haskell parser and a majority of a Python parser. It was good I did the Python one first. The Haskell rules include a clause which says if you don't yet have a syntax error from your tokens, and you have a syntax error by adding the next token, and you would not have a syntax error if you added first a closing brace and then the next token, then insert the corrective closing brace. So you can't just tokenize, infer what's missing, then parse the tokens.

orbifold 12y ago

Its not that hard to implement some form of whitespace sensitive parsing, you need to maintain explicit state, essentially a stack and a number of combinators. See for example https://github.com/purescript/purescript/blob/master/src/Language/PureScript/Parser/Common.hs https://github.com/purescript/purescript/blob/master/src/Lan... The state is defined in https://github.com/purescript/purescript/blob/master/src/Language/PureScript/Parser/State.hs https://github.com/purescript/purescript/blob/master/src/Lan... (its just the column number). I believe the whitespace rules for Haskell are somewhat subtle, but shouldn't be much harder.

purescript 12y ago
I tried to change the whitespace rules in the PureScript parser to match Haskell recently (to support explicit braces), and it proved to be very difficult. The "L" function which is defined in the Haskell 98 Report depends heavily on an interaction between the lexer and parser, in which a failed parse causes the indenter to behave differently in the lexer. For this reason, I stayed with the simpler rules that we have now, and I plan to support explicit braces in the parser instead.