C＃中的语法生产环境类实现-Java 学习之路

语法定义包含产品，非常简单的语法示例：

E -> E + E
E -> n

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

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

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

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

非终端符号将使用括号写入，例如：

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

创建其他数据结构NonTerminal

struct NonTerminal {String Symbol; }

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

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

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

3 回答

4
我用了
```
Dictionary<NonTerminalSymbol,Set<List<Symbol>>>
```
允许通过Nonterminal查找与非终结符相关联的一组生产环境规则右侧（它们自身表示为终端/非终端符号列表） . （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
- "Optional"？
- 你决定你的EBNF有其他作为运算符的其他人（例如，逗号列表，一种说法，其中一个语法元素列表由选定的"comma"字符分隔，或以选定的"semicolon"字符结束，......）
最简单的方法是首先为EBNF本身编写一个EBNF语法：
```
EBNF = RULE+ ;
RULE = LHS "=" TERM* ";" ;
TERM = STRING | SYMBOL | TERM "*" 
       | TERM "+" | ';' STRING TERM | "," TERM STRING 
      "(" TERM* ")" ;
```
请注意，我已经向EBNF添加了逗号和分号列表（扩展，还记得吗？）

现在我们可以简单地检查EBNF以确定需要什么 . 你现在需要的是一组记录（好的，C＃呃的类）来表示这些规则 . 所以：
- 包含一组规则的EBNF类
- 具有LHS符号和LIST的规则的类
- TERM的抽象基类，具有几个具体变体，每个替代TERM一个（所谓的"discriminated union"通常由继承实现，而instance_of检查以OO语言实现） .
请注意，一些具体的变体可以引用表示中的其他类类型，这就是获取树的方式 . 例如：
```
KleeneStar inherits_from TERM {
        T: TERM:
   }
```
详细信息留给读者编码其余部分 .

这为OP提出了一个未说明的问题：你如何使用这个grammmar表示来驱动字符串的解析？

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

如果你不能得到一个（？），或想要 Build 自己的一个，那么，现在你有了你需要爬过来构建它的代表 . 另一种方法是构建一个由此表示驱动的递归下降解析器来进行解析 . 这样做的方法太大而无法包含在这个答案的边缘，但对于那些有递归经验的人来说很简单 .

编辑10/22：OP澄清他坚持解析所有上下文无关语法和"especially NL" . 对于所有上下文无关语法，他都需要非常强大的解析引擎（Earley，GLR，完全回溯，......） . 对于自然语言，他需要比那些更强大的解析器;几十年来，人们一直试图 Build 这样的解析器，只有一些，但绝对不容易，成功 . 这两个要求中的任何一个似乎都使代表语法的讨论毫无意义;如果他确实代表了一个直接的上下文无关语法，它就需要简单地使用出血边类型产生的内容 . 除非他决定成为NL解析领域的真正专家，否则请把我看作是他可能成功的悲观主义者 .
回复于 2024-04-26T18:55:51+08:00
2
这是我存储产品的想法：
```
Dictionary<NonTerminalSymbol, List<Symbol>>
```
哪里

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

所以在你的例子中，字典会有一个键（“E”）和相应列表中的两个值（“[E] [E]”和“n”） .
回复于 2024-04-26T18:55:51+08:00

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

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

所以它看起来像这样

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

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

回复于 2024-04-26T18:55:51+08:00

C＃中的语法 生产环境 类实现

3 回答

相关问题

C＃中的语法生产环境类实现