Сравнение реализаций парсера: подтверждение корректности и (возможно) оптимизация - PullRequest
Новая
       29

Сравнение реализаций парсера: подтверждение корректности и (возможно) оптимизация

3 голосов
/ 23 октября 2011

Я реализовал два парсера выражений, с рекурсивным спуском и приоритетом операторов.Они реализованы в 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 раза больше)!Мои классы компилятора и все статьи, которые я читаю, утверждают, что разбор приоритетов операторов должен быть более эффективным, чем рекурсивный спуск из-за меньшего количества вызовов функций, и это то, чего я ожидаю, так как код, кажется, показывает это.У меня есть inline-d дополнительные функции для проверки приоритета оператора и правильной ассоциативности, но это, похоже, мало помогает.Пожалуйста, скажите мне, сделал ли я что-то не так.Не стесняйтесь просить ясности некоторых вещей.

1 Ответ

1 голос
/ 23 октября 2011

Как и все вещи, компромиссы имеют значение.Рекурсивный спуск проверяет для каждого токена оператора явно, поэтому, если у вас есть N операторов, он должен по существу выполнить N тестов.Приоритет оператора должен знать, что что-то является токеном оператора, и использовать справочную таблицу.Таким образом, вместо N тестов, он может использовать только несколько поисков.Таким образом, приоритет операторов должен быть быстрее, если у вас много операторов.Если в вашей грамматике только несколько, то неясно, является ли это победой, даже если она тщательно настроена.

В общем, скорость синтаксического анализатора, вероятно, не имеет значения.Независимо от того, какой инструмент вы создаете и который использует синтаксический анализатор, он потребует гораздо больших усилий в другом месте, чем анализатор.

Приоритет оператора был интересной идеей, когда машины были небольшими, поскольку можно было закодировать сложные иерархии операторов в таблице.В основном компромиссы, которые он предлагал, не имеют значения для типичной рабочей станции (или даже ручной).Я бы придерживался рекурсивного спуска для простых грамматик и для генераторов парсеров любого вида, которые кажутся удобными для всего остального.

...