パーサーの実装の比較：正しさの確認と（たぶん）最適化

Question

私は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回以上かかる）よりも遅く実行されます！私のコンパイラクラスと私が読んだすべての記事では、演算子の優先順位の解析は、関数呼び出しが少なくて済み、再帰的な降下よりも効率的でなければならないと述べています。私は演算子の優先順位と右アソシエーショニティテストを得るためにインラインdの追加機能を持っていますが、これはあまり役に立たないようです。私が間違っていたかどうか教えてください。特定のことを明確にするように気をつけてください。

Answer 1

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

物事の巨大なスキームでは、パーサの速度はおそらく重要ではありません。パーサーを使用して構築しているツールがあれば、パーサ以外の場所ではもっと多くの労力を費やします。

テーブル内に複雑な演算子階層をエンコードする可能性があるため、マシンが小さい場合は演算子の優先順位が興味深い考えでした。ほとんどの場合、提供されるトレードオフは典型的なワークステーション（または手持ちのもの）には関係ありません。私は簡単な文法のための再帰的な降下に固執し、どのような種類のパーサージェネレータにも、何にも便利だと思われる。