Context Free Grammars

Keywords: cs
Created: 2020-05-11 Mon 16:15

Context free grammars are a concept originating in linguistics but widely used in (theoretical) computer science.

For this section, I'm going to use a bunch of mathematical notation, but I'll try to explain everything as it comes along.

A set is collection of elements where each element appears only once. The set of the number from one to four can be written as context_free_grammars_f491114c333b0cc25cf11196ac4e2baeb2bfce14.svg .

An alphabet is a set with a finite number of elements (the natural numbers 1, 2, 3, …, would be an example for an infinite set).

A context free grammar has four components:

  1. An alphabet context_free_grammars_74962b94729ff85f034d200b7672b8a27cd26760.svg of terminals (read: “things where the expansion terminates”)
  2. An alphabet context_free_grammars_eac9af67e0f87c65fa11961d2999749ba9442ac5.svg of non-terminals (read: “things that can expand into other things”)
  3. A set context_free_grammars_979e97ab5d832c48fd3721a847c0ed3db067f3f7.svg of production rules
  4. The start symbol context_free_grammars_eb7d730089db2c5cd31cfba63d654044aa20db31.svg , an element of the set of non-terminals

It's important that the terminal and non-terminal alphabets are disjoint , i.e. there is no element that is part of both sets.

Production rules have the form context_free_grammars_6700d7d2f7303453e84e421f7084290c004fd98e.svg . context_free_grammars_01a7f3a53629b6215fa55996fc19d12b70c3f555.svg can be read as “Combine the sets context_free_grammars_74962b94729ff85f034d200b7672b8a27cd26760.svg and context_free_grammars_eac9af67e0f87c65fa11961d2999749ba9442ac5.svg ”, context_free_grammars_1a892b25d0f093bfcdbd6ca4ab9c4a5dc62f9bb0.svg is called Kleene star and can be read as “repeated zero or more times”.

The part on the right of the context_free_grammars_dbf954bd26d8cf3e81f2090e9d54b7c6a07f5002.svg is called right hand side , or RHS , the part on the left left hand side or LHS .

A grammar is expanded starting with the start symbol and then replacing each non-terminal with the RHS of one of its rules.

Time for a simple example:

Starting from context_free_grammars_691663fd20baaa50147a4eee986bb1a330fce655.svg , the grammar expands into context_free_grammars_ee79d0c4e06c83c9ad7e369bd8f2e6bc794c6361.svg , then each context_free_grammars_7b97a6ff8140f1f8274cd81b94fb1ff15362dd1a.svg expands into context_free_grammars_cdd73811e838a16e3cfa110b5edd012870a2a64e.svg , so the end result is context_free_grammars_d70a2645bf4cbefd83632aeef5eb0c5d0ed4fdd0.svg .

There can be multiple rules with the same right hand side , so there are (possibly infinitely) many sequences a grammar can expand to.

context_free_grammars_1e8133c28e06fb6d8c11097c2b2526df9a7e5ed1.svg is the notation for an empty sequence, so when expanding context_free_grammars_277e1b40f4a979b5c1d9f9a77956749c63dc9d79.svg , the context_free_grammars_192f5fd796655765424f2ea0e6a7229490f5ab44.svg just disappears.

Expanding this grammar, we have two options, either expand context_free_grammars_192f5fd796655765424f2ea0e6a7229490f5ab44.svg to context_free_grammars_456a5de955b3eade16e2e69678514d357131e23b.svg or to context_free_grammars_1e8133c28e06fb6d8c11097c2b2526df9a7e5ed1.svg .

Expanding context_free_grammars_456a5de955b3eade16e2e69678514d357131e23b.svg further, we have two options again, either expand it to context_free_grammars_b70aa344d76511ca2751688546a6e4cc1874ebfd.svg or to context_free_grammars_8d77919efe0f052a1a76fd427f4bfc5c4e4265eb.svg .

This can be repeated infinitely many times, so the grammar produces sequences of context_free_grammars_874c3fa02641575ceaa7b8cb3e592da0c8b2e2c5.svg of any length. (Remember the Kleene star? We can use it to write that as context_free_grammars_12a3085960a2760a7e8825bcfac64baf61899a03.svg instead).


Last export: 2020-06-30 Tue 13:44
This document is also available as plain text and pdf.

If you have an idea how this page could be improved or a comment send me a mail.