Вопрос, являющийся домашней работой / упражнением, ниже следует объяснение, которое пытается избежать порчи решения;он делает это, будучи написанным на Common Lisp (то есть, и потому что я не знаю Haskell ;-)).
В Common Lisp есть промежуточная функция с именем READ-DELIMITED-LIST, который читает несколько форм в виде списка, пока читатель не достигнет конечного символа.При обнаружении открывающей скобки читатель берет все формы до закрывающей скобки, а затем продолжает анализ с этого места.Разница в том, что он работает с потоками символов, а не с токенами, и что этот поток используется для побочных эффектов.
Без побочных эффектов
В чисто функциональном подходе, как вВ вашем коде функция parse должна вернуть оставшиеся токены для обработки вместе с возвращенным AST.Это позволяет вам использовать столько токенов, сколько вам нужно во время синтаксического анализа, и позволяет вызывающей программе продолжать анализ с того места, где анализатор завершился.
Другими словами, когда вы закрываете скобки, вы должны вернуть xsв контекст вызова.Итак, вы несете объект-накопитель (состояние) вместе с вашим кодом.Я слышал, что монады могут помочь вам с шаблоном.
Ускоренный курс
MULTIPLE-VALUE-BIND и VALUESработать вместе: (values x y) возвращает несколько значений, а multiple-value-bind захватывает несколько значений из выражения и связывать каждое из них с переменной.
DESTRUCTURING-BINDявляется прародителем сопоставления с образцом и просто разбивает список на компоненты.
Неспециализированная форма (f x1 .. x2) - это приложение функции
(case test . clauses) - это переключатель, где каждое предложение представляет собой список, начинающийся с буквального значения (или списка таких значений), за которым следуют выражения.t и otherwise - это специальные ключевые слова, которые всегда совпадают (регистр по умолчанию).
Остальные значения должны быть достаточно понятны (спросите иначе).
Обратите внимание, что я использую символы < и > для представления соответственно открывающих и закрывающих токенов, чтобы избежать путаницы сСкобки Лиспа.Например, список (< a b c < d > >) содержит 8 токенов;Я мог бы использовать left-paren и right-paren, или даже сложные структуры данных, это просто внутреннее представление.
Parser
Функция точки входа parse принимает списоктокены и возвращает проанализированное значение и оставшиеся токены в качестве вторичного значения;это зависит от parse-until-close, определенного ниже:
(defun parse (tokens)
(when tokens
(destructuring-bind (head . tail) tokens
(case head
(> (error "unmatched closing parenthesis"))
(< (parse-until-close tail))
(otherwise (values head tail))))))
Затем parse-until-close - функция, которая рекурсивно анализирует токены, пока не найдет токен, близкий к нему;обратите внимание, что tokens перепривязывается в разных точках:
(defun parse-until-close (tokens)
(when tokens
(case (first tokens)
(> (values nil (rest tokens)))
(otherwise
;; first read the element in head of tokens
(multiple-value-bind (head tokens) (parse tokens)
;; then recurse to read the remaining items in list
(multiple-value-bind (tail tokens) (parse-until-close tokens)
(values (cons head tail) tokens)))))))
Вышеуказанный рекурсивно анализирует токены и составляет список.Если наш список токенов начинается с >, токена закрытия, мы возвращаем пустой список, а также остальные токены.
В противном случае, мы анализируем один элемент и рекурсируем с parse-until-close.
Тест
Каждый вызов возвращает два значения: проанализированный токен и остальные:
(parse '(one token))
=> ONE
(TOKEN)
(parse '(< abc < x > y >))
=> (ABC (X) Y)
NIL
(parse '(< abc def >))
=> (ABC DEF)
NIL
;; incomplete input
(parse '(< < < abc))
=> (((ABC)))
NIL