时间戳

首页 > 解决方案 > C#编写第一个解析器，早期stackoverflow检测

c# - C#编写第一个解析器，早期stackoverflow检测

问题描述

我刚刚开始用 C# 编写一个简单的解析器，你可以在这里找到：https ://github.com/JohnnyErnest/LexerParser/blob/main/Program.cs#L1078

主要特点是我希望能够为我想要分析的一些语法编写 JSON 配置，在运行时加载配置并通过词法分析器/解析器评估一些字符串输入，并生成一个包含每个节点信息的树对于某些语言，例如 SQL/CSS/HTML，使用诸如 yacc/bison 克隆之类的第三方工具来创建要从语法编译的代码，例如语法突出显示和从已解析文本的部分中提取变量之类的事情。

一个简单的问题是，还有哪些其他好的方法可以在 StackOverflowException 之前从格式错误的输入中尽早检测递归问题？详情如下。

我还没有为各种语言完全构建语法，到目前为止只是对一些基本语法的简单测试，但是在尝试实现 EBNF 时遇到了一个问题，例如：https ://en.wikipedia.org/wiki/Extended_Backus %E2%80%93Naur_form当必须处理如何评估语法语句的右侧时，如下所示：

rhs = identifier
     | terminal
     | "[" , rhs , "]"
     | "{" , rhs , "}"
     | "(" , rhs , ")"
     | rhs , "|" , rhs
     | rhs , "," , rhs ;

因此，在我的 JSON 配置中，它的设置如下：https ://github.com/JohnnyErnest/LexerParser/blob/main/Configuration/ParserEBNF.json#L178也用于空格。

"rhsBlock1": {
  "sequence": [
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "tokenList": "bracketOpen" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "sequenceList": "rhs" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "tokenList": "bracketClose" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    }
  ]
},
"rhsBlock2": {
  "sequence": [
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "tokenList": "braceOpen" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "sequenceList": "rhs" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "tokenList": "braceClose" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    }
  ]
},
"rhsBlock3": {
  "sequence": [
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "tokenList": "parenthesisOpen" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "sequenceList": "rhs" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "tokenList": "parenthesisClose" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    }
  ]
},
"rhsBlockPipe": {
  "sequence": [
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "sequenceList": "rhs" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "tokenList": "pipe" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "sequenceList": "rhs" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    }
  ]
},
"rhsBlockComma": {
  "sequence": [
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "sequenceList": "rhs" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "tokenList": "comma" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    },
    { "sequenceList": "rhs" },
    {
      "tokenList": "whitespaces",
      "isOptional": "true"
    }
  ]
},
"rhs": {
  "sequence": [
    { "sequenceList": "identifier,ebnfTerminal,rhsBlock1,rhsBlock2,rhsBlock3,rhsBlockPipe,rhsBlockComma" }
  ]
},

鉴于该定义，以下工作并评估为 true：

        string inputEBNF = "a=\"5\";";
        var ebnfParserResult = ebnfParser.Parse(inputEBNF, "grammar");

但是，如果您将“5”更改为文字，这是无效的 EBNF，您将不会收到错误，您将获得无限递归。

        string inputEBNF = "a=5;";
        var ebnfParserResult = ebnfParser.Parse(inputEBNF, "grammar");
        var exit = ebnfParser.CancelAllParsing;

exit 的值将是 true，因为解析器将在递归中上升到 MaxLevel，然后我将其关闭，否则它将继续运行直到 StackOverflowException。

当 JSON 配置中的早期块（如rhsBlockComma）调用稍后块rhs时，问题就开始了。

在我的代码中，您会看到Parser.Parse调用了一个名为Check的方法：https ://github.com/JohnnyErnest/LexerParser/blob/main/Program.cs#L1017

然后检查将调用CheckSequence：https://github.com/JohnnyErnest/LexerParser/blob/main/Program.cs#L954它将检查序列的每个部分，调用CheckSequenceSection https://github.com/JohnnyErnest/LexerParser/ blob/main/Program.cs#L843

CheckSequenceSection 首先查看 JSON 部分的tokenList中的每个词法分析器标记，然后查看该部分的sequenceList中的每个序列，并在每个序列上调用CheckSequence，这将执行一次递归。

通常，如果输入有效，则可以正常工作。如果不是，则跟踪变量级别，如果超出MaxLevel，则发生中止。我还需要在CheckSequence从CheckSequenceSection之前添加一个抢先返回，否则它只会继续递归直到StackOverflowException。

还有哪些其他方法可以从错误的输入中早期检测递归问题？

标签： c#parsinglex

解决方案

答案在这里解释得更好：https ://stackoverflow.com/a/20179940/5556724

Wikipedia 上的 EBNF 版本是这样写的：

rhs = identifier
     | terminal
     | "[" , rhs , "]"
     | "{" , rhs , "}"
     | "(" , rhs , ")"
     | rhs , "|" , rhs
     | rhs , "," , rhs ;

但应该这样写：

primary = identifier
        | terminal
        | "[" , rhs , "]"
        | "{" , rhs , "}"
        | "(" , rhs , ")"
        ;
factor  = primary , { "|" , primary } ;
rhs     = factor ,  { "," , factor } ;

否则会出现 FIRST/FIRST 冲突。

推荐阅读