Putting węzły do ​​drzewa parsowania, które nie powinny być tam

Question

Piszę parser dla języka, a skaner jest przeznaczony do

1. bądź też powrócić niepotrzebnych terminali (np whitespacing) OR
2. nie w tym celu:

na podstawie flagi boolowskiej.

Teraz, w parserze, nie chcę zagracać gramatyki tymi wszystkimi terminalami, powinny one zostać połknięte w jakiś sposób "automagicznie" przez drzewo analizy, które buduję.

Aby wykonać tę "magię", pomyślałem, że połączę terminale (po prostu połączę okrągłą listę), tak żebym mógł je po prostu powtórzyć i "wypełnić puste miejsca" w miarę jak następuje redukcja (używam LALR (1)) generator parsera).

To brzmi jak rozsądny pomysł, chociaż jest jeden problem. Pamiętaj, że powiedziałem "albo wrócić ... albo nie"? W scenariuszu (2) uwolniłbym terminal, bo kto wie, co będzie dalej? I nie chcę żadnych wycieków pamięci.

Ale w scenariuszu (1) nie mogę zwolnić terminala, ponieważ na jego podstawie zdecyduję się na dalsze redukcje, w których proces "wypełnij puste pola" powinien się zatrzymać.

Nie mogę tego zwolnić warunkowo z tego samego powodu: nie wiem, co będzie dalej. Co się stanie, jeśli nie zostanie uruchomiony proces "wypełnienia pustych miejsc"? A co, jeśli w ogóle nie będzie żadnej redukcji?

Czy miałeś podobne problemy? Jak to rozwiązałeś?

Uwaga: to wszystko w mojej głowie i być może nie wyjaśniłem tego wystarczająco wyraźnie, proszę zapytaj, a ja zmienię moje pytanie. Scenariusz jest nieco bardziej złożony, nie piszę tego od zera, gdzie mógłbym wykorzystać moją wyobraźnię, integruję go z czymś innym, więc być może odpowiem: "Nie mogę tego zrobić z powodu ograniczeń środowiskowych ".

---

Uzupełnienie

Jedynym naprawdę dobry pomysł, który przychodzi mi do głowy jest widelec i poprawić generator parsera, co już robiłem w niektórych pomniejszych miejsc tu i tam, aby przezwyciężyć niektóre z tych ograniczenia, o których wspomniałem powyżej.

Answer 1

Twoje słownictwo jest trochę dziwne. Większość analizatorów składni ma na celu rozpoznanie składni języka. Zazwyczaj definicja języka definiuje pojęcie terminali i jednoznacznie wyklucza "białe spacje", składające się z nieciekawych fragmentów tekstu między tekstem terminali, często obejmujących spacje, tabulatory i różne rodzaje niezależnych komentarzy. Tak więc termin "terminal" używany w analizie zwykle oznacza "te atomy języka, które nie są białymi znakami". Zdefiniowałeś ją pośrednio, aby uwzględnić białe znaki i myślę, że to powoduje twój smutek.

Z tego punktu widzenia najłatwiejszym sposobem uniknięcia zlekceważenia definicji gramatyki używanej przez twój parser z białymi spacjami jest po prostu pominięcie lexer w parserze. Wtedy twoja gramatyka nie musi wskazywać, w jaki sposób są one obsługiwane (i tak, gramatyki, które to robią są naprawdę niechlujne), parser nie musi się nimi martwić i nie pojawiają się w drzewie.

Jeśli budujesz kompilator lub interpreter, to ignorowanie spacji jest najłatwiejsze.

Jeśli budujesz parser re-engineering (patrz nasz DMS Software Reengineering Toolkit, następnie przechwytywanie komentarzy (przynajmniej) w AST jest ważne, ponieważ ostatecznie chce się zregenerować tekst z consturcted ASTs, i to jest pomocne, jeśli regenerowany tekst zawiera również komentarze. [Możesz zrobić to innymi sposobami, ale nie są one tak proste.)

Lider DMS produkuje żetony "mikro", które są twoją koncepcją żetonów, białych spacji i komentarzy wewnętrznie. Usuwa białe żetony, ponieważ po prostu nic nie dodają (patrz powyżej) Przekazuje zwykłe tokeny do parsera, jak się spodziewamy, skleja tokeny komentarza do poprzedzającego lub następującego tokenu językowego, w zależności od typ tokena i wher e napotkany; dla C, a/* ... */widzianego przed dołączeniem tokena i komentarz // ... dołączony do poprzedzającego tokena (z kilkoma bardziej subtelnymi szczegółami, nie omawianymi tutaj). W dalszym ciągu analizowane są tylko żetony językowe, więc gramatyka nie jest niepotrzebnie skomplikowana, a jeśli wszystkie informacje dołączone do tokena znajdują się w drzewie, komentarze idą dalej.

Teraz ludzie często chcą "abstrakcyjnych" drzew składniowych; chcą pominąć rzeczy takie jak "(" i ")". Schemat, który opisałem powyżej, zawierał komentarze do nawet konkretnych tokenów takich jak te. Teraz jest komplikacja: jeśli zostawisz (...) żetony z drzewa, dołączone komentarze znikną. Ups. Tak więc parsery DMS robią skomplikowane rzeczy: komentarze dołączone do tokenów, które mają logiczne miejsce w drzewie, ale tak naprawdę ich tam nie ma ("wyeliminowane terminale") są przenoszone do węzła drzewa nadrzędnego z adnotacją mówiącą, że należą do brakującego tokenu podrzędnego . Tak, wdrożenie tego jest rzeczywiście PITA. Dobrą wiadomością jest to, że musieliśmy zrobić to tylko raz w ogólnej maszynie analizowania DMS i działa ona dla wielu, wielu języków. Ale to oznacza, że ​​musisz chcieć zbudować niezwykły ("reengineering") parser, a my mieliśmy komercyjną motywację, aby to zrobić.

EDYCJA: Nie jest jasne, dlaczego OP chce tego, ale nalega na przechwycenie białych znaków na drzewie. Ponieważ nie powiedział nam dlaczego, zamierzam zgadnąć: chce precyzyjnej informacji o kolumnie dla węzłów tokenów/drzew. To nie jest trudne: naucz lexer'a, aby śledził pozycję (linia/kolumna) i tupnij każdy token (mikro-tokeny, takie jak komentarze) również z pozycją początkową/końcową, i pozwól, aby analiza składowała te informacje w drzewo. W ten sposób unika się również utrzymywania białych znaków w drzewie. (DMS również to robi, ponieważ przy zgłaszaniu problemów dokładne informacje są przydatne, a przy regeneracji kodu często pożądane jest umieszczenie kodu w jego pierwotnej pozycji (co najmniej w tej samej kolumnie).

EDIT2: Jeśli OP nalega na uchwycenie białych znaków, może rozważyć zbadanie scannerless GLR parsing. Zachowuje to każdy znak w strumieniu wejściowym, włącznie z białymi znakami.