Draft:Tunnel Grammar Studio

Written in	C++
Operating system	Windows
Available in	English
License	proprietary
Website	www.experasoft.com/en/products/tgs/

The Tunnel Grammar Studio (TGS) is an Integrated Development Environment (IDE) for generating stand-alone parsing machines from given lexer and parser grammars. The accepted grammar syntax is based on the Augmented Backus–Naur form (ABNF) with an additional syntax for defining tokens with their lexemes. A graphical representation of the developed grammars is available directly into the IDE, which also includes a visual debugger that builds a syntax tree for a given input in forward and backward steps.

The parsers generated by TGS work with an optimized version of the tunnel parsing algorithm. The algorithm can parse an input linearly and deterministically on the basis of some types of ambiguous grammars and grammars that have a deterministic push-down automaton. The algorithm can accept a sequence of tokens based on the their names and on the characters in their lexemes, case-sensitively or case-insensitively.

The tunnel parsing algorithm uses an additional stack with integer counters to be able to handle integer number of repetitions that can be defined for an element in an ABNF grammar. The output of the tunnel parsing algorithm is a sequence of syntax structure construction commands that can be used by the builder module of the automatically generated parsing machine, to build a concrete or an abstract syntax tree with different levels of abstraction.

Each parsing machine might have different modules, such as: supplier, scanner, lexer, parser, optimizer, and builder. The parser module in a generated parsing machine by TGS does not use the thread dedicated stack to recurse into the parsing rules (to minimize the possibility of stack-overflow errors), but instead operates over the input in iterative steps due to the use of the tunnel parsing algorithm. The creation of the syntax trees, their traversal, the conversion of their nodes into a string, and the tree's release can also be performed with iterative steps.

Example

An input string "Hello World" can be processed by a TGS generated lexer using the following lexer grammar:

; using the TGS's addition to the ABNF standard
word = 1*('a'-'z' / 'A'-'Z') 

; can also be written as "word = 1*(%x61-7A / %x41-5A)" by using the ABNF standard syntax

The result of the lexer's processing will be the following token sequence:

 t-sequence("word", "Hello")
 t-character(' '}
 t-sequence("word", "World")
 t-eof

The tokens can be parsed successfully on the basis of the following parser grammar with the tunnel parsing algorithm:

text = {word, %s"Hello"} *(' ' 0*1 {word}) 

; where: {word, %s"Hello"} defines an element that can accept tokens named "word" with a lexeme that matches case-sensitively (the %s prefix) to the string "Hello", {word} defines an element that matches tokens named "word" with any lexeme, and the characters ' ' and ',' can be written as %x20 and %x2C respectively by using the ABNF standard syntax

One of the syntax trees that can be automatically build by the generated, compiled and executed parsing machine for the grammars and the input is shown in the following image:

A graphical representation of the syntax tree

External links

• ExperaSoft UG main web page