c# - C#中的语法生成类实现

Question

语法根据定义包含产生式，非常简单的语法示例:

E -> E + E
E -> n

我想在 c# 中实现 Grammar 类，但我不确定如何存储产生式，例如如何区分终端符号和非终端符号。
我在想:

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

Left 永远是非终结符(它是关于上下文无关语法的)
但是产生式的右侧可以包含终结符和非终结符

所以现在我在考虑两种实现方式:

非终结符将使用方括号书写，例如:

E+E 将表示为字符串 "[E]+[E]"

创建额外的数据结构 NonTerminal

非终端结构体
{
字符串符号；
}

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

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

但认为有更好的想法，听到一些回应会有所帮助

Answer 1

我会用

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

启用非终结符对与非终结符相关联的一组产生式规则右侧(它们本身表示为终结符/非终结符符号列表)的查找。 (OP 的问题表明非终结符 E 可能与两个规则相关联，但如果我们有左侧，我们只需要右侧)。

此表示仅适用于普通 BNF 语法定义，其中没有常见语法定义习语的语法糖。此类习语通常包括choice、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的树结构。
您需要树节点:

符号(终端与否)

替代(有替代列表)

克莱恩 *

克莱恩 +

“可选的” ？

其他你决定你的 EBNF 作为操作符的(例如，逗号列表，一种表示一个语法元素列表由选定的“逗号”字符分隔，或以选定的“分号”字符结尾的方式，.. .)

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

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

请注意，我已将逗号和分号列表添加到 EBNF(扩展，还记得吗？)

现在我们可以简单地检查 EBNF 来决定需要什么。
您现在需要的是一组记录(好吧，C#'er 的类)来表示这些规则中的每一个。
所以:

包含一组规则的 EBNF 类

具有 LHS 符号和 LIST 的 RULE 类

TERM 的抽象基类，具有多个具体变体，每个变体对应一个 TERM(所谓的“有区别的联合”，通常由 OO 语言中的继承和 instance_of 检查实现)。

请注意，某些具体变体可以引用表示中的其他类类型，这就是您获得树的方式。例如:

   KleeneStar inherits_from TERM {
        T: TERM:
   }

细节留给读者编码其余部分。

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

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

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

编辑 10/22:OP 澄清说他坚持解析所有上下文无关语法和“尤其是 NL”。对于所有上下文无关文法，他将需要非常强大的解析引擎(Earley、GLR、完全回溯，...)。对于自然语言，他需要比那些更强大的解析器；几十年来，人们一直在尝试构建这样的解析器，但只取得了一些成功，但绝对不容易。这两个要求中的任何一个似乎都使关于表示语法的讨论变得毫无意义。如果他确实代表了一种直接的上下文无关文法，它就不会解析自然语言(这些人尝试了几十年已经证明了这一点)，如果他想要一个更强大的 NL 解析器，他将需要简单地使用最前沿的类型产生。除非他决定成为 NL 解析领域的真正专家，否则我认为他可能成功是悲观主义者。