Parse Indentation-Based Input

Problem. A file nests its entries by indentation, as YAML or Python do, and you want the nesting as Go maps. A line that is indented inconsistently should be reported as that.

PEG has no memory, so the grammar keeps the indentation of the current block in a variable and checks it with predicates.

// nested.pego
type Entry = {
    Key      node[string]
    Value    *node[string]
    Children []Entry
}

var indent int

@start
rule main = {indent := 0} es:block blank* $$ => $es

// The entries at the current indentation.
rule block = v1:(blank* e:entry)+ => map($v1, (x) => x.$e)

// A line indented exactly at the current depth, with the lines below it that are indented deeper.
rule entry Entry = (
    s:spaces {len($s) == indent} @error(message="inconsistent indentation")
    k:key ":" " "* v:value? eol cs:children?
) => Entry{Key: $k, Value: $v, Children: concat($cs)}

// If the next line is indented deeper, read it and its siblings with that depth as the new indentation.
// A variable binding is visible only in the rule that makes it and the rules it calls, so when this rule returns, the
// parent's indentation is back.
rule children = &(blank* s:spaces) {len($s) > indent} {indent := len($s)} b:block => $b

rule spaces = " "* #atomic
rule key = [a-z_]+ #atomic
rule value = [^\n]+ #atomic
rule eol = "\n" / $$
rule blank = [ \t]* "\n"

// main.go
package main

import (
	_ "embed"
	"encoding/json"
	"fmt"
	"log"
	"os"

	"github.com/ornew/pego"
)

//go:embed nested.pego
var grammar string

// toMap turns entries into nested maps: an entry with children becomes a map, any other a string.
func toMap(entries *pego.Node) map[string]any {
	m := map[string]any{}
	for _, e := range entries.Elems() {
		key := e.Field("Key").(*pego.Node).Text()
		if kids := e.Field("Children").(*pego.Node); kids.Len() > 0 {
			m[key] = toMap(kids)
		} else if v, ok := e.Field("Value").(*pego.Node); ok {
			m[key] = v.Text()
		} else {
			m[key] = ""
		}
	}
	return m
}

func main() {
	log.SetFlags(0) // no time stamps in front of the errors
	p, err := pego.CompileSource(grammar, "main")
	if err != nil {
		log.Fatal(err)
	}
	src, err := os.ReadFile(os.Args[1])
	if err != nil {
		log.Fatal(err)
	}
	tree, err := p.Parse(string(src))
	if err != nil {
		log.Fatal(err)
	}
	out, _ := json.MarshalIndent(toMap(tree), "", "  ")
	fmt.Println(string(out))
}

With this app.yml:

server:
  host: localhost
  port: 8080
  tls:
    cert: server.pem
    key: server.key

log: debug

run it:

go run . app.yml

{
  "log": "debug",
  "server": {
    "host": "localhost",
    "port": "8080",
    "tls": {
      "cert": "server.pem",
      "key": "server.key"
    }
  }
}

A line that is indented to a depth that no enclosing block has, in bad.yml:

server:
    host: localhost
  port: 8080

go run . bad.yml

3:3: inconsistent indentation

How It Works

var indent int declares the variable with its type and initial value 0. { indent := 0 } binds it at the start. A predicate { name := value } binds a variable; it never changes one. The definition is visible to the rules called after it, and ends when the rule that made it returns.
entry matches the leading spaces, captures them as s, and the predicate { len($s) == indent } succeeds only at the current depth. This is also how a block ends: at a line with another indentation, entry fails and block's repetition stops.
children looks ahead at the next line with &(blank* s:spaces). A capture made in a positive lookahead stays visible after it, so the predicates can read $s without consuming the spaces. If the line is indented deeper, the new depth is defined with { indent := len($s) }, and the rule block called after it sees the new depth. When children returns, the parent's indent is back: the variable is scoped by the rule invocation, and a counter is a chain of new bindings, never a mutation.
@error on the predicate. A predicate that fails records no expected token, so without the label the message for the third line above is syntax error: expected " ", "\n", [ \t], which is true and unhelpful.
*node[string] for the optional value. v:value? is a node[string] or nothing, which the struct field must say with *node[string]; in Go, Field("Value") is then a *pego.Node or nil, which v, ok := ....(*pego.Node) tells apart.

Variations and Limits

Tabs. This grammar counts only spaces: a tab at the start of a line is a syntax error. To allow tabs, make spaces match them and decide what len should count, or reject them with a message of their own.
Values with structure. Make value a rule of its own (numbers, quoted strings, lists), as in Read a configuration file into Go structs.
Lists and other forms. - item lines are one more alternative of entry at the same indentation.
Cost. A rule that reads a variable is cached per value of the variable, so keep the number of values small (a depth, not a position); see the guide below.
Python and YAML. Their grammars, parsers/python and parsers/yaml, use the same technique at a larger scale.

See Context-sensitive parsing for predicates, variables and lookahead, and examples/outline for the grammar this one is based on.

Parse Indentation-Based Input

#How It Works

#Variations and Limits

How It Works

Variations and Limits