帶分隔符的Parsec置換解析器

Question

我想解析程序集。我有一個解析彙編地址的固定格式：[ register + offset + label ]我實現了寄存器，偏移量和標籤的解析器。現在我想創建一個解析器來解析整個地址。

的組合我想接受：

[register] 
[offset] 
[label] 
[register + offset] 
[register + label] 
[offset + label] 
[register + offset + label] 

而我不想接受：

[] 
[register offset] 
[register + ] 
... 

當然簡單的解決方案是這樣的：

choice $ try (parseRegister >>= \r -> Address (Just r) Nothing Nothing) 
     <|> try ... 

但它是醜陋的，並不適合更多類型的元素。所以我正在尋找更清潔的解決方案。

Answer 1

如果重新排序表，你看到它的一系列的選擇：

[register + offset + label] 
[register + offset  ] 
[register   + label] 
[register     ] 
[   offset + label] 
[   offset  ] 
[     label] 

的文法可能這樣寫：

address  = '[' (register ('+' offset-label)? | offset-label) ']' 
offset-label = offset ('+' label)? | label 

其中在應用型的風格是非常簡單的，做只有稍微嘈雜的包裝一切在構造：

parseAddress :: Parser Address 
parseAddress = do 
    (register, (offset, label)) <- between (char '[') (char ']') parseRegisterOffsetLabel 
    return $ Address register offset label 

parseRegisterOffsetLabel :: Parser (Maybe Register, (Maybe Offset, Maybe Label)) 
parseRegisterOffsetLabel = choice 
    [ (,) 
    <$> (Just <$> parseRegister) 
    <*> option (Nothing, Nothing) (char '+' *> parseOffsetLabel) 
    , (,) Nothing <$> parseOffsetLabel 
    ] 

parseOffsetLabel :: Parser (Maybe Offset, Maybe Label) 
parseOffsetLabel = choice 
    [ (,) 
    <$> (Just <$> parseOffset) 
    <*> option Nothing (char '+' *> (Just <$> parseLabel)) 
    , (,) Nothing . Just <$> parseLabel 
    ] 

如果再加上一對夫婦的實用功能：

plus :: Parser a -> Parser a 
plus x = char '+' *> x 

just :: Parser a -> Parser (Maybe a) 
just = fmap Just 

我們可以清理這些實現了一下：

parseRegisterOffsetLabel = choice 
    [ (,) 
    <$> just parseRegister 
    <*> option (Nothing, Nothing) (plus parseOffsetLabel) 
    , (,) Nothing <$> parseOffsetLabel 
    ] 

parseOffsetLabel = choice 
    [ (,) 
    <$> just parseOffset 
    <*> option Nothing (plus (just parseLabel)) 
    , (,) Nothing <$> just parseLabel 
    ] 

然後分解出的重複，給我們一個像樣的最終解決方案：

parseChain begin def rest = choice 
    [ (,) <$> just begin <*> option def (plus rest) 
    , (,) Nothing <$> rest 
    ] 

parseRegisterOffsetLabel = parseChain 
    parseRegister (Nothing, Nothing) parseOffsetLabel 

parseOffsetLabel = parseChain 
    parseOffset Nothing (just parseLabel) 

我會讓你照顧+和[]的空白。

Answer 2

類似的東西：

parsePlus = many1 (char ' ') >> char '+' >> many1 (char ' ') 

parseRegisterModified = parsePlus >> parseOffsetLabel 

parseOffsetModified = parsePlus >> parseLabel 

parseRegister' = do 
    Address r _ _ <- parseRegister 
    optionMaybe parseRegisterModified >>= 
    return $ maybe 
      (Address r Nothing Nothing) 
      (\Address _ o l -> Address r o l) 

parseOffset' = do 
    Address _ o _ <- parseOffset 
    optionMaybe parseOffsetModified >>= 
    return $ maybe 
      (Address Nothing o Nothing) 
      (\Address _ _ l -> Address Nothing o l) 

parseOffsetLabel = try parseOffset' <|> parseLabel 

parseAddress = 
    try parseRegister' 
    <|> parseOffset' 
    <|> parseLabel 

Answer 3

你可以使用Monoids和sepBy1有更好的解決方案。

但允許寫[register + register]（在我們的例子中添加他們倆）

parsePlus = many1 (char ' ') >> char '+' >> many1 (char ' ') 

parseAddress1 = 
    try parseRegister 
    <|> parseOffset 
    <|> parseLabel 

parseAddress = sepBy1 parsePlus parseAddress1 >>= return . mconcat 

instance Monoid Address where 
    mempty = Address Nothing Nothing Nothing 
    Address r o l `mappend` Address r' o' l' = 
      Address (r `mappendA` r') (o `mappendA` o') (l `mappendA` l') 
    where 
     a `mappendA` a' = fmap getSum $ fmap Sum a `mappend` fmap Sum a' 

選擇含半幺羣（Sum a，First a，Last a）爲rol，我們改變行爲：

Sum增加First選擇第一個，Last選擇最後一個

... where 
     a `mappendA` a' = getFirst $ First a `mappend` First a' 

Answer 4

我一直在尋找類似的東西，發現 Control.Applicative.Permutation from action-permutations。雖然我的情況可能會從低級平臺獨立擴展。

在你的情況可能看起來像

operand = do 
    (r, o, l) <- runPermsSep (char '+') $ (,,) 
     <$> maybeAtom register 
     <*> maybeAtom offset 
     <*> maybeAtom label 
    -- backtrack on inappropriate combination 
    when (null $ catMaybes [r, o, l]) . fail $ "operand expected" 
    return (r, o, l) 

需要注意的是你真正想要並需要至少一個可選元素存在，這使得你想要的解析器Combinator的非常具體的可選排列解析器。