7

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

E -> E + E
E -> n

我想在 c# 中实现语法类，但我不确定如何存储产品，例如如何区分终端和非终端符号。我在想：

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

左边永远是非终结符号（它是关于上下文无关语法）但生产的右边可以包含终结符号和非终结符号

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

  1. 非终结符号将使用括号写入，例如：

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

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

    struct NonTerminal { 字符串符号；}

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

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

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

4

3 回答 3

5

我会用

 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 解析领域的真正专家。

于 2010-10-24T09:43:45.863 回答
2

这是我存储产品的想法：

Dictionary<NonTerminalSymbol, List<Symbol>>

在哪里

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

所以在你的例子中，字典将有一个键（ "E" ）和对应列表中的两个值（ "[E]+[E]" 和 "n" ）。

于 2010-10-21T11:55:35.910 回答
0

也许将扩展方法用于第二种方法会有所帮助：

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

所以看起来像这样

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

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

于 2010-10-23T20:51:07.437 回答