5 ms·

Does anyone know anything like this, but for an indentation-based language? Writing a Python-like parser was always hard for me, ending up with a generic INDENT

Does anyone know anything like this, but for an indentation-based language? Writing a Python-like parser was always hard for me, ending up with a generic INDENT/DEDENT counter mess.

andai 7y ago
I wrote a simple excel formula parser a while ago, and I used a counter too -- just for parentheses. Your comment made me realize I might have been going about it the hard way.
LessDmesg 7y ago
Pypy seems to be reasonably well-documented: http://doc.pypy.org/en/latest/parser.html http://doc.pypy.org/en/latest/parser.html https://bitbucket.org/pypy/pypy/raw/b7b76322a4a7f53db98a883daba13080ae882500/pypy/interpreter/pyparser/pyparse.py https://bitbucket.org/pypy/pypy/raw/b7b76322a4a7f53db98a883d...
Jaxan 7y ago
Edward Kmett has a talk about parsing with monoids [0]. Somehow that seems an elegant way of doing layout based syntax. I have never done it myself, though. [0] https://www.youtube.com/watch?v=Txf7swrcLYs https://www.youtube.com/watch?v=Txf7swrcLYs
gnulinux 7y ago
You need to use the "lexer trick". While lexing your input data, instead of ignoring whitespace or producing token WS or TAB or whatever, keep track of your indents and newlines. Then it's simple to decide if it's an indent (newline followed by at least 1 more space or tab than previous, add this to your indents stack) or dedent (newline followed by the previous indent (look at your indent stack)). Then produce INDENT and DEDENT seperate tokens. Once you have these tokens produced by tokenizer, it's easy to parse. Do the usual recursive descent. Source: I built my own python compiler (python->C++) as a university projects.
- tomp 7y ago
  Pretty much this. You need a stack because an single NEWLINE might result in 2 DEDENT tokens: if x: if y: f() g() You only need to keep track of whitespace (spaces and/or tabs) after a newline (and you can skip lines with only whitespace & comments). It's also useful to keep tracks of delimiters (like parentheses and brackets), if you want to ignore newlines/indents inside expressions (like Python). The easiest IMO is writing a lexer using a lexer generator (Lex, Flex, ...) and outputting a NEWLINE(spaces) tokens, then have another class that keeps track of indents, parentheses, etc. I wrote a lexer/parser combo that (1) tracks whitespace in top (file) context, (2) ignores whitespace in expressions (parentheses, [] arrays, {} records), except (3) restarts indentation-tracking in {} blocks (even if they're in parentheses themselves!) - now that's hard to code (and debug LOL).
piinbinary 7y ago
The trick used by some parsec parsers is interesting. Instead of trying to keep track of balanced indents and unindents, they just check the intent of the first token of a statement. If it's not the "right" indent, the parse fails. When that happens, it usually ends the current block and tries again with the next indent level. It's not that inefficient because the backtracking happens on the first token of the statement. https://hackage.haskell.org/package/indents https://hackage.haskell.org/package/indents

Does anyone know anything like this, but for an indentation-based language? Writing a Python-like parser was always hard for me, ending up with a generic INDENT/DEDENT counter mess.

andai 7y ago

I wrote a simple excel formula parser a while ago, and I used a counter too -- just for parentheses. Your comment made me realize I might have been going about it the hard way.

LessDmesg 7y ago

Pypy seems to be reasonably well-documented: http://doc.pypy.org/en/latest/parser.html http://doc.pypy.org/en/latest/parser.html https://bitbucket.org/pypy/pypy/raw/b7b76322a4a7f53db98a883daba13080ae882500/pypy/interpreter/pyparser/pyparse.py https://bitbucket.org/pypy/pypy/raw/b7b76322a4a7f53db98a883d...

Jaxan 7y ago

Edward Kmett has a talk about parsing with monoids [0]. Somehow that seems an elegant way of doing layout based syntax. I have never done it myself, though. [0] https://www.youtube.com/watch?v=Txf7swrcLYs https://www.youtube.com/watch?v=Txf7swrcLYs

gnulinux 7y ago

You need to use the "lexer trick". While lexing your input data, instead of ignoring whitespace or producing token WS or TAB or whatever, keep track of your indents and newlines. Then it's simple to decide if it's an indent (newline followed by at least 1 more space or tab than previous, add this to your indents stack) or dedent (newline followed by the previous indent (look at your indent stack)). Then produce INDENT and DEDENT seperate tokens. Once you have these tokens produced by tokenizer, it's easy to parse. Do the usual recursive descent. Source: I built my own python compiler (python->C++) as a university projects.

tomp 7y ago
Pretty much this. You need a stack because an single NEWLINE might result in 2 DEDENT tokens: if x: if y: f() g() You only need to keep track of whitespace (spaces and/or tabs) after a newline (and you can skip lines with only whitespace & comments). It's also useful to keep tracks of delimiters (like parentheses and brackets), if you want to ignore newlines/indents inside expressions (like Python). The easiest IMO is writing a lexer using a lexer generator (Lex, Flex, ...) and outputting a NEWLINE(spaces) tokens, then have another class that keeps track of indents, parentheses, etc. I wrote a lexer/parser combo that (1) tracks whitespace in top (file) context, (2) ignores whitespace in expressions (parentheses, [] arrays, {} records), except (3) restarts indentation-tracking in {} blocks (even if they're in parentheses themselves!) - now that's hard to code (and debug LOL).

piinbinary 7y ago

The trick used by some parsec parsers is interesting. Instead of trying to keep track of balanced indents and unindents, they just check the intent of the first token of a statement. If it's not the "right" indent, the parse fails. When that happens, it usually ends the current block and tries again with the next indent level. It's not that inefficient because the backtracking happens on the first token of the statement. https://hackage.haskell.org/package/indents https://hackage.haskell.org/package/indents