Niejednoznaczna gramatyka

W informatyce gramatyka niejednoznaczna jest gramatyką bezkontekstową, dla której istnieje ciąg , który może mieć więcej niż jedno lewe wyprowadzenie lub drzewo analizy . Każdy niepusty język bezkontekstowy dopuszcza niejednoznaczną gramatykę, wprowadzając np. regułę powielania. Język, który dopuszcza tylko niejednoznaczne gramatyki, nazywany jest językiem z natury niejednoznacznym . Deterministyczne gramatyki bezkontekstowe są zawsze jednoznaczne i stanowią ważną podklasę gramatyk jednoznacznych; istnieją jednak niedeterministyczne gramatyki jednoznaczne.

języków programowania komputerowego gramatyka referencyjna jest często niejednoznaczna z powodu problemów, takich jak problem wiszącego else . Jeśli występują, te niejasności są na ogół rozwiązywane przez dodanie reguł pierwszeństwa lub innych kontekstowej , więc ogólna gramatyka fraz jest jednoznaczna. ^{[ Potrzebne źródło ]} Niektóre algorytmy analizujące (takie jak parsery Earley lub GLR ) mogą generować zestawy drzew analizy (lub „lasy analizy”) z łańcuchów, które są składniowo niejednoznaczne .

Przykłady

Trywialny język

Najprostszym przykładem jest następująca niejednoznaczna gramatyka (z symbolem początkowym A) dla trywialnego języka, który składa się tylko z pustego ciągu:

ZA → ZA | ε

…co oznacza, że nieterminal A może być wyprowadzony albo do samego siebie, albo do pustego łańcucha. Tak więc pusty ciąg ma skrajne lewe wyprowadzenia o długości 1, 2, 3, a nawet dowolnej długości, w zależności od tego, ile razy reguła A → A jest używana.

Język ten posiada również jednoznaczną gramatykę, składającą się z jednej reguły produkcji :

A → ε

…co oznacza, że unikalna produkcja może wytworzyć tylko pusty ciąg, który jest unikalnym ciągiem w języku.

W ten sam sposób każdą gramatykę dla niepustego języka można uczynić niejednoznaczną, dodając duplikaty.

Ciąg jednoargumentowy

Język regularny ciągów jednoargumentowych danego znaku, powiedzmy 'a' (wyrażenie regularne a* ), ma jednoznaczną gramatykę:

A → aA | ε

…ale ma też niejednoznaczną gramatykę:

A → aA | Aa | ε

Odpowiadają one utworzeniu prawego drzewa asocjacyjnego (dla gramatyki jednoznacznej) lub umożliwieniu zarówno lewego, jak i prawego skojarzenia. Zostało to omówione poniżej.

Dodawanie i odejmowanie

Gramatyka bezkontekstowa

ZA → ZA + ZA | A-A | A

jest niejednoznaczne, ponieważ istnieją dwa skrajne lewe wyprowadzenia dla łańcucha a + a + a:

A	→ A + A	A	→ A + A
	→ a + A		→ A + A + A (Pierwsze A jest zastępowane przez A + A. Zastąpienie drugiego A dałoby podobne wyprowadzenie)
	→ za + za + za		→ za + za + za
	→ za + za + za		→ za + za + za
	→ za + za + za		→ za + za + za

Jako inny przykład, gramatyka jest niejednoznaczna, ponieważ istnieją dwa drzewa analizy dla łańcucha a + a - a:

Język, który generuje, nie jest jednak z natury niejednoznaczny; poniżej znajduje się niejednoznaczna gramatyka generująca ten sam język:

ZA → ZA + za | A-a | A

Wiszące inaczej

Typowym przykładem niejednoznaczności w językach programowania komputerów jest problem wiszącego else . W wielu językach else w instrukcji If–then(–else) jest opcjonalne, co powoduje, że zagnieżdżone wyrażenia warunkowe mają wiele sposobów rozpoznawania pod względem gramatyki bezkontekstowej.

Konkretnie, w wielu językach można pisać tryby warunkowe w dwóch ważnych formach: if-then i if-then-else - w efekcie czyniąc klauzulę else opcjonalną:

W gramatyce zawierającej reguły

 Instrukcja →  jeśli  Warunek  to  Instrukcja |  if  Warunek  then  Instrukcja  else  Instrukcja | ... Warunek → ...

mogą pojawić się pewne niejednoznaczne struktury fraz. Ekspresja

  jeśli  a  to  jeśli  b  to  s  jeszcze  s2

można przeanalizować jako albo

    jeśli  a  to  zacznij  jeśli  b  to  s  koniec  inaczej  s2

lub jako

   jeśli  a  to  zacznij  jeśli  b  to  s  inaczej  s2  koniec

w zależności od tego, czy else jest powiązane z pierwszym if czy drugim if .

Jest to rozwiązywane na różne sposoby w różnych językach. Czasami gramatyka jest modyfikowana tak, aby była jednoznaczna, na przykład wymagając endif lub czyniąc else obowiązkowym. W innych przypadkach gramatyka pozostaje niejednoznaczna, ale niejednoznaczność rozwiązuje się, czyniąc ogólną gramatykę kontekstową, na przykład przez powiązanie else z najbliższym if . W tym ostatnim przypadku gramatyka jest jednoznaczna, ale gramatyka bezkontekstowa jest niejednoznaczna. ^{[ wymagane wyjaśnienie ]}

Jednoznaczna gramatyka z wieloma pochodnymi

Istnienie wielu pochodnych tego samego ciągu nie wystarczy, aby wskazać, że gramatyka jest niejednoznaczna; tylko wiele skrajnie lewych (lub równoważnie wiele drzew analizy) wskazuje na niejednoznaczność.

Na przykład prosta gramatyka

S → ZA + ZA ZA → 0 | 1

jest jednoznaczną gramatyką dla języka { 0+0, 0+1, 1+0, 1+1 }. Chociaż każda z tych czterech strun ma tylko jedno skrajne lewe wyprowadzenie, ma na przykład dwa różne wyprowadzenia

 S  ⇒  ZA + ZA ⇒ 0 + ZA ⇒ 0 + 0

I

S ⇒ ZA + ZA ⇒ ZA + 0 ⇒ 0 + 0

Tylko poprzednie wyprowadzenie jest najbardziej wysunięte na lewo.

Rozpoznawanie niejednoznacznych gramatyk

Problem decyzyjny , czy dowolna gramatyka jest niejednoznaczna, jest nierozstrzygalny , ponieważ można wykazać, że jest równoważny problemowi korespondencji pocztowej . Przynajmniej istnieją narzędzia implementujące procedurę półdecyzyjną do wykrywania niejednoznaczności gramatyk bezkontekstowych.

O wydajności parsowania gramatyki bezkontekstowej decyduje automat, który ją akceptuje. Deterministyczne gramatyki bezkontekstowe są akceptowane przez deterministyczne automaty przesuwające w dół i mogą być analizowane w czasie liniowym, na przykład przez parser LR . Stanowią ścisły podzbiór gramatyk bezkontekstowych , które są akceptowane przez automaty przesuwające i mogą być analizowane w czasie wielomianowym, na przykład przez algorytm CYK .

Jednoznaczne gramatyki bezkontekstowe mogą być niedeterministyczne. Na przykład język parzystych palindromów na alfabecie 0 i 1 ma jednoznaczną gramatykę bezkontekstową S → 0S0 | 1S1 | ε. Dowolnego ciągu znaków tego języka nie można przeanalizować bez uprzedniego odczytania wszystkich jego symboli, co oznacza, że automat przesuwający w dół musi wypróbować alternatywne przejścia stanów, aby dostosować się do różnych możliwych długości częściowo przeanalizowanego łańcucha.

Niemniej jednak usunięcie niejednoznaczności gramatycznej może skutkować deterministyczną gramatyką bezkontekstową, a tym samym pozwolić na bardziej wydajną analizę składniową. Generatory kompilatorów, takie jak YACC , zawierają funkcje rozwiązywania niektórych rodzajów niejednoznaczności, na przykład za pomocą ograniczeń pierwszeństwa i asocjatywności.

Języki z natury niejednoznaczne

Podczas gdy niektóre języki bezkontekstowe (zestaw ciągów znaków, które mogą być generowane przez gramatykę) mają zarówno gramatykę niejednoznaczną, jak i jednoznaczną, istnieją języki bezkontekstowe, dla których nie może istnieć jednoznaczna gramatyka bezkontekstowa. Takie języki nazywane są z natury niejednoznacznymi .

Nie ma z natury niejednoznacznych języków regularnych.

Istnienie z natury niejednoznacznych języków bezkontekstowych zostało udowodnione za pomocą twierdzenia Parikha w 1961 roku przez Rohita Parikha w raporcie z badań MIT.

Język ${\ Displaystyle \ {x | x = a ^ {n }b^{m}a^{n^{\prime }}b^{m}{\text{ lub }}x=a^{n}b^{m}a^{n}b^{m^ {\prime }},{\text{ gdzie }}n,n',m,m'\geq 1\}}$ jest z natury niejednoznaczne.

Lemat Ogdena może być użyty do udowodnienia, że pewne języki bezkontekstowe, takie jak ${\ Displaystyle \ {a ^ {n} b ^ {m} c ^ {m} | m, n \ geq 1 \} \ kubek \ {a ^ {m} b ^ {m} c ^{n}|m,n\geq 1\}}$ , są z natury niejednoznaczne. Zobacz tę stronę , aby uzyskać dowód.

związek $\ Displaystyle \ {a ^ {n} b ^ {m} c ^ {m} d ^ {n} \ mid n, m> 0 \}}$ z ${\ Displaystyle \ {a ^ {n} b ^ {n} c ^ {m} d ^ {m} \ mid n, m$ jest z natury niejednoznaczne. Ten zestaw jest bezkontekstowy, ponieważ połączenie dwóch języków bezkontekstowych jest zawsze bezkontekstowe. Ale Hopcroft i Ullman (1979) podają dowód, że jakakolwiek gramatyka bezkontekstowa dla tego języka związkowego nie może jednoznacznie analizować łańcuchów postaci za $\ Displaystyle a ^ {n} b ^ { n}c^{n}d^{n},(n>0)}$ .

Więcej przykładów i ogólny przegląd technik dowodzenia nieodłącznej niejednoznaczności języków bezkontekstowych można znaleźć w Bassino i Nicaud (2011).

Zobacz też

Parser GLR , rodzaj parsera dla gramatyk niejednoznacznych i niedeterministycznych
Parser wykresów , inny typ parsera dla gramatyk niejednoznacznych
Niejednoznaczność składniowa

^ Willem JM Levelt (2008). Wprowadzenie do teorii języków formalnych i automatów . Wydawnictwo Johna Benjamina. ISBN 978-90-272-3250-2 .
^ Scott, Elżbieta (1 kwietnia 2008). „Przetwarzanie w stylu SPPF od Earley Recognizer” . Notatki elektroniczne w informatyce teoretycznej . 203 (2): 53–67. doi : 10.1016/j.entcs.2008.03.044 .
Bibliografia _ „ Wydajny algorytm analizowania bez kontekstu rozszerzonego ”. Lingwistyka komputerowa 13.1-2 (1987): 31-46.
Bibliografia _ _ Motwani, Rajeev ; Ullman, Jeffrey (2001). Wprowadzenie do teorii automatów, języków i obliczeń (wyd. 2). Addison-Wesley. Twierdzenie 9.20, s. 405–406. ISBN 0-201-44124-1 .
^ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). „Analiza gramatyk bezkontekstowych za pomocą przyrostowego narzędzia SAT Solver” (PDF) . Materiały z 35. Międzynarodowego Kolokwium Automatów, Języków i Programowania (ICALP'08), Reykjavik, Islandia . Notatki z wykładów z informatyki . Tom. 5126. Springer Verlag. s. 410–422. doi : 10.1007/978-3-540-70583-3_34 . ISBN 978-3-540-70582-6 .
^ Knuth, DE (lipiec 1965). „O tłumaczeniu języków od lewej do prawej” . Informacji i Kontroli . 8 (6): 607–639. doi : 10.1016/S0019-9958(65)90426-2 .
Bibliografia _ _ Motwani, Rajeev ; Ullman, Jeffrey (2001). Wprowadzenie do teorii automatów, języków i obliczeń (wyd. 2). Addison-Wesley. s. 249–253. ISBN 0-201-44124-1 .
^ Książka, R .; Nawet S.; Greibach S.; Ott, G. (luty 1971). „Niejednoznaczność wykresów i wyrażeń” . Transakcje IEEE na komputerach . C-20 (2): 149–153. doi : 10.1109/tc.1971.223204 . ISSN 0018-9340 .
^ „Języki formalne - Czy wyrażenia regularne mogą być jednoznaczne?” . Przepełnienie matematyki . Źródło 2023-02-23 .
^ Parikh, Rohit (styczeń 1961). Urządzenia generujące język . Kwartalny raport z postępów, Research Laboratory of Electronics, MIT.
^ Parikh, Rohit J. (1966-10-01). „O językach bezkontekstowych” . Dziennik ACM . 13 (4): 570–581. doi : 10.1145/321356.321364 . ISSN 0004-5411 . Tutaj: Twierdzenie 3.
^ Ogden, William (wrzesień 1968). „Pomocny wynik do udowodnienia nieodłącznej niejednoznaczności” . Teoria systemów matematycznych . 2 (3): 191–194. doi : 10.1007/bf01694004 . ISSN 0025-5661 .
^ s. 99-103, sekcja 4.7
^ Fredérique Bassino i Cyril Nicaud (16 grudnia 2011). „Philippe Flajolet i analityczna kombinatoryka: nieodłączna niejednoznaczność języków bezkontekstowych” (PDF) . Zarchiwizowane (PDF) od oryginału w dniu 2022-09-25.

Gross, Maurice (wrzesień 1964). „Wrodzona dwuznaczność minimalnych gramatyk liniowych” . Informacji i Kontroli . 7 (3): 366–368. doi : 10.1016/S0019-9958(64)90422-X .
Michael, Harrison (1978). Wprowadzenie do teorii języka formalnego . Addison-Wesley. ISBN 0201029553 .
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Wprowadzenie do teorii automatów, języków i obliczeń (wyd. 1). Addison-Wesley. ISBN 9780201029888 .
Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Wprowadzenie do teorii automatów, języków i obliczeń (wyd. 2). Addisona Wesleya. s. 217 . ISBN 9780201441246 .
Brabrand, Mikołaj; Giegerich, Robert; Møller, Anders (marzec 2010). „Analiza niejednoznaczności gramatyk bezkontekstowych”. Nauka o programowaniu komputerowym . Elsevier. 75 (3): 176–191. CiteSeerX 10.1.1.86.3118 . doi : 10.1016/j.scico.2009.11.002 .

Notatki

Linki zewnętrzne

dk.brics.grammar - analizator niejednoznaczności gramatycznych.
CFGAnalyzer - narzędzie do analizy gramatyk bezkontekstowych pod kątem uniwersalności języka, niejednoznaczności i podobnych właściwości.

[Levelt2008-1] Willem JM Levelt (2008). Wprowadzenie do teorii języków formalnych i automatów . Wydawnictwo Johna Benjamina. ISBN 978-90-272-3250-2 .

[2] Scott, Elżbieta (1 kwietnia 2008). „Przetwarzanie w stylu SPPF od Earley Recognizer” . Notatki elektroniczne w informatyce teoretycznej . 203 (2): 53–67. doi : 10.1016/j.entcs.2008.03.044 .

[3] Bibliografia _ „ Wydajny algorytm analizowania bez kontekstu rozszerzonego ”. Lingwistyka komputerowa 13.1-2 (1987): 31-46.

[5] Bibliografia _ _ Motwani, Rajeev ; Ullman, Jeffrey (2001). Wprowadzenie do teorii automatów, języków i obliczeń (wyd. 2). Addison-Wesley. Twierdzenie 9.20, s. 405–406. ISBN 0-201-44124-1 .

[6] Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). „Analiza gramatyk bezkontekstowych za pomocą przyrostowego narzędzia SAT Solver” (PDF) . Materiały z 35. Międzynarodowego Kolokwium Automatów, Języków i Programowania (ICALP'08), Reykjavik, Islandia . Notatki z wykładów z informatyki . Tom. 5126. Springer Verlag. s. 410–422. doi : 10.1007/978-3-540-70583-3_34 . ISBN 978-3-540-70582-6 .

[7] Knuth, DE (lipiec 1965). „O tłumaczeniu języków od lewej do prawej” . Informacji i Kontroli . 8 (6): 607–639. doi : 10.1016/S0019-9958(65)90426-2 .

[8] Bibliografia _ _ Motwani, Rajeev ; Ullman, Jeffrey (2001). Wprowadzenie do teorii automatów, języków i obliczeń (wyd. 2). Addison-Wesley. s. 249–253. ISBN 0-201-44124-1 .

[9] Książka, R .; Nawet S.; Greibach S.; Ott, G. (luty 1971). „Niejednoznaczność wykresów i wyrażeń” . Transakcje IEEE na komputerach . C-20 (2): 149–153. doi : 10.1109/tc.1971.223204 . ISSN 0018-9340 .

[10] „Języki formalne - Czy wyrażenia regularne mogą być jednoznaczne?” . Przepełnienie matematyki . Źródło 2023-02-23 .

[11] Parikh, Rohit (styczeń 1961). Urządzenia generujące język . Kwartalny raport z postępów, Research Laboratory of Electronics, MIT.

[12] Parikh, Rohit J. (1966-10-01). „O językach bezkontekstowych” . Dziennik ACM . 13 (4): 570–581. doi : 10.1145/321356.321364 . ISSN 0004-5411 . Tutaj: Twierdzenie 3.

[13] Ogden, William (wrzesień 1968). „Pomocny wynik do udowodnienia nieodłącznej niejednoznaczności” . Teoria systemów matematycznych . 2 (3): 191–194. doi : 10.1007/bf01694004 . ISSN 0025-5661 .

[14] s. 99-103, sekcja 4.7

[15] Fredérique Bassino i Cyril Nicaud (16 grudnia 2011). „Philippe Flajolet i analityczna kombinatoryka: nieodłączna niejednoznaczność języków bezkontekstowych” (PDF) . Zarchiwizowane (PDF) od oryginału w dniu 2022-09-25.