EBNF PGEN

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.

go get github.com/HolliShake/ebnf-pgen

The parser-generator operates in three stages:

┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│  .ebnf file  │ ──► │  GrammarData │ ──► │ source file  │
│  (grammar)   │     │  (indexed)   │     │  (source)    │
└──────────────┘     └──────────────┘     └──────┬───────┘
                                                 │
                                          ┌──────▼───────┐
                                          │   AST Tree   │
                                          │   (output)   │
                                          └──────────────┘

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.

Minimal Example

The integration/ directory contains a complete interactive calculator. 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])  // e.g. "2 + 3 * 4"
    result, _ := eval(ast)
    fmt.Println(result)  // 6
}

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 Grammar Reference

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 in the grammar are rule names or terminal references (e.g., expression, identifier, integer).
• String literals are quoted tokens matched literally against the source (e.g., "+", "fn", "{").
• Comments: C-style /* ... */ block comments are supported.
• 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. This is the recommended way 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:

Terminal	Matches
identifier	Any TokenIDN or TokenKEY (name/identifier)
integer	A TokenINT (integer literal, e.g. 42)
number	A TokenNUM (floating-point literal, e.g. 3.14)
string	A TokenSTR (double-quoted string, e.g. "hello")
epsilon	Always succeeds, consumes nothing
eof	Matches end-of-file

Keyword literals (true, false, null, or any custom keyword registered via the keywords rule) are also matched as terminals as long as they appear in the keywords rule of your grammar.

Quantifiers

Syntax	Name	Meaning
*	Zero-or-more	Matches zero or more repetitions
+	One-or-more	Matches one or more repetitions
?	Optional	Matches zero or one occurrence
!	Not-null	The symbol MUST NOT be epsilon (error if so)

Examples:

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

Special Rules

Rule Name	Purpose
keywords	List of reserved words (scanned as TokenKEY, not TokenIDN)
entrypoint	Explicit start symbol. Falls back to the last rule in the file if absent.

Example:

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

---

API Reference

Public Types

// Token types produced by the lexer.
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
)

// Position tracks line and column (both 1-indexed).
type Position struct {
    Line int
    Colm int
}

// Token represents a single lexical token.
type Token struct {
    Type     TokenType
    Value    string
    Position Position
}

// Ast is the output parse tree node.
// Fields A..E hold child nodes; Next forms linked lists (e.g., statement sequences).
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 identifier/integer/number/string 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 in a list
}

// GrammarData is the indexed grammar used by the parser.
type GrammarData struct {
    EBNF  *EBNFGrammar                 // the raw parsed grammar
    // (internal: rule lookup map)
}

// EBNFGrammar holds all rules parsed from an .ebnf file.
type EBNFGrammar struct {
    Rules []*EBNFRule
}

// EBNFRule is a single production rule.
type EBNFRule struct {
    Name         string
    Alternatives []*EBNFAlternative
}

// EBNFAlternative is one branch of a rule (separated by |).
// Alias renames the AST node produced by this alternative.
type EBNFAlternative struct {
    Symbols []*EBNFSymbol
    Alias   string // optional rename ("as <name>"), empty when absent
}

// EBNFSymbol is a single element in an alternative.
type EBNFSymbol struct {
    Value      string             // identifier name or literal text
    IsLiteral  bool               // true when Value came from a quoted string
    IsGroup    bool               // true when this is a parenthesized group
    Group      []*EBNFAlternative // alternatives inside ( ... )
    Quantifier EBNFQuantifier     // *, +, ?, or none
}

Public Functions

// ParseEBNFFile reads and parses a .ebnf grammar file.
func ParseEBNFFile(path string) (*EBNFGrammar, error)

// ParseEBNF parses EBNF source text directly.
func ParseEBNF(path, src string) (*EBNFGrammar, error)

// Parse parses source text according to the grammar.
func Parse(grammar GrammarData, filePath string, content string) (*Ast, error)

// NewGrammarData builds an indexed GrammarData from a parsed EBNF grammar.
func NewGrammarData(ebnf *EBNFGrammar) GrammarData

// NewTokenizer creates a new tokenizer over source text.
func NewTokenizer(path, src string) *Tokenizer

// RaiseError prints a compiler-style diagnostic with source context.
func RaiseError(path string, content string, pos Position, msg string)

GrammarData Methods

func (g GrammarData) Rule(name string) *EBNFRule  // O(1) rule lookup
func (g GrammarData) KeywordNames() []string        // reserved word list
func (g GrammarData) StartRule() string             // entry-point rule name

Tokenizer Methods

func (t *Tokenizer) RegisterKeyword(word string, tokenType TokenType)
func (t *Tokenizer) Tokenize() []Token

String Methods

func (t TokenType) String() string
func (p Position) String() string
func (t Token) String() string
func (a *Ast) String() string         // pretty-prints the AST
func (g *EBNFGrammar) String() string  // pretty-prints the grammar

---

Writing a Grammar

Full Example: A Mini Language

Below is a realistic grammar that defines a small programming language with functions, classes, enums, control flow, arithmetic, comparisons, and logical expressions.

Grammar (test.ebnf):

keywords :=
    fn | if | else | return
    | enum | class | extends | this | super | new
    | while | for | in | break | continue
    | var | true | false | null
    ;

terminal :=
    identifier | integer | number | string | true | false | null
    ;

primary :=
    "(" expression ")"
    | functionCall
    | memberAccess
    | identifier | number | integer | string | true | false | null
    ;

functionCall := identifier "(" argumentList? ")" ;
argumentList := expression ("," expression)* ;
memberAccess := identifier "." identifier ;

unary :=
    primary
    | "-" unary
    | "!" unary
    ;

multiplicative :=
    unary
    | unary "*" unary | unary "/" unary | unary "%" unary
    ;

additive :=
    multiplicative
    | multiplicative "+" multiplicative | multiplicative "-" multiplicative
    ;

comparison :=
    additive
    | additive "<" additive  | additive ">" additive
    | additive "<=" additive | additive ">=" additive
    | additive "==" additive | additive "!=" additive
    ;

logical :=
    comparison
    | comparison "&&" comparison | comparison "||" comparison
    ;

assignment :=
    identifier "=" assignment | logical
    ;

expression := assignment ;

returnStatement := "return" expression? ";" ;
blockStatement  := "{" statement* "}" ;

ifStatement :=
    "if" "(" expression ")" blockStatement
    | "if" "(" expression ")" blockStatement "else" blockStatement
    ;

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

classDeclaration         := "class" identifier "{" classMember* "}" ;
extendedClassDeclaration := "class" identifier "extends" identifier "{" classMember* "}" ;
classMember              := functionDeclaration | "var" identifier ";" ;

enumDeclaration := "enum" identifier "{" identifier ("," identifier)* "}" ;

statement :=
    functionDeclaration | classDeclaration | extendedClassDeclaration
    | enumDeclaration | ifStatement | returnStatement | expression ";"
    ;

program := statement* eof ;
entrypoint := program;

Source (classes.lang):

class Point {
    var x;
    var y;

    fn move(dx, dy) {
        x = x + dx;
        y = y + dy;
    }
}

Output (AST):

program
  classDeclaration
    identifier "Point"
    identifier "x"
    identifier "y"
    functionDeclaration
      identifier "move"
      parameterList
        identifier "dx"
        identifier "dy"
      assignment
        identifier "x"
        additive
          identifier "x"
          identifier "dx"
      assignment
        identifier "y"
        additive
          identifier "y"
          identifier "dy"

---

Running the Test Suite

A test runner CLI is provided in the integration/ directory of the workspace (../integration relative to this module). It discovers all source files (excluding .ebnf grammar files) in tests/ and parses them against tests/test.ebnf.

cd integration
go run . -test

Example output:

Grammar: 22 rules | Start: "program" | Keywords: [fn if else ...]

  classes                   PASS
  enums                     PASS
  expressions               PASS
  extended_class            PASS
  functions                 PASS

5 passed, 0 failed

Adding New Tests

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 with source context will be shown.

---

Limitations

1. No Left Recursion

The parser uses recursive-descent with a left-recursion guard. Left-recursive rules will silently fail rather than loop infinitely. You must rewrite left-recursive grammars using repetition quantifiers.

❌ Not supported:

expr := expr "+" term | term ;

✅ Use repetition instead:

expr := term ("+" term)* ;

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 obviously-impossible alternatives. This means grammars where two alternatives start with the same token type may cause the parser to pick the wrong branch if the more-specific branch has the same first token as the fallback. The alternative-sorting heuristic (longest-first) mitigates this in most practical cases.

4. Error Recovery is Limited

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

5. No Operator Precedence Built-in

Operator precedence and associativity must be encoded manually in the grammar via rule layering (as shown in the example above). There is no %left / %right / %prec mechanism like in yacc/bison.

6. No Parser Generation (Yet)

Despite the name "parser-generator," the tool does not (yet) generate standalone Go source code for a parser. It is a runtime interpreter that parses source against a grammar loaded at runtime. Code generation is a planned future feature.

7. Keywords are Case-Sensitive

Keyword matching is exact and case-sensitive. If, IF, and if are three different identifiers; only if is recognized as a keyword if registered as such.

8. String Escape Sequences

String literals support standard escape sequences (\n, \t, \\, \", \r, \uXXXX, \UXXXXXXXX). Unrecognized escape sequences produce a lexer error.

9. No Incremental / Partial Parsing

The parser operates on complete source files only. It cannot parse a partial or incrementally-edited buffer and resume.

10. 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 (i.e., rule references or groups — string literals are not counted) will cause a runtime panic. If your rule needs more children, break it 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 ;

11. 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 but means you cannot rely on every grammar rule appearing as a named node:

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

This is by design (it avoids deep nesting of pass-through rules like expression → assignment → logical → comparison → additive), but it means intermediate rule names do not appear in the output tree.

12. 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
}

13. ! 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; it only checks that the symbol actually consumed something.

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

14. 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 either be shoehorned into existing token types or 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 (Rule, KeywordNames, StartRule)
├── 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

---

License

MIT