# Parsing Expression Grammars and Their Induction Algorithm
## 2 Definition of PEGs
The regex accepts all words over the alphabet \(\{a,b\}\) that end with the letter \(b\). The PEG expression, on the contrary, does not recognize any word since PEGs behave greedily, so the part \(+(a\mid b)\) will consume all letters, including the last \(b\). An appropriate PEG solution resembles a CFG:  
\[A \Leftarrow a\mid b\] \[E \Leftarrow b\gg\sim A\mid A\gg E\]  
The sign \(\Leftarrow\) associates an expression to a nonterminal. The sign \(\gg\) denotes concatenation. What makes a difference is the ordered choice \(\mid\) and not-predicate \(\sim\). The nonterminal \(E\) first tries to consume the final \(b\); then, in the case of failure, it consumes \(a\) or \(b\) and recursively invokes itself. In order to write parsing expressions in a convenient way we will freely omit unnecessary parentheses assuming the following operators precedence (from highest to lowest): \(\sim\), \(+\), \(\gg\), \(\mid\Leftarrow\). The Kleene star operation can be performed via \(+e\mid e\) (Python does not have a unary star operator and the PEG implementation library had to be adjusted). The power of PEGs is clearly visible in fast, linear-time parsing and in the possibility of expressing some context-sensitive languages [17]. From now on we will use the symbols \(a\), \(b\), and \(c\) to represent pairwise different terminals, \(A\), \(B\), \(C\), and \(D\) for pairwise different nonterminals, \(x\), \(x_{1}\), \(x_{2}\), \(y\), and \(z\) for strings of terminals, where \(|x_{1}|=k\,(k\geq 0)\), \(|x_{2}|=m\,(m\geq 0)\), and \(e\), \(e_{1}\), and \(e_{2}\) for parsing expressions. To formalize the syntactic meaning of a PEG \(G=(V,T,R,s)\), we define a function consume(\(e\), \(x\)), which outputs a nonnegative integer (the number of \"consumed\" letters) or nothing (None):  
1. consume(\(e,x\)) = 0. 2. consume(\(a,ax\)) = 1; consume(\(a,bx\)) = None; consume(\(a,e\)) = None. 3. consume(\(A,x\)) = consume(\(e,x\)) if \(A\Leftarrow e\). 4. If consume(\(e_{1},x_{1}x_{2}y\)) = \(k\) and consume(\(e_{2},x_{2}y\)) = \(m\), then the following holds: consume(\(e_{1}\gg e_{2},x_{1}x_{2}y\)) = \(k+m\); if consume(\(e_{1},x\)) = None, then consume(\(e_{1}\gg e_{2},x\)) = None; if consume(\(e_{1},x_{1}y\)) = \(k\) and consume(\(e_{2},y\)) = None, then we can be sure that consume(\(e_{1}\gg e_{2},x_{1}y\)) = None. 5. If consume(\(e_{1},x_{1}y\)) = \(k\), then consume(\(e_{1}\mid e_{2},x_{1}y\)) = \(k\); if consume(\(e_{1},x_{1}y\)) = None and consume(\(e_{2},x_{1}y\)) = \(k\), then consume(\(e_{1}\mid e_{2},x_{1}y\)) = \(k\); if consume(\(e_{1},y\)) = None and consume(\(e_{2},y\)) = None, then consume(\(e_{1}\mid e_{2},y\)) = None. 6. If consume(\(e,x_{1}y\)) = \(k\) and consume(\(+e,y\)) = \(n\), then consume(\(+e,x_{1}y\)) = \(k+n\); if consume(e,\(x\)) = None, then consume(\(+e,x\)) = None; if consume(\(e,x_{1}y\)) = \(k\) and consume(\(+e,y\)) = None, then consume(\(+e,x_{1}y\)) = \(k\). 7. If consume(\(e,x\)) = None, then consume(\(\sim\)\(e,x\)) = 0; if consume(\(e,x_{1}y\)) = \(k\), then consume(\(\sim\)\(e,x_{1}y\)) =  None. The language \(L(G)\) of a PEG \(G=(V,T,R,s)\) is the set of strings \(x\) for which consume(\(s,x\)) \(\
eq\) None. Please note that the definition of the language of a PEG differs fundamentally from the much more well-known CFGs: in the former it is enough to consume any prefix of a word (including the empty one) to accept it, and in the latter the whole word should be consumed to accept it. Direct (like \(A\Leftarrow A\gg e\)) as well as indirect left recursions are forbidden, since it can lead to an infinite loop while performing the consume function. It is worth emphasizing that the expression \(\sim\)(\(\sim\)\(e\)) works as non-consuming matching. As a consequence, we can perform language intersection \(L(G_{1})\cap L(G_{2})\) by writing \(\sim\)(\(\approx\)\(s_{1}\)) \(\gg\)\(s_{2}\) if only \(G_{1}=(V_{1},T,R_{1},s_{1})\), \(G_{2}=(V_{2},T,R_{2},s_{2})\), and \(V_{1}\cap V_{2}=\emptyset\). Interestingly, it is not proven yet that there exist context-free languages that cannot be recognized by a PEG.