2

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

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

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在第一个规则中为'*'. 没有看到它，因为我的实际代码有点复杂。:)

4

1 回答 1

1

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

看来您需要一个 LR(1) 解析器，我不确定 Happy 是否。我很肯定，一旦我写了这篇文章，有人将能够纠正我。

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

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

它将寻找一个 Markups1，而后者又寻找一个 Markups1。我能猜到的最好的结果，它并没有对 Markup1 进行查看以查看它是否是一个字符串。

尝试像这样重写它

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

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

于 2011-01-02T18:02:43.253 回答