Когда парсер добавит свою входную строку? - PullRequest
Новая
       9

Когда парсер добавит свою входную строку?

2 голосов
/ 20 апреля 2019

с учетом парсера 

newtype Parser a = Parser { parse :: String -> [(a,String)] }

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = Parser $ \s -> concat [ parse (f a) s' | (a, s') <- parse p s ]

return :: a -> Parser a
return a = Parser (\s -> [(a,s)])

item :: Parser Char
item = Parser $ \s -> case cs of
                         ""     -> []
                         (c:cs) -> [(c,cs)]

Мы можем видеть, что item потребляет часть заданной ему входной строки ("abc" -> [('a', "bc")]). Был ли когда-нибудь случай, когда парсер выдает дополнительный вывод строки или заменяет / модифицирует его (например, Parser $ \s -> [((), 'a':s)])? Я подозреваю, что это может быть в случае контекстно-зависимых грамматик, но у меня возникли проблемы с нахождением разумного примера.

Есть ли причина, по которой имеет смысл сделать это для реальной проблемы?

Ссылки

1 Ответ

3 голосов
/ 21 апреля 2019

Вот пара случаев, когда удобно вводить токены во входной поток. (Как это на самом деле интегрировано в конвейер синтаксического анализа - другой вопрос.)

  1. Расширение макроса в стиле фазы предварительной обработки C / C ++. Возможно, это не лучшая модель для расширения макросов; гигиенические макросы, скорее всего, будут расширены с помощью преобразования дерева, как с разрешением шаблона C ++. Но токен-ориентированный препроцессор скоро не исчезнет. Поскольку он не тесно связан с синтаксисом языка, самая простая реализация состоит в том, чтобы заменить макрос (и аргументы, если применимо) токенами из его расширения.

  2. Автоматическая вставка точек с запятой в стиле Ecmascript (ASI). Синтаксис языка требует, чтобы точка с запятой была вставлена ​​в поток токенов при определенных точно определенных обстоятельствах, которые трудно (по крайней мере) включить в CFG. Поскольку ASI возможен только в том случае, если следующий токен во входном потоке нельзя сместить (и выполнить другие условия), он, безусловно, может быть интегрирован в цикл синтаксического анализатора.

  3. Аналогично, синтаксис с учетом отступов (как, например, в Haskell и Python), безусловно, можно реализовать, заменив начальные пробелы введенным токеном INDENT или некоторым количеством введенных DEDENT. Поскольку эта замена зависит от контекста синтаксического анализа (например, это не делается внутри скобок), разумным подходом может быть внедрение внутри синтаксического анализатора.

Это не исчерпывающий список, но он может быть хотя бы ориентировочным. Не все из этих случаев обязательно включают контекстно-зависимую (я считаю, что ASI, теоретически, может быть обработана с помощью контекстно-свободной грамматики, хотя я не собираюсь пытаться), и не все случаи контекстно-зависимой обязательно требуют инъекции токена (неоднозначность в C между именами типов и переменных требуется только выбор правильного токена).

...