4
$\begingroup$

I have the following context-free grammar:

program   := statement*
statement := expression ';' | loop | if
if        := "if" expression block ("else if" block)* ("else" block )?
loop      := "while" expression block
block     := "{" expression* "}"
...

However, I'd like it to be based on indentation (like YAML and python) and not use curly braces. How to I adapt this grammar to support indentation?

Or if it is not possible, why not?

$\endgroup$
2
  • 1
    $\begingroup$ Not enough for an answer, but I swear I've heard of a method for preprocessing indent levels into bracket-equivalent tokens. $\endgroup$ May 21, 2023 at 20:03
  • 1
    $\begingroup$ The answer to this is kind of unhelpful ─ you replace { with INDENT and } with DEDENT, and make no other changes to the grammar. The hard part is changing the lexer to output the INDENT and DEDENT tokens as appropriate. I have an example in the lexer for my language MJr, which is written in Typescript, if that helps: github.com/kaya3/MJr/blob/main/src/frontend/tokenizer.ts#L309 $\endgroup$
    – kaya3
    May 21, 2023 at 20:14

1 Answer 1

8
$\begingroup$

Following the example of Haskell and Python, keep using braces in the context-free grammar. (Python uses the names “INDENT” and “DEDENT”, and keeps “NEWLINE” as a token, but the concept is the same.) Have the lexer generate pseudo-braces (xxDENT tokens) from the indentation (the layout rules in Haskell, the indentation rules in Python.

The lexer keeps track of all open indentation levels in order to know how many pseudo-braces to generate. It inserts an opening-brace (INDENT) token at the beginning of each line that is more indented than its predecessor, and as many closing-brace (DEDENT) tokens as indentation levels that are removed compared to the predecessor. For example, in the snippet below, I've indicated the indentation level table after each line and the tokens emitted for the line:

Code        | Indentation table | Tokens
------------+-------------------+------------
foo         | ()                | foo
  bar       | (2)               | { foo
   corge    | (2, 3)            | { corge
     qux    | (2, 3, 5)         | { qux
  baz       | (2)               | } } baz
goo         | ()                | } goo

Determining these indentation levels can't be done with a pure stack automaton, and in particular determining that there is no invalid indentation is not context free. Intuitively speaking, knowing whether a line's indentation is valid requires knowing multiple previous lines' indentation without knowing in advance which line will be relevant, which would take up the automaton's stack, and that doesn't leave room for everything else you want to parse.

$\endgroup$
1
  • 1
    $\begingroup$ Something important to add, if you're going for Python-like syntax, is that you have to stop tracking indentation changes inside brackets (parens, square brackets, and braces) because expressions inside brackets are allowed to have arbitrary indentation. So the lexer also needs a stack or counter of brackets to know if it's currently lexing inside brackets, and if so, not update the indentation stack. $\endgroup$
    – kaya3
    May 21, 2023 at 22:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .