1

C++ 次の文法の再帰降下パーサーを作成する方法がわかりません。

<Datalog Program>     ->  Schemes : <Scheme List>     
                         Facts   : <Fact List>
                         Rules   : <Rule List>
                         Queries : <Query List>
                         <EOF>
<Scheme List>         ->  <Scheme> <Scheme List Tail>
<Scheme List Tail>    ->  <Scheme List> | ε
<Scheme>              ->  <Identifier> ( <Identifier List> )
<Identifier List>     ->  <Identifier> <Identifier List Tail>
<Identifier List Tail>->  , <Identifier List> | ε
<Fact List>           ->  <Fact> <Fact List> | ε
<Fact>                ->  <Identifier> ( <Constant List> ) .
<Constant List>       ->  <String> <Constant List Tail>
<Constant List Tail>  ->  , <Constant List> | ε
<Rule List>           ->  <Rule> <Rule List> | ε
<Rule>                ->  <Head Predicate> :- <Predicate List> .
<Head Predicate>      ->  <Identifier> ( <Identifier List> )
<Predicate List>      ->  <Predicate> <Predicate List Tail>
<Predicate List Tail> ->  , <Predicate List> | ε
<Predicate>           ->  <Identifier> ( <Parameter List> )
<Parameter List>      ->  <Parameter> <Parameter List Tail>
<Parameter List Tail> ->  , <Parameter List> | ε
<Parameter>           ->  <String> | <Identifier> | <Expression>
<Expression>          -> ( <Parameter> <Operator> <Parameter> )
<Operator>            -> + | *
<Query List>          ->  <Query> <Query List Tail>
<Query List Tail>     ->  <Query List> | ε
<Query>               ->  <Predicate> ?

これは単純なデータログのような文法です。私はパーサーを書こうとして完全に迷っています。私はすでに、すべてのトークンを含むベクトルを出力する語彙アナライザーを作成しました。プロダクションごとにメソッドを記述する必要があることはわかっていますが、トークンを解析ツリーに接続する方法がわかりません (ツリーが完成した後で toString() 関数を実行できるようにするため)。私は正しい方向に向けられる必要があります。ありがとう。

4

2 に答える 2

2

あなたがすでに書いたことを考えると、それは主に EBNF から C++ ソース コードへの機械的な変換であるため、(たとえば)次のようなルールです。

<Scheme>              ->  <Identifier> ( <Identifier List> ) 
<Identifier List>     ->  <Identifier> <Identifier List Tail>
<Identifier List Tail>->  , <Identifier List> | ε

この一般的な順序で何かに変換されます (ただし、注意してください。これは頭のてっぺんからタイプしているだけなので、まったくテストされていません。そのままコンパイルします)。

bool scheme() { 
    return identifier()        &&
           check_input('(')    &&
           identifier_list()   &&
           check_input(')');
}

bool identifier_list() { 
    if (identifier()) {
        if (check_input(','))
            return identifier_list();
        else
            return true;
    }
    return false;
}

bool identifier() { 
    // you haven't said what's a legal identifier, so for the moment I'm assuming
    // rules roughly like C's.
    int ch;
    std::string id;

    if (!((ch=getinput()) == '_' || isalapha(ch))
        return false;

    do { 
        id += ch;
        ch = getinput();
    } while (isalpha(ch) || isdigit(ch) || ch == '_');
    putback(ch);
    return true;
}

入力を正しく認識したら (そして、何もしていないにもかかわらず、上記で行ったように識別子などを構築したら)、解析ツリー (または何でも) の構築を開始して、ツリーに何かを追加することができます。あなたがそれらを認識するように。C でそれを行う場合、通常は共用体を使用します。C++ では、代わりにクラス階層を使用したい場合があります (ただし、これは非常に短くてふさふさした階層になりますが、実際には、基本クラスから直接派生した他のすべての階層を簡単に作成できます)。

于 2013-02-10T04:29:43.920 に答える
1

少なくとも Datalog を知らない場合や、言語の名前が何であれ、自分の文法で何が起こっているのかを理解するのは簡単ではありません。

知らない人のために読むだけでなく、ターミナルとプロダクションに異なるマークアップを使用していれば、自分自身のためにも読むのがはるかに簡単だったでしょう. 探して後ろを向いていればどれがどれだかわかるはずですが、ちょっとめまいがしそうです。

あなたの文法を見ると、かなり複雑なツリーになってしまうようには見えません。すべてのアイテムが注文されているため。

私の提案は、あなたの文法、つまりデータ構造体に従ってツリーをモデル化することです: DatalogProgram Schmema Fact Rule and Query、Expression HeadPredicate and Predicate

このようにすると、パーサーを機能させるために必要なことは次のようになります

DatalogProgram parse_datalog_progrem (pos){
   DatalogProgram program = new

   while ( Scheme s = parse_scheme () )
       program.append_scheme (s);

   while ( Fact f = parse_fact () )
       program.append_scheme (f);

   while ( Rule r = parse_rule () )
       program.append_rule (r);

   while ( Query q = parse_query () )
       program.append_query (q);

   return program; 
}

Scheme parse_scheme () {
   Scheme s = new ...
   s.id = parse_identifier ();

   parse ('(')

   while (Identifier i = parse_identifier) {
     s.append_id_list (i);
     if (lookahead != ',')
        break;
     parse (',');
   }
   parse (')');
   return s;
}

....

... 等々。要点がわかると思います。

まだ回避策があるようですが、これが最善の方法だと思います。たとえば、次のようなデータ構造体でユニオンを使用することを考えたいと思うかもしれません

struct Parameter {
  enum ParamType type;
  union {
     String  str;
     Identifier id;
     Expression expr;
  }
}

ここから先はまだ長い道のりですが、方向性を気に入っていただければ幸いです。

..ああ、DatalogProgramのようなもの：

struct DatalogProgram {
  struct Scheme *schemes;
  struct Fact *facts;
  struct Rule *rules;
  struct Query *queries;
}

解析ツリーのルート用。

于 2013-02-10T04:54:49.180 に答える