Czy jest to niejednoznaczna gramatyka? Jak mam to rozwiązać?

Question

Aby tego dokonać, moja wiedza na temat tego rodzaju rzeczy jest słaba.

W każdym razie opracowałem gramatykę bezkontekstową, aby opisać strukturę wyrażeń alegarycznych, dzięki czemu mogę nauczyć się, jak działa algorytm parsowania CYK. Rozumiem, jak taka struktura może działać tylko z algebraicznymi wyrażeniami typu infix, ale nie mogę zrozumieć, jak opracować gramatykę, która może obsłużyć zarówno jednoargumentowe, jak i binarne definicje operatora "-".

Dla porównania, tutaj jest gramatyka pisałem (gdzie S jest symbolem start) w CNF:

S -> x
A -> OS
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O ->/
O ->^
K -> -
L -> (
R ->)

Problemem jest to, że jak może cyk analizowania algorytm wiedzieć z wyprzedzeniem, czy zdecydować między S -> KS i A -> OS kiedy napotka operator "-"? Czy gramatyka taka jest już wolna od kontekstu? A co najważniejsze, skoro języki programowania mogą obsługiwać języki z podwójnym i jednoznacznym znakiem minus, jak mam to właściwie przeanalizować?

Answer 1

To wydaje się problemu związanego z automatów skończonych państwa i nie pamiętam wszystko z moim zajęć, ale napisałem parser cyk w SML , więc pójdę do przodu i zrobić zdjęcie :)

Jeśli starasz się analizować wyrażenia jak 3- -4 na przykład, że masz regułę S -> K S zużywają -4 a następnie reguła A -> O S by wchłonąć - -4. To ostatecznie będzie działało zgodnie z najwyższą regułą produkcji S. Powinieneś uważać na gramatykę, której używasz, ponieważ wymieniona reguła produkcyjna A jest niedostępna od S i prawdopodobnie powinieneś mieć jakąś regułę S -> S O S.

Sposób, w jaki algorytmy parsowania CYK działają poprzez cofanie, a nie przez "wiedzenie z wyprzedzeniem", o którym wspomniałeś w swoim pytaniu. To, co powinien zrobić algorytm CYK, to przeanalizowanie reguły -4 jako reguły S -> K S, a następnie spróbuje ponownie zaabsorbować drugą - regułę S -> K S, ponieważ ta reguła produkcji dopuszcza arbitralnie długi łańcuch unarnego -. Ale gdy twój algorytm zorientuje się, że utknął w czasie z parserem pośrednim 3 S, zdaje sobie sprawę, że nie ma symboli produkcyjnych, których mógłby użyć do przeanalizowania tego. Kiedy zda sobie sprawę, że nie można tego dalej parsować, wróci i zamiast tego spróbuje przeanalizować - jako regułę S -> O S i kontynuować swoją wesołą drogę.

Oznacza to, że gramatyka pozostaje bezkontekstowa, ponieważ gramatyka kontekstowa oznacza, że ​​masz terminale po lewej stronie zasad produkcji, więc jesteś dobry pod tym względem. HTH!

Answer 2

Gramatyka jest niejednoznaczna, a analizator składni nie może zdecydować, który przypadek należy zastosować.

Należy prawdopodobnie używać gramatyki jak następuje:

S -> EXPR 
EXPR -> (EXPR) 
EXPR -> - EXPR 
EXPR -> EXPR + EXPR 
EXPR -> EXPR - EXPR 
// etc... 

Answer 3

Gramary oparte na wyrażeniach algebraicznych są raczej trudne do ujednoznacznienia. Oto kilka przykładów problemów, które należy rozwiązać:

a + b + c naturalnie tworzy dwa drzewa parsowane. Aby rozwiązać ten problem, musisz rozwiązać problem niejednoznaczności powiązania z +. Możesz zająć się tą strategią od lewej do prawej, ale ostrożnie: potęgowanie powinno prawdopodobnie kojarzyć od prawej do lewej.

a + b * c w naturalny sposób tworzy dwa drzewa parsowane. Aby rozwiązać ten problem, musisz uporać się z priorytetem operatora.

Niejawne mnożenie (a + bc), jeśli jest dozwolone, powoduje różnego rodzaju koszmary senne, głównie w tokenizacji.

Jednoargumentowe odejmowanie jest problematyczne, jak wspomniałeś.

Jeśli chcemy rozwiązać te problemy, ale nadal mamy szybką analizę gramatyczną specjalizującą się w algebrze, jednym z nich jest posiadanie różnych "poziomów" WYRAZU, po jednym dla każdego poziomu powiązania wymaganego przez poziomy pierwszeństwa. Na przykład,

TERM -> (S) 
EXPO -> TERM^EXPO 
PROD -> PROD * EXPO 
PROD -> PROD/EXPO 
PROD -> -PROD 
SUM -> SUM + PROD 
SUM -> SUM - PROD 
S -> SUM 

Wymaga to pozwalają także "promocja" typów: suma -> PROD, PROD -> EXP EXP -> Term, etc, tak, że wszystko można rozwiązać.

Mam nadzieję, że to pomoże!