algorithm - 在 C# 中解析脚本循环

Question

我正在编写一个应用程序，它将使用自定义语言(略微基于 C 语法和 Allman style 格式)解析脚本，并且正在寻找更好(阅读:更快)的方式将脚本代码块解析为字符串数组，而不是我目前正在执行的方式(当前方法可以，但它更多的是为了调试而不是其他任何方式)。

脚本内容当前从文件中读取到字符串数组中并传递给方法。

这是一个脚本 block 模板:

loop [/* some conditional */ ]
{
  /* a whole bunch of commands that are to be read into
   * a List<string>, then converted to a string[] and
   * passed to the next step for execution */

   /* some command that has a bracket delimited set of
    * properties or attributes */
   {
     /* some more commands to be acted on */
   }
}

基本上，花括号 block 可以嵌套(就像在任何其他基于 C 的语言中一样)，我正在寻找找到像这样的单个 block 的最佳方法。

大括号分隔的 block 将始终格式化为这样 - 括号的内容将从左括号后的行开始，并在最终属性后的行上跟一个括号/command/comment/whatever.

一个例子可能是:

loop [ someVar <= 10 ]
{
  informUser "Get ready to do something"
  readValue
  {
    valueToLookFor = 0x54
    timeout = 10 /* in seconds */
  }
}

这会告诉应用程序在 someVar 小于 10 时循环(对于吮吸鸡蛋的评论感到抱歉)。每一轮，我们都会向用户传递一条消息，并从某处查找特定值(超时为 10 秒)。

这是我目前的做法(注意:调用此方法的方法将包含当前脚本的整个字符串 [] 传递到其中，并带有要读取的索引):

private string[] findEntireBlock(string[] scriptContents, int indexToReadFrom,
                                out int newIndex)
{
    newIndex = 0;
    int openBraceCount = 0;     // for '{' char count
    int closeBraceCount = 0;    // for '}' char count
    int openSquareCount = 0;    // for '[' char count
    int closeSquareCount = 0;   // for ']' char count

    List<string> fullblock = new List<string>();

    for (int i = indexToReadFrom; i < scriptContents.Length; i++)
    {
        if (scriptContents[i].Contains('}'))
        {
            if (scriptContents[i].Contains("[") && fullblock.Count > 0)
            {
                //throw new exception, as we shouldn't expect to
                //to find a line which starts with [ when we've already
            }
            else
            {
                if (scriptContents[i].Contains('{')) openBraceCount++;
                if (scriptContents[i].Contains('}')) closeBraceCount++;
                if (scriptContents[i].Contains('[')) openSquareCount++;
                if (scriptContents[i].Contains(']')) closeBraceCount++;
                newIndex = i;
                fullblock.Add(scriptContents[i]);
                break;
            }
        }
        else
        {
            if (scriptContents[i].Contains("[") && fullblock.Count > 0)
            {
                //throw new exception, as we shouldn't expect to
                //to find a line which starts with [ when we've already
            }
            else
            {
                if (scriptContents[i].Contains('{')) openBraceCount++;
                if (scriptContents[i].Contains('}')) closeBraceCount++;
                if (scriptContents[i].Contains('[')) openSquareCount++;
                if (scriptContents[i].Contains(']')) closeBraceCount++;
                fullblock.Add(scriptContents[i]);
            }
        }
    }
    if (openBraceCount == closeBraceCount &&
        openSquareCount == closeSquareCount)
          return fullblock.ToArray();
    else
        //throw new exception, the number of open brackets doesn't match
        //the number of close brackets
}

我同意这可能是一种稍微迟钝和缓慢的方法，这就是为什么我要就如何重新实现它以提高速度和清晰度(如果可以达到平衡，那就是)寻求任何想法。

我希望远离 RegEx，因为我不能用它来维护括号计数，而且我不确定您是否可以编写一个 RegEx 语句(这是正确的术语吗？)递归地。我正在考虑从内到外的工作，但我相信那会很慢。

我不是找人帮我重写它，但我可以使用的关于算法或技术/库的一般想法会改进我的方法。

作为附带问题，编译器如何处理源代码中的多个嵌套括号？

Answer 1

Let's Build a Compiler由 Jack Crenshaw 撰写，是关于构建基本编译器的精彩且易于阅读的介绍。所讨论的技术应该有助于您在此处尝试执行的操作。