AST: A small repo to build Abstract Syntax Trees

Community Showcase
1

Hey community,

I created something that I'm really fond of: AST.

Basically, you declare your syntax rules in code and construct a custom abstract syntax tree (AST) from the bottom up.

A small example:


// List -> <List> ',' <Expr>

struct RecNextIsList : Rule {
    
    @NonTerminal
    var recognized : CommaSeparatedexpressions
    
    @Terminal var separator = ","
    
    @NonTerminal
    var next : Expression
    
    func onRecognize(in range: ClosedRange<String.Index>) throws -> some ASTNode {
        recognized.exprs.append(next) // we used left recursion so this is basically O(1)
                                      // note that we own the memory of "recognized"!
        return recognized
    }
    
}

// List -> ''

struct EmptyIsList : Rule {
    
    func onRecognize(in range: ClosedRange<String.Index>) throws -> some ASTNode {
        CommaSeparatedexpressions(exprs: [])
    }
    
}

// List -> <Expr>
// we need this rule because we used left recursion and allow empty lists
// without this rule our lists would have to look like ",a,b,a"

struct ExprIsList : Rule {
    
    @NonTerminal
    var expr : Expression
    
    func onRecognize(in range: ClosedRange<String.Index>) throws -> some ASTNode {
        CommaSeparatedexpressions(exprs: [expr])
    }
    
}

// Expr -> <any characters in our alphabet>

struct CharIsExpr : Rule {
    
    var ruleName: String {
        "Char \(char)" // we need to distinguish the rules for each character
    }
    
    @Terminal var char : Character
    
    func onRecognize(in range: ClosedRange<String.Index>) throws -> some ASTNode {
        Expression(char: char)
    }
    
}

Disadvantage:

  • You can't separate your rules from the code and build parsers in another language like you do with e.g. ANTLR.
  • No standard automatic way to traverse the AST once it's generated.

Advantage:

  • The AST is just a custom object. Once it is fully constructed, you can traverse it just by writing methods.
  • It just looks cool and very swifty.
3 Likes