Dlaczego dwuznaczne gramatyki są złe?

Rozumiem, że jeśli istnieją 2 lub więcej drzew lewej lub prawej pochodnej, gramatyka jest niejednoznaczna, ale nie jestem w stanie zrozumieć, dlaczego jest tak źle, że wszyscy chcą się go pozbyć.

Rozważ następującą gramatykę dla wyrażeń arytmetycznych: Rozważ następujące wyrażenie: Jaka jest jego wartość? Oto dwa możliwe drzewa analizy:

Zgodnie z tym po lewej, powinniśmy interpretować jako , co jest zwykłą interpretacją. Zgodnie z tym po prawej, powinniśmy interpretować to jako , co prawdopodobnie nie jest zamierzone.$a-b-c$$(a-b)-c$$a-(b-c) = a-b+c$

Podczas kompilacji programu chcemy, aby interpretacja składni była jednoznaczna. Najłatwiejszym sposobem na egzekwowanie tego jest użycie jednoznacznej gramatyki. Jeśli gramatyka jest niejednoznaczna, możemy zapewnić reguły rozstrzygające, takie jak pierwszeństwo operatora i asocjatywność. Reguły te można równoważnie wyrazić, czyniąc gramatykę jednoznaczną w określony sposób.

Analizuj drzewa generowane przy użyciu generatora drzewa składniowego .

W przeciwieństwie do innych istniejących odpowiedzi [ 1 , 2 ] istnieje rzeczywiście obszar zastosowania, w którym przydatne są niejednoznaczne gramatyki . W dziedzinie przetwarzania języka naturalnego (NLP), gdy chcesz parsować język naturalny (NL) za pomocą gramatyki formalnej, masz problem, że NL jest z natury niejednoznaczny na różnych poziomach [zaadaptowane z Koh18, rozdz. 6.4]:

• Ambuigity składniowe:

  Peter gonił mężczyznę w czerwonym samochodzie sportowym

  Czy Peter czy mężczyzna w czerwonym samochodzie sportowym?

• Ambitość semantyczna:

  Peter poszedł do banku

  Bank, w którym można usiąść, czy bank, z którego można wypłacać pieniądze?

• Pragmatyczna bogactwo:

  Dwóch mężczyzn niosło dwie torby

  Czy nosili razem torby, czy też każdy z nich miał dwie torby?

Różne podejścia do NLP w różny sposób dotyczą przetwarzania ogólnie, w szczególności tych cech. Na przykład Twój potok może wyglądać następująco:

1. Analizuj NL z niejednoznaczną gramatyką
2. Dla każdego wynikowego AST: uruchom generowanie modelu, aby wygenerować niejednoznaczne znaczenia semantyczne i wykluczyć niemożliwe dwuznaczności składniowe od kroku 1
3. Dla każdego wynikowego modelu: zapisz go w pamięci podręcznej.

Robisz ten potok dla każdego zdania. Im więcej tekstu, powiedzmy, z tej samej książki, którą przetwarzasz, tym bardziej możesz wykluczyć niemożliwe zbędne modele, które przetrwały do ​​kroku 3, z poprzednich zdań.

W przeciwieństwie do języka programowania, możemy zrezygnować z wymogu, aby każde zdanie NL miało precyzyjną semantykę. Zamiast tego możemy po prostu księgować wiele możliwych modeli semantycznych podczas parsowania większych tekstów. Od czasu do czasu późniejsze spostrzeżenia pomagają nam wykluczyć wcześniejsze niejasności.

Jeśli chcesz ubrudzić sobie ręce parserami, które są w stanie wyprowadzać wiele pochodnych dla niejednoznacznej gramatyki, zapoznaj się z ramami gramatycznymi . Również [Koh18, rozdz. 5] zawiera wprowadzenie, które pokazuje coś podobnego do mojego potoku powyżej. Zauważ jednak, że skoro [Koh18] są notatkami z wykładów, notatki mogą nie być tak łatwe do zrozumienia bez wykładów.

Referencje

[Koh18]: Michael Kohlhase. „Przetwarzanie języka naturalnego na podstawie logiki. Semestr zimowy 2018/19. Notatki z wykładu”. URL: https://kwarc.info/teaching/LBS/notes.pdf . Adres URL opisu kursu: https://kwarc.info/courses/lbs/ (w języku niemieckim)

[Koh18, rozdz. 5]: Patrz rozdział 5, „Implementowanie fragmentów: ramy gramatyczne i logiczne”, w [Koh18]

[Koh18, rozdz. 6.4] Patrz rozdział 6.4, „Rola obliczeń niejednoznaczności”, w [Koh18]

Nawet jeśli istnieje dobrze zdefiniowany sposób radzenia sobie z dwuznacznością (niejednoznaczne wyrażenia to na przykład błędy składniowe), gramatyki te nadal powodują problemy. Gdy tylko wprowadzisz dwuznaczność do gramatyki, analizator składni nie może już być pewien, że pierwsze dopasowanie, które uzyska, jest ostateczne. Musi próbować wszystkich innych sposobów parsowania instrukcji, aby wykluczyć wszelkie dwuznaczności. Nie masz również do czynienia z czymś prostym, takim jak język LL (1), więc nie możesz użyć prostego, małego, szybkiego parsera. Twoja gramatyka ma symbole, które można odczytać na wiele sposobów, więc musisz być przygotowany na dużo wstecznego.

W niektórych ograniczonych domenach możesz nie być w stanie udowodnić, że wszystkie możliwe sposoby analizy wyrażenia są równoważne (na przykład, ponieważ reprezentują one operację asocjacyjną). (a + b) + c = a + (b + c).

To IF a THEN IF b THEN x ELSE yznaczy

IF a THEN
    IF b THEN
        x
    ELSE
        y

lub

IF a THEN
    IF b THEN x
ELSE
    y

? Na przykład zwisający problem .

Weź najbardziej irytującą analizę w C ++, na przykład:

bar foo(foobar());

Czy jest to deklaracja footypu funkcji bar(foobar())(parametr zwraca wskaźnik funkcji a foobar), czy deklaracja zmiennej footypu inti inicjalizowana domyślnie foobar?

Różni się to w kompilatorach, przyjmując pierwszy, chyba że wyrażenie na liście parametrów nie może być interpretowane jako typ.

gdy pojawi się tak niejednoznaczne wyrażenie, kompilator ma 2 opcje

1. Załóżmy, że wyrażenie jest konkretną pochodną i dodaj do gramatyki jakiś ujednoznacznik, aby umożliwić wyrażenie drugiej pochodnej.

2. popełniają błąd i wymagają jednoznaczności w obu przypadkach

Pierwszy może wypaść naturalnie, drugi wymaga od programisty kompilatora znajomości niejednoznaczności.

Jeśli ta dwuznaczność pozostanie niewykryta, możliwe jest, że 2 różne kompilatory domyślnie używają różnych pochodnych dla tego dwuznacznego wyrażenia. Prowadzi do tego, że kod jest nieprzenośny z nieoczywistych powodów. Co powoduje, że ludzie zakładają, że jest to błąd w jednym z kompilatorów, podczas gdy w rzeczywistości jest to błąd w specyfikacji języka.

Myślę, że pytanie zawiera założenie, które w najlepszym razie jest tylko poprawne na granicy.

W prawdziwym życiu dość powszechne jest po prostu życie z dwuznacznymi gramatykami, o ile nie są one (że tak powiem) zbyt dwuznaczne.

Na przykład, jeśli spojrzysz na gramatyki skompilowane za pomocą yacc (lub podobnych, takich jak bizon lub byacc), zauważysz, że sporo z nich generuje ostrzeżenia o „konfliktach przesunięcia / redukcji N” podczas ich kompilacji. Kiedy yacc napotyka konflikt przesunięcia / zmniejszenia, oznacza to dwuznaczność w gramatyce.

Konflikt przesunięcia / ograniczenia jest jednak zwykle dość niewielkim problemem. Generator analizatora składni rozwiąże konflikt na korzyść „zmiany” zamiast redukcji. Gramatyka jest w porządku, jeśli tego właśnie chcesz (i wydaje się, że sprawdza się doskonale w praktyce).

Konflikt przesunięcia / zmniejszenia zwykle pojawia się w przypadku na tej ogólnej kolejności (użycie limitów dla terminali innych niż terminale i małych liter dla terminali):

A -> B | c
B -> a | c

Kiedy napotykamy a c, pojawia się dwuznaczność: czy powinniśmy parsować cbezpośrednio jako A, czy też powinniśmy parsować jako jako B, co z kolei jest A? W takim przypadku yacc i takie wybiorą prostszą / krótszą trasę i parsują cbezpośrednio jako A, zamiast iść trasą c-> B-> A. Może to być złe, ale jeśli tak, to prawdopodobnie oznacza to, że masz naprawdę prosty błąd w gramatyce i nie powinieneś w ogóle dopuszczać tej copcji A.

Teraz natomiast możemy mieć coś takiego:

A -> B | C
B -> a | c
C -> b | c

Teraz, gdy napotykamy jakiś ckonflikt między tym, czy traktować go cjako Ba C. Istnieje znacznie mniejsze prawdopodobieństwo, że strategia automatycznego rozwiązywania konfliktów wybierze to, czego naprawdę chcemy. Żadna z nich nie jest „zmianą” - obie są „redukcjami”, więc jest to „redukcja / redukcja konfliktu” (co osoby przyzwyczajone do yacc i takie na ogół uznają za znacznie większy problem niż konflikt zmiany / redukcji).

Tak więc, chociaż nie jestem pewien, czy posunę się tak daleko, aby powiedzieć, że ktoś naprawdę przyjmuje dwuznaczność w swojej gramatyce, przynajmniej w niektórych przypadkach jest na tyle niewielki, że tak naprawdę nikogo to nie obchodzi. W skrócie mogą spodobać im się pomysł usunięcia wszelkiej dwuznaczności - ale nie na tyle, by zawsze to robić. Na przykład, mała, prosta gramatyka, która zawiera niewielką dwuznaczność, może być lepsza niż większa, bardziej złożona gramatyka, która eliminuje niejasności (szczególnie gdy wchodzisz do praktycznej dziedziny faktycznego generowania parsera z gramatyki i stwierdzenia, że ​​jest to jednoznaczne gramatyka tworzy parser, który nie będzie działał na twoim komputerze docelowym).