re_sip_uri_short = "sip:(?:%s)?(?:%s)" % (re_userinfo, re_hostport)
re_sip_uri = "sip:(?:%s)?(?:%s)(?:%s)?(?:%s)?" % \
  (re_userinfo, re_hostport, re_parameters_in_uri, re_headers_in_uri)
re_sip_uri_parse = "sip:(?P<userinfo>(?:%s)?)(?P<hostport>(?:%s))" \
    "(?P<params>(?:%s)?)(?P<headers>(?:%s)?)" % \
    (re_userinfo, re_hostport, re_parameters_in_uri, re_headers_in_uri)
re_addr_spec = re_sip_uri
re_addr_spec_short = re_sip_uri_short
re_name_addr = "(?:(?:(?:%s)?)\\s*<(?:%s)>\\s*)" % \
  (re_display_name, re_addr_spec)
## addr is our own term to name (name-addr|addr-spec-short)
re_addr = "(?:%s|%s)" % (re_name_addr, re_addr_spec_short)
## for SipAddress - separate display name and address
re_name_addr_p = "(?:(?P<display_name>(?:%s)?)\\s*<(?P<uri>%s)>\\s*)" % \
  (re_display_name, re_addr_spec)

G>>PEG содержит регулярное подмножество, которое может быть разобрано за линейное время, regexp далеко не всегда преобразуется в КА, особенно с расширениями, поэтому часто работает с откатами (а в перле и подавно).

A parsing expression grammar, or PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.

K>Ну ты дальше читай, дальше. PEG парсится не за линейное время, а (в худшем случае) за экспоненциальное. Ровно так же, как и регэкс. Линейность там достигается с помощью кэширования подстрок, но в этом случае получается экспоненциальный рост памяти в худшем случае — что редьки не слаще

G>>PEG содержит регулярное подмножество, которое может быть разобрано за линейное время, regexp далеко не всегда преобразуется в КА, особенно с расширениями, поэтому часто работает с откатами (а в перле и подавно).

G>PEG это все таки нотация, как и regexp.

Не только, это еще и способ парсинга. Рекурсивный спуск с неограниченным look-ahead. И поскольку там есть откаты, то написать экспоненциальную грамматику тоже при большом желании можно.

var peg = "expression := number (op number)*; op := '+' / '-' / '*' / '/'; number := d+;";
var parsed = peg_parse(peg, "34+17-44");
var numbers = parsed.all_items["number"];//выберет все числа

var grammar = @"
      expression := and-expression;
      and-expression := or-expression ( S* and-op S* or-expression) *;
      or-expression := equal-expression ( S* or-op S* equal-expression) *; 
      equal-expression :=  sum-expression ( S* equal-op S* sum-expression) *;  
      sum-expression := multiply-expression ( S+ sum-op S+ multiply-expression)*;
      multiply-expression := expression-or-number ( S+ multiply-op S+ expression-number) *;         
      expression-or-number := ('(' S* expression S* ')') / number;

      and-op := '&&';
      or-op := '||';
      equal-op := '*=*' / '*=' / '=*' / '==' / '!=' / '<=' / '>=' / '<' / '>';
      multiply-op := '*' / '/';
      sum-op := '+' / '-';

      number := [0-9]+;
";

var parsed = peg_parse(grammar, "(1 + 2) * 4");
var numbers = parsed.all_items["number"];//search: найдет все номера

//replace: заменяем все сложения на вычитание
foreach (var sum_op in parsed.all_items["sum-expression"].item["sum-op"])
{
  if (sum_op.text == "+")
   sum_op.new_text = "-";
}
Console.WriteLine(parsed);//выдаст (1 - 2) * 4

s/(class\s+\w+)\s*,\s*(class\s+\w+)/\2, \1/

perl -i -pe 's/\d{2}:\d{2}:\d{2}\.\d{6}//g' file1 file2....

($h,$m,$s) = m/(\d{2}):(\d{2}):(\d{2}\.\d{6})/; $t = $h*3600 + $m*60 + $s;

J>>Ну и бэк-референсов нету

s/std::basic_string<(\w+), std::char_traits<\1>, std::allocator<\1> >/std::basic_string<\1>/

J>s/(class\s+\w+)\s*,\s*(class\s+\w+)/\2, \1/
J>

var grammar = @"
query := class S* ',' S* class;
class := 'class' S+ word;
";
var parsed = peg_parse(grammar, text);
parsed.all_items["class"][0].new_text = parsed.all_items["class"][1];
parsed.all_items["class"][1].new_text = parsed.all_items["class"][0];
return parsed.ToString();

J>perl -i -pe 's/\d{2}:\d{2}:\d{2}\.\d{6}//g' file1 file2....
J>

var grammar = @"
query := (timestamp / .)*;
timestamp := d{2} ':' d{2} ':' d{2} '.' d{6};
";
return peg_parse(grammar, text).replace(new{timestamp=""}).ToString();

J>($h,$m,$s) = m/(\d{2}):(\d{2}):(\d{2}\.\d{6})/; $t = $h*3600 + $m*60 + $s;
J>

var grammar = @"
query := (timestamp / .)*;
timestamp := hour ':' minute ':' second '.' d{6};
hour := d{2};
minute := d{2};
second := d{2};
";
var parsed = peg_parse(grammar, text);
foreach (var timestamp in parsed.all_items["timestamp"])
{
  var time = timestamp.item["hour"].ToInt() * 3600 + timestamp.item["minute"].ToInt() * 60 + timestamp.item["second"].ToInt();
}

J>>>Ну и бэк-референсов нету

J>s/std::basic_string<(\w+), std::char_traits<\1>, std::allocator<\1> >/std::basic_string<\1>/
J>

var lexer_grammar = @"
  all := (literal / comment / S / .)*;
  literal := ('""' (!'""' .)*  '""') / (""'"" (!""'"" .)*  ""'"");
  S := [ \t] / line-break;
  comment := '//' (!line-break .)* line-break;
  line-break := ([\r][\n]) / [\r] / [\n];
";

var grammar = @"number ( op number )*";

var parsed = peg_parse(lexer_grammar, "12 + 45/10").replace(new{S=""}).parse(grammar);

CalcParser.n(130,41):Error: The parameter "se" has wrong type string (need type int).
CalcParser.n(105,5):Error: You need define method-handler with signature: parenthesesExpr(_ : Nemerle.Peg.NToken, _ : int, _ : Nemerle.Peg.NToken) : int

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxlmnopqrstuvwyz
^.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*l+m+n+o+p+q+r+s+t+u+v+w+y+z+$

Now, Perl's regexps "aren't" -- that is, they aren't "regular" because backreferences per sed and grep are also supported, which renders the language no longer strictly regular and so forbids "pure" DFA implementations.

namespaceMemberDeclarations : NamespaceNodeList = namespaceMemberDeclaration*;

//Это поля объекта грамматики
//Эти для мемоизации
private mutable mutable __GENERATED_PEG__Memeoize_Pos__namespaceMemberDeclarations__ : int

private mutable mutable __GENERATED_PEG__Memeoize_End__namespaceMemberDeclarations__ : int

private mutable mutable __GENERATED_PEG__Memeoize_Res__namespaceMemberDeclarations__ : list[CSharpParser.NamespaceNode]
//Это для сообщений об ошибках.
private mutable mutable __GENERATED_PEG__MaxRollback___namespaceMemberDeclarations__ : int
//Это собственно метод который разбирает описанное выше правило
private __GENERATED_PEG__RULE__namespaceMemberDeclarations__(pos : int, text : string, result : ref list[CSharpParser.NamespaceNode]) : int
{
  unchecked 
  {
    mutable (c : char);
    _  = c;
    
    {
      mutable token_1;
      if (__GENERATED_PEG__Memeoize_Pos__namespaceMemberDeclarations__ == pos) 
      {
        when (__GENERATED_PEG__Memeoize_End__namespaceMemberDeclarations__ >= 0) result = __GENERATED_PEG__Memeoize_Res__namespaceMemberDeclarations__;
        __GENERATED_PEG__Memeoize_End__namespaceMemberDeclarations__
      }; else 
      {
        def newPos = 
        {
          token_1 = SCG.List();
          mutable token_2;
          def rep (pos : int)  
          {
            def newPos = __GENERATED_PEG__RULE__namespaceMemberDeclaration__(pos, text, ref token_2);
            if (newPos >= 0) 
            {
              token_1.Add(token_2);
              rep(newPos)
            }; else pos
          } : _ ;
          rep(pos)
        };
        __GENERATED_PEG__Memeoize_Pos__namespaceMemberDeclarations__ = pos;
        __GENERATED_PEG__Memeoize_End__namespaceMemberDeclarations__ = newPos;
        if (newPos >= 0) 
        {
          result = namespaceMemberDeclarations(token_1);
          ();
          __GENERATED_PEG__Memeoize_Res__namespaceMemberDeclarations__ = result
        }; else when (__GENERATED_PEG__MaxRollback___namespaceMemberDeclarations__ < pos) __GENERATED_PEG__MaxRollback___namespaceMemberDeclarations__ = pos;
        newPos
      }
    }
  }
}

L>Боюсь, что я этот ваш Немерле недостаточно понимаю

      constantDeclaration : TypeMember = attributes? modifiers? "const"S anyType constantDeclarators semicolon;

      fieldDeclaration    : TypeMember = attributes? modifiers? anyType variableDeclarators semicolon;

      methodDeclaration : TypeMember = attributes? modifiers? anyType typeMemberIdentifier typeParameterList? "("s formalParameterList? ")"s typeParameterConstraintsClauses? methodBody;

      propertyDeclaration     : TypeMember        = attributes? modifiers? anyType typeMemberIdentifier "{"s accessorDeclarations "}"s;

      eventDeclaration_1  : TypeMember = attributes? modifiers? "event"S anyType typeMemberIdentifier "{"s eventAccessorDeclarations "}"s;
      eventDeclaration_2  : TypeMember = attributes? modifiers? "event"S anyType variableDeclarators semicolon;
      eventDeclaration    : TypeMember = eventDeclaration_1 / eventDeclaration_2;

      indexerDeclaration  : TypeMember = attributes? modifiers? anyType (typeMemberIdentifier "."s)? "this"S "["s formalParameterList? "]"s "{"s accessorDeclarations "}"s;

      operatorDeclaration : TypeMember = attributes? modifiers? operatorDeclarator "("s formalParameterList? ")"s methodBody;

      constructorDeclaration : TypeMember = attributes? modifiers? identifier "("s formalParameterList? ")"s constructorInitializer? methodBody;

      destructorDeclaration  : TypeMember = attributes? modifiers? "~"s identifier "("s formalParameterList? ")"s methodBody;

      nestedTypeDeclaration  : TypeMember = typeDeclaration;

      typeMemberDeclaration  : TypeMember = methodDeclaration
                                          / propertyDeclaration 
                                          / fieldDeclaration
                                          / constantDeclaration
                                          / constructorDeclaration
                                          / eventDeclaration
                                          / operatorDeclaration
                                          / indexerDeclaration
                                          / destructorDeclaration
                                          / nestedTypeDeclaration
                                          / fixedSizeBufferDeclaration;

Когда это актуально можно и по пегу сишарп сгенерить.

L>А зачем тебе ссылочку? Надеюсь, месье не теоретик?

var regex = new Regex("(x+x+)+y", RegexOptions.Compiled | RegexOptions.RightToLeft);
regex.Match(string.Empty);
var stopWatch = new Stopwatch();
stopWatch.Start();
regex.Match("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
stopWatch.Stop();
Console.WriteLine("Elapsed milliseconds: " + stopWatch.ElapsedMilliseconds);
Console.WriteLine("Elapsed ticks: " + stopWatch.ElapsedTicks );

Elapsed milliseconds: 0
Elapsed ticks: 4761

T>>var regex = new Regex("(x+x+)+y", RegexOptions.Compiled | RegexOptions.RightToLeft);
T>>regex.Match(string.Empty);
T>>var stopWatch = new Stopwatch();
T>>stopWatch.Start();
T>>regex.Match("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
T>>stopWatch.Stop();
T>>Console.WriteLine("Elapsed milliseconds: " + stopWatch.ElapsedMilliseconds);
T>>Console.WriteLine("Elapsed ticks: " + stopWatch.ElapsedTicks );
T>>

L>А про RightToLeft почему не упомянул? Для меня это выглядит как попытка обмануть на невнимательности

L>Ну как, помогает?

        static Regex CreateNonBacktrackingRegex(string  pattern)
        {
            return new Regex(pattern.Replace("(", "(?>(").Replace(")","))"));
        }

        static void Main(string[] args)
        {
            var regex = CreateNonBacktrackingRegex("(x+x+)+y(x+x+)+");
            regex.Match(string.Empty);
            var stopWatch = new Stopwatch();
            stopWatch.Start();
            regex.Match("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
            stopWatch.Stop();
            Console.WriteLine("Elapsed milliseconds: " + stopWatch.ElapsedMilliseconds);
            Console.WriteLine("Elapsed ticks: " + stopWatch.ElapsedTicks );
        }

Elapsed milliseconds: 0
Elapsed ticks: 128907

J>>А то бреда можно всякого много нагенерить

Here's an unrealistic but tiny example, to get the flavor across: