Building an LL(1) SQL Parser in Go

In this article we introduce how to construct an LL(1) parser in Go for parsing SQL queries, covering tokenisation, AST creation, and a finite‑state‑machine driven parsing strategy.

Abstract

The goal is to build a lightweight parser that can handle sub‑selects, functions, nested expressions and other common SQL features using a straightforward approach.

1‑minute theory

A parser consists of two parts:

Lexical analysis (the tokeniser)

Syntax analysis (AST creation)

Lexical analysis

Tokenising the query "SELECT id, name FROM 'users.csv'" yields the following tokens:

SELECT id , name FROM 'users.csv'

The tokeniser result is represented as:

[]string{"SELECT", "id", ",", "name", "FROM", "'users.csv'"}

Syntax analysis

Parsing the tokens creates a structured query object:

query{
Type: "Select",
TableName: "users.csv",
Fields: ["id", "name"]
}

If parsing fails at any step, the process stops and returns an error.

Strategy

We define a parser struct and use a step‑based finite‑state‑machine (FSM) to drive the parsing flow.

type parser struct {
sql   string // The query to parse
i     int    // Current position in the query
query query.Query // The query struct we build
step  step   // Current parsing step
}

The main parsing loop looks like:

func (p *parser) Parse() (query.Query, error) {
p.step = stepType // initial step
for p.i < len(p.sql) {
nextToken := p.peek()
switch p.step {
case stepType:
switch nextToken {
case "UPDATE":
p.query.type = "UPDATE"
p.step = stepUpdateTable
// other cases ...
}
// other step cases ...
}
p.pop()
}
return p.query, nil
}

Peek() implementation

func (p *parser) peek() string {
peeked, _ := p.peekWithLength()
return peeked
}

func (p *parser) pop() string {
peeked, len := p.peekWithLength()
p.i += len
p.popWhitespace()
return peeked
}

Reserved words and token detection are handled by:

var reservedWords = []string{ "(", ")", ">=", "<=", "!=", ",", "=", ">", "<", "SELECT", "INSERT INTO", "VALUES", "UPDATE", "DELETE FROM", "WHERE", "FROM", "SET", }

The full peekWithLength() function scans for reserved words, quoted strings, or identifiers.

func (p *parser) peekWithLength() (string, int) {
if p.i >= len(p.sql) { return "", 0 }
for _, rWord := range reservedWords {
token := p.sql[p.i:min(len(p.sql), p.i+len(rWord))]
if strings.ToUpper(token) == rWord { return rWord, len(rWord) }
}
if p.sql[p.i] == '\'' { return p.peekQuotedStringWithLength() }
return p.peekIdentifierWithLength()
}

Final validation

Implement a parser.validate() method to ensure the built query struct is complete, returning an error if not.

Table‑driven tests in Go can verify the parser behavior:

type testCase struct {
Name string // description of the test
SQL string // input sql e.g. "SELECT a FROM 'b'"
Expected query.Query // expected resulting query struct
Err error // expected error result
}

Running the test suite checks for proper error handling and correct query construction.

Deeper understanding

This experiment is suitable for learning LL(1) parsing algorithms and customizing simple grammars without external dependencies, though more complex expressions may require richer parsing techniques such as parser combinators or tools like goyacc .

Full source code is available at http://github.com/marianogappa/sqlparser .