在快乐/无限循环中嵌套解析器？

Question

我正在尝试为简单的标记语言编写一个解析器，很高兴。目前，我遇到了无限循环和嵌套元素的一些问题。

我的标记语言基本上由两个元素组成，一个用于“普通”文本，一个用于粗体/强调文本。

data Markup
    = MarkupText   String
    | MarkupEmph   [Markup]

例如，像 Foo *bar* 这样的文本应该被解析为 [MarkupText "Foo ", MarkupEmph [MarkupText "bar"]]。

该示例的词法分析工作正常，但解析它会导致无限循环 - 我不明白为什么。这是我目前的方法：

-- The main parser: Parsing a list of "Markup"
Markups     :: { [Markup] }
            : Markups Markup                    { $1 ++ [$2] }
            | Markup                            { [$1]       }

-- One single markup element
Markup      :: { Markup }
            : '*' Markups1 '*'                  { MarkupEmph $2 }
            | Markup1                           { $1            }

-- The nested list inside *..*
Markups1    :: { [Markup] }
            : Markups1 Markup1                  { $1 ++ [$2] }
            | Markup1                           { [$1]       }

-- Markup which is always available:
Markup1     :: { Markup }
            : String                            { MarkupText $1 }

这种方法有什么问题？怎么解决呢？

更新：抱歉。 Lexing 没有按预期工作。无限循环位于词法分析器内部。对不起。 :)

更新 2： 根据请求，我将其用作词法分析器：

lexer :: String -> [Token]
lexer [] = []
lexer str@(c:cs)

    | c == '*'              = TokenSymbol "*"   : lexer cs
    -- ...more rules...
    | otherwise             = TokenString val   : lexer rest

  where (val, rest) = span isValidChar str
        isValidChar = (/= '*')

发生无限递归是因为我使用 lexer str 而不是 lexer cs在 '*' 的第一条规则中。没有看到它，因为我的实际代码有点复杂。 :)

Answer 1

只是一个警告，自从我处理解析器生成器以来已经有一段时间了。

看起来你需要一个 LR(1) 解析器，但我不确定 Happy 是不是。我确信一旦我写下这篇文章，就会有人能够纠正我。

如果您的解析器无法向前查看，它将永远停留在该语句上。

Markups1    :: { [Markup] }
        : Markups1 Markup1 
        | Markup1

它将查找 Markups1，而 Markups1 又会查找 Markups1。我能猜测到的最好的情况是，它不会对 Markup1 进行前瞻性检查以查看它是否是字符串。

尝试像这样重写它

Markups1    :: { [Markup] }
        : Markup1 Markups1
        | 

本质上你希望它首先找到该字符串，然后尝试查找另一个字符串，如果没有找到它需要结束该语句。