Compiler-compiler
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 31.03.07 11:14
Оценка: 98 (5)
Зацените, пожалуйста, вот эту утилитку. В архиве лежат исходники и бинарники. Чтобы бинарники нормально запускались, нужно положить рядом с ними Nemerle.dll, желательно как можно более свежий.

Пока утилитка очень сырая. Например, он не принимает аргументов командной строки — единственным аргументом должно являться имя файла с описанием грамматки. Так же нет нормальной обработки ошибок на последних этапах генераии. Не все фичи пока включены. Ну и конечно, ошибки, которые не удалось выловить.

Документации пока нет. Так что разбираться придётся по следующим источникам:

1. *.bnf — файлы в папке src/Generator. Правда, эти файлы содержат не всё, что необходимо, кроме того, они несколько устарели. Единственное рабочее описание грамматики — test2.bnf.
2. проект TestParser. Собственно, парсер в нём сгенерирован утилитой по описанию из test2.bnf.

Постараюсь некоторые вещи прокомментировать. Вот кусок test2.bnf с пояснениями:

// Здесь размещается список функций, конструирующих 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;
}


Теперь по поводу самого парсера. Для нормальной работы в том же пространстве имён должны присуствовать два модуля — NodeBuilder и TokenManager. Вот как выглядит TokenManager для сгенерированного парсера:

  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)
      }
    }
  }


А вот NodeBuilder, в котором определены функции, описанные в разделе ast:

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();
      }
    }
  }
}


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

Собственно, вопрос к народу: кто-нибудь хочет мне помочь? Если некогда писать код, так хотя бы поделитесь идеями и соображениями по поводу того, что можно такого прикрутить к генератору, что изменить, а что выкинуть. Да, кстати, нужно ещё подобрать хорошее название проекту (а то не называть же exe-шник именем generator.exe).

PS: Пример из TestParser продифференцирует введённое выражение (рядом с exe-шником должен лежать файл formula.txt) по x. Это я так, повеселился чуть-чуть
... << RSDN@Home 1.2.0 alpha rev. 672>>
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.