Overview

The EBNF PGEN is a grammar-driven, recursive-descent parser generator for Go. Define your language in an EBNF (Extended Backus–Naur Form) grammar file, feed it to the parser, and get a working parser that builds an AST for any source file written in that language.

Architecture

The parser-generator operates in three stages:

1. Parse the grammar — ParseEBNFFile("mygrammar.ebnf") reads an .ebnf file and returns an EBNFGrammar AST describing every rule, alternative, symbol, and quantifier.
2. Build GrammarData — NewGrammarData(grammarAST) indexes rules for O(1) lookup, sorts alternatives by specificity (longest-first), and extracts keyword lists for the tokenizer.
3. Parse source code — Parse(gd, "source.txt", content) tokenizes the source, registers keywords, then runs a recursive-descent parser with full backtracking across alternatives (PEG-style ordered choice), producing an Ast tree.

Quick Start

Prerequisites

Go 1.25 or later.

Installation

go get github.com/HolliShake/ebnf-pgen

The integration/ directory contains a complete interactive calculator — it loads a grammar, parses arithmetic expressions, and evaluates the resulting AST. Below is the essence of how it works.

Grammar (calc.ebnf)

keywords := ;

additive := multiplicative addTerm* ;
addTerm  := "+" multiplicative as add | "-" multiplicative as sub ;

multiplicative := unary mulTerm* ;
mulTerm  := "*" unary as mul | "/" unary as div ;

unary  := primary | "-" primary as negate ;

primary := number | integer | group ;
group   := "(" additive ")" ;

entrypoint := additive ;

Go Program — Load, Parse, Walk the AST

package main

import (
    "fmt"
    "os"
    "strconv"

    parser "github.com/HolliShake/ebnf-pgen"
)

func main() {
    grammarAST, _ := parser.ParseEBNFFile("calc.ebnf")
    gd := parser.NewGrammarData(grammarAST)
    ast, _ := parser.Parse(gd, "<input>", os.Args[1])
    result, _ := eval(ast)
    fmt.Println(result)  // e.g. 6 for "2 + 3 * 4"
}

func eval(node *parser.Ast) (float64, error) {
    switch node.Type {
    case "additive":
        r, _ := eval(node.A)
        for t := node.B; t != nil; t = t.Next {
            v, _ := eval(t.A)
            if t.Type == "add" { r += v } else { r -= v }
        }
        return r, nil
    case "multiplicative":
        r, _ := eval(node.A)
        for t := node.B; t != nil; t = t.Next {
            v, _ := eval(t.A)
            if t.Type == "mul" { r *= v } else { r /= v }
        }
        return r, nil
    case "negate":
        v, _ := eval(node.A)
        return -v, nil
    case "integer", "number":
        return strconv.ParseFloat(node.Str, 64)
    }
    return 0, nil
}

Run It

cd integration
go run . "2 + 3 * 4"
# = 6

go run .                # interactive REPL
calc> 2 + 3 * 4
= 6

EBNF Meta-Grammar

The .ebnf file itself is parsed according to this meta-grammar:

grammar     := rule*
rule        := identifier ":=" alternative ( "|" alternative )* ";"
alternative := symbol* ( "as" identifier )?
symbol      := ( identifier | string-literal ) quantifier?
quantifier  := "*" | "+" | "?" | "!"

• Identifiers — rule names or terminal references (e.g., expression, identifier, integer).
• String literals — quoted tokens matched literally against the source (e.g., "+", "fn", "{").
• Comments — C-style /* ... */ block comments are supported anywhere.
• Parentheses — groups can be wrapped in ( ... ) for applying quantifiers to sub-sequences.
• as alias — an alternative may end with as <name> to rename the AST node it produces. Use this to distinguish binary-operator alternatives (e.g., multiplicative "+" multiplicative as add produces an add node instead of the rule name additive).

Built-in Terminals

These terminals are recognized automatically — you do not need to define them in your .ebnf file:

Keyword literals (true, false, null, or any custom keyword registered via the keywords rule) are also matched as terminals.

Quantifiers

parameterList := parameter ("," parameter)* ;
argumentList  := expression ("," expression)* ;
returnType    := ":" typeAnnotation? ;

Special Rules

Public Types

type TokenType int
const (
    TokenIDN TokenType = iota  // identifier (user-defined name)
    TokenKEY                       // keyword (reserved word)
    TokenINT                       // integer literal
    TokenNUM                       // floating-point literal
    TokenSTR                       // string literal
    TokenSYM                       // symbol (operators, punctuation)
    TokenEOF                       // end of file
)

type Position struct {
    Line int
    Colm int
}

type Token struct {
    Type     TokenType
    Value    string
    Position Position
}

type Ast struct {
    Type string    // node type name (matches grammar rule name)
    Pos  Position  // source position of the first token
    Str  string    // literal value for leaf nodes
    A    *Ast      // child 1
    B    *Ast      // child 2
    C    *Ast      // child 3
    D    *Ast      // child 4
    E    *Ast      // child 5
    Next *Ast      // next sibling (linked list for sequences)
}

type GrammarData struct {
    EBNF  *EBNFGrammar
}

type EBNFGrammar  struct { Rules []*EBNFRule }
type EBNFRule    struct { Name string; Alternatives []*EBNFAlternative }
type EBNFAlternative struct {
    Symbols []*EBNFSymbol
    Alias   string // optional rename ("as <name>")
}
type EBNFSymbol struct {
    Value      string
    IsLiteral  bool
    IsGroup    bool
    Group      []*EBNFAlternative
    Quantifier EBNFQuantifier
}

Public Functions

Methods

Writing a Grammar

1. Define Keywords

keywords :=
    fn | if | else | return
    | var | true | false | null
    ;

2. Layer Precedence (Lowest → Highest)

expression  := logical ;
logical     := comparison ("&&" comparison | "||" comparison)* ;
comparison  := additive ("<" additive | "==" additive)* ;
additive    := multiplicative ("+" multiplicative | "-" multiplicative)* ;
multiplicative := unary ("*" unary | "/" unary)* ;
unary       := primary | "-" unary | "!" unary ;
primary     := identifier | integer | number | string | "(" expression ")" ;

Full Walkthrough: Classes & Functions

Grammar Snippet

functionDeclaration :=
    "fn" identifier "(" parameterList? ")" blockStatement ;

parameterList := identifier ("," identifier)* ;

classDeclaration :=
    "class" identifier "{" classMember* "}" ;

extendedClassDeclaration :=
    "class" identifier "extends" identifier "{" classMember* "}" ;

Source

class Animal {
    fn speak() {}
}

class Dog extends Animal {
    fn speak() {
        return "woof";
    }
}

AST Output

program
  classDeclaration
    identifier "Animal"
    functionDeclaration
      identifier "speak"
      blockStatement
  extendedClassDeclaration
    identifier "Dog"
    identifier "Animal"
    functionDeclaration
      identifier "speak"
      returnStatement
        string "woof"

Running the Test Suite

The integration/ directory (in the parent workspace) contains a CLI with a -test flag that discovers all source files (excluding .ebnf grammar files) in tests/ and parses them against tests/test.ebnf.

# Run all tests
cd integration
go run . -test

# Run the pipeline demo (parse test source against test.ebnf)
go run .

# Custom grammar + source files
go run . -grammar ../parser/test.ebnf -source ../parser/test.lang

Adding a New Test

1. Create a new source file in tests/ (any extension except .ebnf).
2. Run go run . -test from integration/.
3. If it passes, you'll see the AST printed. If it fails, a compiler-style error diagnostic appears.

Limitations

1. No Left Recursion

The parser uses recursive-descent with a left-recursion guard. Left-recursive rules silently fail rather than looping infinitely. Rewrite them using repetition quantifiers.

2. No Semantic Actions

The parser only produces an AST. There is no built-in mechanism for attaching semantic actions, type-checking, evaluation, or code generation. You must walk the AST yourself in post-processing.

3. Single-Token Lookahead

The parser uses single-token lookahead to skip impossibly-matching alternatives. Grammars where two alternatives share the same first token may cause incorrect branch selection. The longest-first heuristic mitigates this in most cases.

4. Limited Error Recovery

On a parse error, the parser reports a compiler-style diagnostic and exits. There is no error recovery or resynchronization — it stops at the first error.

5. Manual Precedence Encoding

Operator precedence and associativity must be encoded manually via rule layering. There is no %left / %right mechanism like in yacc/bison.

6. Runtime Interpretation (No Code Generation Yet)

Despite the name "parser-generator," the tool is currently a runtime interpreter — it parses source against a grammar loaded at runtime. Standalone code generation is planned for a future release.

7. Case-Sensitive Keywords

Keyword matching is exact and case-sensitive. If, IF, and if are three different identifiers.

8. Complete Files Only

The parser operates on complete source files. It cannot handle partial or incrementally-edited buffers.

9. Maximum 5 Non-Literal Children per Alternative

The Ast type has exactly five fixed child slots (A through E). Any grammar alternative that produces more than five non-literal children (rule references or groups — string literals are not counted) will cause a runtime panic. Break large rules into smaller sub-rules.

// ❌ Panics: 6 non-literal children (a b c d e f)
bigRule := identifier identifier identifier identifier identifier identifier ;

// ✅ Split into sub-rules
bigRule     := firstThree lastThree ;
firstThree := identifier identifier identifier ;
lastThree  := identifier identifier identifier ;

10. Pass-Through Rule Elimination

When an alternative contains exactly one non-literal symbol, the parser returns that symbol's AST node directly — no wrapper node is created for the parent rule. This keeps the AST clean (avoiding deep nesting of pass-through chains like expression → assignment → logical → …) but means you cannot rely on every grammar rule name appearing as a node type in the output.

// expression := assignment ;   ← no "expression" node in AST!
// The output contains the assignment node directly.

11. Repetition Produces Linked Lists, Not List Nodes

The * and + quantifiers chain repeated elements together via the Next field — a singly-linked list. There is no dedicated "list" wrapper node. To iterate all repetitions, walk node.Next until nil.

for stmt := block.A; stmt != nil; stmt = stmt.Next {
    // process each statement
}

12. ! Means "Not Epsilon", Not Negative Lookahead

Unlike PEG parsers where ! is a negative lookahead predicate (e.g., !"//" means "not followed by //"), the ! quantifier in this parser means "must not match epsilon" — it guards against zero-width matches. It does not look ahead at all.

// ! ensures body is not empty (must match at least one statement)
nonEmptyBody := "{" statement! "}" ;

13. Fixed Token Type System

The tokenizer recognizes exactly 7 token types: TokenIDN, TokenKEY, TokenINT, TokenNUM, TokenSTR, TokenSYM, TokenEOF. There is no mechanism to define custom token types for language-specific constructs like regex literals, heredocs, or template strings. All such constructs must be handled in post-processing.

Project Structure

ebnf-pgen/
├── go.mod                 // module github.com/HolliShake/ebnf-pgen
├── core.go                // Core types: Token, Ast, GrammarData, EBNF AST types
├── token.go               // TokenType, Position, Token helper methods
├── ast.go                 // Ast pretty-printing helpers
├── ebnf.go                // EBNF AST String() methods & GrammarData helpers
├── grammar.go             // EBNF grammar parser (.ebnf → EBNFGrammar)
├── keyword.go             // EBNF keyword constants
├── parser.go              // Grammar-driven language parser (source → AST)
├── error.go               // Compiler-style error diagnostics
├── tokenizer.go           // UTF-8 lexer / tokenizer
├── README.md              // This documentation
├── index.html             // HTML documentation & manual
└── tests/                 // Test fixtures
    ├── test.ebnf          // Grammar for the test suite
    ├── classes.lang
    ├── enums.lang
    ├── expressions.lang
    ├── extended_class.lang
    └── functions.lang

EBNF PGEN — Grammar-driven parsing for Go — MIT License