18

再帰降下パーサーの疑似コードを書きたいと思っています。今、私はこのタイプのコーディングの経験がありません。オンラインでいくつかの例を読んだことがありますが、それらは数式を使用する文法でのみ機能します。これが私がパーサーのベースにしている文法です。

S -> if E then S | if E then S else S | begin S L | print E

L -> end | ; S L

E -> i

メソッドS()、L()andを記述E()していくつかのエラー メッセージを返す必要がありますが、オンラインで見つけたチュートリアルはあまり役に立ちませんでした。誰かが私を正しい方向に向けて、いくつかの例を教えてもらえますか?.

C# や Java の構文の方が理解しやすいので、C# や Java の構文で書きたいと思います。

アップデート

public void S() {
    if (currentToken == "if") {
        getNextToken();
        E();

        if (currentToken == "then") {
            getNextToken();
            S();

            if (currentToken == "else") {
                getNextToken();
                S();
                Return;
            }
        } else {
            throw new IllegalTokenException("Procedure S() expected a 'then' token " + "but received: " + currentToken);
        } else if (currentToken == "begin") {
            getNextToken();
            S();
            L();
            return;
        } else if (currentToken == "print") {
            getNextToken();
            E();
            return;
        } else {
            throw new IllegalTokenException("Procedure S() expected an 'if' or 'then' or else or begin or print  token " + "but received: " + currentToken);
        }
    }
}


public void L() {
    if (currentToken == "end") {
        getNextToken();
        return;
    } else if (currentToken == ";") {
        getNextToken();
        S();
        L();
        return;
    } else {
        throw new IllegalTokenException("Procedure L() expected an 'end' or ';' token " + "but received: " + currentToken);
    }
}


public void E() {
    if (currentToken == "i") {
        getNextToken();
        return;
    } else {
        throw new IllegalTokenException("Procedure E() expected an 'i' token " + "but received: " + currentToken);
    }
}
4

3 に答える 3

18

基本的に再帰下降構文解析では、文法の各非終端記号がプロシージャに変換され、各プロシージャ内で、現在表示しているトークンが非終端記号の右側に表示されるものと一致するかどうかを確認します。手順に対応する終端記号。それがプロダクションの適用を続行する場合、そうでない場合はエラーが発生したため、何らかのアクションを実行する必要があります。

したがって、上記のように、手順があります。、、、S()およびL()、を実装E()する方法の例を示します。その後、自分でL()試してみることができます。S()E()

入力をトークン化するために他のプログラムが必要になることに注意することも重要です。そうすれば、そのプログラムに入力から次のトークンを要求することができます。

/**
 * This procedure corresponds to the L non-terminal
 * L -> 'end'
 * L -> ';' S L
 */ 
public void L()
{
   if(currentToken == 'end')
   {
      //we found an 'end' token, get the next token in the input stream
      //Notice, there are no other non-terminals or terminals after 
      //'end' in this production so all we do now is return
      //Note: that here we return to the procedure that called L()
      getNextToken();
      return; 
   } 
   else if(currentToken == ';')
   {
      //we found an ';', get the next token in the input stream
      getNextToken();
      //Notice that there are two more non-terminal symbols after ';'
      //in this production, S and L; all we have to do is call those
      //procedures in the order they appear in the production, then return
      S();
      L();
      return;
   }
   else
   {
      //The currentToken is not either an 'end' token or a ';' token 
      //This is an error, raise some exception
      throw new IllegalTokenException(
          "Procedure L() expected an 'end' or ';' token "+
          "but received: " + currentToken);
   }
}

今、あなたは試しS()てE()、そして投稿します。

また、クリストファーが指摘しているように、あなたの文法にはぶら下がりと呼ばれるものがあります。つまり、同じことから始まり、ある時点までのプロダクションがあることを意味します。

S -> if E then S 
S -> if E then S else S

したがって、これは、パーサーが「if」トークンを検出した場合、入力を処理するためにどのプロダクションを選択する必要があるかという疑問を投げかけます。答えは、人間とは異なり、コンパイラは入力ストリームを先読みして「else」トークンを検索できないため、どちらを選択すればよいかわからないということです。これは、代数の問題を因数分解する方法と非常によく似た、左因数分解と呼ばれるルールを適用することで修正する簡単な問題です。

あなたがしなければならないのは、新しい非終端記号S'（S-prime）を作成することだけです。その右側には、一般的ではないプロダクションの断片が保持されるため、Sプロダクションは次のようになりません。

S  -> if E then S S'
S' -> else S 
S' -> e   
(e is used here to denote the empty string, which basically means there is no   
 input seen)
于 2012-03-22T00:11:48.260 に答える
8

これは、最初のプロダクション ルールで無限の量の先読みがあるため、開始するのが最も簡単な文法ではありません。

S -> if E then S | if E then S else S |  begin S L | print E

検討

if 5 then begin begin begin begin ...

この愚かな他の人をいつ決定しますか？

また、考慮してください

if 5 then if 4 then if 3 then if 2 then print 2 else ...

さて、それはフラグメントelseにバインドすることになっていましたか? if 5 thenそうでない場合は、実際にはクールですが、明示的にしてください。

文法を次のように同等に書き換えることができます (おそらく、else ルールによって異なります)。

S -> if E then S (else S)? | begin S L | print E
L -> end | ; S L
E -> i

あなたが望むものかもしれないし、そうでないかもしれません。しかし、疑似コードの種類はこれから飛び出します。

define S() {
  if (peek()=="if") {
    consume("if")
    E()
    consume("then")
    S()
    if (peek()=="else") {
      consume("else")
      S()
    }
  } else if (peek()=="begin") {
    consume("begin")
    S()
    L()
  } else if (peek()=="print") {
    consume("print")
    E()
  } else {
    throw error()
  }
}

define L() {
  if (peek()=="end") {
    consume("end")
  } else if (peek==";")
    consume(";")
    S()
    L()
  } else {
    throw error()
  }
}

define E() {
  consume_token_i()
}

代替案ごとに、一意のプレフィックスを調べる if ステートメントを作成しました。マッチ試行の最後の else は、常にエラーになります。キーワードを消費し、プロダクション ルールに対応する関数を呼び出します。

疑似コードから実際のコードへの変換はそれほど複雑ではありませんが、簡単ではありません。これらのピークと消費は、おそらく文字列に対して実際には機能しません。トークンを操作する方がはるかに簡単です。そして、単に文をたどって消費することは、それを解析することとまったく同じではありません。断片を消費するときに何らかの処理を行い、おそらく解析ツリーを構築します (これは、これらの関数がおそらく何かを返すことを意味します)。また、エラーをスローすることは大まかなレベルでは正しいかもしれませんが、意味のある情報をエラーに入れたいと思うでしょう。また、先読みが必要な場合は、さらに複雑になります。

この種の問題を見るときは、Terence Parr (再帰降下パーサー ジェネレーターである antlr を書いた人物) による Language Implementation Patterns をお勧めします。Dragon Book (Aho など、コメントで推奨) も優れています (おそらく、コンパイラ コースの主流の教科書です)。

于 2012-03-22T00:14:06.287 に答える
4

私は前学期にPLクラスの構文解析セクションを教えました（本当に助けました）。私たちのページから解析スライドを見るのを本当にお勧めします：ここ。基本的に、再帰下降構文解析では、次の質問を自問します。

非終端記号を少し解析しましたが、次に解析する内容を選択できるようになりました。次に見るものは、私がどの非終端記号にいるのかを決定します。

ちなみに、あなたの文法は、「ぶら下がっている他の人」と呼ばれる非常に一般的なあいまいさを示しています。これは、アルゴルの時代から存在しています。シフトリデュースパーサー（通常はパーサージェネレーターによって生成されます）では、これによりシフト/リデュースの競合が発生します。通常、リデュースではなく任意にシフトすることを選択し、共通の「最大」プリンシパルを提供します。（したがって、「if（b）then if（b2）S1 else S2」と表示された場合は、「if（b）then {if（b2）{s1;} else {s2;}}」と読みます）

これを文法から外して、少し単純な文法で作業してみましょう。

T -> A + T
 |   A - T
 |   A
A -> NUM * A
   | NUM / A
   | NUM

また、NUMはレクサーから取得するもの（つまり、単なるトークン）であると想定します。この文法はLL（1）です。つまり、単純なアルゴリズムを使用して実装された再帰下降パーサーを使用して解析できます。アルゴリズムは次のように機能します。

parse_T() {
  a = parse_A();
  if (next_token() == '+') {
    next_token();  // advance to the next token in the stream
    t = parse_T();
    return T_node_plus_constructor(a, t);
  }
  else if (next_token() == '-') {
    next_token();  // advance to the next token in the stream
    t = parse_T();
    return T_node_minus_constructor(a, t);
  } else {
    return T_node_a_constructor(a);
  }
}
parse_A() {
  num = token(); // gets the current token from the token stream
  next_token();  // advance to the next token in the stream
  assert(token_type(a) == NUM);
  if (next_token() == '*') {
    a = parse_A();
    return A_node_times_constructor(num, a);
  }
  else if (next_token() == '/') {
    a = parse_A();
    return A_node_div_constructor(num, a);
  } else {
    return A_node_num_constructor(num);
  }
}

ここにパターンがありますか：

文法の非終端記号ごとに：最初に解析し、次に何を解析するかを決定するために何を見なければならないかを確認します。完了するまでこれを続けてください！

また、このタイプの解析では、通常、算術演算に必要なものが生成されないことに注意してください。再帰下降パーサー（末尾再帰で少しトリックを使用しない限り）は、左端の派生を生成しません。特に、左端の結合性が本当に必要な「a-> a-a」のような左再帰ルールを書くことはできません！これが、人々が通常、より洗練されたパーサジェネレータツールを使用する理由です。しかし、再帰下降トリックは、それでも知って遊んでみる価値があります。

于 2012-03-22T00:10:21.380 に答える