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

Question

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

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

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

我还没有为各种语言完全构建语法，到目前为止只是对一些基本语法的简单测试，但是我运行在尝试实现 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" }
  ]
},

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

        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 的值将为真，因为解析器将递归到 MaxLevel，我在那个时候将其关闭，否则它将继续运行直到出现 WhosebugException。

当 JSON 配置中较早的块（如 rhsBlockComma 调用较晚的块 rhs 时，问题就开始了。

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

Check 然后会调用 CheckSequence: https://github.com/JohnnyErnest/LexerParser/blob/main/Program.cs#L954 which will check each section of a sequence, calling CheckSequenceSection https://github.com/JohnnyErnest/LexerParser/blob/main/Program.cs#L843

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

如果输入有效，通常可以正常工作。如果不是，则跟踪变量 level，如果它超出 MaxLevel，则会发生中止。我还需要在 CheckSequence 中的 CheckSequence 之前添加一个先发制人的 return ，否则它将继续进行递归直到 WhosebugException.

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

Answer 1

这里的答案解释得更好：

维基百科上的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冲突。

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

C# writing a first parser, early stackoverflow detection

c#

parsing

lex