Незапланированное жадное поведение в uu-parsinglib

Question

Эта проблема

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

Так что ниже вы можете найти пример парсера комбинаторов. Самый важный из них pOperator, который очень простым способом (только для демонстрационных целей) строит оператор AST. Он использует "x" и может использовать несколько "x", разделенных пробелами.

У меня также есть pParens комбинатор, который определяется как:

pPacked pParenL (pWSpaces *> pParenR)

поэтому он использует пробельные символы перед закрывающей скобкой.

Пример ввода / вывода

Правильный ввод / вывод ДОЛЖЕН быть:

in: "(x)"
out: Single "x"

in: "(x )"
out: Single "x"

но я получаю:

in: "(x)"
out: Single "x"

in: "(x )" 
out: Multi (Single "x") (Single "x")
--  Correcting steps: 
--    Inserted  'x' at position LineColPos 0 3 3 expecting one of ['\t', ' ', 'x']

но во втором примере я получаю ошибку - и синтаксический анализатор ведет себя так, как будто он жадно съедает некоторые токены (и нет жадной операции).

Буду благодарен за любую помощь с этим.

Образец кода

import Prelude hiding(lex)
import Data.Char hiding (Space)
import qualified Text.ParserCombinators.UU as UU
import           Text.ParserCombinators.UU hiding(parse)
import qualified Text.ParserCombinators.UU.Utils as Utils
import           Text.ParserCombinators.UU.BasicInstances hiding (Parser)


data El = Multi El El
        | Single String
        deriving (Show)


---------- Example core grammar ----------

pElement     = Single <$> pSyms "x"
pOperator    = applyAll <$> pElement <*> pMany (flip <$> (Multi <$ pWSpaces1) <*> pElement)

---------- Basic combinators ----------

applyAll x (f:fs) = applyAll (f x) fs
applyAll x []     = x

pSpace    = pSym ' '
pTab      = pSym '\t'
pWSpace   = pSpace <|> pTab
pWSpaces  = pMany pWSpace
pWSpaces1 = pMany1 pWSpace
pMany1 p  = (:) <$> p <*> pMany p

pSyms []       = pReturn []
pSyms (x : xs) = (:) <$> pSym x <*> pSyms xs

pParenL     = Utils.lexeme $ pSym '('
pParenR     = Utils.lexeme $ pSym ')'
pParens     = pPacked pParenL (pWSpaces *> pParenR)

---------- Program ----------

pProgram = pParens pOperator
-- if you replace it with following line, it works:
--  pProgram = pParens pElement
-- so it seems like something in pOperator is greedy

tests = [ ("test", "(x)")
        , ("test", "(x )")
        ]

---------- Helpers ----------

type Parser a = P (Str Char String LineColPos) a

parse p s = UU.parse ( (,) <$> p <*> pEnd) (createStr (LineColPos 0 0 0) s)

main :: IO ()
main = do 
    mapM_ (\(desc, p) -> putStrLn ("\n=== " ++ desc ++ " ===") >> run pProgram p) tests
    return ()

run :: Show t =>  Parser t -> String -> IO ()
run p inp = do  let (a, errors) =  parse p inp
                putStrLn ("--  Result: \n" ++ show a)
                if null errors then  return ()
                               else  do putStr ("--  Correcting steps: \n")
                                        show_errors errors
                putStrLn "-- "
             where show_errors :: (Show a) => [a] -> IO ()
                   show_errors = sequence_ . (map (putStrLn . show))

ВАЖНЫЙ

pOperator    = applyAll <$> pElement <*> pMany (flip <$> (Multi <$ pWSpaces1) <*> pElement)

эквивалентно:

foldr pChainl pElement (Multi <$ pWSpaces1)

в соответствии с: синтаксический анализ Combinator: краткое руководство

И он используется для определения предшествующего оператора.

Answer 1

Определение pMany гласит:

pMany :: IsParser p => p a -> p [a]
pMany p = pList p

и это предлагает решение. Когда мы видим пространство, мы не должны сразу же делать выбор, чтобы продолжить с дополнительными x-es, поэтому мы определяем:

pMany :: IsParser p => p a -> p [a]
pMany_ng p = pList_ng p

Конечно, вы также можете немедленно вызвать pList_ng. Еще лучше было бы написать:

pParens (pChainr_ng (pMulti <$ pWSpaces1) px) -- 

Я не проверял это, так как не уверен, должен ли быть между x-es хотя бы один пробел и т. Д.

Doaitse