Всем привет.

Давичи мне указали на то что в мире имеется еще один интересный алгоритм распознавания текстов — Pratt. Это так называемый "Top Down Operator Precedence".

По сути это ни что иное как обычный Top Down парсер, т.е. без откатов (бэктрекинка) как в PEG (и прочих блэкджеков).

Интересен он тем, что алгоритм рекурсивного спуска дополнен отдельной стадией обработки приоритетов и ассоциативности (или правых и левых приоритетов) операторов. Учитывая что многое при парсинге можно описать в виде операторов (в том числе точку в С-подобных языках и даже скобки) — этот подход может существенно упростить описание грамматик современных языков программирования.

На мой взгляд это весьма разумный подход который может быть легко интегрирован с PEG-ом (разбираемым с помощью парсеров рекурсивного спуска с откатами). Простой пример... Недавно hardcase реализовал парсер C# 4.0 на базе макроса Nemerle PegGrammar

Автор: VladD2
Дата: 18.08.10

. При реализации он столкнулся с тем, что в парсере не врено обрабатывался приоритет оператора "as". Попытки решить проблему в лоб не не привили к положительному результату. Оказалось, что на грамматике такого объема с операторами очень легко запутаться. Посовещавшись мы решили вместо описания приоритетов операторов в виде иерархии правил использовать алгоритм с двумя стеками. В результате вместо нагромождения правил (в которых черт ногу сломит) получились три простых правила (Parser.n):

binaryOperator            : BinaryOperatorInfo = ("??" / "||" / "|" / "&&" / "&" / "==" / "!=" / "<=" / "<<" / "<" 
                                                  / ">=" / ">>" / ">" / "*" / "/" / "%" / "+" / "-" / "^")s;
typeTestingOperator       : BinaryOperatorInfo = ("is" / "as")S;
binaryOperatorExpression  : Expr = prefixExpression ( (binaryOperator prefixExpression) / (typeTestingOperator anyTypeAccess) )*;

И довольно прозрачная процедура обработки операторов в соответствии с их приоритетами (Parser_Expressions.n):

    binaryOperator(op : NToken, _ : NToken) : Identifier * int * int
    {
      def opStr = op.GetText();
      def opId = Identifier(GetLocation(_), opStr);
      match(opStr) {
        | "??"  => (opId, 11, 10) // right associative
        | "||"  => (opId, 20, 20)
        | "|"   => (opId, 40, 40)
        | "&&"  => (opId, 30, 30)
        | "&"   => (opId, 60, 60)
        | "=="  => (opId, 70, 70)
        | "!="  => (opId, 70, 70)
        | "<="  => (opId, 80, 80)
        | "<<"  => (opId, 90, 90)
        | "<"   => (opId, 80, 80)
        | ">="  => (opId, 80, 80)
        | ">>"  => (opId, 90, 90)
        | ">"   => (opId, 80, 80)
        | "*"   => (opId, 110, 110)
        | "/"   => (opId, 110, 110)
        | "%"   => (opId, 110, 110)
        | "+"   => (opId, 100, 100)
        | "-"   => (opId, 100, 100)
        | "^"   => (opId, 50, 50)
        | _ => throw ArgumentOutOfRangeException("op")
      }
    }

    typeTestingOperator(op : NToken, _ : NToken) : Identifier * int * int
    {
      (Identifier(GetLocation(_), op.GetText()), 70, 200)
    }

    binaryOperatorExpression( head : VToken[Expr],
                              tail : SCG.List[VToken[Identifier * int * int] * VToken[Expr]]) : Expr
    {
      match(tail.Count) {
        | 0 => head.Value

        | 1 =>
          def a = head.Value;
          def (op, b) = tail[0];
          def b = b.Value;
          Expr.BinaryOperator(a.Location + b.Location, a, b, op.Value[0])

        | _ =>
          def opStack = SCG.Stack();
          def exprStack = SCG.Stack();
          exprStack.Push(head.Value);
  
          def evalOperandsOnStack() {
            def b = exprStack.Pop();
            def a = exprStack.Pop();
            exprStack.Push(Expr.BinaryOperator(a.Location + b.Location, a, b, opStack.Pop()[0]));
          }
  
          foreach((op, operand) in tail) {
            def (op, leftPrior, rightPrior) = op.Value;
            when (!opStack.IsEmpty() && opStack.Peek()[1] >= leftPrior)
              evalOperandsOnStack();
            exprStack.Push(operand.Value);
            opStack.Push(op, rightPrior);
          }
  
          while(!opStack.IsEmpty())
            evalOperandsOnStack();
  
          exprStack.Pop() // exprStack becomes empty
      }
    }

Собственно мораль сей басни в том, что к генераторам парсеров и комбинаторным парсерам использующим алгоритм рекурсивного спуска очень полезно было бы добавить данную возможность (приоритетной обработки операторов).

ЗЫ

Надеюсь, что данные ссылки будут кому-то интересны.
Забавно, что идея стара (почти) как мир (алгоритм разработан на Лиспе еще в 70-ых). Но почему-то до недавнего момента я о нем ни разу не слышал. Все же хорошие идеи обязаны популяризироваться. Что я и делаю .

Ссылки по теме:
Extensible, Statically Typed Pratt Parser in C#
Обсуждение с кучей ссылок
Описание реализации для Ява-скрипта с кучей ссылок