C#中的语法生产类实现

Question

语法定义包含产品,非常简单的语法示例:

E -> E + E
E -> n

我想在c#中实现语法类,但我不确定如何存储产品,例如如何区分终端和非终端符号.我在考虑:

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

Left将始终是非终端符号(它是关于无上下文的语法)但是生产的右侧可以包含终端和非终端符号

所以现在我想到了两种实现方式:

1. 非终端符号将使用括号编写,例如:

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

2. 创建其他数据结构NonTerminal

   struct NonTerminal {String Symbol; }

和E + E将表示为数组/列表:

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

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

Answer 1

我会用

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

启用非终端对与非终端相关联的一组生产规则右侧（本身表示为终端/非终端符号列表）进行查找。（OP的问题表明，非终结E可能与两个规则相关联，但是如果我们有左手边，那么我们仅需要右手边）。

此表示仅适用于普通的BNF语法定义，在该定义中，没有用于通用语法定义惯用语的语法糖。这样的习惯用法通常包括choice，Kleene star / plus，...，当它们在定义语法时不可行时，您会得到所谓的Extended 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解析领域的真正专家，否则请指望我对他可能取得的成功感到悲观。