A Note on Parsing Expression Languages

Thanks to a recent excursion into the realm of RCGs, I have found the answer to another comparison with the boolean closure of some context-free languages: the comparison with PEL (Ford, 2004).

Parsing expression languages are closed under union, intersection, and complement, and properly include DCFLs (Birman and Ullman, 1973). Thus a comparison with the boolean closure of DCFLs is of some interest (on the other hand, it is widely conjectured that they do not capture all the CFLs). Using again the results of Kutrib et al. (2004, Theorem 17), we know that the language

ℒ_exp = { a²ⁿ | n ≥ 1 },

which is not semilinear, is not in Bool(CFL) and thus not in Bool(DCFL).

But we can generate this language with the PEG

S ← a S a / a a

(see Exercise 6.1.1 by Aho and Ullman, 1972). Thus the inclusion of Bool(DCFL) in the set of parsing expression languages is proper.