Gramatyka bezkontekstowa — Context-free grammar

W teorii języka formalnego gramatyka bezkontekstowa ( CFG ) to gramatyka formalna, której reguły produkcji mają postać

${\ Displaystyle A \ \ do \ \ alfa}$

z pomocą pojedynczego nieterminalowi symbol i ciąg zacisków i / lub nieterminali ( może być pusta). Gramatyka formalna jest „bezkontekstowa”, jeśli jej reguły produkcji mogą być stosowane niezależnie od kontekstu nieterminala. Bez względu na to, jakie symbole go otaczają, pojedynczy nieterminal po lewej stronie można zawsze zastąpić prawym. To właśnie odróżnia ją od gramatyki kontekstowej . ${\ Displaystyle A}$ ${\ Displaystyle \ alfa}$${\ Displaystyle \ alfa}$

Gramatyka formalna jest zasadniczo zbiorem reguł produkcji, które opisują wszystkie możliwe ciągi znaków w danym języku formalnym. Zasady produkcji to proste zamienniki. Na przykład pierwsza zasada na zdjęciu:

${\ Displaystyle \ langle {\ tekst {Stmt}} \ rangle \ do \ langle {\ tekst {identyfikator}} \ rangle = \ langle {\ tekst {wyraż}} \ rangle;}$

zastępuje się . Dla danego symbolu nieterminalowego może istnieć wiele reguł zastępowania. Język generowany przez gramatykę jest zbiorem wszystkich łańcuchów symboli terminalowych, które mogą być wyprowadzone, przez powtarzające się zastosowania reguł, z określonego symbolu nieterminalnego ("symbol startowy"). Symbole nieterminalne są używane podczas procesu wyprowadzania, ale nie pojawiają się w końcowym ciągu wynikowym. ${\ Displaystyle \ langle {\ tekst {Stmt}} \ rangle}$${\ Displaystyle \ langle {\ tekst {identyfikator}} \ rangle = \ langle {\ tekst {wyraż}} \ rangle;}$

Języki generowane przez gramatyki bezkontekstowe są znane jako języki bezkontekstowe (CFL). Różne gramatyki bezkontekstowe mogą generować ten sam język bezkontekstowy. Ważne jest, aby odróżnić właściwości języka (właściwości wewnętrzne) od właściwości danej gramatyki (właściwości zewnętrzne). Równość język zapytania (zrobić dwa podane gramatyk bezkontekstowych generować ten sam język?) Jest nierozstrzygalny .

Gramatyki bezkontekstowe powstają w językoznawstwie, gdzie są używane do opisu struktury zdań i słów w języku naturalnym i zostały w rzeczywistości wymyślone przez językoznawcę Noama Chomsky'ego w tym celu. Natomiast w informatyce , wraz ze wzrostem użycia rekurencyjnie definiowanych pojęć, były one coraz częściej stosowane. We wczesnej aplikacji do opisu struktury języków programowania używane są gramatyki . W nowszych aplikacjach są one używane w podstawowej części Extensible Markup Language (XML) o nazwie Document Type Definition .

W językoznawstwie niektórzy autorzy używają terminu gramatyka struktury fraz w odniesieniu do gramatyk bezkontekstowych, przy czym gramatyki struktury fraz różnią się od gramatyk zależności . W informatyce popularnym zapisem gramatyk bezkontekstowych jest forma Backus-Naur lub BNF .

Tło

Przynajmniej od czasów Pāṇini lingwiści opisali gramatyki języków pod kątem ich struktury blokowej i opisali, w jaki sposób zdania są rekurencyjnie budowane z mniejszych fraz i ostatecznie pojedynczych słów lub elementów słownych. Istotną właściwością tych struktur blokowych jest to, że jednostki logiczne nigdy się nie nakładają. Na przykład zdanie:

John, którego niebieski samochód stał w garażu, poszedł do sklepu spożywczego.

można umieścić w nawiasach logicznych (z logicznymi metasymbole [ ] ) w następujący sposób:

[ John [ , [ którego [ niebieski samochód ]] [ był [ w [ garaż ]]] , ]] [ podszedł [ do [ [ sklep spożywczy ]]]] .

Gramatyka bezkontekstowa zapewnia prosty i matematycznie precyzyjny mechanizm opisywania metod, za pomocą których frazy w niektórych językach naturalnych są budowane z mniejszych bloków, odwzorowując w naturalny sposób „strukturę blokową” zdań. Jego prostota sprawia, że ​​formalizm jest podatny na rygorystyczne badania matematyczne. Ważne cechy składni języka naturalnego, takie jak zgodność i odwołanie, nie są częścią gramatyki bezkontekstowej, ale podstawową rekurencyjną strukturą zdań, sposobem, w jaki zdania zagnieżdżają się w innych zdaniach oraz sposobem, w jaki listy przymiotników i przysłówków są połknięte przez rzeczowniki i czasowniki, jest dokładnie opisane.

Gramatyki bezkontekstowe to szczególna forma systemów Semi-Thue, które w swojej ogólnej formie wywodzą się z prac Axela Thue .

Formalizm gramatyk bezkontekstowych został opracowany w połowie 1950 przez Noama Chomsky'ego , a także ich klasyfikację jako szczególny rodzaj z formalnym gramatyki (który nazwał gramatyk fraza struktura ). To, co Chomsky nazwał gramatyką struktury fraz, jest obecnie znane również jako gramatyka okręgowa, w której gramatyki okręgowe stoją w przeciwieństwie do gramatyk zależnościowych . W ramach gramatyki generatywnej Chomsky'ego składnia języka naturalnego została opisana za pomocą reguł bezkontekstowych połączonych z regułami transformacji.

Struktura blokowa została wprowadzona do języków programowania komputerowego przez projekt Algol (1957-1960), który w konsekwencji zawierał również gramatykę bezkontekstową do opisu powstałej składni Algola. Stało się to standardową cechą języków komputerowych, a notacja gramatyczna używana w konkretnych opisach języków komputerowych stała się znana jako forma Backus-Naur , po dwóch członkach komitetu projektowego języka Algol. Aspekt „struktury blokowej”, który przechwytują gramatyki bezkontekstowe, jest tak fundamentalny dla gramatyki, że terminy składnia i gramatyka są często utożsamiane z regułami gramatyki bezkontekstowej, zwłaszcza w informatyce. Formalne ograniczenia, które nie zostały uchwycone przez gramatykę, są wówczas uważane za część „semantyki” języka.

Gramatyki bezkontekstowe są na tyle proste, że umożliwiają konstruowanie wydajnych algorytmów analizowania, które dla danego ciągu określają, czy i jak można go wygenerować na podstawie gramatyki. Earley analizator jest przykładem takiego algorytmu, podczas gdy powszechnie stosowane LR i Parsery LL prostsze algorytmy, które zajmują jedynie bardziej restrykcyjnych podzbiorów bezkontekstowych gramatyk.

Formalne definicje

Gramatyka bezkontekstowa G jest zdefiniowana przez 4- krotkę , gdzie ${\ Displaystyle G = (V \ Sigma, R, S)}$

1. V jest zbiorem skończonym; każdy element jest nazywany znakiem nieterminalnym lub zmienną . Każda zmienna reprezentuje inny typ frazy lub klauzuli w zdaniu. Zmienne są również czasami nazywane kategoriami składniowymi. Każda zmienna definiuje podjęzyk języka zdefiniowanego przez G .${\ Displaystyle v \ w V}$
2. Σ jest skończonym zbiorem terminali s, rozłącznych od V , które tworzą rzeczywistą treść zdania. Zbiór terminali to alfabet języka zdefiniowanego przez gramatykę G .
3. R jest skończoną relacją w , gdzie gwiazdka reprezentuje operację gwiazdy Kleene . Elementy R są nazywane regułami (przepisywania) lub produkcją gramatyki. (również powszechnie symbolizowany przez P )${\ Displaystyle V \ razy (V \ filiżanka \ Sigma) ^ {*}}$
4. S jest zmienną startową (lub symbolem startowym), używaną do reprezentowania całego zdania (lub programu). Musi to być element V .

Notacja reguł produkcji

Przepis produkcji w R jest sformalizowane matematycznie w postaci pary , w którym jest nieterminalowi i stanowi łańcuch zmiennych i / lub terminal; zamiast używać notacji par uporządkowanych , reguły produkcji są zwykle pisane przy użyciu operatora strzałki z jego lewą stroną i β jako prawą stroną: . ${\displaystyle (\alfa,\beta)\w R}$${\ Displaystyle \ alfa \ w V}$${\ Displaystyle \ beta \ w (V \ filiżanka \ Sigma) ^ {*}}$${\ Displaystyle \ alfa}$${\ Displaystyle \ alfa \ rightarrow \ beta}$

Dopuszcza się, aby β był ciągiem pustym i w tym przypadku zwyczajowo oznaczamy go przez ε. Forma nazywa się produkcją ε . ${\ Displaystyle \ alfa \ rightarrow \ varepsilon}$

Powszechnie wymienia się wszystkie prawe strony tej samej lewej strony w tym samym wierszu, używając | ( symbol rury ), aby je oddzielić. Reguły i dlatego mogą być zapisywane jako . W tym przypadku i są nazywane odpowiednio pierwszą i drugą alternatywą. ${\displaystyle \alfa \rightarrow \beta_{1}}$${\ Displaystyle \ alfa \ rightarrow \ beta _ {2}}$${\ Displaystyle \ alfa \ rightarrow \ beta _ {1} \ mid \ beta _ {2}}$${\displaystyle \beta_{1}}$${\displaystyle \beta_{2}}$

Stosowanie reguł

Dla dowolnych łańcuchów , mówimy , że u daje bezpośrednio v , zapisane jako , if with i takie , że i . Zatem v jest wynikiem zastosowania reguły do u . ${\ Displaystyle u, v \ w (V \ puchar \ Sigma) ^ {*}}$${\displaystyle u\rightarrow v\,}$${\ Displaystyle \ istnieje (\ alfa, \ beta) \ w R}$${\ Displaystyle \ alfa \ w V}$${\ Displaystyle u_ {1}, u_ {2} \ w (V \ puchar \ Sigma) ^ {*}}$${\displaystyle u\,=u_{1}\alfa u_{2}}$${\displaystyle v\,=u_{1}\beta u_{2}}$${\displaystyle (\alfa ,\beta )}$

Powtarzające się stosowanie reguł

Dla strun mówimy u daje v lub v jest pochodzący z U , jeśli istnieje liczba całkowita dodatnia k i ciągi takie, że . Ta relacja jest oznaczona lub w niektórych podręcznikach. Jeśli , relacja jest zachowana. Innymi słowy, i są na zwrotne przechodni zamknięcie (pozwalającą na łańcuch, z wytworzeniem się) i czasownik zamknięcie (wymagające co najmniej jeden etap) , odpowiednio. ${\ Displaystyle u, v \ w (V \ filiżanka \ Sigma) ^ {*}}$ ${\ Displaystyle u_ {1}, \ cdots, u_ {k} \ w (V \ filiżanka \ Sigma) ^ {*}}$${\ Displaystyle u = u_ {1} \ strzałka w prawo u_ {2} \ strzałka w prawo \ cdots \ strzałka w prawo u_ {k} = v}$${\ Displaystyle u {\ stos {*} {\ Strzałka w prawo}} v}$${\ Displaystyle u \ Strzałka w prawo \ Strzałka w prawo v}$${\displaystyle k\geq 2}$${\ Displaystyle u {\ stos {+} {\ Strzałka w prawo}} v}$${\ Displaystyle ({\ stos {*} {\ Strzałka w prawo}})}$${\ Displaystyle ({\ stos {+} {\ Strzałka w prawo}})}$${\ styl wyświetlania (\strzałka w prawo)}$

Język bez kontekstu

Język gramatyki to zbiór ${\ Displaystyle G = (V \ Sigma, R, S)}$

${\ Displaystyle L (G) = \ {w \ w \ Sigma ^ {*}: S {\ stos {*} {\ Strzałka w prawo}} w \}}$

wszystkich ciągów symboli terminala, które można wyprowadzić z symbolu startowego.

Mówi się, że język L jest językiem bezkontekstowym (CFL), jeśli istnieje CFG G , taki, że . ${\displaystyle L\,=\,L(G)}$

Niedeterministyczne automaty pushdown rozpoznają dokładnie języki bezkontekstowe.

Przykłady

Słowa połączone z ich rewersem

Gramatyka , z produkcjami ${\ Displaystyle G = (\ {S \}, \ {a, b \}, P, S)}$

S → aSa ,

S → bSb ,

S → ε ,

jest bezkontekstowy. To nie jest właściwe, ponieważ zawiera produkcję ε. Typowym wyprowadzeniem w tej gramatyce jest

S → aSa → aaSaa → aabSbaa → aabba .

To wyjaśnia, że . Język jest bezkontekstowy, jednak można udowodnić, że nie jest regularny . ${\ Displaystyle L (G) = \ {ww ^ {R}: w \ w \ {a, b \} ^ {*} \}}$

Jeśli produkcje

S → a ,

S → b ,

są dodawane, otrzymuje się gramatykę bezkontekstową dla zbioru wszystkich palindromów nad alfabetem { a , b } .

Dobrze uformowane nawiasy

Kanonicznym przykładem gramatyki bezkontekstowej jest dopasowanie nawiasów, które jest reprezentatywne dla przypadku ogólnego. Istnieją dwa symbole końcowe „(” i „)” i jeden symbol nieterminalny S. Zasady produkcji to

S → SS ,

S → ( S ) ,

S → ()

Pierwsza reguła pozwala na mnożenie symbolu S; druga zasada pozwala na umieszczenie symbolu S w dopasowanych nawiasach; a trzecia reguła kończy rekurencję.

Dobrze uformowane nawiasy zagnieżdżone i nawiasy kwadratowe

Drugim kanonicznym przykładem są dwa różne rodzaje dopasowywania nawiasów zagnieżdżonych, opisane w produkcjach:

S → SS

S → ()

S → ( S )

S → []

S → [ S ]

z symbolami terminala [ ] ( ) i nieterminalem S.

W tej gramatyce można wyprowadzić następującą sekwencję:

([ [ [ ()() [ ][ ] ] ]([ ]) ])

Pasujące pary

W gramatyce bezkontekstowej możemy łączyć znaki w pary tak, jak robimy to z nawiasami . Najprostszy przykład:

S → aSb

S → ab

Ta gramatyka generuje język , który nie jest regularny (zgodnie z lematem o pompowaniu dla języków regularnych ). ${\ Displaystyle \ {a ^ {n} b ^ {n}: n \ geq 1 \}}$

Znak specjalny ε oznacza pusty ciąg. Zmieniając powyższą gramatykę na

S → aSb

S → ε

zamiast tego otrzymujemy gramatykę generującą język . Różni się tylko tym, że zawiera pusty ciąg, podczas gdy oryginalna gramatyka nie. ${\ Displaystyle \ {a ^ {n} b ^ {n}: n \ geq 0 \}}$

Odrębna liczba a i b

Gramatyka bezkontekstowa dla języka składającego się ze wszystkich ciągów znaków powyżej {a,b} zawierających nierówną liczbę a i b:

S → T | U

T → VaT | VaV | TaV

U → VbU | VbV | UbV

V → aVbV | bVaV | ε

Tutaj nieterminal T może generować wszystkie łańcuchy z większą liczbą a niż b, nieterminal U generuje wszystkie łańcuchy z większą liczbą b niż a, a nieterminal V generuje wszystkie łańcuchy z równą liczbą a i b. Pominięcie trzeciej alternatywy w regułach T i U nie ogranicza języka gramatyki.

Drugi blok b podwójnego rozmiaru

Innym przykładem języka nieregularnego jest . Jest bezkontekstowy, ponieważ można go wygenerować za pomocą następującej gramatyki bezkontekstowej: ${\ Displaystyle \ {{\ tekst {b}} ^ {n} {\ tekst {a}} ^ {m} {\ tekst {b}} ^ {2n}: n \ geq 0, m \ geq 0 \} }$

S → bSbb | A

A → aA | ε

Formuły logiczne pierwszego rzędu

Te zasady formacji do warunków i formuł logiki formalnej pasuje do definicji bezkontekstowych gramatyki, chyba że zbiór symboli może być nieskończona i nie może być więcej niż jeden symbol początek.

Przykłady języków, które nie są bezkontekstowe

W przeciwieństwie do dobrze uformowanych nawiasów zagnieżdżonych i nawiasów kwadratowych w poprzedniej sekcji, nie ma gramatyki bezkontekstowej do generowania wszystkich sekwencji dwóch różnych typów nawiasów, z których każdy jest oddzielnie zrównoważony bez względu na drugi , gdzie dwa typy nie muszą być zagnieżdżone w jednym inny, na przykład:

[ ( ] )

lub

[ [ [ [(((( ] ] ] ]))))(([ ))(([ ))([ )( ])( ])( ])

Fakt, że język ten nie jest bezkontekstowy, można udowodnić za pomocą lematu o pompowaniu dla języków bezkontekstowych oraz dowodu przez sprzeczność, przy czym wszystkie słowa formy powinny należeć do języka. Język ten należy raczej do bardziej ogólnej klasy i można go opisać za pomocą gramatyki spójników , która z kolei obejmuje również inne języki nie bezkontekstowe, takie jak język wszystkich słów formy . ${\ Displaystyle {(} ^ {n} {[} ^ {n} {)} ^ {n} {]} ^ {n}}$${\ Displaystyle {\ tekst {a}} ^ {n} {\ tekst {b}} ^ {n} {\ tekst {c}} ^ {n}}$

Regularne gramatyki

Każda zwykła gramatyka jest bezkontekstowa, ale nie wszystkie gramatyki bezkontekstowe są regularne. Na przykład poniższa gramatyka bezkontekstowa jest również regularna.

S → a

S → aS

S → bS

W tutaj zaciski są i B , podczas gdy tylko nieterminalowi jest S . Opisany język to wszystkie niepuste ciągi s i s, które kończą się na . ${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$

Ta gramatyka jest regularna : żadna reguła nie ma więcej niż jednego nieterminala po swojej prawej stronie, a każdy z tych nieterminali znajduje się na tym samym końcu po prawej stronie.

Każda gramatyka regularna odpowiada bezpośrednio niedeterministycznemu automatowi skończonemu , wiemy więc, że jest to język regularny .

Używając symboli kreski pionowej, powyższą gramatykę można opisać bardziej zwięźle w następujący sposób:

S → a | jako | bS

Pochodne i drzewa składniowe

Wyprowadzenie z ciągiem do gramatyki jest ciągiem zastosowań reguł gramatyki, które przekształcają się symbol startu do łańcucha. Wyprowadzenie dowodzi, że ciąg należy do języka gramatyki.

Wyprowadzenie jest w pełni określone przez podanie, dla każdego kroku:

• zasada zastosowana w tym kroku
• występowanie jego lewej strony, do której jest stosowany

Dla jasności zwykle podaje się również ciąg pośredni.

Na przykład za pomocą gramatyki:

1. S → S + S
2. S → 1
3. S → a

sznurek

1 + 1 +

można wyprowadzić z symbolu początkowego S z następującym wyprowadzeniem:

S

→ S + S (zgodnie z zasadą 1. na S )

→ S + S + S (zgodnie z zasadą 1. na drugim S )

→ 1 + S + S (zgodnie z zasadą 2. na pierwszym S )

→ 1 + 1 + S (zgodnie z zasadą 2. na drugim S )

→ 1 + 1 + a (zgodnie z zasadą 3. na trzecim S )

Często stosuje się strategię, która deterministycznie wybiera następny nieterminal do przepisania:

• w najbardziej lewostronnej derywacji zawsze jest to najbardziej lewy nieterminal;
• w najbardziej prawostronnym wyprowadzeniu jest zawsze najbardziej prawostronnym nieterminalem.

Przy takiej strategii wyprowadzenie jest całkowicie zdeterminowane kolejnością zastosowanych reguł. Na przykład jedną skrajną lewą derywacją tego samego ciągu jest

S

→ S + S (zgodnie z zasadą 1 po lewej stronie S )

→ 1 + S (zgodnie z zasadą 2 po lewej stronie S )

→ 1 + S + S (zgodnie z zasadą 1 po lewej stronie S )

→ 1 + 1 + S (zgodnie z zasadą 2 po lewej stronie S )

→ 1 + 1 + a (zgodnie z zasadą 3 po lewej stronie S ),

co można podsumować jako

Zasada nr 1

zasada 2

Zasada nr 1

zasada 2

zasada 3.

Jednym najbardziej prawym pochodnym jest:

S

→ S + S (zgodnie z zasadą 1 po prawej stronie S )

→ S + S + S (zgodnie z zasadą 1 po prawej stronie S )

→ S + S + a (zgodnie z zasadą 3 po prawej stronie S )

→ S + 1 + a (zgodnie z zasadą 2 po prawej stronie S )

→ 1 + 1 + a (zgodnie z zasadą 2 po prawej stronie S ),

co można podsumować jako

Zasada nr 1

Zasada nr 1

zasada 3

zasada 2

zasada 2.

Rozróżnienie między wyprowadzeniem skrajnym lewym i prawym jest ważne, ponieważ w większości parserów transformacja wejścia jest definiowana przez podanie fragmentu kodu dla każdej reguły gramatycznej, która jest wykonywana za każdym razem, gdy reguła jest stosowana. Dlatego ważne jest, aby wiedzieć, czy parser określa lewą, czy prawą derywację, ponieważ określa to kolejność wykonywania fragmentów kodu. Zobacz na przykład parsery LL i parsery LR .

Wyprowadzenie również narzuca w pewnym sensie strukturę hierarchiczną na wyprowadzony łańcuch. Na przykład, jeśli ciąg „1 + 1 + a” jest wyprowadzony zgodnie z wyprowadzeniem najbardziej od lewej opisanym powyżej, struktura ciągu będzie następująca:

{{1} _S + {{1} _S + { a } _S } _S } _S

gdzie {...} _S wskazuje podciąg rozpoznawany jako należący do S . Ta hierarchia może być również postrzegana jako drzewo:

To drzewo jest nazywane drzewem analizy lub „drzem składni konkretnej” ciągu, w przeciwieństwie do abstrakcyjnego drzewa składni . W tym przypadku przedstawione skrajnie lewe i prawe wyprowadzenia definiują to samo drzewo analizy; istnieje jednak inna najbardziej prawostronna derywacja tego samego ciągu

S

→ S + S (zgodnie z zasadą 1 po prawej stronie S )

→ S + a (zgodnie z zasadą 3 po prawej stronie S )

→ S + S + a (zgodnie z zasadą 1 po prawej stronie S )

→ S + 1 + a (zgodnie z zasadą 2 po prawej stronie S )

→ 1 + 1 + a (zgodnie z zasadą 2 po prawej stronie S ),

który definiuje ciąg o innej strukturze

{{{1} _S + { a } _S } _S + { a } _S } _S

i inne drzewo analizy:

Zauważ jednak, że oba drzewa parsowania można uzyskać zarówno z lewej, jak i z prawej strony. Na przykład ostatnie drzewo można uzyskać z wyprowadzeniem najbardziej od lewej w następujący sposób:

S

→ S + S (zgodnie z zasadą 1 po lewej stronie S )

→ S + S + S (zgodnie z zasadą 1 po lewej stronie S )

→ 1 + S + S (zgodnie z zasadą 2 po lewej stronie S )

→ 1 + 1 + S (zgodnie z zasadą 2 po lewej stronie S )

→ 1 + 1 + a (zgodnie z zasadą 3 po lewej stronie S ),

Jeśli ciąg w języku gramatyki ma więcej niż jedno drzewo analizowania, mówi się, że gramatyka jest gramatyka niejednoznaczna . Takie gramatyki są zwykle trudne do przeanalizowania, ponieważ parser nie zawsze może zdecydować, którą regułę gramatyczną ma zastosować. Zwykle niejednoznaczność jest cechą gramatyki, a nie języka, i można znaleźć jednoznaczną gramatykę, która generuje ten sam język bezkontekstowy. Istnieją jednak pewne języki, które mogą być generowane tylko przez niejednoznaczne gramatyki; takie języki nazywane są językami z natury niejednoznacznymi .

Przykład: wyrażenia algebraiczne

Oto gramatyka bezkontekstowa dla poprawnych składniowo wyrażeń algebraicznych wrostkowych w zmiennych x, y i z:

1. S → x
2. S → y
3. S → z
4. S → S + S
5. S → S – S
6. S → S * S
7. S → S / S
8. S → ( S )

Ta gramatyka może na przykład generować ciąg

( x + y ) * x – z * y / ( x + x )

następująco:

S

→ S – S (zgodnie z zasadą 5)

→ S * S – S (zgodnie z zasadą 6, stosuje się do skrajnie lewej S )

→ S * S – S / S (zgodnie z zasadą 7, stosuje się do skrajnego S )

→ ( S ) * S – S / S (zgodnie z zasadą 8, stosuje się do skrajnie lewej S )

→ ( S ) * S – S / ( S ) (zgodnie z zasadą 8, stosuje się do skrajnej prawej S )

→ ( S + S ) * S – S / ( S ) (zgodnie z zasadą 4, stosuje się do skrajnie lewej S )

→ ( S + S ) * S – S * S / ( S ) (zgodnie z zasadą 6, stosuje się do czwartego S )

→ ( S + S ) * S – S * S / ( S + S ) (zgodnie z zasadą 4, stosuje się do skrajnie prawej S )

→ ( x + S ) * S – S * S / ( S + S ) (itd.)

→ ( x + y ) * S – S * S / ( S + S )

→ ( x + y ) * x – S * S / ( S + S )

→ ( x + y ) * x – z * S / ( S + S )

→ ( x + y ) * x – z * y / ( S + S )

→ ( x + y ) * x – z * y / ( x + S )

→ ( x + y ) * x – z * y / ( x + x )

Zwróć uwagę, że dokonano wielu wyborów dotyczących tego, które przepisanie zostanie wykonane w następnej kolejności. Te wybory wyglądają dość arbitralnie. W rzeczywistości są, w tym sensie, że ostatecznie wygenerowany ciąg jest zawsze taki sam. Na przykład drugi i trzeci przepis przepisuje

→ S * S – S (zgodnie z zasadą 6, stosuje się do skrajnie lewej S )

→ S * S – S / S (zgodnie z zasadą 7, stosuje się do skrajnego S )

można to zrobić w odwrotnej kolejności:

→ S – S / S (zgodnie z zasadą 7, stosuje się do skrajnej prawej S )

→ S * S – S / S (zgodnie z zasadą 6, stosuje się do skrajnie lewej S )

Dokonano również wielu wyborów, według której reguła ma być stosowana do każdego wybranego S . Zmiana dokonanych wyborów, a nie tylko kolejności, w jakiej zostały wykonane, zwykle wpływa na to, który ciąg terminala pojawia się na końcu.

Przyjrzyjmy się temu bardziej szczegółowo. Rozważ drzewo analizy tego wyprowadzenia:

Zaczynając od góry, krok po kroku, S w drzewie jest rozszerzane, aż nie pozostanie już nierozwinięty S es (nieterminale). Wybranie innej kolejności rozwinięcia da inną derywację, ale to samo drzewo analizy. Drzewo analizy zmieni się tylko wtedy, gdy wybierzemy inną regułę do zastosowania w jakiejś pozycji w drzewie.

Ale czy inne drzewo analizy może nadal generować ten sam ciąg końcowy, który w tym przypadku jest ( x + y ) * x – z * y / ( x + x ) ? Tak, dla tej konkretnej gramatyki jest to możliwe. Gramatyki z tą właściwością nazywane są niejednoznacznymi .

Na przykład x + y * z można utworzyć za pomocą tych dwóch różnych drzew analizy:

Jednak język opisany przez tę gramatykę nie jest z natury niejednoznaczny: dla języka można podać alternatywną, jednoznaczną gramatykę, na przykład:

T → x

T → y

T → z

S → S + T

S → S – T

S → S * T

S → S / T

T → ( S )

S → T ,

ponownie wybierając S jako symbol startu. Ta alternatywna gramatyka wygeneruje x + y * z z drzewem parsowania podobnym do lewego powyżej , tj. niejawnie zakładając skojarzenie ( x + y ) * z , które nie jest zgodne ze standardową kolejnością operacji . Można skonstruować bardziej rozbudowane, jednoznaczne i bezkontekstowe gramatyki, które tworzą drzewa analizowania, które przestrzegają wszystkich pożądanych reguł pierwszeństwa operatorów i asocjatywności.

Normalne formy

Każda gramatyka bezkontekstowa bez tworzenia ε ma równoważną gramatykę w postaci normalnej Chomsky'ego i gramatykę w postaci normalnej Greibacha . „Ekwiwalent” oznacza tutaj, że obie gramatyki generują ten sam język.

Szczególnie prosta forma reguł produkcji w gramatykach postaci normalnej Chomsky'ego ma implikacje zarówno teoretyczne, jak i praktyczne. Na przykład, mając gramatykę bezkontekstową, można użyć postaci normalnej Chomsky'ego do skonstruowania algorytmu wielomianowego , który decyduje, czy dany ciąg jest w języku reprezentowanym przez tę gramatykę, czy nie ( algorytm CYK ).

Właściwości zamknięcia

Języki bezkontekstowe są zamykane pod różnymi operacjami, to znaczy, jeśli języki K i L są bezkontekstowe, to jest to wynik następujących operacji:

• związek K ∪ L ; konkatenacja K ∘ L ; Gwiazda Kleene L ^*
• substytucja (w szczególności homomorfizm )
• odwrotny homomorfizm
• przecięcie ze zwykłym językiem

Nie są one zamknięte pod ogólnym przecięciem (a więc ani pod dopełnieniem ) i ustawić różnicę.

Rozstrzygalne problemy

Poniżej przedstawiono kilka rozstrzygających problemów dotyczących gramatyk bezkontekstowych.

Rozbiór gramatyczny zdania

Problem parsowania, sprawdzania, czy dane słowo należy do języka podanego przez gramatykę bezkontekstową, jest rozstrzygalny przy użyciu jednego z algorytmów parsowania ogólnego przeznaczenia:

• Algorytm CYK (dla gramatyk w postaci normalnej Chomsky'ego )
• Parser Earleya
• Parser GLR
• Parser LL (tylko dla właściwej podklasy gramatyk dla LL( k ))

Leslie G. Valiant wykazał, że parsowanie bezkontekstowe dla gramatyk postaci normalnej Chomsky'ego można zredukować do mnożenia macierzy logicznej , dziedzicząc w ten sposób górną granicę złożoności O ( n ^2.3728639 ). Odwrotnie, Lillian Lee pokazała, że mnożenie macierzy logicznej O ( n ^3−ε ) jest redukowalne do parsowania O ( n ^3−3ε ) CFG, ustanawiając w ten sposób pewnego rodzaju dolne ograniczenie dla tego ostatniego.

Osiągalność, produktywność, nieważność

Przykładowa gramatyka:
S → Bb | DW | Ee
B → Bb | b
C → C
D → Bd | Cd | D
E → Ee

Symbol nieterminalny jest nazywany produktywnym lub generującym , jeśli istnieje wyprowadzenie jakiegoś łańcucha symboli końcowych. jest nazywany osiągalnym, jeśli istnieje wyprowadzenie niektórych łańcuchów symboli nieterminalnych i końcowych z symbolu startowego. nazywana jest bezużyteczną, jeśli jest nieosiągalna lub nieproduktywna. nazywa się nullable , jeśli istnieje wyprowadzenie . Reguła nazywa się ε-produkcją . Wyprowadzenie nazywa się cyklem . ${\ Displaystyle X}$${\ Displaystyle X {\ stos {*} {\ Strzałka w prawo}} w}$${\ Displaystyle w}$${\ Displaystyle X}$${\ Displaystyle S {\ stos {*} {\ Strzałka w prawo}} \ alfa X \ beta}$${\displaystyle \alfa,\beta}$${\ Displaystyle X}$${\ Displaystyle X}$${\ Displaystyle X {\ stos {*} {\ Strzałka w prawo}} \ varepsilon}$${\displaystyle X\rightarrow \varepsilon}$${\ Displaystyle X {\ stos {+} {\ Strzałka w prawo}} X}$

Wiadomo, że algorytmy eliminują z danej gramatyki, nie zmieniając jej wygenerowanego języka,

• nieproduktywne symbole,
• nieosiągalne symbole,
• ε-produkcje, z jednym możliwym wyjątkiem, oraz
• cykle.

W szczególności alternatywę zawierającą bezużyteczny symbol nieterminalowy można usunąć z prawej strony reguły. Takie zasady i alternatywy nazywane są bezużytecznymi .

W przedstawionym przykładzie gramatyki nieterminal D jest nieosiągalny, a E jest nieproduktywne, podczas gdy C → C powoduje cykl. Stąd pominięcie trzech ostatnich reguł nie zmienia języka generowanego przez gramatykę, ani pominięcie alternatyw "| Cc | Ee " z prawej strony reguły dla S .

Mówi się, że gramatyka bezkontekstowa jest właściwa, jeśli nie zawiera bezużytecznych symboli, ani produkcji ε, ani cykli. Łącząc powyższe algorytmy, każdą gramatykę bezkontekstową nie generującą ε można przekształcić w słabo równoważną właściwą.

Kontrola prawidłowości i LL( k )

Rozstrzyga się, czy dana gramatyka jest gramatykią regularną , a także czy jest to gramatyka LL( k ) dla danego k ≥0. Jeśli k nie jest podane, ten ostatni problem jest nierozstrzygnięty.

Biorąc pod uwagę język bezkontekstowy , nie można rozstrzygnąć, czy jest on regularny, ani czy jest to język LL( k ) dla danego k .

Pustka i skończoność

Istnieją algorytmy decydujące o tym, czy język danego języka bezkontekstowego jest pusty, a także skończony.

Nierozstrzygnięte problemy

Niektóre pytania, które są nierozstrzygnięte dla szerszych klas gramatyk, stają się rozstrzygalne dla gramatyk bezkontekstowych; np. problem pustki (czy gramatyka w ogóle generuje jakieś ciągi końcowe) jest nierozstrzygalny dla gramatyk kontekstowych , ale rozstrzygalny dla gramatyk bezkontekstowych.

Jednak wiele problemów jest nierozstrzygniętych nawet dla gramatyk bezkontekstowych. Przykłady to:

Uniwersalność

Czy dany CFG generuje język wszystkich ciągów znaków w alfabecie symboli terminali użytych w jego regułach?

Zmniejszenie tego problemu można wykazać na podstawie dobrze znanego nierozstrzygalnego problemu określania, czy maszyna Turinga akceptuje określone dane wejściowe ( problem zatrzymania ). Redukcja wykorzystuje koncepcję historii obliczeń , ciągu opisującego całe obliczenie maszyny Turinga . Można skonstruować CFG, który generuje wszystkie ciągi, które nie akceptują historii obliczeń dla określonej maszyny Turinga na określonym wejściu, a zatem zaakceptuje wszystkie ciągi tylko wtedy, gdy maszyna nie zaakceptuje tego wejścia.

Równość językowa

Czy biorąc pod uwagę dwa CFG, generują ten sam język?

Nierozstrzygalność tego problemu jest bezpośrednią konsekwencją poprzedniego: nie można nawet zdecydować, czy CFG jest równoważny z trywialnym CFG definiującym język wszystkich napisów.

Włączenie języka

Biorąc pod uwagę dwa CFG, czy pierwszy może wygenerować wszystkie ciągi, które może wygenerować drugi?

Gdyby ten problem był rozstrzygalny, to równość języków również mogłaby zostać rozstrzygnięta: dwie CFG G1 i G2 generują ten sam język, jeśli L(G1) jest podzbiorem L(G2) i L(G2) jest podzbiorem L(G1).

Będąc na niższym lub wyższym poziomie hierarchii Chomsky'ego

Korzystając z twierdzenia Greibacha można wykazać, że dwa następujące problemy są nierozstrzygalne:

• Czy biorąc pod uwagę gramatykę kontekstową , opisuje ona język bezkontekstowy?
• Czy biorąc pod uwagę gramatykę bezkontekstową, opisuje ona język regularny ?

Niejednoznaczność gramatyczna

Czy dane CFG są niejednoznaczne ?

Nierozstrzygalność tego problemu wynika z faktu, że gdyby istniał algorytm określania niejednoznaczności, to można by rozstrzygnąć problem korespondencji pocztowej , o którym wiadomo, że jest nierozstrzygalny.

Rozłączność językowa

Biorąc pod uwagę dwa CFG, czy istnieje jakiś ciąg, który można wyprowadzić z obu gramatyk?

Gdyby ten problem był rozstrzygalny, można by też rozstrzygnąć nierozstrzygalny problem z korespondencją pocztową : dane ciągi nad jakimś alfabetem , niech gramatyka składa się z reguły ${\ Displaystyle \ alfa _ {1} \ ldots \ alfa _ {N} \ beta _ {1} \ ldots \ beta _ {N}}$${\displaystyle \{a_{1},\ldots,a_{k}\}}$${\displaystyle G_{1}}$

${\ Displaystyle S \ do \ alfa _ {1} S \ beta _ {1} ^ {rev} | \ cdots | \ alfa _ {N} S \ beta _ {N} ^ {rev} | B}$;

gdzie oznacza odwrócony ciąg i nie występuje wśród ; i niech gramatyka składa się z reguły ${\ Displaystyle \ beta _ {i} ^ {rev}}$${\ Displaystyle \ beta _ {i}}$${\displaystyle b}$${\displaystyle a_{i}}$${\displaystyle G_{2}}$

${\ Displaystyle T \ do a_ {1}Ta_ {1} | \ cdots | a_ {k} Ta_ {k} | b}$;

Wtedy problem Post podany przez ma rozwiązanie wtedy i tylko wtedy, gdy i udostępnia ciąg, który można wyprowadzić. ${\ Displaystyle \ alfa _ {1} \ ldots \ alfa _ {N} \ beta _ {1} \ ldots \ beta _ {N}}$${\ Displaystyle L (G_ {1})}$${\displaystyle L(G_{2})}$

Rozszerzenia

Oczywistym sposobem rozszerzenia bezkontekstowego formalizmu gramatycznego jest umożliwienie nieterminalom posiadania argumentów, których wartości są przekazywane w ramach reguł. Dzięki temu funkcje języka naturalnego, takie jak zgodność i odniesienie , oraz analogi języka programowania, takie jak prawidłowe użycie i definicja identyfikatorów, mogą być wyrażane w naturalny sposób. Np. możemy teraz łatwo wyrazić, że w zdaniach angielskich podmiot i czasownik muszą się zgadzać w liczbie. W informatyce Przykłady takiego podejścia obejmują umieszczają gramatyk , gramatyk atrybutów , indeksowane gramatyki i Van Wijngaarden dwupoziomowe gramatyk . Podobne rozszerzenia istnieją w językoznawstwie.

Szerszym kontekście wolne gramatyki (lub stałym elementem gramatyki prawo ) jest taka, w której po prawej stronie od zasad produkcji może być wyrażenie regularne nad terminalami i nieterminali gramatyki za. Rozszerzone gramatyki bezkontekstowe opisują dokładnie języki bezkontekstowe.

Innym rozszerzeniem jest umożliwienie pojawiania się dodatkowych symboli terminala po lewej stronie reguł, ograniczając ich zastosowanie. Daje to formalizm gramatyk kontekstowych .

Podklasy

Istnieje kilka ważnych podklas gramatyk bezkontekstowych:

• Gramatyki LR( k ) (znane również jako deterministyczne gramatyki bezkontekstowe ) umożliwiają parsowanie (rozpoznawanie ciągów znaków) za pomocą deterministycznych automatów pushdown (PDA), ale mogą opisywać tylko deterministyczne języki bezkontekstowe .
• Proste gramatyki LR , Look-Ahead LR to podklasy, które pozwalają na dalsze uproszczenie parsowania. SLR i LALR są rozpoznawane przy użyciu tego samego PDA co LR, ale w większości przypadków z prostszymi tabelami.
• Gramatyki LL( k ) i LL( * ) umożliwiają parsowanie przez bezpośrednią konstrukcję pochodnej skrajnej lewej strony, jak opisano powyżej, i opisują jeszcze mniej języków.
• Proste gramatyki są podklasą gramatyk LL(1), interesującą głównie ze względu na swoją teoretyczną właściwość, że równość językowa prostych gramatyk jest rozstrzygalna, podczas gdy włączenie języka nie jest.
• Gramatyki w nawiasach mają tę właściwość, że symbole terminali są podzielone na pary lewego i prawego nawiasu, które zawsze pasują do siebie w regułach.
• Gramatyki liniowe nie mają reguł z więcej niż jednym nieterminalem po prawej stronie.
• Gramatyki regularne są podklasą gramatyk liniowych i opisują języki regularne , tzn. odpowiadają automatom skończonym i wyrażeniom regularnym .

Parsowanie LR rozszerza parsowanie LL w celu obsługi większego zakresu gramatyk; z kolei uogólnione parsowanie LR rozszerza parsowanie LR o obsługę dowolnych gramatyk bezkontekstowych. W gramatykach LL i gramatykach LR zasadniczo wykonuje odpowiednio parsowanie LL i parsowanie LR, podczas gdy w gramatykach niedeterministycznych jest tak wydajny, jak można się spodziewać. Chociaż parsowanie GLR zostało opracowane w latach 80-tych, wiele nowych definicji języka i generatorów parserów nadal opiera się na parsowaniu LL, LALR lub LR do dnia dzisiejszego.

Aplikacje językowe

Chomsky początkowo miał nadzieję na pokonanie ograniczeń gramatyk bezkontekstowych poprzez dodanie reguł transformacji .

Takie reguły są kolejnym standardowym narzędziem w językoznawstwie tradycyjnym; np. pasywacja w języku angielskim. Wiele gramatyki generatywnej poświęcono znalezieniu sposobów udoskonalenia opisowych mechanizmów gramatyki struktury fraz i reguł transformacji, tak aby można było wyrazić dokładnie takie rodzaje rzeczy, na jakie pozwala język naturalny. Zezwalanie na dowolne przekształcenia nie spełnia tego celu: są one zbyt potężne, ponieważ są kompletne pod względem Turinga, chyba że zostaną dodane znaczące ograniczenia (np. żadne przekształcenia, które wprowadzają, a następnie przepisują symbole w sposób bezkontekstowy).

Ogólne stanowisko Chomsky'ego dotyczące braku kontekstu bezkontekstowego języka naturalnego utrzymało się od tego czasu, chociaż jego konkretne przykłady dotyczące nieadekwatności gramatyk bezkontekstowych ze względu na ich słabą zdolność generatywną zostały później obalone. Gerald Gazdar i Geoffrey Pullum twierdzili, że pomimo kilku konstrukcji niebezkontekstowych w języku naturalnym (takich jak zależności między szeregami w szwajcarskim niemieckim i reduplikacja w Bambara ), zdecydowana większość form w języku naturalnym jest rzeczywiście bezkontekstowa.

Zobacz też

• Gramatyka wyrażeń parsowania
• Stochastyczna gramatyka bezkontekstowa
• Algorytmy do bezkontekstowego generowania gramatyki
• Lemat o pompowaniu dla języków bezkontekstowych

Bibliografia

Uwagi

Dalsza lektura

• Hopcroft, John E .; Ullman, Jeffrey D. (1979), Wprowadzenie do teorii automatów, języków i obliczeń , Addison-Wesley. Rozdział 4: Gramatyki bezkontekstowe, s. 77-106; Rozdział 6: Właściwości języków bezkontekstowych, s. 125–137.
• Sipser, Michael (1997), Wprowadzenie do teorii obliczeń , Wydawnictwo PWS, ISBN 978-0-534-94728-6. Rozdział 2: Gramatyki bezkontekstowe, s. 91–122; Sekcja 4.1.2: Rozstrzygalne problemy dotyczące języków bezkontekstowych, s. 156-159; Sekcja 5.1.1: Redukcje poprzez historie obliczeń: s. 176–183.
• J. Berstel, L. Boasson (1990). Jan van Leeuwen (red.). Języki bezkontekstowe . Podręcznik informatyki teoretycznej. B . Elsevier. s. 59–102.

Zewnętrzne linki

• Programiści komputerowi mogą uznać rozwiązanie wymiany stosu za przydatne.
• CFG Developer stworzony przez Christophera Wonga na Uniwersytecie Stanforda w 2014 roku; zmodyfikowany przez Kevina Gibbonsa w 2015 roku.