JetPAG
Encyclopedia
JetPAG is an open source
LL(k)
parser
and lexical analyzer
generator
, licensed under the GNU General Public License
. It is a personal work of Tareq H. Sharafy, and is currently at final beta stages of development.
lexical analyzer and parser generator with emphasis on ease of use, code readability and high performance of generated code. After a long period of in-house development and testing, the first development package of JetPAG was released through SourceForge
in 18 November 2006. Development of JetPAG is current at beta stage, current version is 0.6.1. The development was delayed from mid-2007 until early 2009 but resumed after.
The front end accepts the grammar metalanguages as an input.
The analyzers mainy perform two operations through tree traversal
. The first is calculating strong lookahead
sets for the elements in the grammar and the second is constructing lookahead paths from the lookahead sets. Lookahead paths group, factorize and perform many enhancements and optimizations
to lookahead sets using special analysis. From lookahead paths lookahead sets are transformed to a nested tree form, gaining a great overall efficiency and improvement in most cases
.
Code generators generate source code for recognizers compatible with the input grammars based on them along with information collected from the analyzers. Currently JetPAG generates source code in C++ only.
The nature of JetPAG's metalanguage and framework make it easy and simple to integrate generated recognizers into larger applications. JetPAG also includes some facilities in the provided framework to aid developers with small utilities and save development time from many minimal language recognition tasks.
based on the EBNF form and regular expressions, with extensive additions and tweaks. The meta language of JetPAG grammars was designed to be maximally flexible handle both simple grammars and large, complicated ones easily. Parsers and lexical analyzers are simillary defined and generated for simplicity and ease of use. This is a simple example of a grammar for a basic calculator:
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
LL(k)
LL parser
An LL parser is a top-down parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Leftmost derivation of the sentence...
parser
Parsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
and lexical analyzer
Lexical analysis
In computer science, lexical analysis is the process of converting a sequence of characters into a sequence of tokens. A program or function which performs lexical analysis is called a lexical analyzer, lexer or scanner...
generator
Compiler-compiler
A compiler-compiler or compiler generator is a tool that creates a parser, interpreter, or compiler from some form of formal description of a language and machine...
, licensed under the GNU General Public License
GNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
. It is a personal work of Tareq H. Sharafy, and is currently at final beta stages of development.
History
Tareq started JetPAG as a small program written for practice purposes only. Soon when it started expanding many goals were added rapidly, and it was obvious that JetPAG is worthy being a complete project. Real development of JetPAG started in late 2005, targeting a complete framework for a powerful recursive descentRecursive descent parser
A recursive descent parser is a top-down parser built from a set of mutually-recursive procedures where each such procedure usually implements one of the production rules of the grammar...
lexical analyzer and parser generator with emphasis on ease of use, code readability and high performance of generated code. After a long period of in-house development and testing, the first development package of JetPAG was released through SourceForge
SourceForge
SourceForge Enterprise Edition is a collaborative revision control and software development management system. It provides a front-end to a range of software development lifecycle services and integrates with a number of free software / open source software applications .While originally itself...
in 18 November 2006. Development of JetPAG is current at beta stage, current version is 0.6.1. The development was delayed from mid-2007 until early 2009 but resumed after.
Overview
Jetpag incorporates several modules: the front end, the analyzers and the code generators.The front end accepts the grammar metalanguages as an input.
The analyzers mainy perform two operations through tree traversal
Tree traversal
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited...
. The first is calculating strong lookahead
Lookahead
Lookahead is a tool in algorithms for looking ahead a few more input items before making a cost effective decision at one stage of the algorithm.- Lookahead in search problems :...
sets for the elements in the grammar and the second is constructing lookahead paths from the lookahead sets. Lookahead paths group, factorize and perform many enhancements and optimizations
Optimization (computer science)
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...
to lookahead sets using special analysis. From lookahead paths lookahead sets are transformed to a nested tree form, gaining a great overall efficiency and improvement in most cases
Best, worst and average case
In computer science, best, worst and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively...
.
Code generators generate source code for recognizers compatible with the input grammars based on them along with information collected from the analyzers. Currently JetPAG generates source code in C++ only.
The nature of JetPAG's metalanguage and framework make it easy and simple to integrate generated recognizers into larger applications. JetPAG also includes some facilities in the provided framework to aid developers with small utilities and save development time from many minimal language recognition tasks.
JetPAG grammars
JetPAG's garmmars are written in a meta languageMetalanguage
Broadly, any metalanguage is language or symbols used when language itself is being discussed or examined. In logic and linguistics, a metalanguage is a language used to make statements about statements in another language...
based on the EBNF form and regular expressions, with extensive additions and tweaks. The meta language of JetPAG grammars was designed to be maximally flexible handle both simple grammars and large, complicated ones easily. Parsers and lexical analyzers are simillary defined and generated for simplicity and ease of use. This is a simple example of a grammar for a basic calculator:
grammar Calc:
parser CalcP:
expression:
multiplicative
( '+' multiplicative
| '-' multiplicative
)*
;
multiplicative:
factor
( '*' factor
| '/' factor
)*
;
factor:
INT
| '(' expression ')'
;
scanner CalcS:
INT: '0'-'9'+;
PLUS: '+';
MINUS: '-';
STAR: '*';
SLASH: '/';
LP: '(';
RP: ')';