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ć.
Rzeczywiście, jednoznaczna forma jest lepsza do praktycznych zastosowań, jednoznaczna forma używa mniejszej liczby reguł produkcji, buduje mniejsze drzewo wysoko (stąd efektywny kompilator - zajmuje mniej czasu na analizę). Większość narzędzi zapewnia zdolność do rozwiązywania niejasności w gramatyce pobocznej.
Grijesh Chauhan
3
„każdy chce się go pozbyć”. Cóż, to po prostu nieprawda. W językach istotnych z handlowego punktu widzenia często pojawiają się dwuznaczności w miarę ewolucji języków. Np. C ++ celowo dodawał niejednoznaczność std::vector<std::vector<int>>w 2011 r., Która wcześniej wymagała spacji między nimi >>. Kluczową sprawą jest to, że języki te mają znacznie więcej użytkowników niż dostawców, więc usunięcie drobnych uciążliwości dla użytkowników usprawiedliwia wiele pracy wykonawców.
MSalters
Odpowiedzi:
52
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:
X→ X+ X∣ X- X∣ X∗ X∣ X/ X∣var∣const
a−b−c
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)−ca−(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.
@HIRAKMONDAL Fakt, że składnia jest niejednoznaczna, nie jest prawdziwym problemem. Problem polega na tym, że dwa różne drzewa analizy mają różne zachowanie. Jeśli twój język ma niejednoznaczną gramatykę, ale wszystkie drzewa parsowania dla wyrażenia są semantycznie równoważne, nie stanowi to problemu (np. Weź przykład Yuval i rozważ przypadek, w którym twój jedyny operator +).
Bakuriu
14
@ Bakuriu To, co powiedziałeś, jest prawdą, ale „semantycznie równoważny” to duże zamówienie. Na przykład arytmetyka zmiennoprzecinkowa w rzeczywistości nie jest asocjacyjna (więc dwa drzewa „+” nie byłyby równoważne). Dodatkowo, nawet jeśli odpowiedź wyszła w ten sam sposób, niezdefiniowany porządek oceny ma duże znaczenie w językach, w których wyrażenia mogą mieć skutki uboczne. To, co powiedziałeś, jest technicznie prawdziwe, ale w praktyce byłoby bardzo niezwykłe, aby dwuznaczność gramatyki nie miała wpływu na użycie tej gramatyki.
Richard Rast
Niektóre języki obecnie sprawdzają przepełnienie liczb całkowitych w dodatkach, więc nawet a + b + c dla liczb całkowitych zależy od kolejności oceny.
gnasher729
3
Co gorsza, w niektórych przypadkach gramatyka nie zapewnia żadnego sposobu osiągnięcia alternatywnego znaczenia. Widziałem to w językach zapytań, w których wybór gramatyki zmiany znaczenia (np. Dwukrotność znaku specjalnego w celu zmiany znaczenia) uniemożliwia wyrażenie niektórych zapytań.
Przestań krzywdzić Monikę
12
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:
Analizuj NL z niejednoznaczną gramatyką
Dla każdego wynikowego AST: uruchom generowanie modelu, aby wygenerować niejednoznaczne znaczenia semantyczne i wykluczyć niemożliwe dwuznaczności składniowe od kroku 1
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.
Dzięki tona .. Miałem te same wątpliwości i wyjaśniłeś to .. :)
HIRAK MONDAL
1
Nie wspominając o problemach z Buffalo Buffalo Buffalo Buffalo Buffalo Buffalo ... dla odpowiedniej liczby bawołów
Hagen von Eitzen
Piszesz „przeciwnie”, ale nazwałbym to drugą stroną medalu z tego, co odpowiedziałem. Przetwarzanie języków naturalnych z ich dwuznacznymi gramatykami jest tak trudne, że tradycyjne parsery nie mogą tego zrobić!
Davislor
1
@ComFreek Powinienem tu być bardziej precyzyjny. Krótkie spojrzenie na GF (dzięki za link!) Pokazuje, że czyta gramatyki bezkontekstowe z trzema rozszerzeniami (np. Zezwalając na reduplikację) i zwraca listę wszystkich możliwych pochodnych. Algorytmy pozwalające to zrobić istnieją od lat 50-tych. Jednak możliwość obsługi w pełni ogólnych CFG oznacza, że Twój najgorszy czas działania ulega awarii, a w praktyce, nawet gdy używasz ogólnego parsera, takiego jak GLL, inżynierowie oprogramowania próbują użyć podzbioru CFG, takich jak gramatyki LL, które mogą być analizowane bardziej wydajnie.
Davislor
1
@ComFreek Więc nie jest tak, że komputery nie radzą sobie z CFG (chociaż języki naturalne nie są tak naprawdę kontekstowe, a faktycznie przydatne tłumaczenie maszynowe wykorzystuje zupełnie inne techniki). Chodzi o to, że jeśli wymagasz od parsera obsługi niejednoznaczności, wyklucza to pewne skróty, które zwiększyłyby jego wydajność.
Davislor
10
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 dobry przykład pokazujący, że nawet niejednoznaczna gramatyka (jak w Javie, C, C ++, ...) pozwala na pozorne (!) Dwuznaczności z ludzkiej perspektywy. Mimo że jesteśmy formalnie i obliczeniowo w porządku, teraz mamy więcej problemów z programowaniem bez UX / błędów.
ComFreek
5
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
Załóżmy, że wyrażenie jest konkretną pochodną i dodaj do gramatyki jakiś ujednoznacznik, aby umożliwić wyrażenie drugiej pochodnej.
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).
std::vector<std::vector<int>>w 2011 r., Która wcześniej wymagała spacji między nimi>>. Kluczową sprawą jest to, że języki te mają znacznie więcej użytkowników niż dostawców, więc usunięcie drobnych uciążliwości dla użytkowników usprawiedliwia wiele pracy wykonawców.Odpowiedzi:
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:X→ X+ X∣ X- X∣ X∗ X∣ X/ X∣var∣const a−b−c
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 .
źródło
+).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]:
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:
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]
źródło
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).
źródło
To
IF a THEN IF b THEN x ELSE yznaczylub
? Na przykład zwisający problem .
źródło
Weź najbardziej irytującą analizę w C ++, na przykład:
Czy jest to deklaracja
footypu funkcjibar(foobar())(parametr zwraca wskaźnik funkcji afoobar), czy deklaracja zmiennejfootypuinti inicjalizowana domyślniefoobar?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
Załóżmy, że wyrażenie jest konkretną pochodną i dodaj do gramatyki jakiś ujednoznacznik, aby umożliwić wyrażenie drugiej pochodnej.
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.
źródło
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):
Kiedy napotykamy a
c, pojawia się dwuznaczność: czy powinniśmy parsowaćcbezpośrednio jakoA, czy też powinniśmy parsować jako jakoB, co z kolei jestA? W takim przypadku yacc i takie wybiorą prostszą / krótszą trasę i parsującbezpośrednio jakoA, 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ć tejcopcjiA.Teraz natomiast możemy mieć coś takiego:
Teraz, gdy napotykamy jakiś
ckonflikt między tym, czy traktować gocjakoBaC. 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).
źródło