Короче говоря, даже если у вас есть список токенов, вам все еще нужен парсер.
Parsec может обрабатывать альтернативные потоки токенов, но вам, вероятно, придется обратиться к руководству - PDF, доступному на "устаревшей" домашней странице Daan Leijen - http://legacy.cs.uu.nl/daan/download/parsec/parsec.pdf. Вы можете свернуть свой собственный анализатор без использования комбинатора библиотека, но вы будете повторно реализовать некоторую часть Parsec. Насколько я помню, UU_parsing рассчитывает работать с отдельным сканером, так что это еще один вариант.
Хотя он не обрабатывает синтаксический анализ, вы можете найти, что «Лямбда-исчисление, приготовленное четырьмя способами» Леннарта Огастсона полезно для других вещей - http://www.augustsson.net/Darcs/Lambda/top.pdf
Редактировать - вот частично разработанный план того, как вы можете это сделать с помощью Parsec, для подробностей вы должны обратиться к разделу 2.11 руководства.
Предположим, у вас есть этот тип данных для конкретных "внутренних" токенов:
data InternalTok = Ident String
| BinOpPlus
| BinOpMinus
| UnaryOpNegate
| IntLiteral Int
deriving (Show)
Затем вы получите следующие типы токенов Parsec и выполните синтаксический анализ:
type MyToken = Token InternalTok
type MyParser a = GenParser MyToken () a
Определите вспомогательную функцию в соответствии с руководством Parsec - это дескрипторы show и pos, поэтому отдельные определения короче ср. функция mytoken на стр. 19.
mytoken :: (MyToken -> Maybe a) -> MyParser a
mytoken test = token showToken posToken testToken
where
showToken tok = show tok
posToken tok = no_pos
testToken tok = test tok
На данный момент тип вашего токена не отслеживает исходную позицию, поэтому:
no_pos :: SourcePos
no_pos = newPos "" 0 0 0
Для каждого терминала вы должны определить функцию токена:
identifier :: MyParser MyToken
identifier = mytoken (\tok -> case tok of
a@(Prefix (Ident _)) -> Just a
_ -> Nothing)
intLiteral :: MyParser MyToken
intLiteral = mytoken (\tok -> case tok of
a@(Prefix (IntLiteral _)) -> Just a
_ -> Nothing)
binPlus :: MyParser MyToken
binPlus = mytoken (\tok -> case tok of
a@(Infix BinOpPlus _ _) -> Just a
_ -> Nothing)
binMinus :: MyParser MyToken
binMinus = mytoken (\tok -> case tok of
a@(Infix BinOpMinus _ _) -> Just a
_ -> Nothing)
unaryNegate :: MyParser MyToken
unaryNegate = mytoken (\tok -> case tok of
a@(Prefix UnaryNegate _ _) -> Just a
_ -> Nothing)
Редактировать - для обработки пользовательских инфиксных операторов вам понадобятся следующие парсеры токенов:
tokInfixL :: Int -> MyParser MyToken
tokInfixL n = mytoken $ \tok -> case tok of
a@(Infix _ i InfixL) | i == n -> Just a
_ -> Nothing)
tokInfixR :: Int -> MyParser MyToken
tokInfixR n = mytoken $ \tok -> case tok of
a@(Infix _ i InfixR) | i == n -> Just a
_ -> Nothing)
tokInfixC :: Int -> MyParser MyToken
tokInfixC n = mytoken $ \tok -> case tok of
a@(Infix _ i InfixC) | i == n -> Just a
_ -> Nothing)
tokPrefix :: MyParser MyToken
tokPrefix = mytoken (\tok -> case tok of
a@(Prefix _) -> Just a
_ -> Nothing)
Теперь вы можете определить синтаксический анализатор - вам нужно заранее зафиксировать количество уровней приоритета, нет никакого способа обойти этот факт, так как вам нужно кодировать синтаксический анализатор для каждого уровня.
Анализ выражений верхнего уровня просто вызывает синтаксический анализатор с наивысшим приоритетом
pExpression :: Parser Expersion
pExpression = expression10
Для каждого уровня приоритета вам нужен примерно такой синтаксический анализатор, вам придётся работать самостоятельно. Также вам может понадобиться поработать с chainl / chainr - я только написал парсер в этом стиле с UU_Parsing, он может немного отличаться для Parsec. Примечание Применить обычно находится на самом высоком уровне приоритета.
expression10 :: Parser Expression
expression10 =
Apply <$> identifier <*> pExpression
<|> Prefix <$> tokPrefix <*> pExpression
<|> chainl (Infix <$> tokInfixL 10) expression9
<|> chainr (Infix <$> tokInfixR 10) expression9
expression9 :: Parser Expression
expression9 =
Prefix <$> tokPrefix <*> pExpression
<|> chainl (Infix <$> tokInfixL 9) expression8
<|> chainr (Infix <$> tokInfixR 9) expression8
...
Вам придется расширить синтаксис для обработки IntLiterals и идентификаторов, которые имеют приоритет на уровне 0:
expression0 :: Parser Expression
expression0 =
IntLit <$> intLiteral
<|> Ident <$> identifier
<|> ...
Редактировать - для неограниченного приоритета - возможно, если у вас есть только приложение и Atom, может быть, что-то подобное будет работать. Обратите внимание, что вам придется изменить синтаксические анализаторы tokInfixL и tokInfixR, чтобы они больше не соответствовали ассоциативному уровню, и вам, возможно, придется поэкспериментировать с порядком альтернатив.
expression :: Parser Expression
expression =
Apply <$> identifier <*> expression
<|> Prefix <$> tokPrefix <*> expression
<|> chainl (Infix <$> tokInfixL) expression
<|> chainr (Infix <$> tokInfixR) expression
<|> intLiteral
<|> identifier
intLiteral :: Parser Expression
intLiteral = Atom . convert <$> intLiteral
where
convert = ??
identifier :: Parser Expression
identifier = Atom . convert <$> intLiteral
where
convert = ??