Megaparsec：無法解析算術字符串

我正在使用Megaparsec處理一個小的解析器，並嘗試解析算術。Megaparsec：無法解析算術字符串

-- Arithmetic expressions 
data Aexp = N Num 
      | V Var 
      | Mult Aexp Aexp 
      | Add Aexp Aexp 
      | Sub Aexp Aexp 
      deriving (Show, Eq, Read) 


arithParser :: Parser Aexp 
arithParser = V <$> strParser 
      <|> N <$> numParser 
      <|> Mult <$> arithParser <* tok "*" <*> arithParser 
--boolParser :: Parser Bexp 


strParser :: Parser Var 
strParser = tok "\"" *> some (noneOf ("\n\r\"=[]{},:")) <* tok "\"" 

numParser :: Parser Num 
numParser = (some (oneOf ['0' .. '9']) >>= return . read) <* whitespace

如果我運行命令Parse arithParser "5*5" "5*5"它只是返回Right (N 5)，它應該返回Mult(N 5) (N 5)。因爲arithParser中的優先級。但如果我改變順序，那麼它似乎進入了一個無限循環和崩潰。

不知道我在做什麼錯在這裏，任何幫助將不勝感激。

來源

2017-04-08 Bort

我不是Parsec和朋友的專家，但是當語法是遞歸的時候，很多解析技巧會遇到問題（無限循環），這是您的問題。本文似乎表明它可能是Parser組合器的一個問題：http://stuckinaninfiniteloop.blogspot.com/2011/10/left-recursion-in-parsec.html?m=1 – chrisleague

在它嘗試正確的之前，Parsec嘗試使用<|>的左側替代方法。如果左邊的選擇成功，那麼它不會打擾正確的選擇。因此，在這種情況下，飼餵時輸入5*5，秒差距的過程是這樣的：

嘗試V <$> strParser。 strParser以tok "\""開頭，但輸入字符串不以'"'開頭，因此strParser失敗。
嘗試N <$> numParser。 numParser成功解析數字5，所以Parsec只返回N 5。
完成！不需要嘗試第三種選擇。

所以我們可以嘗試通過移動Mult選項到頂部修補此解析器起來，裹在try，以便它可以原路返回，並嘗試numParser或strParser如果輸入原來不被乘法。

arithParser :: Parser Aexp 
arithParser = try (Mult <$> arithParser <* tok "*" <*> arithParser) 
      <|> N <$> numParser 
      <|> V <$> strParser

此解析器有另一個更微妙的問題。我們來看看如上所述的步驟。

嘗試try (Mult <$> arithParser <* tok "*" <*> arithParser)。該解析器以arithParser開頭，因此遞歸調用arithParser。
嘗試try (Mult <$> arithParser <* tok "*" <*> arithParser)。該解析器以arithParser開頭，因此遞歸調用arithParser。
嘗試try (Mult <$> arithParser <* tok "*" <*> arithParser)。該解析器以arithParser開頭，因此遞歸調用arithParser。
...

這是一個無限循環。 Parsec無法處理左遞歸語法。您必須設計解析器，以便在遞歸調用之前至少使用一個令牌。這樣做的一個常用的方法是「拉平」你的語法：

expr, term :: Parser AExp 
expr = do 
    n <- term 
    rest <- optional $ tok "*" *> expr 
    return $ maybe n (Mult n) rest 
term = N <$> numParser 
    <|> V <$> strParser 
    <|> parenthesised expr 

parenthesised = between (char '(') (char ')')

這裏，我已經分裂解析器爲一體，它解析任意expr - 一個term任選接着乘號和被乘數expr - 以及解析單個數字，字符串和括號表達式的單個文件。expr的遞歸調用現在可以 - expr內部的調用僅在您解析了term（總是消耗輸入）並且term內部的調諧發生在您解析了左括號後才發生。

請注意，expr有一個類似列表的結構：它解析一個單一的東西可能後面有很多事情。一般而言，您應該考慮使用線性輸入流的輸入令牌的解析器，因此列表形解析器往往比樹形解析器更有效也就不足爲奇了。

Text.Megaparsec.Expr模塊包含封裝該模式和解析具有任意優先級和固定規則的表達式的函數。

expr = makeExprParser term [[InfixR $ tok "*" $> Mult]]

來源

2017-04-08 19:25:27

這非常有幫助，感謝您採取這個時間！ – Bort

的類型是騙你：當你定義一個遞歸解析器p，你沒有真正允許使用p本身，無論你想要的！您需要首先輸入部分輸入內容，以確保您正在取得進展。否則，Haskell確實會很樂意進入一個無限循環。

這個問題一般通過定義表達式的不同「層」來解決，只允許「簡單」或括號 - 在左遞歸位置中包含「更復雜」的一個（因爲匹配一個開括號會迫使你使通過部分輸入字符串的方式）。

E.g.爲您的表達式語法就會變成（從最簡單到最複雜的）：

<Literal> ::= [0-9]+ 
<Var>  ::= [a-zA-Z]+ 
<Base> ::= '(' <Expr> ')' | <Var> | <Literal> 
<Factor> ::= <Base> | <Base> '*' <Factor> 
<Expr> ::= <Factor> | <Factor> '+' <Expr> | <Factor> '-' <Expr>

這是一個總的語言眼前一亮：因爲類型必須是當它涉及到終端完全誠實的，就根本不可能編寫這些表現不好的左遞歸分析器。 typechecker告訴你，你必須找到另一種方式來識別你的語言條款。

例如在不動點組合子fix我在總解析器組合庫的使用不具有類型(a -> a) -> a而是（忽略搞笑括號內）(□ a → a) → a這正是阻止你使用遞歸調用你已經取得了一些進展之前。你仍然可以寫一個parser for Expr，但類型檢測者在這裏警告你當你非法移動。

來源

2017-07-04 23:28:21 gallais

Megaparsec：無法解析算術字符串

回答

相關問題