“Hardest” languages to test parsers. Most examples taken from
Expressive power of LL(k) Boolean grammars
Linear context-free language
”Balanced brackets”:
{anbn∣n≥0}
And variations of the above:
{anbncl∣n,l≥0}
{ambmanbn∣m,n≥0}
Classical context sensitive (LinConjLL)
Classical context sensitive example:
{anbncn∣n≥0}
PEG
Same example used by Ford to show that PEG can handle context sensitive grammar.
Actually it can’t handle exactly this language, but it still can handle other context sensitive language. See https://github.com/SRI-CSL/PVSPackrat/issues/3
Other context sensitive
{an2∣n≥0}
{an∣n is prime}
”copy langauge”:
{ww∣w∈Σ∗}
TAG (Tree Adjoining Grammar)
{anbmcndm∣n,m≥0}
MG (Minimalist Grammar)
{anbncnenfn∣n≥0}
CFLL, but not in LinCFLL
{anbncs∣n≥0,s∈{a,b}}
Strongly non-left-recursive Boolean P-complete language
an−1−jnban−2−jn−1b…a2−j3ba1−j2b
Strongly non-left-recursive conjunctive language
{wcw∣w∈{a,b}∗}
Jeż language
{a4n∣n≥0}
LL(1) linear Boolean language
{ambn∣0≤m≤n}
Boolean
{anb2n∣n≥1}
Context sensitive with backreferences
(a*)b\1b\1
anbanban