<p>I have the following context-free grammar:</p>
<pre><code>program   := statement*
statement := expression ';' | loop | if
if        := &quot;if&quot; expression block (&quot;else if&quot; block)* (&quot;else&quot; block )?
loop      := &quot;while&quot; expression block
block     := &quot;{&quot; expression* &quot;}&quot;
...
</code></pre>
<p>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?</p>
<p>Or if it is not possible, why not?</p>

<parsing><indentation><context-free-grammar>
Context-free grammar for a language where indentation marks code blocks?
CC BY-SA 4.0
2023-05-21T20:03:35.783Z
Not enough for an answer, but I swear I've heard of a method for preprocessing indent levels into bracket-equivalent tokens.
Unrelated String
CC BY-SA 4.0
2023-05-21T20:14:01.430Z
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: https://github.com/kaya3/MJr/blob/main/src/frontend/tokenizer.ts#L309
kaya3
<p>Following the example of <a href="https://www.haskell.org/onlinereport/haskell2010/haskellch10.html#x17-18000010.5" rel="noreferrer">Haskell</a> and <a href="https://docs.python.org/3/reference/compound_stmts.html" rel="noreferrer">Python</a>, 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 <a href="https://www.haskell.org/onlinereport/haskell2010/haskellch10.html#x17-17800010.3" rel="noreferrer">layout rules in Haskell</a>, the <a href="https://docs.python.org/3/reference/lexical_analysis.html#indentation" rel="noreferrer">indentation rules in Python</a>.</p>
<p>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:</p>
<pre><code>Code        | Indentation table | Tokens
------------+-------------------+------------
foo         | ()                | foo
  bar       | (2)               | { foo
   corge    | (2, 3)            | { corge
     qux    | (2, 3, 5)         | { qux
  baz       | (2)               | } } baz
goo         | ()                | } goo
</code></pre>
<p>Determining these indentation levels can't be done with a pure stack automaton, and in particular determining that there is no invalid indentation is <a href="https://cs.stackexchange.com/questions/77989/is-python-a-context-free-language/77992#77992">not context free</a>. 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.</p>

CC BY-SA 4.0
2023-05-21T20:26:33.950Z
2023-05-21T20:26:33.950Z
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-21T22:06:15.450Z
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.
kaya3
# Context-free grammar for a language where indentation marks code blocks?
Posted by: username_0 on 2023-05-21
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?
**Tags:** parsing indentation context-free-grammar
> **Comments:**
> **username_1**: Not enough for an answer, but I swear I've heard of a method for preprocessing indent levels into bracket-equivalent tokens.  
> **username_2**: 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: https://github.com/kaya3/MJr/blob/main/src/frontend/tokenizer.ts#L309  
---
## 1 answers
### Answer by username_3 on 2023-05-21. Score: 9
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.
> **Comments:**
> **username_2** (2023-05-21): 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.  
---
