Tunnel Grammar Studio documentation

The article proposes an addition to the tunnel parsing algorithm that enables it to parse grammars having countable repetitions and configurations of grammar elements generating empty words without refactoring the grammar. The equivalency of trees built by the use of ambiguous grammar is discussed. The class of the ε-ambiguous grammars is defined as a subclass of the ambiguous grammars relative to these trees. The ε-deterministic grammars are then defined as a subclass of the ε-ambiguous grammars. A technique for linearly parsing on the basis of non-left recursive ε-deterministic grammars with the tunnel parsing algorithm is shown.

The article describes a string recognition approach, engraved in the parsers generated by Tunnel Grammar Studio that use the tunnel parsing algorithm, of how a lexer and a parser can operate on the input during its recognition. Proposed is an addition of the augmented Backus-Naur form syntax that enables the formal language to be expressed with a parser grammar and optionally with an additional lexer grammar. The tokens outputted from the lexer are matched to the phrases in the parser grammar by their name and optionally by their lexeme, case sensitively or insensitively.

This article describes a new and efficient algorithm for parsing (called tunnel parsing) that parses from left to right on the basis of context-free grammar without left recursion nor rules that recognize empty words. The algorithm is mostly applicable for domain-specific languages. In the article, particular attention is paid to the parsing of grammar element repetitions. As a result of the parsing, a statically typed concrete syntax tree is built from top to bottom, that accurately reflects the grammar. The parsing is not done through a recursion, but through an iteration. The tunnel parsing algorithm uses the grammars directly without a prior refactoring and is with a linear time complexity for deterministic context-free grammars.

The article specifies the definitions of a Concrete Syntax Tree and an Abstract Syntax Tree. The different types of knowledge that are shared between a parser and builder modules in a parsing machine, about the syntax tree building, are discussed. For the building of the syntax tree, various Syntax Structure Construction Commands are presented. They are transmitted from the parser to the builder, depending on the type of tree. Template grammars and a computer program (Parser Generator Profiler) that performs parser tests on their basis are described. The empirical results from the different tests (for different combinations of grammar elements), performed with different types of syntax trees, for different parsers generated by different parser generators, are shown. The measurements are based on different criteria such as the time for the tree building, its traversal time, its destruction time, and the memory used by it.

In the parsing theory, seemingly different parsing machines exist, due to the use of different terms that have similar meanings. This article addresses the diversity in the parsing terminology by proposing definitions for various objects and processes in a parsing machine. Based on the defined objects and processes, a common architecture of a parsing machine is proposed that is applicable in practice when using different parsing approaches. The modules of the parsing machine and their close relations are shown. The proposed parsing machine architecture is to a large extent used in the parsers generated by Tunnel Grammar Studio.