C#中的语法产生类实现

Question

语法按照定义包含产生式，以下是一个非常简单的语法示例：

E -> E + E
E -> n

我希望在C#中实现一个语法类（Grammar class），但是我不确定如何存储产生式，例如如何区分终结符和非终结符。 我在考虑：

struct Production
{
   String Left;       // for example E
   String Right;      // for example +
}

左侧始终为非终端符号（这是关于上下文无关文法的），但产生式的右侧可以包含终端和非终端符号。

因此，现在我考虑两种实现方式：

1. 使用括号编写非终端符号，例如：

   E+E将被表示为字符串“[E]+[E]”

2. 创建额外的数据结构NonTerminal

   struct NonTerminal { String Symbol; }

并且E+E将表示为数组/列表：

[new NonTerminal("E"), "+", new NonTerminal("E")]

但是认为还有更好的想法，听到一些回应会很有帮助。

- dfens

---

你看过http://www.antlr.org/吗？这是一个语言设计工具，包括一个非常好用的IDE。 - Pieter van Ginkel

有两种快速存储语法规则的方法。使用哪一种取决于用例：您是想生成字符串还是解析它们？ - Fred Foo

如果您的目标是解析字符串，且您的语法是静态的，则不需要“语法类”。您需要的是从语法中合成的解析器（关于ANTLR的先前评论很好）。如果您的语法随意更改，但不解析许多字符串，则任何语法表示都可以，并且您可以通过语法规则编写递归下降和/或Early解析器。如果您需要动态语法和高解析率，则需要一个解析器生成器，您将回到类似ANTLR的东西。 - Ira Baxter

@dfens：你为什么给这个标签加上了“自然语言”？BNF几乎只用于描述人工（计算机）语言。如果你想解析自然语言，你需要更复杂的工具。 - Ira Baxter

@Ira Baxter：我的目标是实现解析器，而不是使用解析器。它被标记为自然语言，因为它必须解析所有上下文无关文法，特别是自然语言。 - dfens

首先，有太多的词法解析器和其他东西需要处理语法，而且如果你想要编写自己的解析器，为什么要选择C#？你可以轻松地使用F#来完成。 - Saeed Amiri

Answer 1

我会使用

 Dictionary<NonTerminalSymbol,Set<List<Symbol>>> 

实现通过非终结符查找与其相关联的产生式右侧（它们本身表示为终结符/非终结符符号列表）的集合。 （OP的问题显示非终结符E可能与两个规则相关联，但我们只需要左侧，就可以得到右侧）。

这种表示仅适用于纯BNF语法定义，在其中没有常见语法定义习惯用法的语法糖。这些习惯用法通常包括选择，Kleene star/plus等，当它们在定义语法时可用时，你会得到所谓的扩展BNF或EBNF。如果我们仅允许使用由|表示的选择来编写EBNF，则OP作为示例暗示的表达式语法的扁平形式是：

         E = S ;
         S = P | S + P | S - P ; 
         P = T | P * T | P / T ;
         T = T ** M | ( E ) | Number | ID ;

我的第一个建议可以代表这个意思，因为交替只用于显示不同的规则右侧。然而，它不能代表这个：

         E = S ;
         S = P A* ;
         A = + P | - P ;
         P = T M+ ; -- to be different
         M = * T | / T ;
         T = T ** M | ( E ) | Number | ID | ID ( E  ( # | C) * ) ; -- function call with skipped parameters
         C = , E ;

这个额外的符号引入的关键问题是能否在子语法定义中重复组合WBNF运算符，这正是EBNF的全部意义。

要表示EBNF，必须将产生式存储为代表EBNF表达式结构的树（实际上，这本质上与表示任何表达式语法相同）。

要表示EBNF（表达式）树，需要定义EBNF的树结构。您需要以下树节点：

- 符号（终止或非终止） - 交替（具有备选项列表） - Kleene * - Kleene + - “可选”？ - 其他您认为EBNF具有的运算符（例如，逗号分隔的列表，一种表示一个由选择的“逗号”字符分隔的语法元素列表或以选择的“分号”字符结束的方法等）

最简单的方法是首先为EBNF本身编写EBNF语法。

EBNF = RULE+ ;
RULE = LHS "=" TERM* ";" ;
TERM = STRING | SYMBOL | TERM "*" 
       | TERM "+" | ';' STRING TERM | "," TERM STRING 
      "(" TERM* ")" ;

请注意，我已经在EBNF中添加了逗号和分号列表（扩展的，记得吗？）。

现在我们可以简单地检查EBNF以决定需要什么。

你现在需要的是一组记录（对于C#程序员来说是类），用于表示这些规则中的每一个。

因此：

- 一个包含一组规则的EBNF类 - 一个具有LHS符号和列表的RULE类 - 一个TERM的抽象基类，具有几个具体变体，每个变体对应TERM的一个选择（通常通过继承和实例化检查在OO语言中实现所谓的“判别联合”）。

请注意，一些具体变体可以引用表示中的其他类类型，这就是如何获得树形结构。例如：

   KleeneStar inherits_from TERM {
        T: TERM:
   }

留下编码其余部分的详细信息。

这给OP带来了一个未明确说明的问题：如何使用这个语法表示来驱动字符串的解析？

简单的答案是获得一个解析器生成器，这意味着你需要弄清楚它使用的EBNF。 （在这种情况下，将您的EBNF存储为文本并将其交给该解析器生成器可能更容易，这使得整个讨论有点无意义）。

如果你不能获得一个（？），或者想要构建自己的，那么现在你有了你需要爬过去构建它的表示。 另一种选择是构建一个由此表示驱动的递归下降解析器来进行解析。 这种方法对于有递归经验的人来说很简单，但太大了，不能包含在本答案的边距中。

编辑10/22：OP澄清他坚持解析所有上下文无关文法，尤其是自然语言。 对于所有上下文无关文法，他将需要非常强大的解析引擎（Earley，GLR，完全回溯，...）。 对于自然语言，他将需要比这些更强大的解析器； 人们已经尝试了几十年来构建这样的解析器，只有一些人取得了成功，但绝对不是易事。 这两个要求似乎使表示语法的讨论变得毫无意义； 如果他表示一个简单的上下文无关文法，它将不能解析自然语言（由那些尝试几十年的人证明），如果他想要更强大的NL解析器，他将需要使用最前沿的类型所产生的。 除非他决定成为NL解析领域的真正专家，否则我对他的可能成功持悲观态度。

- Ira Baxter

Answer 2

这里是我关于产品存储的想法：

Dictionary<NonTerminalSymbol, List<Symbol>>

关键字

Symbol 是 NonTerminalSymbol，TerminalSymbol 和 Production 类的父（抽象？）类。

因此，在您的示例中，该字典将具有一个键（“E”），并且在相应列表中有两个值（“[E]+[E]”和“n”）。

- zgorawski

---

+1 对于对象层次结构的想法，正是我的想法。然而，这种“字典”编码只适用于生产环境，而不适用于解析。 - Fred Foo

嗯，如果您有两个具有相同非终端的规则怎么办？（例如，请参见OP的示例规则）。据我所知，字典只允许每个键存储一个项目。 - Ira Baxter

没错，Ira是对的，考虑E->E+E，E->n。在你的结构中左侧E只有一个条目。 - dfens

Answer 3

或许使用扩展方法来实现第二个方法会更有帮助：

static class StringEx
{
   public static NonTerminal NonTerminal(this string obj)
   {
       return new NonTerminal(obj);
   }
}

所以它会看起来像这样

["E".NonTerminal(), "+", "E".NotTerminal()]

这种方法的优点是修改代码会很容易。

- obenjiro