c# - C# での文法プロダクション クラスの実装

Question

定義による文法には、非常に単純な文法の例である生成が含まれます。

E -> E + E
E -> n

C# で Grammar クラスを実装したいのですが、ターミナル シンボルと非ターミナル シンボルを区別する方法など、プロダクションを格納する方法がわかりません。私は考えていました：

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

左側は常に非終端記号になります (これは文脈自由文法に関するものです)。ただし、プロダクションの右側には終端記号と非終端記号を含めることができます

だから今、私は実装の2つの方法について考えています:

1. 非終端記号は角かっこを使用して記述されます。次に例を示します。

   E+E は文字列 "[E]+[E]" として表されます

2. 追加のデータ構造 NonTerminal を作成します

   struct NonTerminal {文字列シンボル; }

E+E は配列/リストとして表されます。

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

しかし、もっと良いアイデアがあると思います。

Answer 1

I'd use

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

enabling lookup by Nonterminal of the set of production rule right-hand-sides (themselves represented as lists of Terminal/Nonterminal Symbols) associated with the Nonterminal. (OP's question shows that the Nonterminal E might be associated with two rules, but we only need the right-hand sides if we have the left hand side).

This representation works only for a vanilla BNF grammar definitions, in which there is no syntactic sugar for common grammar-defining idioms. Such idioms typically include choice, Kleene star/plus, ... and when they are avialable in defining the grammar you get an so-called Extended BNF or EBNF. If we write EBNF only allowing choice denoted by |, the Expression grammar in flat form hinted at by OP as an example is:

         E = S ;
         S = P | S + P | S - P ; 
         P = T | P * T | P / T ;
         T = T ** M | ( E ) | Number | ID ;

and my first suggestion can represent this, because the alternation is only used to show different rule right-hand-sides. However, it won't represent this:

         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 ;

The key problem that this additional notation introduces is the ability to compose the WBNF operators repeatedly on sub-syntax definitions, and that's the whole point of EBNF.

To represent EBNF, you have to store productions essentially as trees that represent the, well, expression structure of the EBNF (in fact, this is essentially the same problem as representing any expression grammar).

To represent the EBNF (expression) tree, you need to define the tree structure of the EBNF. You need tree nodes for:

• symbols (terminal or not)
• Alternation (having a list of alternatives)
• Kleene *
• Kleene +
• "Optional" ?
• others that you decide your EBNF has as operators (e.g., comma'd lists, a way to say that one has a list of grammar elements seperated by a chosen "comma" character, or ended by a chosen "semicolon" character, ...)

The easiest way to do that is to first write an EBNF grammar for the EBNF itself:

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

Note that I've added comma'd and semicolon'ed list to the EBNF (extended, remember?)

Now we can simply inspect the EBNF to decide what is needed. What you now need is a set of records (OK, classes for C#'er) to represent each of these rules. So:

• a class for EBNF that contains a set of rules
• a class for a RULE having an LHS symbol and a LIST
• an abstract base class for TERM with several concrete variants, one for each alternative of TERM (a so-called "discriminated union" typically implemented by inheritance and instance_of checks in an OO language).

Note that some of the concrete variants can refer to other class types in the representation, which is how you get a tree. For instance:

   KleeneStar inherits_from TERM {
        T: TERM:
   }

Details left to the reader for encoding the rest.

This raises an unstated problem for the OP: how do you use this grammmar representation to drive parsing of strings?

The simple answer is get a parser generator, which means you need to figure out what EBNF it uses. (In this case, it might simply be easier to store your EBNF as text and hand it to that parser generator, which kind of makes this whole discussion moot).

If you can't get one (?), or want to build one of your own, well, now you have the representation you need to climb over to build it. One other alternative is to build a recursive descent parser driven by this representation to do your parsing. The approach to do that is too large to contain in the margin of this answer, but is straightforward for those with experience with recursion.

EDIT 10/22: OP clarifies that he insists on parsing all context free grammars and "especially NL". For all context free grammars, he will need very a stong parsing engine (Earley, GLR, full backtracking, ...). For Natural Language, he will need parsers much stronger than those; people have been trying to build such parsers for decades with only some, but definitely not easy, success. Either of these two requirements seems to make the discussion of representing the grammar rather pointless; if he does represent a straight context free grammar, it won't parse natural language (proven by those guys trying for decades), and if he wants a more powerful NL parser, he'll need to simply use what the bleeding edge types have produced. Count me a pessimist on his probable success, unless he decides to become a real expert in the area of NL parsing.

Answer 2

作品を保存するという私の考えは次のとおりです。

Dictionary<NonTerminalSymbol, List<Symbol>>

どこ

Symbolの親（抽象？）クラスNonTerminalSymbol、TerminalSymbolおよびProductionクラス

したがって、あなたの例では、辞書には対応するリストに1つのキー（ "E"）と2つの値（ "[E] +[E]"と"n"）があります。

Answer 3

2番目の方法に拡張メソッドを使用すると役立つ場合があります。

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

だからそれはこのようになります

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

この方法の利点は、コードを簡単に変更できることです。