# Parsing Expression Grammars and Their Induction Algorithm
## 3 Induction Algorithm
### Python's PEG Library Performance Evaluation  
In order to assess the fifth property of Algorithm 1 (for random words output PEGs are many times smaller than the input), we created random sets of words with different sizes, lengths and alphabets. Table 1 shows our settings in this respect. Naturally, \(|X|\) and \(|Y|\) denote the number of examples and counter-examples, while words' lengths vary from \(d_{max}\) to \(d_{min}\). Those datasets are publicly available along with the source code of our PEG library. Figure 3 depicts the number of symbols in a PEG and the number of letters in a respective test set. The number of letters in an input file simply equals \(\sum_{w\in X\cup Y}\left(|w|+1\right)\), where \(+1\) stands for a new line sign (i.e., words' separator). As for PEGs, the symbol \(\gg\) has not been counted, since it may be omitted. Outside the Python language, concatenation of two symbols, for instance \(a\) and \(b\), can be written as \(ab\) instead of \(a\gg b\). Notice also that in Figure 3 the ordinates are in the logarithmic scale, because the differences are large. \begin{table}
\begin{tabular}{r r r r r r} \hline \hline
**No.** & \(|\Sigma|\) & \(|X|\) & \(|Y|\) & \(d_{min}\) & \(d_{max}\) \\ \hline
1 & 2 & 10 & 10 & 1 & 10 \\
2 & 2 & 100 & 100 & 2 & 20 \\
3 & 4 & 500 & 500 & 3 & 30 \\
4 & 4 & 1000 & 1000 & 4 & 40 \\
5 & 8 & 5000 & 5000 & 5 & 50 \\
6 & 8 & 6000 & 6000 & 6 & 60 \\
7 & 16 & 7000 & 7000 & 7 & 70 \\
8 & 16 & 8000 & 8000 & 8 & 80 \\
9 & 32 & 9000 & 9000 & 9 & 90 \\
10 & 32 & 10,000 & 10,000 & 10 & 100 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The settings of the generator of random input for our PEG algorithm. The runtime of Python implementation of the proposed PEG library was benchmarked against comparable libraries, i.e., Arpeggio and Grako. The pyPEG library was rejected, because we were unable to define more complex expressions with it. As a testbed we have chosen [PERSON]'s languages [19]. This test set contains seven different expressions that serve as rules for the generation of words over a binary alphabet. Their description in a natural language can be found in Table 2. Seven regular expressions appropriate to the rules were created, and then the generators of random input words were implemented. Thus, for every language we had two sets: matching (positive) and non-matching (negative) words to a particular regular expression. These expressions take the following forms:  
1. a*
2. (ab)*
3. ((b[(aa))](((a(bb))((bb))(a(bb))*)(aa))*((a?)[((a(bb))((bb))(a(bb)))*)(a?))) 4. a*((b[bb)aa*)*(b[bb]a*)
5. (aa|bb)*((ba|ab)(bb|aa)*(ba|ab)(bb|aa)*)*(aa|bb)*
6. ((a(ab)*(b[aa)])(b(ba)*(a|bb)))*
7. a*b*a*b*  
Equivalent PEG expressionswere defined as well in every comparable library (see Table 2). Table 3 summarizes CPU time results. Every row contains the means for 30 runs. In all experiments we used the implementation of algorithms written in Python (our PEG library, Grako, and Arpeggio) and C++ EGG. An interpreter ran on a four-core Intel i7-965, 3.2 GHz processor in a Windows 10 operating system with 12 GB RAM. As can be seen, in all cases our library worked much faster than other Python libraries. Grammar 3 was skipped because we were unable to define it either by means of the Arpeggio or Grako libraries. It should be stated, however, that both of the libraries have more functionality than our PEG library, its principal function being only the membership operation, i.e., matching or not a word to a PEG. As a