AST - Faza druga (sytuacje błędne)

Znalazłem dziś chwilę czasu którą postanowiłem poświęcić na wznowienie budowy mojego pierwszego edytora tekstowego.

Do utworzenia wstępnego szkicu gramatyki posłużyłem się specyfikacją pierwszej wersji języka xpath którą możesz znaleźć tutaj. Jednak gramatyka utworzona w ten sposób nie jest wystarczająca by zastosować ją jako serce edytora tekstowego. Dlaczego? Ponieważ buduje ona poprawne AST tylko dla poprawnego źródła, te jednak w naszym przypadku przez większość czasu zawiera błędy. W trakcie edycji niejednokrotnie następowałaby utrata struktury AST wymaganej do synchronizacji modelu wewnętrznego. Bez modelu natomiast nie bylibyśmy w stanie oznaczyć powstałych błędów, utworzyć listy podpowiedzi etc. Poniżej postaram się zaprezentować opisaną sytuację wraz z przykładową korektą gramatyki.

Do testu posłuży nam proste wyrażenie:

doc("Elementy")//elementA/elementB/elementC



Jak widać drzewo AST jest łatwe do dalszej analizy. Co wydarzy się jednak gdy użytkownik postanowi dodać predykat wybierający instancje 'elementA' spełniające określony warunek? Sprawdźmy jak wygląda sytuacja po dodaniu pierwszego znaku '[' (modyfikacja zaznaczona kolorem).

doc("Elementy")//elementA[/elementB/elementC



Jak widać parser całkowicie się pogubił, całość utrudniła możliwość wystąpienia podwyrażenia absolutnego w ramach predykatu. W wyniku tego w poszukiwaniu nawiasu zamykającego parser zjada nam resztę wyrażenia. W tym momencie zmuszeni bylibyśmy zaznaczyć połowę tekstu jako błędną co nie wyglądałoby zbyt estetycznie nie wspominając o braku podpowiedzi etc. Spróbujmy wybrnąć z tej sytuacji inaczej.

Ponieważ w samej gramatyce nie bardzo jesteśmy w stanie ocenić w jakim miejscu powinien znaleźć się nawias zamykający, zastosujemy mechanizm auto edycji (IAutoEditStrategy) który dołoży go zaraz za wstawianym przez użytkownika nawiasem otwierającym. Podobne działanie można zobaczyć w wielu edytorach w środowisku Eclipse. Poniżej możemy zobaczyć wynikowe wyrażenie wraz z odpowiadającym AST (modyfikacja zaznaczona kolorem).

doc("Elementy")//elementA[]/elementB/elementC



Na drzewie ponownie możemy zobaczyć utracone wcześniej elementy jednak całość jest nadal bezużyteczna. Powodem jest brak obsługi pustych predykatów w naszej gramatyce które nie są poprawnymi elementami wyrażenia. Ponieważ jednocześnie chcemy by nasz parser potrafił sytuację obsłużyć poprawnie oraz oznaczyć miejsce błędu zastosujemy wirtualny token 'ERR_EMPTY_PREDICATE_TOKEN' (modyfikacja zaznaczona kolorem).

predicate
     : '[' expr ']' -> ^(PREDICATE_TOKEN expr)//;
     | '[' ']' -> ^(PREDICATE_TOKEN ERR_EMPTY_PREDICATE_TOKEN);


Poniżej zobaczyć możemy wynikowe drzewo AST:



Jak widać pierwsza sytuacja błędna została opanowana. Pozostało 99 kolejnych którymi będę musiał się zająć gdy znów znajdę czas wolny. Pozdrowienia.

2 komentarze:

Jacek Pospychala pisze...

ha, to jest dobry temat :)
ogólnie zabawa polega na tym, żeby jak najszybciej "zresetować" się w przypadku napotkania złych tokenów. Obrazowo, by dotrzeć np. do najbliższego średnika (w gramatykach jak C/java/pascal) by móc dalej przetwarzać. O ile pamiętam, ANTLR powinien mieć jakeś specjalne tokeny do errorów. Dzięki temu nie musiałbyś zaśmiecać swojej gramatyki i obsługa błędów byłaby rozwiązana na wyższym poziomie (przez parser, nie przez Ciebie).

muszę gdzieś poszukać moje gramatyki i sprawdzić jak to było :)

Grzegorz Bialek pisze...

Szybkie resetowanie jest OK jednak w tym przypadku kuszącą alternatywą jest parsowanie pomimo błędów.

Przykładowo w wyrażeniu
"/elementA[poleA poleB]/elem..."
poleB jest tokenem nadmiarowym (sytuacja ta odzwierciedla brak operatora).

Jeżeli pomnielibyśmy ten token aż do nawiasu zamykającego utracilibyśmy o nim informację z AST. Jeżeli jednak zdecydujemy się go parsować (wrzucając wcześniej marker) dowiemy się że jest on drugą ścieżką relatywną. Informację tą możemy później wykorzystać by zgłosić czytelniejszy błąd w stylu 'brakujący operator' etc.

Oczywiście to tylko "gdybanie" ponieważ nie mam jeszcze gramatyki transformacji do modelu oraz obsługi błędów... ;)