Interesting languages

“Hardest” languages to test parsers. Most examples taken from Expressive power of LL(k) Boolean grammars

Linear context-free language

“Balanced brackets”:

\{a^n b^n | n \geq 0\}

And variations of the above:

\{a^n b^n c^l | n, l \geq 0\}

\{a^m b^m a^n b^n | m, n \geq 0\}

Classical context sensitive example:

\{a^nb^nc^n | n \geq 0\}

S → A&C
A → aA | D
D → bDc | ε
C → aCc | B
B → bB | ε

Same example used by Ford to show that PEG can handle context sensitive grammar.

A ← aAb/ε
B ← bBc/ε
S ← &(A!b)a∗ B!.

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

\{a^{n^2} | n \geq 0\}

\{a^{n} | n \text{ is prime}\}

“copy langauge”:

\{ww | w \in \Sigma^*\}

\{ a^n b^m c^n d^m | n, m \geq 0 \}

\{ a^n b^n c^n e^n f^n | n \geq 0 \}

\{a^n b^n cs | n \geq 0, s \in \{a, b\}\}

S → X &¬T
T → X &¬Aca&¬Acb
A → aAb | ε
X → aX | bX | cX | ε.

a^{n−1−j_n} b a^{n−2−j_{n−1}} b \ldots a^{2−j_3} b a^{1−j_2} b

S → E&¬AbS&¬CS
A → aA | ε
C → aCAb | b
E → aE | bE | ε.

\{wcw | w \in \{a, b\}^*\}

S → C &D
C → XCX | c
X → a | b
D → aA&aD | bB&bD | cE
A → XAX | cEa
B → XBX | cEb
E → aE | bE | ε.

\{a^{4n} | n \geq 0\}

A1 → A1 A3 & A2 A2 | a
A2 → A1 A1 & A2 A6 | aa
A3 → A1 A2 & A6 A6 | aaa
A6 → A1 A2 & A3 A3.

\{a^m b^n | 0 \leq m \leq n\}

S → aS&¬A | bB
A → aAb | ε
B → bB | ε

\{ a^n b^{2^n} | n \geq 1\}

a^nba^nba^n