Converting an indentation-sensitive language into a parse tree

[ghost]

Did I already mention that I simply love PEGTL? It has saved me tonnes of time! However, I'm recently having a problem with parsing an indentation-sensitive language very similar to Haskell. How would one go to tackle this particular problem in a "neat" way?

One naive solution I thought of is by replacing every (hidden) occurrence of eol in the grammar with indent_reset and every (hidden) occurrence of blank with indent_increment, but I'm having a feeling it can be done better. Moreover, I'm having problems applying this solution with the code living on the master branch, so if this is the way to go I'll probably have to file a separate issue.

[ghost]

I went on to hack the source in order to force bump.hpp to keep track of the indentation level. Will keep you updated.

[ghost]

Never mind; I just went on to learn from this answer that relying on "global" state using a PEG parser can cause unwanted side-effects. Will have to find another tool that can handle the job 😢

[ColinH]

While the expressive power of PEGs can be a limit, the PEGTL allows for arbitrary custom rules with arbitrary state which can basically parse "everything"; perhaps we can add an example for an indentation-sensitive grammar to the PEGTL.

[ghost]

@ColinH Oh really, even with location-dependant indentation? Then my reasoning was wrong! Would love to see such an example. Would make it myself but that's where the problem lies. 😅 Maybe a a very basic Python-ish language, if I may make a suggestion?

[ColinH]

Is it possible to see the source and/or specification for the language you are trying to parse? We don't have any experience with designing PEGTL grammars for indentation-aware languages yet, and the toy example I just wanted to implement seems to be too simple, it doesn't really pose any problem. (Global state with a stack of indentation scopes; the rule for every line starts with star< one< ' ' >> which has an action that compares the number of spaces to the entries on the stack and adds/erases as appropriate).

Speaking of a global parser state, that can be a general issue with PEGs; in the case of the PEGTL this role is taken by the state variables passed to the PEGTL parse() function (which can change, but can still be conceptually seen as global state). Our usual approach is to minimise backtracking in the grammar, and to carefully choose where to attach the actions, in a way that actions never have to be undone.

[ColinH]

I just added an (improved over yesterday's version) example for how one could handle a Python-style indentation aware grammar in src/example/pegtl/indent_aware.cpp. For now the code is not particularly elegant, but it does seem to work for the very simplified language that it is intended to recognise, including the check for whether an else has a matching preceding if.