Grammars provide rules that specify the structure of languages, independently from the actual meaning of the content. Grammars are classified according to the complexity of the structure they describe. The class of context free grammars (CFG) is the most common one use to describe the syntax of programming languages. In this class, the category a token belongs to (e.g. reserved words, identifiers, etc.) is what matters rather than the specific token (e.g. the identifier xyz).In addition, the formatting of the program (the content of whitespace) and the actual text of identifiers does not affect the syntax of the grammar. This is very important in parsing technology. Grammars that are not context free cannot be parsed by the LR, LALR or LL parsing algorithms.

Backus-Naur Form

Backus-Naur Form, or BNF for short, is a notation used to describe context free grammars. The notation breaks down the grammar into a series of rules - which are used to describe how the programming languages tokens form different logical units

The actual reserved words and recognized symbol categories in the grammar represent “terminals”. Usually, terminals are left without special formatting or are delimited by single or double quotes. Examples include: if, while, ‘=’ and identifier.

In Backus-Naur Form, rules are represented with a “nonterminal” - which are structure names. Typically, nonterminals are delimited by angle-brackets, but this is not always the case. Examples include <statement> and <exp>. Both terminals and nonterminals are referred to generically as “symbols”. Each nonterminal is defined using a series of one or more rules (also called productions). They have the following format:

N ::= s

where N is a nonterminal and s is a series of zero or more terminals and nonterminals.  Different alternatives for rules can be specified in Backus-Naur Form. For readability, often productions are grouped together and  separated by a “pipe” symbol which is read as the word “or”.

In summary , there are slight variations in use, but the notation has the following properties.

• A rule consists of one or more productions.
• The production starts with a single nonterminal, which is the name of the rule being defined
• This nonterminal is followed by a ::= symbol which means “as defined as”. The  ::= symbol is often used interchangeably with the symbol. They both have the same meaning.
• The symbol is followed by a series of terminals and nonterminals.

The following chart identifies the various parts of a rule definition.

For example, the following defines a rule called <Value> which can contain either an Identifier terminal or the contents of another rule called <Literal>

<Value> ::= Identifier | <Literal> <Literal> ::= Number | String

The <Literal> rule can contain either a  Number  or String   terminal. As a result of this definition, a <Value> can contain an Identifier, Number or String.

Rules can also be recursively defined. The following rule defines a series of one or more Identifiers.

<Identifiers> ::= Identifier <Identifiers> | Identifier

Extended BNF

There is another version of BNF called Extended BNF, or EBNF (ISO/IEC 14977), for short. This variant was originally developed by Niklaus Wirth to define the syntax for the Pascal Programming Language. The notation was designed to simplify the notation of BNF by allowing the developer to use special notation for defining lists and optional sets of symbols.

Variations between different versions of EBNF exist, but most use similar notation. Square brackets “[ … ]” are used to denote optional elements of a rule. Elements of a rule can also be grouped together using braces “{ … }” which denotes a repetition of zero to infinity. Symbols can also be grouped using parenthesis “( … )” and followed by a Kleene closure. In this case, the semantics are identical to those used in Regular Expressions.

This format, while powerful, creates a number of implied rules. For instance, if the programmer was to define a rule with an optional clause, the system would have two distinct forms of the rule - the one with the clause and one without. This is also the case with lists and other enhanced features. For instance, the If-then-else statement could be defined as:

<If Stm> ::= IF <Expression> THEN <Stms> [ ELSE <Stms> ]

This would create the following rules:

<If Stm> ::= IF <Expression> THEN <Stms>
| IF <Expression> THEN <Stms> ELSE <Stms>

When a software engineer designs and writes a program, it is often in one of the many modern programming languages available. Rather than taking on the rather tedious task of writing the program using the actual instructions used by the computer processor, the logic and behavior of the program are expressed using human-like and English-like terms. Whether the programming language is C++ or COBOL,  the representation of which actions the program is to perform and how they are actually implemented differs greatly.Programming languages are classified by their “generation”. The first programs were written in machine code - since no other programming technology had been developed. If another computer processor was designed with the same basic instruction set, but a slightly different machine code format, programs had to be completely rewritten. This lead to the development of “second generation” programming languages: assemblers. Assemblers display each instruction using a keyword rather than the binary format. This gives a layer of  abstraction between the machine code and the instruction set itself. Programs became far easier to read and write.

The disadvantage to the second generation languages was that programs could not be ported to other platforms. As a result, computer scientists designed the first “third generation” programming language: FORTRAN. Though it is not used much today, its effect on the computer industry was great. Programs could be written in human-like and English-like terms and then later compiled and executed on different machines. When most programmers use the term “programming language”, they are referring to the third generation languages such as C++, COBOL, Visual Basic, Java and Delphi.

There is, however, a catch. To convert a modern third generation language to machine code, those human-like and English-like terms must be broken down into their different logical units. This is the job of a parser.

Parsers

While the text of a program is easy to understand by humans, the computer must convert it into a form which it can understand before any emulation or compilation can begin.

This process is know generally as “parsing” and consists of two distinct parts.

The first part is the “tokenizer” - also called a “lexer” or “scanner”. The tokenizer takes the source text and breaks it into the reserved words, constants, identifiers, and symbols that are defined in the language. These “tokens” are subsequently passed to the actual ‘parser’  which analyzes the series of tokens and then determines when one of the language’s syntax rules is complete.

As these completed rules are “reduced” by the parser, a tree following the language’s grammar and representing the program is created. In this form, the program is ready to be interpreted or compiled by the application.

Modern bottom-up parsers use a Deterministic Finite Automaton (DFA) to implement the tokenizer and a LALR(1) state machine to parse the created tokens.  Practically all common parser generators, such as the UNIX standard YACC, use these algorithms.

The actual LALR(1) and DFA algorithms are easy to implement since they rely on tables to determine actions and state transition. Consequently, it is the computing of these tables that is both time-consuming and complex.

The GOLD Parser Builder performs this task. Information is read from an source grammar and the the appropriate tables are computed . These tables are then saved to a file which can be, subsequently, loaded by the actual parser engine and used.