Каковы алгоритмы разбора запрограммированных грамматик?

Я думаю, это хорошо объяснено в мощь запрограммированных грамматик с графики из разных классов:

Контекстно-свободная грамматика определяется как четверка G = (N, T, S, P), где N — конечное непустое множество, называемое нетерминальным алфавитом, T — конечное непустое множество, называемое терминальным алфавитом, (N ∩ T = ∅), S ∈ N — начальный символ, а P — конечное подмножество. из N × (N ∪ T)∗ называется набором правил. Правила также называются постановками.

Запрограммированная грамматика (без проверки внешнего вида) представляет собой набор из шести кортежей G = (N, T, S, Lab, P, PG), где N , T and S указаны как в контекстно-свободной грамматике, Lab — это алфавит (меток), P — конечный набор контекстно-свободных правил, называемых базовыми произведениями множества. , а PG — это конечное множество троек r = (q, p, σ), где q ∈ Lab — это метка r, p ∈ P — это контекстно-свободная продукция, называемая основной продукцией r, а σ — это подмножество Lab, называемое полем успеха r. Элементы PG называются правилами G.

Язык L(G), сгенерированный запрограммированной грамматикой G, указанной выше, определяется как множество всех слов w ∈ T∗, таких, что существует производное S = w0 =⇒r1 w1 =⇒r2 w2 =⇒r3 . . . =⇒rk wk = w,, где k ≥ 1 и, для 1 ≤ i ≤ k, wi−1 = wi−1 Ai wi−1 и wi = wi−1 vi wi−1, для некоторых слов wi−1 , wi−1 ∈ (N ∪ T)∗ , ri = (qi , Ai → vi , σi) и, для i < k, qi+1 ∈ σi.

Извините за отсутствие LaTeX.

Подобно тому, как лемма Огдена сильнее, чем лемма прокачки (из-за маркировки), концепция запрограммированной грамматики является более строгой. чем контекстно-свободный из-за этих маркировок.