我会使用
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+ ;
M = * T | / T ;
T = T ** M | ( E ) | Number | ID | ID ( E ( # | C) * ) ;
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解析领域的真正专家,否则我对他的可能成功持悲观态度。