Parsing

# Notation

NameMath notationPlain textOther namesOther notations
Alphabet$\Sigma$
Empty string$\varepsilon$""
Empty language$\emptyset$set: $\{\}$, Br: $\phi$
Trivial language$\epsilon$set: $\{\varepsilon\}$, RE: $\epsilon$, Br: $\lambda$
Singleton language$\{a\}$RE: $a$
Symbol$X$XVariable, Non-terminal
Token$a$"a"Letter, Terminal
Rule$S \rightarrow \ldots$S -> ...Language equationBNF: S := ..., PEG: S <- ...
Concatenation$XY$X Ysequence, cartesian p.$X \cdot Y$, Might: $X \circ Y$, set: $X \times Y$
Unordered choice$X \vert Y$X|Yunion, disjunctionRE: $X+Y$, set: $X \cup Y$
Kleene star$X^\ast$X*Kleene closureMight: $X \star$
Kleene plusX+$X \cdot X^*$, X{1,}
OptionalX?$X \vert \epsilon$, X{0,1}
QuantifierX{n,m}, X{n,}, X{n}
Any character$\Sigma$.
Intersection$X \cap Y$conjuctionBr: $X \& Y$
Negation$X^\prime$absolute complementset: $\Sigma^* \setminus X$, $!X$, $L^c$
Positive lookahead$(\&X) Y$&X Y
Negative lookahead$(!X) Y$!X Y
Range[a-z]
Set of characters$a \vert b \vert c$[abc]set: $\{a, b, c\}$
Negation of set$\Sigma \setminus (a \vert b)$[^ab]
Escape sequences"\n"
Ordered choice$X / Y$X / Y
End of file!.

## Examples

There are a lot of different formalisms about languges and they all use slightly different notations, but in the end it’s the same thing.

### Regular Expressions

Regular expressions doesn’t use symbols and rules to define language. There is only one rule - regular expression. Classical regular expressions use only tokens, concatenation, unordered choice and Kleene star. Also in science papers they don’t bother to put quotes around letters - this way notation is more terse.

For example

RELanguage
$\epsilon${""}
$a${"a"}
$ab${"ab"}
$a \vert b${"a", "b"}
$a^*${"", "a", "aa", ...}
$(a \vert b)c${"ac", "bc"}

### Regular Expressions Extended

Same as classical regular expressions, but also adds intersection and negation (which makes it full set of Boolean operations). Those two operations doesn’t add to calculation power (still can produce only regular languages).

See: Janusz A. Brzozowski. 1964. Derivatives of Regular Expressions. J. ACM 11, 4 (Oct. 1964), 481–494. https://doi.org/10.1145/321239.321249

### Modern regular expressions

Modern regular expressions add some more tricks, like: Kleene plus, Optional, Quantifier, Any character, Range, Set of characters, Negation of set, Escape sequences. Depends on the flavor (implementation). Those, again, doesn’t add to computational power, but they are quite convenient.

### Chomsky generative grammar

Chomsky grammar uses: symbols (non-terminals), rules, tokens (terminals), concatenation, unordered choice.

ChomskyLanguage
$S \rightarrow \epsilon${""}
$S \rightarrow a${"a"}
$S \rightarrow ab${"ab"}
$S \rightarrow a \vert b${"a", "b"}
$S \rightarrow Sa \vert \epsilon${"", "a", "aa", ...}
$X \rightarrow a \vert b; S \rightarrow X c${"ac", "bc"}

Becuase ”$\vert$” is unordered choice those are the same rules:

$S_1 \rightarrow S_1 a \vert \epsilon \\ S_2 \rightarrow \epsilon \vert S_2 a \\ S_3 \rightarrow \epsilon \\ S_3 \rightarrow S_3 a$

Depending on which restrictions you put on the rules it can genrate: regular, context-free, context-sensitive, recursive enumerable languages. This formalism is used to define Chomsky hierarchy.

### Backus–Naur form

BNF is variation of Chomsky grammar which can generate only context-free languages. There are a lot of variations which also add: Kleene plus, Optional, Quantifier, Any character, Range, Set of characters, Negation of set, Escape sequences. Which doesn’t add anything to computational power, but makes it more practical. BNF looks like this

<S> ::= "" | "a"

### Parsing Expression Grammars

PEG again can be treated as variation of Chomsky grammar, but instead of unoredered choice it uses ordered chocie and also adds positive lookahead, negative lookahead and any character. PEG can recognize some context-sensitive grammars. PEG looks like this:

$A \leftarrow a A b / \epsilon \\ B \leftarrow b B c / \epsilon \\ S \leftarrow \&(A !b) a^\ast B!.$

### Parsing with Derivatives

PwD adds to classical regular expressions: rules and symbols (which allows to do general recursion). PwD can handle context-free languages. You can express Kleene closure in three ways:

$S_1 \rightarrow Sa \vert \epsilon \\ S_2 \rightarrow aS \vert \epsilon \\ S_3 \rightarrow a^* \\$

You can as well say that they added Kleene star to Chomsky grammar.

### Conjuctive grammar

It adds intersection to Chomsky grammar. It can handle some context-sensitive languages. It looks like this (in original paper they use $\&$ instead of $\cap$):

$A \rightarrow Aa \vert \epsilon \\ C \rightarrow Cc \vert \epsilon \\ X \rightarrow a A b \vert \epsilon \\ Y \rightarrow b B c \vert \epsilon \\ S \rightarrow XC \cap AY$

### Boolean grammar

It adds intersection and negationto Chomsky grammar. It can handle some context-sensitive languages.

Interesting: in PwD they added general recursion to classical regular expressions to recieve context-free Chomsky grammar. If we add general recursion to REE we will recieve Boolean grammar.

Interesting: in PwD they added general recursion to classical regular expressions to recieve context-free Chomsky grammar. If we add general recursion to REwLA we will recieve PEG. And ordered choice can be expressed as $A / B = A \vert (!A)B$.

## History

There is an interesting story behind how notation changed over time. See this video

• 1951 Stephen Kleene develops regular expressions to describe McCulloch-Pitts (1943) nerve nets (uses ∨ for choice; considers postfix ∗, but decides to make it a binary operator to avoid having empty strings: x∗y means any number of copies of x, followed by y).
• 1956 Journal publication of Kleene’s technical report: binary ∗ only.
• 1958 Copi, Elgot, and Wright formulate REs using · and ∨ and postfix ∗.
• 1962 Janusz Brzozowki uses binary + for ∨ and introduces postfix +.
• 1968 Ken Thompson’s paper “Regular Expression Search Algorithm” uses |.
• 1973 Thompson creates grep from ed editor for use by Doug McIlroy.
• 1975 Alfred Aho creates egrep (includes ( ), |, *, +, ?).
• 1978 CMU Alphard project uses regular expressions with *, +, and #.
• 1981 CMU FEG and IDL use regular expressions with *, +, and ?.

## Operations concept map

TODO: I need to update it and explain abbreviations. 