syntax

Syntactic analysis toolkit, language-agnostic parser generator.

Implements LR and LL parsing algorithms.

You can get an introductory overview of the tool in this article.

Table of Contents

• Installation
• Development
• CLI usage example
• Parser generation
• Language agnostic parser generator
• JavaScript default
• Python plugin
• PHP plugin
• Ruby plugin
• C++ plugin
• C# plugin
• Rust plugin
• Java plugin
• Julia plugin
• Grammar format
• JSON-like notation
• Yacc/Bison notation
• Grammar properties
• Lexical grammar and tokenizer
• Getting list of tokens
• Using custom tokenizer
• Start conditions of lex rules, and tokenizer states
• Access tokenizer from parser semantic actions
• Case-insensitive match
• Working with precedence and associativity
• Associative precedence
• Non-associative precedence
• Handler arguments notation
• Positioned notation
• Named notation
• Capturing location objects
• Parsing modes
• LL parsing
• LR parsing
• LR conflicts
• Conflicts resolution
• Validating grammar
• Module include, and parser events
• Debug mode

Installation

The tool can be installed as an npm module (notice, it's called syntax-cli there):

npm install -g syntax-cli

syntax-cli --help

Development

1. Fork the https://github.com/DmitrySoshnikov/syntax repo
2. Make your changes
3. Make sure npm test passes (add new tests if needed)
4. Submit a PR

NOTE: If you need to implement a Syntax plugin for a new target programming language, address this instruction.

For development from the github repository, run build command to transpile ES6 code:

git clone https://github.com/<your-github-account>/syntax.git
cd syntax
npm install
npm run build

./bin/syntax --help

Or for faster development cycle, one can also use watch command (notice though, it doesn't copy template files, but only transpiles ES6 code; for templates copying you have to use build command):

npm run watch

CLI usage example

./bin/syntax --grammar examples/grammar.lr0 --parse "aabb" --mode lr0 --table --collection

Parser generation

To generate a parser module, specify the --output option, which is a path to the output parser file. Once generated, the module can normally be required, and used for parsing strings based on a given grammar.

Example for the JSON grammar:

./bin/syntax --grammar examples/json.ast.js --mode SLR1 --output json-parser.js

✓ Successfully generated: json-parser.js

Loading as a JS module:

const JSONParser = require('./json-parser');

let value = JSONParser.parse('{"x": 10, "y": [1, 2]}');

console.log(value); // JS object: {x: 10, y: [1, 2]}

Language agnostic parser generator

See this instruction how to implement a new plugin.

JavaScript default

Syntax is language agnostic when it comes to parser generation. The same grammar can be used for parser generation in different languages. Currently Syntax supports JavaScript, Python, PHP, Ruby, C#, Rust, and Java. The target language is determined by the output file extension.

Python plugin

For example, this is how to use the same calculator grammar example to generate parser module in Python:

./bin/syntax -g examples/calc.py.g -m lalr1 -o calcparser.py

The calcparser module then can be required normally in Python for parsing:

>>> import calcparser
>>> calcparser.parse('2 + 2 * 2')
>>> 6

Another example shows how to use parser hooks (such as on_parse_begin, on_parse_end, and other) in Python. They are discussed below in the module include section.

PHP plugin

For PHP the procedure is pretty much the same, take a look at the similar example:

./bin/syntax -g examples/calc.php.g -m lalr1 -o CalcParser.php

The output file contains the class name corresponding to the file name:

<?php

require('CalcParser.php');

var_dump(CalcParser::parse('2 + 2 * 2')); // int(6)

The parser hooks for PHP can be found in this example.

Ruby plugin

Ruby is another target language supported by Syntax. Its calculator example is very similar:

./bin/syntax -g examples/calc.rb.g -m lalr1 -o CalcParser.rb

And also the output file contains the class name corresponding to the file name:

require 'CalcParser.php'

puts CalcParser.parse('2 + 2 * 2') // 6

Ruby's parsing hooks can be found in the following example.

C++ plugin

Syntax has support for modern C++ as a target language. See its calculator example:

./bin/syntax -g examples/calc.cpp.g -m lalr1 -o CalcParser.h

Then callers can use the module as:

#include "CalcParser.h"

using namespace syntax;

...

CalcParser parser;

std::cout << parser.parse("2 + 2 * 2");  // 6
std::cout << parser.parse("(2 + 2) * 2") // 8

Parsing hooks example in C++ format can be found in this example.

C# plugin

Syntax supports as well C# as a target language. See its calculator example:

./bin/syntax -g examples/calc.cs.g -m lalr1 -o CalcParser.cs

Then callers can use the module as:

using SyntaxParser;

...

var parser = new CalcParser();
Console.WriteLine(parser.parse("2 + 2 * 2")); // 6

Parsing hooks example in C# format can be found in this example.

Rust plugin

Rust is a system programming language focusing on efficiency and memory safety. Syntax has support for generating parsers in Rust. See the simple example, and an example of generating an AST with recursive structures.

./bin/syntax -g examples/calc.rs.g -m lalr1 -o lib.rs

Callers can create a crate (called syntax in the example below), which contains the parser, and use it as:

extern crate syntax;

use syntax::Parser;

fn main() {
    let mut parser = Parser::new();

    let result = parser.parse("2 + 2 * 2");
    println!("{:?}", result); // 6
}

Check out README file from rust directory for more information.

Java plugin

Syntax has support for generating LR parsers in Java. See the simple example, and an example of generating an AST with recursive structures.

./bin/syntax -g examples/calc.java.g -m lalr1 -o com/syntax/CalcParser.java

By default Syntax generates parsers in the com/syntax package.

import com.syntax.*;
import java.text.ParseException;

public class SyntaxTest {
  public static void main(String[] args) {

    CalcParser calcParser = new CalcParser();

    try {
      System.out.println(calcParser.parse("2 + 2 * 2")); // 6
      System.out.println(calcParser.parse("(2 + 2) * 2")); // 8
    } catch (ParseException e) {
      e.printStackTrace();
    }
  }
}

Check out README from the Java plugin for more information.

Julia plugin

Julia is a general purpose programming language often used within the scientific computing space. Julia was designed from the beginning for high performance and utilizes LLVM as a compile target. Julia is a dynamically typed functional programming language which relies heavily on the concept of Multiple Dispatch. Syntax has support for generating parsers in Julia. See the simple example, and an example of more complex usage to generate a Vector based AST with recursive structures.

./bin/syntax -g examples/calc.jl.g -m lalr1 -o SyntaxParser.jl

The resultant parser module depends on the common DataStructures.jl package for clarity and performance reasons. Callers can include the Julia file which defines a module called SyntaxParser.jl, which contains the parser, and use it as:

using Pkg
Pkg.add("DataStructures")

output = SyntaxParser.parse("5 + 5")

For complex Julia parser implementations it is recommended to leverage the JSON-like notation for the lexical grammar, as it is easier to properly manage and understand escape sequences that need to travel between JavaScript in the parser generator to Julia notation in the resultant parser file. For example, the following includes proper escape sequences for handling strings that are read in and will have escaped double quotes inside them as well as numbers with scientific notation:

{
  rules: [
    // Comments
    ["\\/\\/.*",                                    `# skip single line comments`],
    ["\/\\*[\\s\\S]*?\\*\/",                        `# skip multiline comments`],
    [`\\s+`,                                        `# skip whitespace`],

    // Math operators (+, -, *, /, %)
    [`(\\+|\\-)`,                                   `return "ADDITIVE_OPERATOR"`],
    [`(\\*|\\/|%)`,                                 `return "MULTIPLICATIVE_OPERATOR"`],

    // Literals
    [`[-+]?([0-9]*[.])?[0-9]+([eE][-+]?\\d+)?`,     `return "NUMERIC"`],
    [`\\"(?:[^\\"\\\\]|\\\\.)*\\"`,                 `return "STRING"`],
    [`#-?\\d+`,                                     `return "OBJECT"`],
    [`E_[a-zA-Z]+`,                                 `return "ERROR"`],
  ]
}

Grammar format

Syntax support two main notations to define grammars: JSON-like notation, and Yacc/Bison-style notation.

JSON-like notation

JSON-"like" is because it's excented JSON notation, and may include any JavaScript syntax (e.g. quotes may be omitted for properties, can use comments, etc):

/**
 * Basic calculator grammar in JSON notation.
 */

{
  // ---------------------------
  // Lexical grammar.

  lex: {
    rules: [
      [`\\s+`,        `/* skip whitespace */`],
      [`\\d+`,        `return 'NUMBER'`],
      [`\\+`,         `return '+'`],
      [`\\*`,         `return '*'`],
      [`\\(`,         `return '('`],
      [`\\)`,         `return ')'`],
    ],
  },

  // ---------------------------
  // Operators precedence.

  operators: [
    [`left`, `+`],
    [`left`, `*`],
  ],

  // ---------------------------
  // Syntactic grammar.

  bnf: {
    e: [[`e + e`,   `$$ = $1 + $3`],
        [`e * e`,   `$$ = $1 * $3`],
        [`( e )`,   `$$ = $2`],
        [`NUMBER`   `$$ = Number($1)`]],
  }
}

As we can see, lex defines lexical grammar, bnf provides syntactic grammar, and operators may defines associativity and precedence of needed symbols. List of available grammar properties is specified below.

Yacc/Bison notation

And here is the same grammar in the Yacc/Bison format:

/**
 * Basic calculator grammar in Yacc/Bison notation.
 */

%lex

%%

\s+             /* skip whitespace */
\d+             return 'NUMBER'

/lex

%left '+'
%left '*'

%%

e
  : e '+' e    { $$ = $1 + $3 }
  | e '*' e    { $$ = $1 + $3 }
  | '(' e ')'  { $$ = $2 }
  | NUMBER     { $$ = Number($1) }
  ;

Simple tokens like '+' can be defined inline (with quotes), and complex tokens like NUMBER has to be defined in the lexical grammar. Lexical and syntactic grammars can also be