Language - Context Free Grammar (CFG)

1 - About

A context-free grammar is a set of grammar rules (known as production) that describe all possible strings in a given formal language without context.

They are the type 2 of the Chomsky grammar hierarchy.

Context-free grammars are used to put a tree structure on strings, typically text strings.

In context-free grammars, all rules are:

  • one-to-one,
  • one-to-many,
  • or one-to-none.

These rules can be applied regardless of context.

In a context free grammar, each (production|grammar) rule has :

  • a non-terminal symbol as its left-hand side (ie the symbol will not appear in the resulting formal language)
  • and a sequence of zero or more non-terminal and terminal symbols as its right-hand side.

In context-free grammars, terminal symbols never appear on the left hand side of a production rule

Starting from a sentence consisting of a single distinguished nonterminal, called the goal symbol, a given context-free grammar specifies a language, namely, the (perhaps infinite) set of possible sequences of terminal symbols that can result from repeatedly replacing any nonterminal in the sequence with a right-hand side of a production for which the nonterminal is the left-hand side.

3 - Usage

3.1 - Grammar Checking

Rules can be applied in reverse to check if a string is grammatically correct according to the grammar.

4 - EBNF

Syntactic equations of the form defined in EBNF generate context-free languages.

5 - Context Free meaning

The term context free is due to Chomsky and stems from the fact that substitution of:

  • the symbol left of =
  • by a sequence derived from the expression to the right of =

is always permitted, regardless of the context in which the symbol is embedded within the sentence.

It has turned out that this restriction to context freedom (in the sense of Chomsky) is quite acceptable for programming languages, and that it is even desirable.

6 - Syntax

A CFG consists of the following components:

  • a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.
  • a set of nonterminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols.
  • a set of productions, which are rules for replacing (or rewriting) nonterminal symbols (on the left side of the production) in a string with other nonterminal or terminal symbols (on the right side of the production).
  • a start symbol, which is a special nonterminal symbol that appears in the initial string generated by the grammar.

7 - Implementation

To generate a string of terminal symbols from a CFG, we:

  • Begin with a string consisting of the start symbol;
  • Apply one of the productions with the start symbol on the left hand size, replacing the start symbol with the right hand side of the production;
  • Repeat the process of selecting nonterminal symbols in the string, and replacing them with the right hand side of some corresponding production, until all nonterminals have been replaced by terminal symbols.

8 - Documentation / Reference

code/compiler/context_free.txt ยท Last modified: 2018/10/25 21:44 by gerardnico