Как сделать токены indent / dedent в стиле Python с alex / haskell?

Question

Я пишу лексер для небольшого языка в Алекс с Haskell.

Язык указывается с значительным отступом в Pythonesque, с токеном INDENT или DEDENT, генерируемым при изменении уровня отступа.

В традиционном императивном языке, таком как C, вы бы сохраняли глобальный элемент в лексере и обновляли его уровнем отступа в каждой строке.

Это не работает в Alex / Haskell, потому что я не могу нигде хранить глобальные данные с Haskell, и я не могу поместить все свои правила лексизма в какую-либо монаду или что-либо еще.

Итак, как я могу это сделать? Это вообще возможно? Или мне придется написать свой собственный лексер и избегать использования alex?

Answer 1

Обратите внимание, что в других языках, чувствительных к пробелам, таких как Haskell, обработка макетов действительно выполняется в лексере. GHC фактически реализует обработку макетов в Alex. Вот источник:

https://github.com/ghc/ghc/blob/master/compiler/parser/Lexer.x

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

Посмотрите на структуру AlexState, которую предоставляет Alex, позволяя вам определять состояние потока через лексер. Затем посмотрите, как состояние используется в реализации компоновки GHC для реализации отступа / отступа от правил компоновки. (Найдите «Обработка макета» в лексере GHC, чтобы увидеть, как состояние выдвигается и выталкивается).

Answer 2

Я не могу нигде хранить глобальные данные с Haskell

Это не правда; в большинстве случаев достаточно что-то вроде State monad , но есть и монада ST .

Однако для этой задачи вам не нужно глобальное состояние. Написание парсера состоит из двух частей; лексический анализ и синтаксический анализ. Лексический анализ просто превращает поток символов в поток значимых токенов. Синтаксический анализ превращает токены в AST; Здесь вы должны разобраться с отступом.

Когда вы интерпретируете отступ, вы будете вызывать функцию-обработчик при изменении уровня отступа - когда он увеличивается (вложение), вы вызываете свою функцию-обработчик (возможно, с одним увеличенным аргументом, если вы хотите отслеживать уровень отступа) ); когда уровень снижается, вы просто возвращаете соответствующую часть AST из функции.

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

Наконец, я думаю, что фраза «я не могу поместить все свои правила лексизма в какую-либо монаду» указывает на какое-то недопонимание монад. Если бы мне нужно было проанализировать и сохранить глобальное состояние, мой код выглядел бы так:

data AST = ...
type Step = State Int AST

parseFunction :: Stream -> Step
parseFunction s = do
   level <- get
   ...
   if anotherFunction then put (level + 1) >> parseFunction ...
   else parseWhatever
   ...
   return node

parse :: Stream -> Step
parse s = do
   if looksLikeFunction then parseFunction ...

main = runState parse 0 -- initial nesting of 0

Вместо комбинирования функциональных приложений с (.) или ($) вы объединяете их с (>>=) или (>>). Кроме этого, алгоритм тот же. («Монада» не должна быть «внутри».)

Наконец, вам могут понравиться аппликативные функторы:

eval :: Environment -> Node -> Evaluated
eval e (Constant x) = Evaluated x
eval e (Variable x) = Evaluated (lookup e x)
eval e (Function f x y) = (f <$> (`eval` x) <*> (`eval` y)) e

(или

eval e (Function f x y) = ((`eval` f) <*> (`eval` x) <*> (`eval` y)) e

если у вас есть что-то вроде "funcall" ... но я отвлекся.)

Существует много литературы по разбору аппликативных функторов, монад и стрел; все из которых могут решить вашу проблему. Читайте о них и посмотрите, что вы получите.