How does GHC implement layout?

[Sebastian Graf]

Hi Alexis, Hi Iavor,

I'm afraid I'm not particularly acquainted with how GHC implements
indentation-sensitive parsing, but I really like the way in which this book
<https://www.springer.com/gp/book/9783642175398> frames the problem. If you
look at the preview for the first chapter, you'll notice that (they call
the lexer scanner, and) they introduce an additional pass between lexer and
parser that handles the context-sensitive bits about indentation-sensitive
parsing, which doesn't fit well with the parser (which assumes a
context-free grammar to stay sane) or with the lexer (which should better
be just a simple DFA).

In particular, the short section 1.3 about the screener explicitly mentions
Haskell as use case:

[image: 2021-04-05-140820_543x163_scrot.png]
Although that doesn't really explain the how. Maybe section 2.5 (where impl
of screeners is covered) provides more insight into that.
Screeners are a bit like semantic analysis, but on the token stream instead
of the parse tree.

Reach out in private if you want more excerpts.

Cheers,
Sebastian

Am Mo., 5. Apr. 2021 um 00:19 Uhr schrieb Alexis King <lexi.lambda at gmail.com
>:

> On 4/4/21 1:52 PM, Iavor Diatchki wrote:
>
> Hi Alexis,
>
> I wasn't sure what the "alternative layout" is either and did some
> googling, and it appears that it is something that was never really
> documented properly.   The following link contains pointers to the commit
> that introduced it (in 2009!)  (not the main ticket but some of the
> comments)
>
> Thanks, that’s a helpful pointer, though of course it still doesn’t
> explain very much. I’m still interested in understanding what the purpose
> of “alternative layout” is and how it operates, if anyone else has any idea.
>
> Overall, I do think that Haskell's layout rule is more complicated than it
> needs to be, and this is mostly because of the rule that requires the
> insertion of a "virtual close curly" on a parse error.
>
> Yes, this does seem to be by far the trickiest bit. But I’d be sad not to
> have it, as without it, even simple things like
>
> let x = 3 in e
>
> would not be grammatically valid.
>
> My feeling is that it'd be pretty tricky to do layout in the parser with
> grammar rules, but you may be able to do something with the parser state.
>
> Yes, I have some vague ideas, but none of them are particularly fleshed
> out. It’s entirely possible that I just don’t understand the relationship
> between the lexer and the parser (which seems somewhat obscured by the
> “alternative layout” stuff), and the ideas I have are what’s already
> implemented today. I’ll have to study the implementation more closely.
>
> In any case, thank you for your response! The ALR-related pointer
> certainly clarifies at least a little.
>
> Alexis
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20210405/3225db78/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2021-04-05-140820_543x163_scrot.png
Type: image/png
Size: 32946 bytes
Desc: not available
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20210405/3225db78/attachment.png>