函数式编程：理解解析器组合器

Question

我正在尝试使用解析器组合器解决问题。我尝试了以下方法：

注意：下面的代码使用了combinator library

styleParserItalic : Bool -> Parser ( List (List Char , Style))
styleParserItalic bolded =
let
style = if bolded then Italic else Unstyled
 in
 (end `andThen` always (  succeed ( [] )))
 <|> (string "(!ITALIC!)" `andThen`  \_ -> styleParserItalic ( not bolded )   ) 
 <|> ( anyChar `andThen` \c -> styleParserItalic bolded `andThen` \cs -> succeed ((c :: [],style) :: cs) )

我很难理解这个解析器是如何运行的，因为 styleParserItalic 解析器在解析器成功之前被调用。

有人能解释一下给定字符串时解析器是如何工作的吗？

如果有人对解析器的用途和完整代码感兴趣，是我之前的问题。

这是我目前的理解

解析器将首先检查它是否是一行的结尾，如果不是，它将尝试解析字符串 (!ITALIC!) 如果是，那么它将使用参数 True 或 false (如果为假，则将其变为真..)

如果解析器没有找到字符串 (!ITALIC!)，它将尝试解析任何字符，然后再次调用解析器。

让我感到困惑的是，只要解析器成功解析任何字符，解析器就会继续调用自身！

编辑：* 注意以下不是问题的一部分，如果有人感兴趣，只是为了分享代码

感谢所有回复，我已更新解析器以解析粗斜体下划线...，按照下面的屏幕截图

type Style = Bold| Unstyled | Italic | Coded | Lined | Titled | Marked     | Underline

styleParser : Bool ->Bool ->Bool ->Bool-> Bool-> Bool->Bool
                                -> Parser ( List (List Char ,     (Style,Style,Style,Style,Style,Style,Style)))
                                --(bold,italic ,code,line ,Titled,mark)
styleParser bolded italiced coded lined titled marked  underlined=
  let
    style = (
     if bolded     then Bold      else Unstyled
    ,if italiced   then Italic    else Unstyled
    ,if coded      then Coded     else Unstyled
    ,if lined      then Lined     else Unstyled
    ,if titled     then Titled    else Unstyled
    ,if marked     then Marked    else Unstyled
    ,if underlined then Underline else Unstyled
    )
  in
    (end `andThen` always ( succeed ( [] )))
    <|> (string "//"  `andThen` \_ -> styleParser  bolded      italiced         coded       lined       titled       marked        (not underlined))
    <|> (string "**"  `andThen` \_ -> styleParser (not bolded) italiced        coded       lined       titled       marked        underlined)
    <|> (string "*"   `andThen` \_ -> styleParser bolded       (not italiced)  coded       lined       titled       marked        underlined)
    <|> (string "`"   `andThen` \_ -> styleParser bolded       italiced        (not coded) lined       titled       marked        underlined)
    <|> (string "/br" `andThen` \_ -> styleParser bolded       italiced        coded       (not lined) titled       marked        underlined)
    <|> (string "/*"  `andThen` \_ -> styleParser bolded       italiced        coded       lined       (not titled) marked        underlined)
    <|> (string "{-"  `andThen` \_ -> styleParser bolded       italiced        coded       lined       titled       (not marked)  underlined)
    <|> ( anyChar     `andThen` \c -> styleParser bolded       italiced         coded       lined       titled       marked        underlined  `andThen`    \cs -> succeed ((c :: [],style) :: cs) )


foldStyleHtml : List ( List Char , (    Style,Style,Style,Style,Style,Style,Style) ) -> List (Html Msg)
foldStyleHtml lst =
  List.map styleToHtml lst


styleToHtml : ( List Char, (Style ,Style,Style,Style,Style,Style,Style)) -> Html Msg
styleToHtml (a,b) =
  case b of
    (Bold,Italic,_,_,_,_,Unstyled)       -> strong [] [em [][ text   (String.fromList a)]]
    (Bold,Italic,_,_,_,_,Underline)      -> u[][ strong [] [em [][ text (String.fromList a)]]]
    (Bold,Unstyled,_,_,_,_,Underline)    -> u[][ strong [] [text (String.fromList a)]]
    (Unstyled,Italic,_,_,_,_,Underline)  -> u[][ em     [] [text (String.fromList a)]]
(Unstyled,Italic,_,_,_,_,_)          -> em[] [text (String.fromList a)]
(Bold,Unstyled,_,_,_,_,_)            -> strong [][ text (String.fromList a)]
 (_,_,Coded,_,_,_,_)                  -> code   [codeStyle ][text     (String.fromList a)]
(_,_,_,Lined,_,_,_)                  -> br [][text " "]
  --  (_,_,_,_,Titled,_,_)                 -> div [][text (String.fromList a)]
    (_,_,_,_,_,Marked,_)                 -> mark [][text (String.fromList a)]
    (_,_,_,_,_,_,Underline)              -> u [][text (String.fromList a)]
   (_,_,_,_,_,_,_)                      -> text  (String.fromList a)

htmlParser : Parser  (List (Html Msg))
htmlParser =
 styleParser False False False False False False False `andThen` (succeed << foldStyleHtml )

runParser : Parser (List (Html Msg)) -> String -> Html Msg
runParser parser str                                    =
  case parse parser str of
    (Ok htmls,_)-> div [] htmls
    (Err err, _) -> div [ style [("color", "red")] ] [ text <| toString <| err]

Answer 1

解析器组合器（通常）在成功时消耗输入。在这个库中，如果 string "(!ITALIC!)" 失败，它不会消耗任何输入。由于使用了 <|> 组合器，因此它会尝试使用以 anyChar.

开头的代码的下一部分

当 anyChar 成功时，它会消耗该单个字符并在 andThen 之后的 c 中捕获它。然后，当对 styleParserItalic bolded 进行递归调用时，剩余的字符串（除了 anyChar 捕获的字符以外的所有内容）都是 "crawled" 。第二个 andThen 将递归组合器的输出捕获到 cs 并将捕获的字符添加到递归调用的其余字符列表中。

我认为要记住的重要部分是组合器在成功时消耗输入，并且（通常）在失败时不消耗输入。

Answer 2

首先进行一些简化...

(1) 签名中内部List的每个元素：

styleParserItalic : Bool -> Parser ( List (List Char , Style))
                                           ^^^^^^^^^

只是一个字符。通过从最后一行删除 :: []，

 <|> ... `andThen` \cs -> succeed ((c ,style) :: cs) )
                                    ^^^
                                      removed `:: []`

你可以让它有这个签名。

(2) 请注意，bolded 参数仅影响样式 - 它对控制流没有影响。它确实应该被称为 italic，因为如果参数为 True，输出中出现的样式为 Italic，否则为 Unstyled。

另请注意，一旦此参数设置为True，它将在所有后续递归调用。

所以现在算法是：

如果在行尾，return空列表。
如果在 (!ITALIC!)，在解析的其余部分使用 Italic 作为样式。
否则，解析一个字符，解析该行的剩余部分并连接结果。

近似的 Python 算法类似于：

def parseLine(style, line):
  result = []
  while line:
    if line.startsWith('(!ITALIC!)'):
      line = line[8:]
      style = Italic
      # loop around
    else:
      result.append( (line[0], style) )
      line = line[1:]
  return result

函数式编程：理解解析器组合器

functional programming : understand parser combinator

elm