Basics: What Are Grammars

Interactive Parser Explanations

By @MonoidMusician

Letʼs look at .

The structure of a grammar

Regular expressions

Regular expressions are a restricted type of grammar. But wait, regexes look like /^([a-zA-Z0-9_\-\.]+)@([a-zA-Z0-9_\-\.]+)\.([a-zA-Z]{2,5})$/, and thatʼs not at all like what weʼve been considering here.

Thereʼs two things going on here:

  1. Regular expressions that we write have a lot of fancy features, like character classes /[0-9]/, that are really just syntax for simpler features, like /0|1|2|3|4|5|6|7|8|9/ in that example.
  2. The simpler features of the formal definition of regular expressions can be converted into our grammars without too much work.

Regular expressions, considered as formal types of grammars, have only a few operations:

The trick is that we can encode these operations into many rules.