vartan

vartan is an LALR(1) parser generator for golang. vartan also provides a command to perform syntax analysis to allow easy debugging of your grammar.

Installation

Compiler:

$ go install github.com/nihei9/vartan/cmd/vartan@latest

Code Generator:

$ go install github.com/nihei9/vartan/cmd/vartan-go@latest

Usage

1. Define your grammar

vartan uses BNF-like DSL to define your grammar. As an example, let's write a grammar that represents a simple expression.

#name expr;

#prec (
	#left mul div
	#left add sub
);

expr
	: expr add expr
	| expr sub expr
	| expr mul expr
	| expr div expr
	| func_call
	| int
	| id
	| l_paren expr r_paren #ast expr
	;
func_call
	: id l_paren args r_paren #ast id args
	| id l_paren r_paren      #ast id
	;
args
	: args comma expr #ast args... expr
	| expr
	;

ws #skip
	: "[\u{0009}\u{0020}]+";
int
	: "0|[1-9][0-9]*";
id
	: "[A-Za-z_][0-9A-Za-z_]*";
add
	: '+';
sub
	: '-';
mul
	: '*';
div
	: '/';
l_paren
	: '(';
r_paren
	: ')';
comma
	: ',';

Save the above grammar to a file in UTF-8. In this explanation, the file name is expr.vartan.

⚠️ The input file must be encoded in UTF-8.

2. Compile the grammar

Next, generate a parsing table using vartan compile command.

$ vartan compile expr.vartan -o expr.json

3. Debug

3.1. Parse

If you want to make sure that the grammar behaves as expected, you can use vartan parse command to try parse without implementing a driver.

⚠️ An encoding that vartan parse command and the driver can handle is only UTF-8.

$ echo -n 'foo(10, bar(a)) + 99 * x' | vartan parse expr.json
expr
├─ expr
│  └─ func_call
│     ├─ id "foo"
│     └─ args
│        ├─ expr
│        │  └─ int "10"
│        └─ expr
│           └─ func_call
│              ├─ id "bar"
│              └─ args
│                 └─ expr
│                    └─ id "a"
├─ add "+"
└─ expr
   ├─ expr
   │  └─ int "99"
   ├─ mul "*"
   └─ expr
      └─ id "x"

When vartan parse command successfully parses the input data, it prints a CST or an AST (if any).

3.2. Resolve conflicts

vartan compile command also generates a report named *-report.json. This file describes each state in the parsing table in detail. If your grammar contains conflicts, see Conflicts and States sections of this file. Using vartan show command, you can see the report in a readable format.

$ vartan show expr-report.json

4. Test

vartan test command allows you to test whether your grammar recognizes an input text as a syntax tree with an expected structure. To do so, you need to define a test case as follows.

This is an example.
---
a / b * 100
---
(expr
	(expr
		(expr (id 'a'))
		(div '/')
		(expr (id 'b')))
	(mul '*')
	(expr (int '100')))

The test case consists of a description, an input text, and a syntax tree you expect. Each part is separated by the delimiter ---. The syntax tree is represented by the syntax like an S-expression.

A text of a token is represented by a string enclosed in ' or ". Within "...", characters can alose be represented by Unicode code points (for instance, \u{000A} is LF).

Save the above test case to test.txt file and run the following command.

$ vartan test expr.vartan test.txt
Passed test.txt

When you specify a directory as the 2nd argument of vartan test command, it will run all test cases in the directory.

5. Generate a parser

Using vartan-go command, you can generate a source code of a parser to recognize your grammar.

$ vartan-go expr.json

Then you will get the following files.

• expr_parser.go
• expr_lexer.go
• expr_semantic_action.go

You need to implement a driver to use the parser. An example is below.

package main

import (
	"fmt"
	"io"
	"os"
)

func main() {
	toks, err := NewTokenStream(os.Stdin)
	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}
	gram := NewGrammar()
	tb := NewDefaultSyntaxTreeBuilder()
	p, err := NewParser(toks, gram, SemanticAction(NewASTActionSet(gram, tb)))
	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}
	err = p.Parse()
	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}
	synErrs := p.SyntaxErrors()
	if len(synErrs) > 0 {
		for _, synErr := range synErrs {
			printSyntaxError(os.Stderr, synErr, gram)
		}
		os.Exit(1)
	}
	fmt.Println("accepted")
	PrintTree(os.Stdout, tb.Tree())
}

func printSyntaxError(w io.Writer, synErr *SyntaxError, gram Grammar) {
	var msg string
	tok := synErr.Token
	switch {
	case tok.EOF():
		msg = "<eof>"
	case tok.Invalid():
		msg = fmt.Sprintf("'%v' (<invalid>)", string(tok.Lexeme()))
	default:
		if term := gram.Terminal(tok.TerminalID()); term != "" {
			msg = fmt.Sprintf("'%v' (%v)", string(tok.Lexeme()), term)
		} else {
			msg = fmt.Sprintf("'%v'", string(tok.Lexeme()))
		}
	}
	fmt.Fprintf(w, "%v:%v: %v: %v", synErr.Row+1, synErr.Col+1, synErr.Message, msg)

	if len(synErr.ExpectedTerminals) > 0 {
		fmt.Fprintf(w, ": expected: %v", synErr.ExpectedTerminals[0])
		for _, t := range synErr.ExpectedTerminals[1:] {
			fmt.Fprintf(w, ", %v", t)
		}
	}

	fmt.Fprintf(w, "\n")
}

Please save the above source code to main.go and create a directory structure like the following.

/project_root
├── expr_parser.go
├── expr_lexer.go
├── expr_semantic_action.go
└── main.go (the driver you implemented)

Now, you can perform the syntax analysis.

$ echo -n 'foo+99' | go run .
accepted
expr
├─ expr
│  └─ id "foo"
├─ add "+"
└─ expr
   └─ int "99"

$ echo -n 'foo+99?' | go run .
1:7: unexpected token: '?' (<invalid>): expected: <eof>, add, sub, mul, div
exit status 1

Vartan syntax

Grammar name

A grammar name #name <Identifier> is an identifier that represents a grammar name. For now, this identifier is used as a file name generated like <grammar-name>_parser.go.

Production rules

A production rule consists of a non-terminal symbol and sequences of symbols the non-terminal symbol derives. The first production rule will be the start production rule.

Production rule:

<non-terminal-symbol>
	: <alternative-1>
	| <alternative-2>
	| ...
	| <alternative-N>
	;

or

<terminal-symbol>
	: <pattern-or-string-literal>
	;

Alternative:

<element-1> <element-2> ... <element-N>

An element an alternative contains is a terminal symbol or a non-terminal symbol.

If a production rule satisfies all of the following conditions, it is considered to define a terminal symbol.

• A rule has only one alternative.
• The alternative has only one pattern or string literal.

Fragment:

fragment <terminal-symbol>
	: <pattern-or-string>
	;

Using the fragment keyword, you can also define a fragment that represents a part of a pattern. You can use a fragment by embedding it into a pattern like "\f{some_fragment}".

Types

Identifier

An identifier is a string that satisfies all of the following rules:

• Contains only the lower-case letters (a-z), the digits (0-9), and the underscore (_).
• The first letter is only the lower-case letters.
• The last letter is only the lower-case letters or the digits.

examples:

expression, if_statement, parameter1

Pattern

A pattern is a string enclosed with " and represents a regular expression. A pattern that appears in production rules is used in lexical analysis. For more information on the syntax of regular expressions, please see Regular Expression.

examples:

"if", "\+", "[A-Za-z_][0-9A-Za-z_]*", [\u{0009}\u{0020}]+

String literal

A string literal is a string enclosed with '. A string literal is interpreted literally, not as a regular expression.

examples:

'if', '+', '=='

Directives for non-terminal symbols

#ast {<symbol-or-label: Identifier>}

A #ast directive allows you to define a structure of an AST (Abstract Syntax Tree).

example 1:

Consider a grammar that accepts comma-separated list of integers. You can avoid including brackets and commas in an AST by specifying only the necessary symbols int the #ast directive parameters. Also, you can flatten an AST using ... operator. ... operator expands child nodes of a specified symbol.

#name example;

list
	: l_bracket elems r_bracket #ast elems...
	;
elems
	: elems comma int #ast elems... int
	| int
	;

ws #skip
	: "[\u{0009}\u{0020}]+";
l_bracket
	: '[';
r_bracket
	: ']';
comma
	: ',';
int
	: "0|[1-9][0-9]*";

The above grammar generates an AST as follows:

$ echo -n '[1, 2, 3]' | vartan parse example.json
list
├─ int "1"
├─ int "2"
└─ int "3"

example 2:

Consider a grammar that accepts ternary-if expression (<condition> ? <value if true> : <value if false>). As this grammar contains two int symbols, you need to add labels to each symbol to distinguish them. A label consists of @ + an identifier.

#name example;

if_expr
	: id q int@true colon int@false #ast id true false
	;

ws #skip
	: "[\u{0009}\u{0020}]+";
q
	: '?';
colon
	: ':';
id
	: "[a-z_][0-9a-z_]*";
int
	: "0|[1-9][0-9]*";

The above grammar generates an AST as follows:

$ echo -n 'x? 0 : 99' | vartan parse example.json
if_expr
├─ id "x"
├─ int "0"
└─ int "99"

Labels are intended to identify elements in directives. An AST doesn't contain labels.

#prec <symbol: Identifier>

A #prec directive gives alternatives the same precedence as symbol.

See Operator precedence and associativity section for more details on the #prec directive.

#recover

A parser transitions to an error state when an unexpected token appears. By default, the parser recovers from the error state when it shifts three tokens after going to the error state.

When the parser reduces a