问：

我正在寻找一种算法，它允许我解析内联 Markdown 元素（在 or 之间如此强烈强调，在 or 之间定期强调，等等），以避免自我嵌套这些元素。**__*_

用于此的 CommonMark 算法不会阻止自嵌套，因此输入 like 将被解释为 .**some **random** text**some random text

由于嵌套或标签不会使文本更加粗体或斜体，因此我认为以这种方式解析输入没有意义，并且更愿意保留对任何其他样式没有贡献的星号，因此输出将如下所示。some **random** text

我知道我可以在代码生成阶段而不是解析阶段解决这个问题，方法是让 AST 访问者检查我们是否已经发出标签，然后根据此决定发出星号，但由于也可以使用下划线，源文本中使用的分隔符现在也必须添加到令牌中，总的来说，这感觉就像是错误的事情。文本不应该从一开始就以这种方式解析。

CommonMark 算法的问题在于，由于它使用回溯来查找匹配的开始分隔符以关闭分隔符（而不是相反，这在我发现的其他 markdown 变体解析器中似乎更常见），它会将之前已标记为强调的节点包装到新的强调节点中。

我的一个想法是搜索离结束分隔符最远的开始分隔符，而不是最接近的开始分隔符，但这意味着输入，例如将被解释为，实际上只允许在整行文本中强调一个重点。**some** random **text**some** random **text

那么问题来了：
是否已经存在可以做到这一点的算法？或者有没有办法修改 CommonMark 算法以防止这种情况发生？

作为参考，这是我在 Rust 中为 CommonMark 算法编写的实现（略有修改，不解析链接）。

算法解析 Markdown CommonMark

1赞 Krokodil 11/2/2023

乍一看，您可能希望将文本标记化并考虑空格，因为从您的最后一条评论来看，它们显然很重要。因此，您可能希望尝试将文本拆分为标记列表，然后解析这些标记（遍历它们）以查看哪些标记具有哪种类型的样式。我现在不能做这件事，但如果有人没有在我之前回答，我明天会再看一眼。但与此同时，看看你能用我的上述想法做些什么:)

答：

0赞 Krokodil 11/3/2023 #1

理念

我认为解决这个问题的正确方法是对文本进行标记化并填充标记数组。

这样，您还可以删除不允许的特殊字符。

标记可以是单词、特殊字符或强调标签（如 **）

程序功能的描述

以下代码背后的想法是：

通过将文本拆分为非单词字符来标记文本
将特殊字符替换为特殊字符代码;如果不允许，只需将其替换为“？
对于每个令牌：
- 如果是单词，则允许它（将其附加到要返回的）parsedText
- 如果是特殊字符代码，请将其替换为它所象征的特殊字符
- 如果是强调标签：
  - 检查上一个标记是否为空格 - 如果是，则此标记为开始标记
    - 如果是开场标签
      - 如果其他标签尚未打开，请打开它（通过输入“”）
      - 如果它们已经打开，那么不要打开它
    - 关闭标签的逻辑也类似
然后，对于每个强调标签，如果打开的标签数量与关闭的标签数量不同，请关闭或打开必要的新标签，以使关闭和打开的标签数量相等

示例实现

下面是一个 JavaScript 实现：

function tokenise(str, specCharsDict) {
    const matches = str.matchAll(/[^\w\*\_]/g);
    for(const [match] of matches) {
        str = str.replace(match, specCharsDict[match] || "&qmk#");
    }
    const tokenArr = str.split(/(\*{1,2})|(\_{1,2})|(\&\w{3}\#)/).filter(Boolean);
    return tokenArr;
}


function parseMarkdown(str) {
    const specCharsDict = {
        " ": "&spc#",
        "!": "&xcl#",
        "?": "&qmk#",
        ".": "&prd#",
        ",": "&cma#",
        "#": "&hsh#",
        "&": "&aps#"
        // todo - add more allowed characters here, like ":", ";", etc
        // unallowed characters are replaced by a "?"
    };
    const emphasisTags = {
        open: {
            single: "<em>",
            double: "<strong>"
        },
        close: {
            single: "</em>",
            double: "</strong>"
        }
    };

    const tokenArr = tokenise(str, specCharsDict);
    let parsedText = [];

    const tokenDataArr = [];
    let emphasisCounter = {
        single: 0,
        double: 0
    };

    for (let i = 0; i < tokenArr.length; i++) {
        const tokenData = {
            token: tokenArr[i],
            type: "word",
            emphasisType: null, // single (*) or double (**)
            emphasisTagType: null,
            index: i
        };
        tokenDataArr.push(tokenData);

        if(tokenData.token.includes("*") || tokenData.token.includes("_")) {
            tokenData.type = "emphasis";
            tokenData.emphasisType = tokenData.token.length === 1 ? "single" : "double";
        } else if(tokenData.token.includes("&")) {
            tokenData.type = "spec char";
        }

        switch(tokenData.type) {
            case "word": 
                parsedText.push(tokenData.token);
                break;
            case "spec char":
                const specCharIndex = Object.values(specCharsDict).indexOf(tokenData.token);
                parsedText.push(Object.keys(specCharsDict)[specCharIndex]);
                break;
            case "emphasis":
                const prevTokenData = tokenDataArr[i-1];
                const prevWasSpace = prevTokenData === undefined || prevTokenData.token === specCharsDict[" "];
                if(prevWasSpace) {
                    tokenData.emphasisTagType = "opening";
                    if(emphasisCounter[tokenData.emphasisType] === 0) {
                        emphasisCounter[tokenData.emphasisType]++;
                        parsedText.push(emphasisTags.open[tokenData.emphasisType]);
                    } else {
                        parsedText.push(tokenData.token);
                        emphasisCounter[tokenData.emphasisType]++;
                    }   
                } else {
                    tokenData.emphasisTagType = "closing";
                    if(emphasisCounter[tokenData.emphasisType] === 1) {
                        emphasisCounter[tokenData.emphasisType] = 0;
                        parsedText.push(emphasisTags.close[tokenData.emphasisType]);
                    } else {
                        parsedText.push(tokenData.token);
                        emphasisCounter[tokenData.emphasisType]--;
                    }
                }
                
                break;

        }
    }

    // todo parse emphasisCounter
    // if either double or single is not 0, then there is an unclosed or unopened tag
    // if < 0, then there's an unopened tag
    // if > 0, then there's an unclosed tag
    let firstOpenIndex = Infinity;
    let numOpened = 0;
    for(const emType of ["single", "double"]) {
        if(emphasisCounter[emType] < 0) {
            for (const tokenData of tokenDataArr) {
                if(tokenData.emphasisTagType !== "opening") {
                    continue;
                }
                parsedText[tokenData.index] = emphasisTags.open[tokenData.emphasisType];
                if(tokenData.index < firstOpenIndex) {
                    firstOpenIndex = tokenData.index;
                }
                emphasisCounter[emType]++;
                numOpened++;
                if(emphasisCounter[emType] === 0) {
                    break;
                }
            }
        }
        if(emphasisCounter[emType] > 0) {
            for (let i = tokenDataArr.length-1; i >=0 ; i--) {
                const tokenData = tokenDataArr[i];
                if(tokenData.emphasisTagType !== "closing") {
                    continue;
                }
                parsedText[tokenData.index] = emphasisTags.close[tokenData.emphasisType];
                emphasisCounter[emType]--;
                if(emphasisCounter[emType] === 0) {
                    break;
                }
            }
        }
        if(firstOpenIndex !== Infinity) {
            for (let i = firstOpenIndex; i < tokenDataArr.length; i++) {
                const tokenData = tokenDataArr[i];
                if(tokenData.emphasisTagType !== "closing") {
                    continue;
                }
                parsedText[tokenData.index] = emphasisTags.close[tokenData.emphasisType];
                numOpened--;
                if(numOpened === 0) {
                    break;
                }
            }
        }
    }

    return parsedText.join("");
}




const testStrings = [
    "Weak** weak** **strong**", 
    "Weak** **strong**", 
    "**Strong** and **strong**", 
    "**Strong **not nested** endstrong**",
    "**strong** *italic* __strong, meanwhile *italic*__"
];

testStrings.forEach(testStr => {
    const parsed = parseMarkdown(testStr);
    console.log(parsed);
    document.write(parsed + "<br>");
});

如有任何问题或误解的要求，请告诉我。

上一个：如何在具有多个嵌套模型的 C# 中解析 Json

下一个：langchain.schema.output_parser。OutputParserException：获取无效的 JSON 对象。错误：额外数据：第 7 行第 1 列（char 1406）

用于解析内联 Markdown 元素的算法，避免 sef 嵌套

Algorithm for parsing inline markdown elements, avoiding sef-nesting

评论

理念

程序功能的描述

示例实现