// Здесь размещается список функций, конструирующих AST. Эти функции должны реально
// присутствовать в некотором модуле (NodeBuilder). Параметры этих
// функций должны совпадать с параметрами, описанными здесь. См. src/TestParser/NodeBuilder.n.
// Так же возможно описывать типы параметров после двоеточия (не тип .NET). На данный момент 
// параметры могут иметь типы node и bool, причём по умолчанию параметрам присваивается
// тип node. Соответсвенно, параметры типа node должны быть описаны как Node
// в NodeBuilder, а параметры типа bool должны быть описаны как bool в NodeBuilder.
ast
{
  fun Binary(first, op, second);
  fun Prefix(op, expr);
  fun Function(id, args);
  fun List(head, tail);
}

// Правила для лексического анализатора.
lexer (generate = false)
{
  // Подстановочные правила. Не будет создано типов лексем с именами таких правил.
  // Кроме того, эти правила видны только внутри текущего блока. Подстановочные
  // правила не могут быть рекурсивными.
  subst IdStart ::= "a".."z" | "A".."Z";
  subst Digit ::= "0".."9";
  subst IdPart ::= IdStart | Digit;
  subst Digits ::= Digit+;
  
  // А это обычные правила. По ним будут создаваться лексемы. Кроме того, на них
  // можно ссылаться из раздела parser.
  Identifier ::= IdStart IdPart*;
  Number ::= Digits ("." Digits)?;
  Space ::= " "+;
  
  // К таким правилам в разделе parser можно ссылаться не только по иднтификатору,
  // но и по строке.
  Comma ::= ",";
  Minus ::= "-";
  Plus ::= "+";
  Star ::= "*";
  Slash ::= "/";
  LeftParen ::= "(";
  RightParen ::= ")";
  
  // Так же определены операции:
  //   ~x - дополнение x 
  //   x & y - пересечение x и y
  //   x \ y - разность x и y (эквивалентно x & ~y)
  // Правда, эти операции работают только для односимвольных множеств
  // Существуют так же специальные предопределённые правила для символов Юникода и для некоторых других вещей.
  // Вот наиболее полезные: eof, any, empty.
}

// Правила для синтаксического анализатора. Синтаксис эквивалентен предыдущему разделу.
// Правда, для некоторых операций (+, *, ~, &, \) генератор напишет, что они не поддерживаются (пока).
// Нельзя использовать произвольные строки, как в lexer. Любая строка здесь рассматривается как 
// ссылка на правило из раздела lexer.
parser (type = LALR, root = Negative)
{
  // Эквивалентно Minus[op] Additive[expr] | Additive;
  Negative[Prefix] ::= "-"[op] Additive[expr] | Additive;

  // Казалось бы, можно сократить это и написать как-то так:
  //   (Additive[first] ("+" | "-")[op])? Multiplicative
  // но этот вариант неправильный, т.к. если бы свёртка произошла по правилу Additive -> Multiplicative, 
  // то была бы всё равно вызвана функция Binary с первыми двумя параметрами равными Node.Null. А
  // так ничего не вызвается, просто копируется вершина стека. Хотя, если залезть в NodeBuilder.Binary и
  // немного поменять его логику, то приемлем и сокращённый вариант.
  Additive[Binary] ::= Additive[first] ("+" | "-")[op] Multiplicative[second] | Multiplicative;
  
  Multiplicative[Binary] ::= Multiplicative[first] ("*" | "/")[op] Primitive[second] | Primitive;
  Primitive ::= Parenthesized | FunctionCall | Identifier | Number;
  Parenthesized ::= "(" Negative ")";
  FunctionCall[Function] ::= Identifier[id] "(" Args[args] ")";
  
  // А вот здесь ? допустим, т.к. для последнего элемента списка второй параметр должен быть равен null.
  Args[List] ::= Arg[head] ("," Args[tail])?;
  Arg ::= Negative;
}

  module TokenManager
  {
    public Filter(token : Token) : bool
    {
      match (token.TokenType)
      {
        | TokenType.Space 
        | TokenType.Error => false
        | _ => true
      }
    }
    
    public Eval(token : Token) : Node
    {
      match (token.TokenType)
      {
        | TokenType.Identifier => Node.Id(token.Locator, token.Text)
        // Нужно иметь ввиду небольшое ограничение (может быть, будет устранено в дальнейшем). А именно:
        // для лексем нельзя возвращать Node.Null
        | _ => Node.Token(token.Locator, token.TokenType)
      }
    }
  }

namespace Rsdn.ParserTools.Test
{
  module NodeBuilder
  {
    // Первые два параметра - loc и log, а остальные соответствуют описанию в разделе ast.
    // (правда, в дальнейшем нужно не передавать log каждый раз, а переделать NodeBuilder из
    // модуля в класс, в конструкторе которого при необходимости присутствует log)
    public Binary(loc : TextLocator, _ : IErrorLog, first : Node, op : Node, second : Node) : Node
    {
      match (op)
      {
        | Node.Token(TokenType.Plus) => Node.Function(loc, "+", [first, second])
        | Node.Token(TokenType.Minus) => Node.Function(loc, "-", [first, second])
        | Node.Token(TokenType.Star) => Node.Function(loc, "*", [first, second])
        | Node.Token(TokenType.Slash) => Node.Function(loc, "/", [first, second])
        | _ => throw Exception();
      }
    }
    
    public Prefix(loc : TextLocator, _ : IErrorLog, op : Node, expr : Node) : Node
    {
      match (op)
      {
        | Node.Token(TokenType.Minus) => Node.Function(loc, "-", [expr])
        | _ => throw Exception();
      }
    }
    
    public Function(loc : TextLocator, _ : IErrorLog, id : Node, args : Node) : Node
    {
      match ((id, args))
      {
        | (Node.Id(id), Node.List(args)) => Node.Function(loc, id, args)
        | _ => throw Exception();
      }
    }
    
    public List(loc : TextLocator, _ : IErrorLog, head : Node, tail : Node) : Node
    {
      match (tail)
      {
        | Node.List(l) => Node.List(loc, head :: l);
        | Node.Null() => Node.List(loc, [head]);
        | _ => throw Exception();
      }
    }
  }
}

K>// Здесь размещается список функций, конструирующих AST. Эти функции должны реально
K>// присутствовать в некотором модуле (NodeBuilder).

K>// Параметры этих
K>// функций должны совпадать с параметрами, описанными здесь. См. src/TestParser/NodeBuilder.n.

K>// Так же возможно описывать типы параметров после двоеточия (не тип .NET).

K>// На данный момент 
K>// параметры могут иметь типы node и bool, причём по умолчанию параметрам присваивается
K>// тип node. Соответсвенно, параметры типа node должны быть описаны как Node
K>// в NodeBuilder, а параметры типа bool должны быть описаны как bool в NodeBuilder.
K>ast
K>{
K>  fun Binary(first, op, second);
K>  fun Prefix(op, expr);
K>  fun Function(id, args);
K>  fun List(head, tail);
K>}

K>// Правила для синтаксического анализатора. Синтаксис эквивалентен предыдущему разделу.
K>// Правда, для некоторых операций (+, *, ~, &, \) генератор напишет, что они не поддерживаются (пока).
K>// Нельзя использовать произвольные строки, как в lexer. Любая строка здесь рассматривается как 
K>// ссылка на правило из раздела lexer.

K>parser (type = LALR, root = Negative)
K>{
K>  // Эквивалентно Minus[op] Additive[expr] | Additive;
K>  Negative[Prefix] ::= "-"[op] Additive[expr] | Additive;

K>  // Казалось бы, можно сократить это и написать как-то так:
K>  //   (Additive[first] ("+" | "-")[op])? Multiplicative
K>  // но этот вариант неправильный, т.к. если бы свёртка произошла по правилу Additive -> Multiplicative, 
K>  // то была бы всё равно вызвана функция Binary с первыми двумя параметрами равными Node.Null. А
K>  // так ничего не вызвается, просто копируется вершина стека. Хотя, если залезть в NodeBuilder.Binary и
K>  // немного поменять его логику, то приемлем и сокращённый вариант.
K>  Additive[Binary] ::= Additive[first] ("+" | "-")[op] Multiplicative[second] | Multiplicative;
  
K>  Multiplicative[Binary] ::= Multiplicative[first] ("*" | "/")[op] Primitive[second] | Primitive;
K>  Primitive ::= Parenthesized | FunctionCall | Identifier | Number;
K>  Parenthesized ::= "(" Negative ")";
K>  FunctionCall[Function] ::= Identifier[id] "(" Args[args] ")";
  
K>  // А вот здесь ? допустим, т.к. для последнего элемента списка второй параметр должен быть равен null.
K>  Args[List] ::= Arg[head] ("," Args[tail])?;
K>  Arg ::= Negative;
K>}
K>

K>PS: Пример из TestParser продифференцирует введённое выражение (рядом с exe-шником должен лежать файл formula.txt) по x. Это я так, повеселился чуть-чуть

Идентификатор ::= "строка";

if (x < 50)
    if (x < 25)
        if (x < 12)
            0
        else
            1
    else 2
else -1

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

Identifier ::= identifier | "get" | "set" | "yield";

K>if (x < 50)
K>    if (x < 25)
K>        if (x < 12)
K>            0
K>        else
K>            1
K>    else 2
K>else -1
K>

using Nemerle.Utility;
using Nemerle.Imperative;
using System;
using System.IO;
using Rsdn.ParserTools;


namespace Rsdn.ParserTools.Benchmark
{
  [assembly:Bnf(
    bnf
    {
      lexer
      {
        Comment ::= SingleLineComment | DelimitedComment;
        subst SingleLineComment ::= "//" CommentInputChar* (NewLineChar | "\u000D" "\u000A");
        subst CommentInputChar ::= ~NewLineChar;
        subst NewLineChar ::= "\u000D" | "\u000A" | "\u0085" | "\u2028" | "\u2029" | eof;
        subst DelimitedComment ::= "/*" (~"*" | "*"+ ~"/")* "*"+ "/" | eof;
        Whitespace ::= (PureWhitespace | NewLineChar | eof)+;
        subst PureWhitespace ::= U_Zs | "\u0009" | "\u000B" | "\u000C";
        subst UnicodeEscapeSequence ::=
          "\\u" HexDigit HexDigit HexDigit HexDigit |
          "\\U" HexDigit HexDigit HexDigit HexDigit HexDigit HexDigit HexDigit HexDigit;
        subst HexDigit ::= "0".."9" | "A".."F" | "a".."f";
        Identifier ::= "@"? IdentifierStartCharacter IdentifierPartCharacter*;
        subst IdentifierStartCharacter ::= U_Ll | U_Lu | U_Lt | U_Lm | U_Lo | 
            UnicodeEscapeSequence | "_";
        subst IdentifierPartCharacter ::=
            U_Nl | U_Ll | U_Lu | U_Lt | U_Lm | U_Lo | U_Nd |
            UnicodeEscapeSequence | U_Mc | U_Mn | "_";
          
        Keyword ::=
            "abstract" | "as" | "base" | "bool" | "break" | "byte" | "case" | "catch" |
            "char" | "checked" | "class" | "const" | "continue" | "decimal" | "default" |
            "delegate" | "do" | "double" | "else" | "enum" | "event" | "explicit" |
            "extern" | "false" | "finally" | "fixed" | "float" | "for" | "foreach" |
            "goto" | "if" | "implicit" | "in" | "int" | "interface" | "internal" | "is" |
            "lock" | "long" | "namespace" | "new" | "null" | "object" | "operator" |
            "out" | "override" | "params" | "private" | "protected" | "public" | "readonly" |
            "ref" | "return" | "sbyte" | "sealed" | "short" | "sizeof" | "stackalloc" |
            "static" | "string" | "struct" | "switch" | "this" | "throw" | "true" |
            "try" | "typeof" | "uint" | "ulong" | "unchecked" | "unsafe" | "ushort" |
            "using" | "virtual" | "void" | "volatile" | "while";
        
        RealLiteral ::=
            DecimalDigit+ "." DecimalDigit+ ExponentPart? RealTypeSuffix? |
            "." DecimalDigit+ ExponentPart? RealTypeSuffix? |
            DecimalDigit+ ExponentPart? RealTypeSuffix? |
            DecimalDigit+ RealTypeSuffix?;
        IntegerLiteral ::= DecIntLiteral | HexIntLiteral;
        subst DecIntLiteral ::= DecimalDigit+ IntegerTypeSuffix?;
        subst DecimalDigit ::= "0".."9";
        subst LSuff ::= "L" | "l";
        subst USuff ::= "U" | "u";
        subst IntegerTypeSuffix ::= USuff | LSuff | USuff LSuff | LSuff USuff;
        subst HexIntLiteral ::= ("0x" | "0X") HexDigit+ IntegerTypeSuffix?;
        subst ExponentPart ::= ("e" | "E") Sign? DecimalDigit+;
        subst Sign ::= "+" | "-";
        subst RealTypeSuffix ::= "F" | "f" | "D" | "d" | "M" | "m";
        CharLiteral ::= "'" Character "'";
        subst Character ::=
          SingleCharacter | SimpleEscapeSequence |
          HexEscapeSequence | UnicodeEscapeSequence;
        subst SingleCharacter ::= ~("\u0027" | "\u005C" | NewLineChar);
        subst SimpleEscapeSequence ::=
          "\\'" | "\\\"" | "\\\\" | "\\0" | "\\a" | "\\b" |
          "\\f" | "\\n" | "\\r" | "\\t" | "\\v";
        subst HexEscapeSequence ::= "\\x" HexDigit HexDigit? HexDigit? HexDigit?;
        StringLiteral ::= RegularStringLiteral | VerbatimStringLiteral;
        subst RegularStringLiteral ::= "\"" RegularStringChar* "\"";
        subst RegularStringChar ::= ~("\u0022" | "\u005C" | NewLineChar) |
          SimpleEscapeSequence | HexEscapeSequence | UnicodeEscapeSequence;
        subst VerbatimStringLiteral ::= "@\"" VerbatimStringChar* "\"";
        subst VerbatimStringChar ::= ~"\"" | "\"\"";
        
        Brace ::= "{" | "}";
        Paren ::= "[" | "]" | "(" | ")";
        Dot ::= ".";
        Comma ::= ",";
        Semicolon ::= ";";
        
        Symbol ::=
            ":" | "::" | "+" | "-" | "*" | "/" | "%" | "&" | "|" | "^" | "!" |
            "~" | "=" | "<" | ">" | "?" | "??" | "++" | "--" | "&&" | "||" |
            "<<" | ">>" | "==" | "!=" | "<=" | ">=" | "+=" | "-=" | "*=" |
            "/=" | "%=" | "&=" | "|=" | "^=" | "<<=" | ">>=" | "->";
        Preprocessor ::= "#" (any \ NewLineChar)*;

        /*
         *  Hacks
         */
        IntegerLiteral_Dot ::= DecIntLiteral ".";
      }
    }
  )]

  module Starter
  {
    Main(args : array[string]) : void
    {
      def url = args[0];
      def reader = StreamReader(url);
      def lexer = LexerHelper(reader, url);
      
      def start = DateTime.Now.Ticks;
      mutable count = 0;
      while (true)
      {
        def token = lexer.GetToken();
        when (token.TokenType == TokenType.Eof)
          break;
        count++;
      }
      def end = DateTime.Now.Ticks;
      def elapsed = (end - start) / 10000;
      reader.Close();
      
      Console.WriteLine($"elapsed: $elapsed, tokens: $count");
    }
  }
}

match (n)
{
    0 => ...
    1 => ...
    2 => ...
    ...
}

• сгенерированнный лексер — 6062 мс
  
• макролексер — 6671 мс