КПК и контекстно-свободная грамматика
Если грамматика G не зависит от контекста, мы можем построить эквивалентный недетерминированный КПК, который принимает язык, созданный с помощью контекстно-свободной грамматики G. Парсер может быть построен для грамматикиG.
Кроме того, если P является автоматом выталкивания, эквивалентную контекстно-свободную грамматику G можно построить, где
L(G) = L(P)
В следующих двух темах мы обсудим, как конвертировать из КПК в CFG и наоборот.
Алгоритм поиска КПК, соответствующего заданному CFG
Input - А CFG, G = (V, T, P, S)
Output- Эквивалент КПК, P = (Q, ∑, S, δ, q 0 , I, F)
Step 1 - Преобразуйте продукцию CFG в GNF.
Step 2 - КПК будет иметь только одно состояние {q}.
Step 3 - Начальный символ CFG будет стартовым символом в КПК.
Step 4 - Все нетерминалы CFG будут символами стека КПК, а все терминалы CFG будут входными символами КПК.
Step 5 - Для каждой продукции в форме A → aX где a - терминал и A, X являются комбинацией терминального и нетерминального, сделайте переход δ (q, a, A).
Проблема
Создайте КПК из следующего CFG.
G = ({S, X}, {a, b}, P, S)
где производство -
S → XS | ε , A → aXb | Ab | ab
Решение
Пусть эквивалентный КПК,
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
где δ -
δ (q, ε, S) = {(q, XS), (q, ε)}
δ (q, ε, X) = {(q, aXb), (q, Xb), (q, ab)}
δ (q, a, a) = {(q, ε)}
δ (q, 1, 1) = {(q, ε)}
Алгоритм поиска CFG, соответствующего данному КПК
Input - А CFG, G = (V, T, P, S)
Output- Эквивалентный КПК, P = (Q, ∑, S, δ, q 0 , I, F) такой, что нетерминалы грамматики G будут {X wx | W, X ∈ Q} и начальное состояние будет q0, F .
Step 1- Для любых w, x, y, z ∈ Q, m ∈ S и a, b ∈ ∑, если δ (w, a, ε) содержит (y, m) и (z, b, m) содержит (x, ε) добавьте правило продукции X wx → a X yz b в грамматику G.
Step 2- Для каждого w, x, y, z ∈ Q добавьте правило продукции X wx → X wy X yx в грамматику G.
Step 3- Для w ∈ Q добавьте правило продукции X ww → ε в грамматику G.