Headline

A kind of grammar used, for example, for syntax definition

Illustration

Context-free grammars consist of:

• a set of terminal ("strings" from which to compose inputs),
• a set of nonterminal (placeholders for syntactical categories in derivations),
• an (optional) designated startsymbol (a nonterminal from which to start derivations), and
• a set of productions (rules) for derivations.

In fact, a context-free grammar can be described just by the rules as these rules enumerate the terminals and nonterminals as well. (We may also assume that the left-hand side nonterminal of the first rule is simply the startsymbol). What's important is the structure of rules. Each rules consists of:

• a left-hand side which is a nonterminal, and
• a right-hand side which is some expression over terminals and nonterminals.

In the most basic form, said expressions are simply sequences over terminals and nonterminals. Alternatives for derivation are already expressible, as there could be multiple rules with the same left-hand side nonterminal. In practice, notational extensions are commonplace. For example, so-called EBNF notations may cater for these expression forms:

• x*: Any number of repetitiions of x including 0 repetitions.
• x?: Any number of repetitiions of x excluding 0 repetitions.
• x|y: x or y.
• x?: x or the empty string.

Here is a context-free grammar for a possible concrete syntax for companies of the @system; for what it matters, we use Technology:ANTLR's EBNF-like notation:

Nonterminals (with explanation):

• Company: complete company structures
• Department: department sub-structures of companies
• Employee: employee sub-structures of departments
• NonManager: managers rather than non-managerial employees
• QString: double-quoted strings for names and addresses
• Number: floating point numbers for salaries

Terminals:

• "company"
• "department"
• "employee"
• "manager"
• "address"
• "salary"
• "{"
• "}"

Startsymbol: Company

Productions:

Company :  
  'company' QString '{'
    Department* 
  '}';

Department :
  'department' QString '{' 
    'manager' Employee    
    Department* 
    NonManager* 
  '}';

NonManager : 'employee' Employee;

Employee : QString '{' 
    'address' QString
    'salary' Number 
  '}';

As an exercise, let us define about the same syntax with a different grammar. In the original grammar, the lists of departments and employees were separated. We may also consider a mixed list of departments and employees. To this end, we assume an extra nonterminal "SubUnit" for a choice between department and employee. As a result, we would need these alternative productions:

Company :  
  'company' QString '{'
    Department* 
  '}';

Department :
  'department' QString '{' 
    'manager' Employee    
    SubUnit* 
  '}';

SubUnit : NonManager | Department ;

NonManager : 'employee' Employee;

Employee : QString '{' 
    'address' QString
    'salary' Number 
  '}';

A (context-free) grammar has a simple semantics. It defines a set of strings (the so-called language generated by the grammar) which are derivable by repeated rule application starting from the symbol such that nonterminals are replaced by matching right-hand sides until no nonterminals are left. This generative definition also gives rise to an algorithmic problem, the parsing problem, such that one can check whether a given string is actually in the language generated by a grammar and recover the underlying syntactical structure as parse tree.