Gramatyka bezkontekstowa

Definition - Gramatyka bezkontekstowa (CFG) składająca się z skończonego zestawu reguł gramatycznych jest poczwórną (N, T, P, S) gdzie

• N jest zbiorem symboli nieterminalnych.

• T to zestaw terminali, w których N ∩ T = NULL.

• P to zbiór zasad, P: N → (N ∪ T)*czyli lewa strona reguły produkcji P ma jakiś prawy lub lewy kontekst.

• S to symbol początku.

Example

• Gramatyka ({A}, {a, b, c}, P, A), P: A → aA, A → abc.
• Gramatyka ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε
• Gramatyka ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε

Generowanie drzewa pochodnego

Drzewo derywacyjne lub drzewo parsowania to uporządkowane drzewo z korzeniami, które graficznie przedstawia informacje semantyczne jako ciąg znaków wywodzących się z gramatyki bezkontekstowej.

Technika reprezentacji

• Root vertex - Musi być oznaczony symbolem startu.

• Vertex - Oznaczone symbolem nieterminowym.

• Leaves - Oznaczone symbolem zacisku lub ε.

Jeśli S → x ₁ x ₂ …… x _n jest regułą produkcyjną w CFG, to drzewo wyprowadzenia / drzewo wyprowadzenia będzie następujące -

Istnieją dwa różne podejścia do rysowania drzewa pochodnego -

Top-down Approach −

• Rozpoczyna się od symbolu początkowego S

• Schodzi do liści drzew za pomocą produkcji

Bottom-up Approach −

• Zaczyna się od liści drzew

• Przechodzi w górę do korzenia, który jest symbolem początkowym S

Wyprowadzenie lub wydajność drzewa

Wyprowadzenie lub wydajność drzewa parsowania jest końcowym ciągiem otrzymanym przez konkatenację etykiet liści drzewa od lewej do prawej, ignorując wartości Null. Jeśli jednak wszystkie liście mają wartość Null, wyprowadzenie ma wartość Null.

Example

Niech będzie CFG {N, T, P, S}

N = {S}, T = {a, b}, Symbol początkowy = S, P = S → SS | aSb | ε

Jednym z wyprowadzeń z powyższego CFG jest „abaabb”

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

Forma zdaniowa i drzewo wyprowadzania częściowego

Częściowe drzewo derywacji jest poddrzewem drzewa pochodnego / drzewa parsowania, tak że albo wszystkie jego dzieci znajdują się w poddrzewie, albo żadne z nich nie znajduje się w poddrzewie.

Example

Jeśli w jakimkolwiek CFG produkcje są -

S → AB, A → aaA | ε, B → Bb | ε

drzewo częściowej pochodnej może wyglądać następująco -

Jeśli drzewo częściowej pochodnej zawiera korzeń S, nazywa się to a sentential form. Powyższe poddrzewo również ma formę zdaniową.

Wyprowadzenie ciągu z lewej i prawej strony

• Leftmost derivation - Wyprowadzenie skrajnie lewe uzyskuje się przez zastosowanie produkcji do skrajnej lewej zmiennej w każdym kroku.

• Rightmost derivation - Najbardziej prawe wyprowadzenie uzyskuje się przez zastosowanie produkcji do skrajnej prawej zmiennej na każdym etapie.

Example

Niech będzie jakikolwiek zestaw reguł produkcji w CFG

X → X + X | X * X | X | za

nad alfabetem {a}.

Najbardziej lewe wyprowadzenie ciągu "a+a*a" może być -

X → X + X → a + X → a + X * X → a + a * X → a + a * a

Krokowe wyprowadzenie powyższego ciągu jest pokazane poniżej -

Najbardziej prawe wyprowadzenie powyższego ciągu "a+a*a" może być -

X → X * X → X * a → X + X * a → X + a * a → a + a * a

Krokowe wyprowadzenie powyższego ciągu jest pokazane poniżej -

Gramatyki rekurencyjne dla lewej i prawej strony

W gramatyce bezkontekstowej G, jeśli w formularzu jest produkcja X → Xa gdzie X nie jest terminalem i ‘a’ jest ciągiem terminali, nazywa się a left recursive production. Gramatyka mająca lewą rekurencyjną produkcję nazywa się aleft recursive grammar.

A jeśli w gramatyce bezkontekstowej G, jeśli jest produkcja w formie X → aX gdzie X nie jest terminalem i ‘a’ jest ciągiem terminali, nazywa się a right recursive production. Gramatyka mająca odpowiednią rekurencyjną produkcję nazywa się aright recursive grammar.