parsing - 簡単なパーサーの開発

Question

私の日常の仕事には、Pascal ライクなコンパイラの開発作業が含まれます。私はずっと最適化とコード生成に取り組んできました。

また、同じ言語用の単純なパーサーを作成する方法を学びたいと思っています。ただし、これについてどうすればよいかよくわかりません。Flex と Bison が選択されているようです。しかし、C++ や C# を使用してパーサーを作成することはできませんか? 私はCに少し不気味です。

Yacc++ は C# をサポートしていますが、ライセンスが必要です。この点に関して、私が見つけることができるすべての助けを探しています。提案をいただければ幸いです。

score 6 · Accepted Answer

C# で ANTLR を使用できると思います。私は（まだ）自分で試したことはありませんが、ここに正しい方向を示すチュートリアルがあります。

score 5 · Accepted Answer

個人的には、独自のレクサーとパーサー (LL) を作成しています。これは非常に簡略化された例です。これは C++ で書かれていますが、うまくいけばそれを適応させることができます。マクロ PARSE_HIGHER を使用して、コードをあまり変更せずに、さまざまな優先順位レベルで演算子を簡単に挿入できるようにします。

 // routine to scan over whitespace/comments
void ScanWhite(const char* &pc){
  while(true){
    if(0);
    else if (WHITESPACE(*pc)) pc++;
    else if (pc[0]=='/' && pc[1]=='/'){
      while(*pc && *pc++ != '\n');
    }
    else break;
  }
}
// routine to lex an identifier
bool SeeId(const char* &pc, string sId){
  ScanWhite(pc);
  const char* pc0 = pc;
  if (alpha(*pc)){
    sId = "";
    while(alphanum(*pc)) sId += (*pc++);
    return true;
  }
  pc = pc0;
  return false;
}
// routine to lex a number
bool SeeNum(const char* &pc, double &dNum){
  ScanWhite(pc);
  const char* pc0 = pc;
  if (digit(*pc)){
    dNum = 0;
    while(digit(*pc)) dNum = dNum * 10 + (*pc++ - '0');
    if (*pc == '.'){
      double divisor = 1, frac = 0;
      while(digit(*pc)){
        divisor *= 0.1;
        frac += (*pc++ - '0') * divisor;
      }
      dNum += frac;
    }
    return true;
  }
  pc = pc0;
  return false;
}
// routine to lex some constant word
bool SeeWord(const char* &pc, const char* sWord){
  ScanWhite(pc);
  const char* pc0 = pc;
  int len = strlen(sWord);
  if (strncmp(pc, sWord, len)==0 && !alphanum(pc[len])){
    pc += len;
    return true;
  }
  pc = pc0;
  return false;
}
// routine to lex a single character like an operator
bool SeeChar(const char* &pc, const char c){
  ScanWhite(pc);
  const char* pc0 = pc;
  if (*pc == c){
    pc++;
    return true;
  }
  pc = pc0;
  return false;
}
// primitive expression parser
void ParsePrimitiveExpr(const char* &pc, CNode* &p){
  double dNum;
  char sId[100];
  if (0);
  else if (SeeNum(pc, dNum)){
    p = new CNode(dNum);
  }
  else if (SeeId(pc, sId)){
    // see if its a function call
    if (SeeChar(pc, '(')){
      p = MakeNewFunctionCallNode(sId);
      while(!SeeChar(pc, ')')){
        CNode* p1 = null;
        ParseExpression(pc, p1);
        AddArgumentExprToFunctionCallNode(p, p1);
        SeeChar(pc, ','); /* optional comma separator */
      }
    }
    // otherwise its just a variable reference
    else {
      p = new CNode(sId);
    }
  }
  // handle embedded expressions
  else if (SeeChar(pc, '(')){
    ParseExpression(pc, p);
    if (!SeeChar(pc, ')')) /* deal with syntax error */
  }
}
#define PARSE_HIGHER ParsePrimitiveExpr
// product parser
void ParseProduct(const char* &pc, CNode* &p){
  PARSE_HIGHER(pc, p);
  while(true){
    if (0);
    else if (SeeChar(pc, '*')){
      CNode p1 = null;
      PARSE_HIGHER(pc, p1);
      p = new CNode('*', p, p1);
    }
    else if (SeeChar(pc, '/')){
     CNode p1 = null;
     PARSE_HIGHER(pc, p1);
     p = new CNode('/', p, p1);
   }
   else break;
  }
}
#undef  PARSE_HIGHER
#define PARSE_HIGHER ParseProduct
// sum parser
void ParseSum(const char* &pc, CNode* &p){
  PARSE_HIGHER(pc, p);
  while(true){
    if (0);
    else if (SeeChar(pc, '+')){
      CNode p1 = null;
      PARSE_HIGHER(pc, p1);
      p = new CNode('+', p, p1);
    }
    else if (SeeChar(pc, '-')){
      CNode p1 = null;
      PARSE_HIGHER(pc, p1);
      p = new CNode('-', p, p1);
    }
   else break;
  }
}
#undef  PARSE_HIGHER
// can insert more routines like the above
// to handle move operators
#define PARSE_HIGHER ParseSum
// overall expression parser
void ParseExpression(const char* &pc, CNode* &p){
  PARSE_HIGHER(pc, p);
}

Pascal スタイルのステートメント構文をいくつか追加しました。

void ParseStatement(const char* &pc){
  char sId[100];
  if(0);
  else if (SeeWord(pc, "begin")){
    while(!SeeWord(pc, "end")){
      ParseStatement(pc);
      SeeChar(pc, ';');
    }
  }
  else if (SeeWord(pc, "while")){
    CNode* p1 = null;
    ParseExpression(pc, p1);
    ParseStatement(pc);
    /* semantics for while statement */
  }
  else if (SeeWord(pc, "if")){
    CNode* p1 = null;
    ParseExpression(pc, p1);
    ParseStatement(pc);
    if (SeeWord(pc, "else")){
      ParseStatement(pc);
    }
    /* semantics for if statement */
  }
  else if (SeeWord(pc, "for")){
    /* you do it */
  }
  // handle assignments and subroutine calls
  else if (SeeId(pc, sId)){
    if(0);
    else if (SeeChar(pc, '=')){
      CNode* p1 = null;
      ParseExpression(pc, p1);
      /* semantics for assignment statement */
    }
    else if (SeeChar(pc, '(')){
      CNode* p = MakeNewFunctionCallNode(sId);
      while(!SeeChar(pc, ')')){
        CNode* p1 = null;
        ParseExpression(pc, p1);
        AddArgumentExprToFunctionCallNode(p, p1);
        SeeChar(pc, ','); /* optional comma separator */
      }
    }
    else {
      /* we have a 1-word statement, which is OK in pascal */
    }
  }
  else {
    /* syntax error */
  }
}

配列のインデックス付け、変数の宣言、および関数の定義にはまだ構文が必要ですが、その方法が明確になっていることを願っています。

score 1 · Accepted Answer

Niklaus Wirth は、彼の古典的なプログラミングテキストであるAlgorithms + Data Structures = Programsで、単純な Pascal0 に似た言語用に (Pascal で) 完全な再帰降下パーサーを開発しています。

score 0 · Accepted Answer

flex と bison は C++ で実際に使用できます。たとえば、このチュートリアルでは、セクション 5 がその問題に専念していることがわかります。グーグルで検索すれば、たくさんの例が見つかるはずです。

score 0 · Accepted Answer

この質問に従ってC#が必要な場合は、 Gardens Point GPPGとGPLEXを試してください。

score 0 · Accepted Answer

Java で書いている場合は、ANTLR をお勧めします。Java で書かれた素敵な LL(*) パーサージェネレーターです。アマゾンにも素晴らしい本があります。

score 0 · Accepted Answer

bison と flex は正規のパーサージェネレーターです。C++ に興味があるなら、ブーストスピリットが役立つと思います。ただし、コンパイラのように複雑なものには使用したことがありません。C# などの他の言語について、他の人が興味深い提案をしてくれると確信しています...

score 0 · Accepted Answer

flex と bison を使用して XSLT パーサーを作成しました。最近では、ANTLR を使用してプロジェクトを行っています。

JFig 言語の構文は効率的で明確ですか (Spring-Framework の XML DSL より優れていますか)?

Flex や Bison よりも ANTLR での作業が好きです。ANTLR は、いくつかの点でより高いレベルの抽象化をもたらします。字句定義とパーサー文法はすべて 1 つのファイルに入れることができます。(ANTLR はトークンファイルを生成します。)

重要な項目の 1 つは、ツリー文法を定義する機能です。基本的に、入力言語に対して文法解析を実行し、非常に最適な AST ツリー出力 (メモリ内にリンクされたデータ構造として残る) に書き換えるアクションを実行します。その後、別のツリーパーサーファイルで定義された別のパーサーにこのツリーを渡すことができます。ツリーパーサーは、必要なアクションアイテムの実際の作業を行う場所です。

AST フォームを保持し、必要に応じて繰り返し再処理できるため、これは優れたアプローチです。特定のサブツリーノードを剥がして、後のアクションに基づいて処理するなどです。言語インタープリターのようなものを考えてみてください。for ループに入って言語を最初から何度も処理する代わりに、AST 表現を処理するだけです。

私の場合、IoC 依存性注入を行うための Bean ファクトリを考案しました。私の Bean ファクトリは、実行時に Bean 記述子の AST を保持します。新しい Bean インスタンスを作成 (または取得) する必要がある場合は、Bean 記述子の AST サブツリーをツリーパーサーに渡すだけです。結果は目的の Bean インスタンスです (インスタンス化する方法を決定するには多くの要因があります)。これには、参照される他の Bean の作成や、メタ属性を介した他の特別な動作の適用が含まれます)。

最後に、現在の Bean ファクトリは Java をターゲットにしていますが、ActionScript3 と C# .NET をターゲットにしたいと考えています。ANTLR はそれをサポートしています。

前述のように、Terrence Parr は ANTLR の使用方法に関する本を書いています。これは、ANTLR で何か実用的なことを行う必要がある作業中のプログラマーを対象としています (主題の学術的な扱いとは対照的に)。

score 0 · Accepted Answer

Lex と Yacc を使用する場合、実際には C でほとんど何も記述しません。Lexは独自の言語であり、Yacc も同様です。つまり、レキシカルアナライザーを Lex で記述し、パーサーをYaccで記述します。ただし、Pascal の場合、Lex と Yacc の入力は既に利用可能です。

結果として得られるパーサーとレクサーには C インターフェースがあります。これは事実です。ただし、C++ を含むほとんどの言語には、C インターフェイスを呼び出す (またはラップする) 簡単な方法があります。

私はその専門家ではありませんが、上記のすべてが ANTLR にも当てはまると確信しています。

「純粋な C++」(それが何を意味するにせよ) でそれを行うように求めている場合は、 boost spirit の使用を検討してください。ただし、それが大量の作業を引き起こす場合、理論的な純粋さの意味は実際にはわかりません。

独自のレクサーとパーサーを手動で作成するのは、実際にはちょっと楽しい作業です。字句解析器は、 gotoとプリプロセッサの両方を使用して正当化できる数少ない状況の 1 つです。ただし、回避できるのであれば、Pascal のような本格的な言語にはお勧めしません。それは大変な作業です。私は工数を話している。

parsing - 簡単なパーサーの開発

9 に答える 9

Related

Reference