Produkcja (computer science) - Production (computer science)

Produkcja lub produkcja reguła w informatyce jest reguła przepisywania określając zastąpienie symboli, które mogą być wykonywane rekurencyjnie do generowania nowych sekwencji symboli. Skończony zestaw produkcji jest głównym składnikiem w specyfikacji gramatykę formalną (konkretnie gramatyki generatywne ). Inne składniki są skończony zestaw z symboli nieterminalowi , skończony zestaw (znany jako alfabetu) z symboli końcowych , który jest odłączony od i odróżnić symboli czyli symbolu startu . ${\ Displaystyle P}$ ${\ Displaystyle N}$ ${\ Displaystyle \ Sigma}$ ${\ Displaystyle N}$ ${\ Displaystyle S \ w N}$

W nieograniczonego gramatyki , produkcja jest postaci gdzie i są arbitralne ciągi terminali i nieterminali jednak nie może być pusty. Jeśli jest łańcuchem pustym, to oznaczamy symbolem lub (zamiast pozostawić puste boczny prawy). Więc produkcje są członkami iloczyn kartezjański ${\ Displaystyle u \ v}$ ${\ Displaystyle U}$ ${\ V} displaystyle$ ${\ Displaystyle U}$ ${\ V} displaystyle$ ${\ Displaystyle \ epsilon}$ ${\ Displaystyle \ N}$

{\ Displaystyle v ^ {*} NV ^ {*} \ razy v ^ {*} = (v ^ {*} \ setminus \ Sigma ^ {*}) ^ V \ razy {} *}

,

gdzie to słowa , to gwiazda Kleene operatora wskazuje konkatenacji , a oznacza zestaw związek . Jeśli nie pozwolić symbol początek występuje w (słowo po prawej stronie), musimy zastąpić przez po prawej stronie symbolu kartezjańskiej produktu. ${\ Displaystyle V: = N \ kubek \ Sigma}$ ${\ Displaystyle {} *} {^}$ ${\ Displaystyle v ^ {*} NV ^ {*}}$ ${\ Displaystyle \} kubek$ ${\ V} displaystyle$ ${\ Displaystyle v ^ {*}}$ ${\ Displaystyle (V \ setminus \ {s \}) ^ {*}}$

Inne rodzaje formalnej gramatyki w hierarchii Chomsky'ego nałożyć dodatkowe ograniczenia dotyczące tego, co stanowi produkcję. Zwłaszcza w gramatyce bezkontekstowych , strona lewa produkcji musi być pojedynczym nieterminalowi symbol. Więc produkcje mają postać:

{\ Displaystyle N \ do (N \ kubek \ Sigma) ^ {*}}

generacja gramatyka

Aby wygenerować ciąg w języku, zaczyna się ciąg składający się tylko z jednym symbolem startowym , a następnie kolejno stosuje zasady (dowolną ilość razy, w dowolnej kolejności), aby przepisać ten ciąg. To zatrzymuje się, gdy otrzymujemy ciąg zawierający tylko terminale. Język składa się ze wszystkich ciągów, które mogą być generowane w ten sposób. Jakaś konkretna sekwencja wyborów prawnych podjętych w trakcie tego procesu przepisywania daje jeden konkretny ciąg znaków w języku. Jeśli istnieje wiele różnych sposobów generowania ten jeden ciąg, a następnie gramatyka mówi się niejednoznaczna .

Dla przykładu przyjmijmy, że alfabet składa się i , z symbolem startowym i mamy następujące zasady: ${\ A} displaystyle$ ${\ Displaystyle b}$ ${\ S} displaystyle$

1.

{\ Displaystyle S \} rightarrow ASB

2.

{\ Displaystyle S \ rightarrow BA}

Następnie zaczynamy , i może wybrać regułę stosuje się do niego. Jeśli zdecydujemy reguły 1, wymienimy się i uzyskać ciąg . Jeżeli ponownie wybierzemy reguły 1, wymienimy się i uzyskać ciąg . Proces ten jest powtarzany aż do mamy tylko symbole z alfabetu (tj, i ). Jeśli teraz wybrać regułę 2, wymienimy się i uzyskać ciąg , i gotowe. Możemy napisać tę serię wyborów bardziej krótko, za pomocą symboli: . Językiem gramatyki jest zbiorem wszystkich ciągów, które mogą być generowane przy użyciu tego procesu: . ${\ S} displaystyle$ ${\ S} displaystyle$ ${\ Displaystyle ASB}$ ${\ Displaystyle ASB}$ ${\ S} displaystyle$ ${\ Displaystyle ASB}$ ${\ Displaystyle aaSbb}$ ${\ A} displaystyle$ ${\ Displaystyle b}$ ${\ S} displaystyle$ ${\ Displaystyle BA}$ ${\ Displaystyle aababb}$ ${\ Displaystyle S \ strzałka_w_prawo ASB \ strzałka_w_prawo aaSbb \ strzałka_w_prawo aababb}$ ${\ Displaystyle \ {BA ABAB, aababb, aaababbb \ dotsc \}}$