3

我想解析汇编程序。我有一个用于解析程序集地址的固定格式：[ 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 ...

但它很丑陋，并且不能很好地适应更多类型的元素。所以我正在寻找更清洁的解决方案。

4

4 回答 4

2

如果您对表格重新排序，您会看到一系列选择：

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

可以写的语法：

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

在 Applicative 风格中非常简单，通过将所有内容包装在构造函数中只会产生轻微的噪音：

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)

我会让你处理周围+和内部的空白[]。

于 2013-08-07T22:39:26.277 回答
1

像这样的东西：

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
于 2013-08-06T19:04:49.190 回答
1

我一直在寻找类似的东西并 Control.Applicative.Permutation从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)

请注意，您实际上想要可选的排列解析器，该解析器需要至少存在一个可选元素，这使得您想要的解析器组合器非常具体。

于 2017-12-02T00:25:07.440 回答
0

您可以使用Monoidsand获得更优雅的解决方案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'

为选择 Monoid ( Sum a, First a, Last a) r o l，我们改变行为：

Sum相加，First选第一个，Last选最后一个

   ... where
      a `mappendA` a' = getFirst $ First a `mappend` First a'
于 2013-08-07T18:00:42.467 回答