Parsec не потребляет весь вход?

Question

Я пишу код для анализа команд из простого императивного языка, определенного в Теория языков программирования (Reynolds, 1998).

У меня есть модуль lexer, который задает строку, извлекает из него токены, если это допустимое выражение языка, а затем передаю этот список токенов парсеру, который должен построить внутреннее представление команды (определяемой как алгебраические данные тип).

Это мои токены:

--Tokens for the parser 
data Token = Kw Keyword 
| Num Int 
| Op Operator 
| Str String 
| Sym Symbol 
deriving Show 

У меня возникли проблемы с бинарными операторами. Я приведу в качестве примера сумму, но она будет одинаковой со всеми из них, будь то логическая или целая.

Например, если бы я запустить программу синтаксического анализа «х: = 2 + 3» я должен получить следующий список лексем из лексером
[Str «х», Op Колон, Op Равное , Num 2, OP, Plus, Num 3]
Это на самом деле то, что я получаю.

Но тогда анализатор должен вернуть команду
Назнач «х» (IBIN Plus (Const 2) (Const 3)
который является правильным представлением команды. Но вместо того, что я получаю следующее представление:
Присвоить «х» (Const 2)

я полагаю, что я ввернул это в какой-то момент в функции pIntExpr, так как переменная идентификатор и : = из назначение анализируется ОК, и оно не анализирует последние элементы. Вот соответствующие синтаксические анализаторы для этого примера, чтобы увидеть, может ли кто-то ориентировать меня в том, что я делаю неправильно.

-- Integer expressions 
data IntExpr = Const Int 
     | Var Iden --Iden=String 
     | Neg IntExpr 
     | IBin OpInt IntExpr IntExpr 
     deriving Show 

type TParser = Parsec [Token]() 

--Internal representation of the commands 
data Comm = Skip 
     | Assign Iden IntExpr 
     | If Assert Comm Comm 
     | Seq Comm Comm 
     | While Assert Comm 
     | Newvar Iden IntExpr Comm 
     deriving Show 

--Parser for non sequential commands 
pComm' :: TParser Comm 
pComm' = choice [pif,pskip,pAssign,pwhile,pNewVar] 

--Parser for the assignment command 
pAssign :: TParser Comm 
pAssign = do v <- pvar 
      _ <- silentOp Colon 
      _ <- silentOp Equal 
      e <- pIntExp 
      return $ Assign v e 

-- Integer expressions parser 
pIntExp :: TParser IntExpr 
pIntExp = choice [ var' --An intexp is either a variable 
        , num --Or a numeric constant 
        , pMul --Or <intexp>x<intexp> 
        , pSum --Or <intexp>+<intexp> 
        , pRes --Or <intexp>-<intexp> 
        , pDiv --Division 
        , pMod --Modulus 
        , pNeg --Unary "-" 
       ] 

-- Parser for <intexp>+<intexp> 
pSum :: TParser IntExpr 
pSum = do 
    e <- pIntExp 
    _ <- silentOp Lexer.Plus 
    e' <- pIntExp 
    return $ IBin Lang.Plus e e' 

UPDATE УЧЕТ ОТВЕТА СЧЕТ AndrewC в
К сожалению, перемещение Var» анализатора вниз в списке выбора не работает, это приводит к тому же результату. Но я принял во внимание ответ AndrewC и попытался «вручную» отслеживать выполнение (я не знаком с отладчиком ghci и в итоге сделал много одиночных шагов и в конце концов потерялся). Это, как я урезонить его:

Я получил этот символический список из лексера: [Str "х", Op Colon, Op Ровный, Num 2, OP Plus, Num 3]

Так , то PComm» анализатор выдает PIF и pskip, но succeds с pAssign, потребляющие Str "х", Op Colon и Op Равное и пытается разобрать [Num 2, OP Plus, N um 3] с pIntExp (!!)

pIntExp анализатор затем пробует вар» парсер и выходит из строя, но succeds с Num парсер потребляющего Num 2 маркер и, следовательно, возвращая ошибочный результат Присвоить„х“(Const 2).

Так с советами AndrewC в виду о выбора, я переехал Num анализатор вниз в списке тоже. Ради простоты я рассмотрю pIntExp как выбор [pSum, num, var'] что это то, что актуально для этого конкретного примера.

Первая часть рассуждений остается прежней. Так что я буду перезапускать из (!!), где мы имели
[Num 2, Op Plus, Num 3] быть разобран pIntExp
pIntExp пытается в настоящее время первый с Psum, который, в свою очередь, «звонки» pIntExp еще раз, , который попробует pSum еще раз, и поэтому программа зависает. Я попробовал, и он действительно висит и никогда не кончается.

Так мне было интересно, если есть форма, чтобы сделать Psum анализатор «опережения» для Op Plus маркер, а затем разобрать соответствующие выражения?

UPDATE 2: После «прибегая к помощи» немного более теперь, когда я определил эту проблему я обнаружил, что комбинационные парсеры chainl1 и/или chainl может быть только то, что мне нужно. Я буду играть с ними, и если я его выработаю, отправьте решение.

Answer 1

Функция выбора пробуждает синтаксический анализатор в том порядке, в котором они находятся в списке.

Поскольку анализатор yoiur для переменных появляется перед вашим синтаксическим анализатором для более сложного выражения сложения, он преуспевает до того, как будет проверен другой.

Чтобы решить эту проблему, установите переменный парсер после любых выражений, которые начинаются с переменным (и думают, через любые другие вопросы подстроки сопоставления при использовании выбора

Аналогичных проблемы incude 3 -. 4 + 1 оценка до -2. Люди ожидают левую ассоциацию при отсутствии других приоритетов (так что сумма вместо суммы-суммы).

Вам также может не понадобиться 1 + 10 * 5, чтобы развить до 55, так что вы будете иметь чтобы быть осторожным вокруг + и * и т. д., если вы хотите реализовать приоритет оператора. Вы можете добиться этого, разобрав выражение, состоящее из умножения, как термин, а затем additi ve выражение как сумма термов.