Учитывая синтаксический анализатор

 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)] )? Я подозреваю, что это может иметь место с контекстно-зависимыми грамматиками, но мне трудно найти разумный пример.

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

Ссылки

• Монадический синтаксический анализ в Haskell

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

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

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

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

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