W jaki sposób kompilatory Haskell implementują w praktyce regułę parse-error (t)?

Question

Raport Haskell zawiera nieco notoryczną klauzulę w regułach dotyczących layoutu o nazwie "parse-error(t)". Celem tej reguły jest uniknięcie zmuszania programisty do pisania nawiasów klamrowych w wyrażeniach jednowierszowych let i podobnych sytuacjach. Odpowiedni zdanie brzmi:

Warunkiem strona parse-error (t) należy interpretować w następujący sposób: jeśli tokeny generowane dotychczas przez L wraz z kolejnym tokenem t reprezentuje nieprawidłowy prefiks gramatyki Haskell, a żetony generowane do tej pory przez L, po którym następuje token "}" reprezentują poprawny przedrostek gramatyki Haskella, a następnie parsowanie-błąd (t) jest prawdziwe.

Stwarza to niezwykłą zależność, w której leksytarz musi zarówno generować tokeny dla analizatora składni, jak i reagować na błędy powstałe w parserze, wstawiając dodatkowe tokeny do użycia przez parser. W przeciwieństwie do niemal wszystkiego, co można znaleźć w dowolnej innej definicji języka, znacznie komplikuje implementację, jeśli jest interpretowana w 100% dosłownie.

Nie jest zaskakujące, że żaden kompilator Haskella, o którym wiem, nie implementuje całej reguły w formie pisemnej. Na przykład, GHC fails to parse the following expression, co jest legalne według raportu:

let x = 42 in x == 42 == True 

Istnieje szeroka gama innych podobnych dziwnych przypadków. This post zawiera listę szczególnie trudnych przykładów. Niektóre z tych GHC działa poprawnie, ale również (od 7.10.1) nie powiedzie się na tym jednym:

e = case 1 of 1 -> 1 :: Int + 1 

Ponadto wydaje się GHC ma nieudokumentowane przedłużenie język zwany AlternativeLayoutRule zastępujący parsującej-błąd (t) klauzula ze stosem kontekstów tokena w lexer, który daje podobne wyniki w większości przypadków; nie jest to jednak zachowanie domyślne.

Co robią kompilatory Haskella w świecie rzeczywistym (w tym w szczególności GHC) w celu zbliżenia zasady parsowania błędów (t) podczas leksykowania? Jestem ciekawy, ponieważ próbuję zaimplementować prosty kompilator Haskella i ta reguła naprawdę mnie potknęła. (Patrz również this related question.)

Answer 1

Nie sądzę reguła parse-error(t) jest oznaczało być trudne do wdrożenia. Tak, wymaga on od parsera komunikowania się z lexerem, ale poza tym prawdopodobnie został zaprojektowany jako względnie łatwy do implementacji z dominującą technologią analizowania czasu: oparty na LALR (1) generowany parser z niewielkimi wsparcie dla korekcji błędów, takie jak GNU Bison, lub rzeczywiście jak Happy, którego używa GHC.

To może być ironia losu, przynajmniej częściowo ze względu na sukces Haskella przy włączaniu bibliotek kombinatoryjnych parsera, że ​​stara technologia nie jest tak dominująca jak kiedyś, przynajmniej w społeczności Haskell.

LALR (1) (lub LR (1)) generowane parser posiada następujące cechy, które pasują raczej dobrze jak reguła parse-error(t) jest przeznaczone należy interpretować:

• To nigdy nie cofa.
• Jego decyzje oparte na tabelach oznaczają, że zawsze "wie", czy dany token jest legalny w bieżącym miejscu, a jeśli tak, to co z nim zrobić.

okazji ma specjalny error żeton, który może być stosowany w celu osiągnięcia działania, gdy prąd żeton leksykalny jest nie prawny. Biorąc pod uwagę tego, most relevant definition w Happy gramatyki GHC jest

close :: {() } 
     : vccurly    {() } -- context popped in lexer. 
     | error     {% popContext } 

vccurly („wirtualny blisko kręcone”) jest token lexer wysyła gdy wybiera sama zamknąć poziom układu. popContext to an action defined in the lexer source, który usuwa poziom układu ze stosu układu. (Uwaga: W tej implementacji obudowa error ma numer , a nie wymaga od lexera wysłania z powrotem tokena vccurly).

Używając tego, wszystkie reguły parsera GHC muszą w inny sposób używać close jako ich nieterminowego tokena dla zakończenia bloku wcięć otwartego z vocurly. Zakładając, że reszta gramatyki jest poprawna, implementuje to również poprawnie.

A przynajmniej taka jest teoria. Okazuje się, że czasami się to psuje ze względu na inne cechy Haskella/GHC, które nie pasują do gramatyki LALR (1).

Z dwóch powyższych przykładów, pierwsza została zmieniona w Haskell 2010 (ponieważ ludzie zdali sobie sprawę, że było to niezręczne do przeanalizowania), więc GHC jest tam poprawny. Ale drugi (e = case 1 of 1 -> 1 :: Int + 1) dzieje się z powodu different design decision GHC sprawia:

Making parser zanalizować dokładnie prawo język jest trudne. Dlatego parser GHC działa zgodnie z następującą zasadą:

• Często parsujemy "zbyt hojnie" i odfiltrowujemy złe przypadki później.

GHC ma wystarczające rozszerzenia, które Int + 1mógł parse jako typ z wystarczająco dużo z nich włączone. Ponadto, aby napisać LALR (1) -parser, aby bezpośrednio obsługiwać każdą kombinację włączonych/wyłączonych rozszerzeń, byłoby to niezręczne (nie wiem, czy to możliwe). Najpierw analizuje najpierw najbardziej ogólny język, a następnie kończy się niepowodzeniem, gdy sprawdza, czy wymagane rozszerzenia są włączone. Ale do tego czasu przetwarzanie jest zakończone i jest za późno, aby wywołać regułę parse-error. (Albo więc jestem przy założeniu).

Wreszcie, należy powiedzieć, że nie sądzę, jest coś niemożliwe temat obchodzenia się z reguły parse-error(t) nawet jeśli nie używasz (LA) LR (1) parser . Podejrzewam, że coś w rodzaju tokena GHC close może działać dobrze również w kombinacji. Ale nadal potrzebujesz jakiejś komunikacji z lexerem.