Haskell: сопоставление строковых префиксов со списком

В последнее время я изучаю Haskell и подумал, что лексер может быть интересным проектом. Я использую эту грамматику ANSI C Yacc как Руководство.

Общая структура программы:

lex :: [Char] -> Maybe [Token]
lex s =
  case tokenize([], s) of
    Just (tokens, []) -> Just tokens
    _ -> Nothing

tokenize :: ([Token], [Char]) -> Maybe ([Token], [Char])

Где tokenize составляет список токенов. Мне сложно придумать подходящую структуру для tokenize. Например, для соответствия таким ключевым словам, как int, я мог бы написать:

tokenize (toks, 'i':'n':'t':' ':rest) = tokenize (toks++[TokenKeyword IntK], rest)

Но это кажется ужасным способом делать что-то. Есть ли способ сопоставления шаблонов с элементами в списке? Могу ли я создать список всех ключевых слов и попытаться сопоставить их как префиксы входной строки?


haskell lexer
person avery_laird    schedule 25.02.2019    source источник
comment
Сопоставление префиксов не приведет вас очень далеко, потому что некоторые токены не будут предопределенными строками, например числами или идентификаторами.   -  person Fyodor Soikin    schedule 25.02.2019
comment
Верно, конечно, сопоставление префиксов не покрывает все. Я говорил конкретно о зарезервированных ключевых словах   -  person avery_laird    schedule 25.02.2019
comment
Возможно, вам подойдет regex-Applicative.   -  person Daniel Wagner    schedule 25.02.2019
comment
Вам, вероятно, следует научиться пользоваться какой-нибудь библиотекой parsec.   -  person Karol Samborski    schedule 25.02.2019
comment
Спасибо всем за их вклад. Чтобы прояснить мой вопрос, я хотел бы ограничить, насколько я использую библиотеки синтаксического анализа / регулярных выражений.   -  person avery_laird    schedule 26.02.2019

Ответы (1)


arrow_upward
1
arrow_downward

Если вы хотите найти соответствие на основе префикса строки, вы можете использовать расширение ViewPatterns. Это расширение можно включить, передав компилятору -XViewPatterns, запустив :set -XViewPatterns в ghci или поместив {-# LANGUAGE ViewPatterns #-} в начало файла.

Затем вы можете написать функцию matchPrefix (не на 100% оптимальную, поскольку она выполняет итерацию по prefix дважды):

matchPrefix :: String -> String -> Maybe String
matchPrefix prefix result
  | and (zipWith (==) prefix result) = Just (drop (length prefix) result)
  | otherwise = Nothing

А затем используйте его в следующем шаблоне:

startsWithInt :: String -> Bool
startsWithInt (matchPrefix "int " -> Just rest) = True
startsWithInt _ = False

Если вы хотите найти соответствие на основе списка токенов и получить остальную часть строки и соответствующий токен, вы можете сделать это, изменив matchPrefix для этого.

person Izaak Weiss    schedule 25.02.2019