Как компиляторы Haskell реализуют правило parse-error (t) на практике?

Question

В отчете Haskell есть несколько печально известное предложение в правилах макета, называемых «parse-error(t)». Цель этого правила состоит в том, чтобы не заставлять программиста писать фигурные скобки в однострочных выражениях let и подобных ситуациях. Соответствующее предложение:

сторона состояние синтаксического анализа ошибок (т) следует интерпретировать следующим образом: если маркеры генерируется до сих пор L вместе со следующим маркером т представляют недопустимый префикс грамматики Haskell, и токены, сгенерированные до сих пор L, за которым следует токен "}", представляют собой действительный префикс грамматики Haskell, тогда parse-error (t) истинно.

Это создает необычную зависимость, где лексер обязательно и производит маркеры для синтаксического анализа и реагирует на ошибки, полученных в парсер, вставив дополнительные маркеры для парсер, чтобы потреблять. Это не похоже на то, что вы найдете в любом другом определении языка, и сильно усложняет реализацию, если оно интерпретируется буквально на 100%.

Неудивительно, что компилятор Haskell, о котором я знаю, реализует все правило в письменном виде. Например, GHC fails to parse the following expression, который является законным согласно отчету:

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

Есть широкий спектр других подобных странных случаев. This post имеет список некоторых особенно трудных примеров. Некоторые из этих GHC работают правильно, но он также (по состоянию на 7.10.1) не будет работать на этой одном:

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

Кроме того, он, кажется, GHC имеет расширение недокументированного языка называется AlternativeLayoutRule, заменяющий разбор ошибка (т) с стеком контекста токенов в лексере, который дает аналогичные результаты в большинстве случаев; однако это не поведение по умолчанию.

Что делают компиляторы Haskell реального мира (в частности, GHC в частности), чтобы приблизить правило parse-error (t) во время lexing? Мне любопытно, потому что я пытаюсь реализовать простой компилятор Haskell, и это правило действительно отключает меня. (Смотри также this related question.)

Answer 1

Я не думаю, что parse-error(t) правило означает будет трудно реализовать. Да, это требует, чтобы синтаксический анализатор связывался с лексером, но кроме этого он, вероятно, был разработан относительно easy для реализации с доминирующей технологией синтаксического анализа того времени: основанный на LALR (1) парсер с небольшим поддержка коррекции ошибок, например, GNU Bison, или даже как Happy, который использует GHC.

Возможно, по иронии судьбы, хотя бы частично благодаря успеху Хаскелла в создании библиотек-комбайнов-парсеров, эта старая технология не настолько доминирует, как раньше, по крайней мере, в сообществе Haskell.

LALR (1) (или LR (1)), генерируемый парсер имеет следующие особенности, которые соответствуют, а также с тем, как parse-error(t) правила предназначено быть истолковано:

• Он никогда не откатывается.
• Его решения, основанные на таблицах, означают, что он всегда «знает», является ли данный токен законным в текущем месте, и если да, то что с ним делать.

Счастливые имеет специальный error маркер, который может быть использован для достижения действия, когда текущий лексический маркер не законных. Учитывая это, most relevant definition в Happy грамматике GHC является

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

vccurly («виртуальный близко фигурная») является лексема лексер посылает, когда он выбирает сам по себе, чтобы закрыть уровень макета. popContext - an action defined in the lexer source, который удаляет уровень макета из стека компоновки. (Обратите внимание, что в этой реализации error случай не нужен лексер для отправки маркера vccurly).

Используя это, все правила парсера GHC должны в противном случае использовать close как их нетерминальный токен для завершения отступающего блока, открытого с vocurly. Предполагая, что остальная часть грамматики правильная, это правильно реализует правило.

Или, по крайней мере, это теория. Оказывается, что это иногда ломается из-за других особенностей Haskell/GHC, что не подходит также и в грамматике LALR (1).

Из двух приведенных выше примеров первый был изменен в Haskell 2010 (потому что люди поняли, что это слишком сложно для синтаксического анализа), поэтому GHC там верен. Но второй (e = case 1 of 1 -> 1 :: Int + 1) происходит из-за different design decision GHC делает:

Создание парсера разобрать точно правильный язык трудно. Таким образом, парсер GHC следует следующему принципу:

• Мы часто разбираем «чрезмерно щедро» и отфильтровываем плохие случаи позже.

GHC имеет достаточные расширения, Int + 1мог синтаксического анализа как тип с их достаточно включены. Кроме того, необходимость написать LALR (1) -парсер для прямой обработки каждой комбинации включенных/отключенных расширений будет действительно неудобно (не уверен, что это даже возможно). Таким образом, он сначала анализирует наиболее общий язык и не работает позже, когда проверяет, разрешены ли необходимые расширения для результата. Но к этому времени разбор закончен, и уже слишком поздно запускать правило parse-error. (Или так я предполагаю.)

Наконец, я должен сказать, что я не думаю, что есть что-нибудь невозможно об обращении с parse-error(t) правило, даже если вы не используете (LA) LR (1) парсер , Я подозреваю, что токен GHC close может хорошо работать и в комбинаторе. Но вы все еще нуждаетесь в некотором обращении к lexer.