# Parsing Expression Grammars and Their Induction Algorithm
## 3 Induction Algorithm
### Python's PEG Library Performance Evaluation
\begin{table}
\begin{tabular}{l l l} \hline \hline
**No.** & **Description** & **PEG Grammar** \\ \hline
1 & Sequence of a’s & \(S\Leftarrow a\gg S\mid\sim\)(\(a\mid b\)) \\ \hline
2 & Sequence of (ab)’s & \(S\Leftarrow a\gg b\gg S\mid\sim\)(\(a\mid b\)) \\ \hline  & Any string without an odd & \(A\Leftarrow a\gg\
eg a\mid a\gg a\gg A\) \\  & number of consecutive b’s & \(B\Leftarrow b\gg\
eg b\mid b\gg b\gg B\) \\  & after an odd number of & \(C\Leftarrow a\gg A\mid\sim a\) \\  & consecutive a’s & \(D\Leftarrow b\gg B\mid\sim\) \\  & & \(S\Leftarrow(a\gg a\mid b)\gg S\mid A\gg D\gg S\mid\sim\)(\(a\mid b\)) \\ \hline  & Any string without more & \(S\Leftarrow(a\mid\epsilon)\gg(+((b\gg b\mid b)\gg\
eg a)\mid\epsilon)\gg\) \\  & than two consecutive b’s & \((b\gg b\gg\
eg(a\mid b)\mid b\gg\
eg(a\mid b)\mid\sim\)(\(a\mid b)))\) \\ \hline  & Any string of even length & \(A\Leftarrow(a\gg a\mid b\gg b)\mid\epsilon\) \\  & that, making pairs, has an & \(B\Leftarrow a\gg b\mid b\gg a\) \\  & even number of (ab)’s or & \(S\Leftarrow A\gg(+(B\gg A\gg B\gg A)\mid\epsilon)\gg A\gg\
eg(a\mid b)\) \\ \hline  & Any string such that the & \(A\Leftarrow a\gg(+(a\gg b)\mid\epsilon)\gg(b\mid a\gg a)\) \\  & difference between the & \(B\Leftarrow b\gg(+(b\gg a)\mid\epsilon)\gg(a\mid b\gg b)\) \\  & multiple of three & \(S\Leftarrow(A\mid B)\gg\
eg(a\mid b)\mid\sim\)(\(a\mid b\)) \\ \hline  & Zero or more a’s followed by & \(A\Leftarrow+a\mid\epsilon\) \\
7 & zero or more a’s followed by & \(B\Leftarrow+b\mid\epsilon\) \\  & zero or more b’s & \(S\Leftarrow A\gg B\gg A\gg B\gg\
eg(a\mid b)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: PEG expressions created based on _[PERSON]_ (1982) languages. result, Arpeggio, Grako, and pyPeg are relatively not intuitive and obvious, especially for users not familiarized with formal languages theory. The dash character in the EGG result denotes segmentation runtime error. As expected the C++ library (EGG) overcame its Python counterparts. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Case No.** & **Positive/Negative** & **Word Length** & **PEG [s]** & **Grako [s]** & **Arpeggio [s]** & **EGG [s]** \\ \hline  
ositive & 1–100 & \textless{}0.01 & 0.2 & 0.02 & \textless{}0.01 \\
5 & Positive & 101–1000 & 0.04 & 2.12 & 0.36 & \textless{}0.01 \\
5 & Positive & 1001–10,000 & 0.26 & 12.37 & 2.28 & 0.01 \\
5 & Positive & 10,001–100,000 & 2.4 & 102.19 & 20.29 & \textless{}0.01 \\
5 & Negative & 1–100 & 0.01 & 0.27 & 0.02 & 0.05 \\
5 & Negative & 101–1000 & 0.04 & 2.11 & 0.32 & 0.02 \\
5 & Negative & 1001–10,000 & 0.25 & 11.93 & 2.01 & 0.08 \\
5 & Negative & 10,001–100,000 & 2.32 & 98.61 & 17.98 & 0.08 \\
6 & Positive & 1–100 & 0.01 & 0.23 & 0.02 & \textless{}0.01 \\
6 & Positive & 101–1000 & 0.05 & 2.52 & 0.17 & \textless{}0.01 \\
6 & Positive & 1001–10,000 & 0.40 & 17.64 & 1.21 & \textless{}0.01 \\
6 & Positive & 10,001–100,000 & 1.67 & 71.70 & 4.93 & 0.01 \\
6 & Negative & 1–100 & 0.01 & 0.34 & 0.02 & 0.03 \\
6 & Negative & 101–1000 & 0.12 & 5.34 & 0.33 & 0.06 \\
6 & Negative & 1001–10,000 & 1.05 & 44.86 & 2.61 & 0.09 \\
6 & Negative & 10,001–100,000 & 4.61 & 187.90 & 10.42 & 0.17 \\
7 & Positive & 1–100 & \textless{}0.01 & 0.23 & 0.02 & \textless{}0.01 \\
7 & Positive & 101–1000 & 0.04 & 1.85 & 0.09 & \textless{}0.01 \\
7 & Positive & 1001–10,000 & 0.17 & 7.94 & 0.42 & 0.01 \\
7 & Positive & 10,001–100,000 & 1.91 & 73.4 & 3.92 & \textless{}0.01 \\
7 & Negative & 1–100 & \textless{}0.01 & 0.16 & 0.01 & 0.03 \\
7 & Negative & 101–1000 & 0.02 & 1.09 & 0.06 & 0.02 \\
7 & Negative & 1001–10,000 & 0.11 & 5.37 & 0.28 & 0.15 \\
7 & Negative & 10,001–100,000 & 1.26 & 49.92 & 2.64 & 0.10 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Average CPU times for available Python PEG libraries (in seconds).