# Parsing Expression Grammars and Their Induction Algorithm
## 2 Definition of PEGs  
PEGs reference _regular expressions_ (RE) and _context-free grammars_ (CFGs), both derivative from formal language theory. We briefly introduce the most relevant definitions. An alphabet \(\Sigma\) is a non-empty set of symbols (characters without any meaning). A string or word (\(s\), \(w\)) is a finite sequence of symbols. The special case of the string is an empty string \(\epsilon\) (the empty sequence of symbols). The example of the alphabet is a set \(\{a,b,c\}\) and an example of strings over the alphabet is \(\{a,aa,ab,ba,abc\}\). A formal language \(L\) over an alphabet \(\Sigma\) is a subset of \(\Sigma^{*}\) (Kleene star, all strings over \(\Sigma\)). A regular expression is a formal way of describing the class of languages called _regular language_. Let \(r\), \(r_{1}\), and \(r_{2}\) be the regular expression over \(\Sigma\), and \(a,b\in\Sigma\); the following operations are allowed in syntax:  
* \(\epsilon\), the empty string;
* \(a\), symbol or string occurrence;
* \(r*\), zero or more repetitions of regular expression;
* \(a+\), one or more repetitions;
* \(a\mid b\), non-deterministic choice of symbol, formally defined as \(a+b\);
* \(r_{1}r_{2}\), concatenation;
* \((r)\), parenthesis for grouping of expressions. Given an alphabet \(\Sigma=\{a,b\}\), a formal language \(L=\{w\in\Sigma^{*}\mid w\text{ begins with }a\text{ and ends with }a\}\) can be expressed as the regular expression \(a(a\mid b)^{*}a\). CFG is a tuple of \(G=(V,\Sigma,R,S)\), where \(V\) is the final set of nonterminal symbols, \(\Sigma\) is the final set of terminal symbols disjoint from \(V\), \(R\) is a finite relation \(V\rightarrow(V\cup\Sigma)\) and defines rules, and \(S\) is the start symbol, chosen from \(V\). The most common \(R\) is defined as the production rule notation; for example, for formal language: \(L=\{w\in\Sigma^{*}\mid w^{n}w^{n}\,n>1\}\), the equivalent context-free grammar is \(G=(\{S\},\{a,b\},P,S)\) with the productions:  
\[S \to aSa\] \[S \to bSb\] \[S \to a\mid b\]  
The word _aba_ can be accepted using the first production and the third one. The book by [PERSON] et al. [15] contains more information related to the formal language field. The formalism of PEGs was introduced by [PERSON] in 2004 [16]. However, herein we give definitions and notation compatible with the provided PEG library. Let us start with an informal introduction to parsing expression grammars (PEGs). A _parsing expression grammar_ (PEG) is a 4-tuple \(G=(V,T,R,s)\), where \(V\) is a finite set of nonterminal symbols, \(T\) is a finite set of terminal symbols (letters), \(R\) is a finite set of rules, \(s\) is a parsing expression called the _start expression_, and \(V\cap T=\emptyset\). Each rule \(r\in R\) is a pair \((A,e)\), which we write as \(A\Leftarrow e\), where \(A\in V\) and \(e\) is a parsing expression. For any nonterminal \(A\), there is exactly one \(e\) such that \(A\Leftarrow e\in R\). We define _parsing expressions_ inductively as follows. If \(e\), \(e_{1}\), and \(e_{2}\) are parsing expressions, then so is:  
1. \(e\), the empty string;
2. \(a\), any terminal, \(a\in T\);
3. \(A\), any nonterminal, \(A\in V\);
4. \(e_{1}\gg e_{2}\), a sequence;
5. \(e_{1}\mid e_{2}\), prioritized choice;
6. \(+e\), one or more repetitions;
7. \(\sim\)\(e\), a not-predicate. The choice of operators \(\gg\), \(\mid\), \(+\), \(\sim\), and \(\Leftarrow\) is caused by being consistent with our Python library. The operators have their counterparts in Python (>>, \(\mid\), \(+\), \(\sim\), and \(<=\)) with the proper precedence. Thus the reader is able to implement expressions in a very natural way, using the native operators. A PEG is an instance of a recognition system, i.e., a program for recognizing and possibly structuring a string. It can be written in any programming language and looks like a grammar combined with a regex, but its interpretation is different. Take as an example the following regex: \((a\mid b)^{+}b\). We can write a \"similar\" PEG expression: \(+(a\mid b)\gg b\).