• What is a parser generator?
• Lex and Yacc
• How ProGrammar is different

What is a Parser Generator?

A parser generator creates a parser for formatted data, given a rule-based description of its structure known as a grammar. Grammars can be used to describe the syntax of any formal language; including programming languages, scripting languages, protocols and standardized formats such as HTML and SQL. A popular notation for defining grammars is Backus-Naur Form (BNF), which has several variants.

Parser generators are commonly used in the development of compilers and interpreters; however, they are useful any time that data elements need to be extracted from a structured data source.

Typically, the output of a parser generator is source code for some programming language (such as C, C++, or Java), which can then be compiled and linked to the client application. Semantic actions defined within the grammar are used to control how the client application processes data elements as they’re parsed, by binding specific symbols from the grammar to programmer-written application code. When a given symbol is parsed by the parser, application code corresponding to the semantic action for that symbol gets executed. Semantic actions are usually defined directly within the grammar definition and consist of compilable statements from the target programming language. In many cases, semantic actions are used to construct internal representations of the parsed data for subsequent use by the application.

Lex and Yacc

The most widely-used parser generator is Yacc, which is an acronym for "yet another compiler compiler". Its name reflects a common traditional use for parser generators--that of compiler construction. Yacc uses a BNF-like notation for describing the syntax of context-free grammars. In Yacc, semantic actions consist of C language statements that are entered directly into the grammar definition. Yacc generates C code to be compiled and linked directly with a client program.

Yacc operates in coordination with Lex, which is a lexical analyzer (or tokenizer) that scans the input to produce a sequence of tokens. Tokens are used as input to the parser generated by Yacc. Lex uses regular expressions to describe tokens.

Many parser generators are based on Lex and Yacc, or are visual front-ends to Lex and Yacc. Examples include Bison and Flex.

How ProGrammar is Different

ProGrammar differs from traditional parser generators in several important ways:

• ProGrammar provides an Object-Oriented Grammar Definition Language for describing the syntax of a data source. While many parser generators produce object-oriented code that can be reused at the source code level (e.g., C++ or JAVA), only ProGrammar implements an object-oriented language and notation which can be reused at the grammar definition level.
• Semantic actions are not defined in the grammar definition. Because semantic actions typically define an application-specific interpretation of data, they are not included in the grammar. This eliminates the need to include programming language statements in the grammar definition--resulting in grammars that are programming language independent, less cluttered, and more reusable across multiple applications having different uses for the same data.
• ProGrammar makes no distinction between lexical analysis and parsing. The separation of lexical analysis and parsing reflected by Lex and Yacc is somewhat arbitrary, and complicates the process of building parsers. By eliminating this distinction, ProGrammar provides the full power of parsing to the tokenizer.