3

再帰的降下と演算子の優先順位で、2 つの式パーサーを実装しました。これらは Object Pascal で実装されています。再帰的な降下は次のとおりです。

function ParseFactor: PNode;
var
  Temp: PNode;
begin
  Result := ParsePrimary;
  if t.Kind in [tkDoubleAsterisks] then begin
    New(Temp);
    Temp^.Kind := nkPower;
    Temp^.LeftOperand := Result;
    // power operator is right associative
    Lexer.Get(t);
    Temp^.RightOperand := ParseFactor();
    Result := Temp;
  end;
end;

function ParseTerm: PNode;
var
  Temp: PNode;
begin
  Result := ParseFactor;
  while t.Kind in [tkAmpersand,tkAsterisk,tkSlash,tkDoubleLessThan,tkDoubleGreaterThan] do begin
    New(Temp);
    case t.Kind of
      tkAmpersand        : Temp^.Kind := nkAnd;
      tkAsterisk         : Temp^.Kind := nkMultiplication;
      tkSlash            : Temp^.Kind := nkDivision;
      tkDoubleLessThan   : Temp^.Kind := nkShiftLeft;
      tkDoubleGreaterThan: Temp^.Kind := nkShiftRight;
    end;
    Temp^.LeftOperand := Result;
    Lexer.Get(t);
    Temp^.RightOperand := ParseFactor;
    Result := Temp;
  end;
end;

function ParseExpression: PNode;
var
  Temp: PNode;
begin
  Result := ParseTerm;
  while t.Kind in [tkHorzBar,tkCaret,tkPlus,tkMinus] do begin
    New(Temp);
    case t.Kind of
      tkHorzBar: Temp^.Kind := nkOr;
      tkCaret  : Temp^.Kind := nkXor;
      tkPlus   : Temp^.Kind := nkAddition;
      tkMinus  : Temp^.Kind := nkSubstraction;
    end;
    Temp^.LeftOperand := Result;
    Lexer.Get(t);
    Temp^.RightOperand := ParseTerm;
    Result := Temp;
  end;
end;

演算子の優先順位は次のとおりです。

function GetTokenPrecedence(const Kind: TTokenKind): Integer; inline;
begin
  case Kind of
    tkHorzBar,tkCaret,tkPlus,tkMinus:
      Result := 1;
    tkAmpersand,tkAsterisk,tkSlash,tkDoubleLessThan,tkDoubleGreaterThan:
      Result := 2;
    tkDoubleAsterisks:
      Result := 3;
    else
      Result := -1;
  end;
end;

function IsRightAssociative(const Kind: TTokenKind): Boolean; inline;
begin
  Result := Kind in [tkDoubleAsterisks];
end;

function ParseBinaryRHSExpression(LHS: PNode; const CurrentPrecedence: Integer): PNode;
var
  Op: TTokenKind;
  RHS: PNode;
begin
  while GetTokenPrecedence(t.Kind) >= CurrentPrecedence do begin
    Op := t.Kind;
    Lexer.Get(t);
    RHS := ParsePrimary;
    while (GetTokenPrecedence(t.Kind) > GetTokenPrecedence(Op))
      or (IsRightAssociative(t.Kind) and (GetTokenPrecedence(t.Kind) >= GetTokenPrecedence(Op)))
    do begin
      RHS := ParseBinaryRHSExpression(RHS,GetTokenPrecedence(t.Kind));
    end;
    New(Result);
    case Op of
      tkHorzBar          : Result^.Kind := nkOr;
      tkCaret            : Result^.Kind := nkXor;
      tkPlus             : Result^.Kind := nkAddition;
      tkMinus            : Result^.Kind := nkSubstraction;
      tkAmpersand        : Result^.Kind := nkAnd;
      tkAsterisk         : Result^.Kind := nkMultiplication;
      tkSlash            : Result^.Kind := nkDivision;
      tkDoubleLessThan   : Result^.Kind := nkShiftLeft;
      tkDoubleGreaterThan: Result^.Kind := nkShiftRight;
      tkDoubleAsterisks  : Result^.Kind := nkPower;
    end;
    Result^.LeftOperand := LHS;
    Result^.RightOperand := RHS;
    LHS := Result;
  end;
  Result := LHS;
end;

function ParseExpression: PNode;
begin
  Result := ParsePrimary;
  if Assigned(Result) then begin
    Result := ParseBinaryRHSExpression(Result,0);
  end;
end;

これらは、両者の唯一の本質的な違いです。いくつかの簡単なテストでは、両方が正しく解析されているように見えることが示されています。ただし、実際に実装するのはこれが初めてなので、演算子の優先順位の実装についてはよくわかりません。そして、私を悩ませている驚くべき事実は、再帰降下バージョンよりも遅く実行されることです (1.5 倍多くかかります)! 私のコンパイラクラスと私が読んだすべての記事は、関数呼び出しが少ないため、演算子の優先順位の解析は再帰的降下よりも効率的であると述べており、コードがそれを示しているように見えるので、それも期待しています。演算子の優先順位と右結合テストを取得するために追加の関数をインライン化しましたが、これはあまり役に立たないようです。私が何か間違ったことをしたかどうか教えてください。特定の事項の明確化については、遠慮なくお尋ねください。

4

1 に答える 1

1

すべてのものと同様に、トレードオフが重要です。再帰降下は、各演算子トークンを明示的にチェックするため、N 個の演算子がある場合は、基本的に N 個のテストを実行する必要があります。演算子の優先順位は、何かが演算子トークンであることを認識し、ルックアップ テーブルを使用するだけで済みます。したがって、N 個のテストの代わりに、数回のルックアップを使用できます。したがって、演算子の数が多い場合は、演算子の優先順位が速くなるはずです。あなたの文法がほんの少ししかない場合、注意深く調整されたとしても、それが勝つかどうかは明らかではありません.

全体として、パーサーの速度はおそらく重要ではありません。パーサーを使用するどのようなツールを構築していても、パーサー以外の場所でより多くの労力を費やすことになります。

オペレーターの優先順位は、テーブル内の複雑なオペレーター階層をエンコードできるため、マシンが小さいときに興味深いアイデアでした。それが提供するほとんどのトレードオフは、典型的なワークステーション (またはハンドヘルドでさえ) には関係ありません。単純な文法については再帰降下に固執し、その他の場合には便利と思われる種類のパーサー ジェネレーターを使用します。

于 2011-10-23T15:00:28.047 に答える