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 parsing machines. Each parsing machine might have different modules, such as: supplier, scanner, lexer, parser, optimizer, and builder.

TGS is a parsing machine generator and it is used to develop stand alone parsing machines from a lexer and a parser grammars. The accepted grammar syntax is the Augmented Backus–Naur form (ABNF). Graphical representation of the developed grammars is available directly into the IDE. TGS handles parsing deterministically for some types of ambiguous grammars.

Parsing Machine

The input of the generated parsing machines is in bits. The parsing machine is organized in different modules.

Token Types

In the machine there are 4 token types:

• Character token -- each token of this type contain a name consisting of a single character. These tokens are written as the tuple (t-character,x) for character x;
• Sequence token -- these tokens are contain a name from a set of names and a lexeme consisting of at least one character. These tokens are written as the tuple (t-sequence,e) for lexeme e, such that |e|>0;
• Limit token -- tokens, which are output by a module, when some of its technical limitations is reached, and the module cannot continue to perform. These tokens are written as the tuple (t-limit,Q,e) for a nonempty set of names Q and lexeme e;
• EOF token -- the last token output by a module, written as (t-eof).

Supplier

The module which is responsible for the supplying of the bytes to the parsing machine is the Supplier module. There can be different suppliers which "bring" the bytes from different byte sources: Stream Supplier which reads bytes from the file system, Network Supplier which downloads bytes from any network, and so on.

The generated code from TGS has an interface

Scanner

The job of the scanner module is to decode the bits it receives from a supplier module into Unicode code points. The output date is a sequence of character tokens.

Lexer

The job of the lexer module is to receive tokens from the previous module in the machine and to group, if possible, some of these tokens into new larger tokens.

Parser

The parser receives tokens from the previous module in the machine, checks whether the tokens form a valid sentence in the language defined by the parser grammar, and outputs syntax structure construction commands.

Builder

The builder module receives the stream of commands from the previous module. The handling of the received commands is made by an architect. There are two types of architects -- an abstract and a concrete.

Tunnel Parsing

that can be decoded by many different optionally available decoders (ASCII, ISO 8859-1 (Latin1), WIN-1252, UTF-8, UTF-16 LE/BE and UTF-32 LE/BE). The decoded input sequence forms an Unicode char array that may pass a lexical analyses (by a dedicated lexer grammar) where one or more characters can be grouped into phrases (an extension to the ABNF syntax integrated into the EGS). The phrases are recognized by the parser (having a dedicated parser grammar) as a single token. This method of two phases parsing effectively may parse some context-free languages deterministically. 

During runtime, the PM are emitting events per input syntax error discovered, that optionally contain byte offset of the error, Unicode code point offset or textual line and line character offsets. Additionally the syntax error message may contain information of the current not recognized token as well as a list of all possible expected tokens at the error location. The result of successful parsing is an explicit concrete syntax tree. The parsing process uses dynamic memory for in depth recursion, to preventing stack overflow events, and only few function calls depth are made using the dedicated thread stack (DTS). As a consequence, the DTS may be significantly reduced, especially important for server applications.

Architecture

The PM may be run in a single thread (executed in steps or till completion: error/success) or in up to three threads for multi-threaded parallel parsing, where each thread operates on specific part of the parsing pipeline, that may bring noticeable speed up especially for longer inputs. The parsing machine does not spawn threads to do parsing for different ambiguous grammar cases, but splits the parsing in sequential tasks that are run by different threads, effectively creating a pipeline.

The generated PM source code (including the syntax tree) is object-oriented. The target language for each PM is C++98 with single or multi threaded (currently with Win32 API) run time and x86/64 CPU architecture support. The generated PM are operating online - each instance can process as much as input is available, pause and wait for more input and continue later when more is available.

Debugger

Epsilon Grammar Studio has a an integrated debugger that visualises the PM progress step by step for an input string, and automata visualizer to help the developer to create grammars.

Grammar Analysis

At compile time, a grammar analysis is performed detect grammar ambiguities and is the grammar deterministic or context free. All collisions between grammar elements are reported visually into the IDE.

External links

• ExperaSoft UG main web page