PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.03.10 20:09
Оценка:
Хочу привлечь желающих к проекту "макроса построителя парсеров на основе PEG-нотации", сокращенно "PEG-парсер", или еще более сокращенно nPEG.

Цель этого проекта разработать макрос который позволял бы описывать грамматику компьютерных языков (например, языков программирования) в формате PEG и получать (во время компиляции или во время работы в IDE) парсер соответствующий описанной грамматике.

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

Вот требования которые предъявляемые к этому проекту:
1. Скорость работы. Парсер полученный с помощью nPEG должен максимально быстро парсить LL(1)-грамматики и приемлемо быстро грамматики LL(*) (т.е. с неограниченным заглядыванием вперед).
2. Должна поддерживаться нотация PEG (в том числе предикаты).
3. Парсер должен поддерживать модульность. Пока что предполагается, что от класса в котором реализуется парсер можно будет унаследовать другие классы в которых можно будет изменять (дополнять, изменять или упрощать) исходную грамматику, но возможно, что стоит внести и более мощные методы расширения (подключение нескольких грамматик).
4. Реакции (т.е. код который должен выполняться в те моменты когда парсер распознает ту или иную конструкцию описанную в грамматике) должны оформляться отдельными методами и находиться внутри классов, а не внутри описания грамматики (как это происходит в большинстве современных построителях парсеров).

Заготовка проекта находится здесь, т.е. в репозитории Nemerle.

Чтобы получить доступ на запись в репозиторий Nemerle нужно прислать мне гуглеый экаунт (это может быть адрес на gmail или экаунт заведенный на code.google.com).

Вот пример простого калькулятора описанного с помощью данного макроса:
  [PegGrammar(start,
  grammar
  {
    any            = ['\u0000'..'\uFFFF'];
    digit          = ['0'..'9'];
    spaces         = ' '*;
    num      : int = digit+ spaces;

    expr0          = opAdd / opSub / expr1;
    opAdd    : int = expr1 '+' spaces expr0;
    opSub    : int = expr1 '-' spaces expr0;

    expr1          = opDiv / opMul / expr2;
    opDiv    : int = expr2 '/' spaces expr1;
    opMul    : int = expr2 '*' spaces expr1;

    expr2    : int = num / brackets;

    brackets : int = ('(' spaces expr0 ')' spaces)

    start          = spaces expr0 spaces !any;
  })]
  class CalcGrammar
  {
    // этот обработчик вызывается после окончания разбора правила "num"
    num(digitsTok : TokenInfo, _spacesTok : TokenInfo) : int
    {
      int.Parse(digitsTok.GetString())
    }

    // этот обработчик вызывается после окончания разбора правила "brackets"
    brackets(_leftBracket : TokenInfo, _spaces1 : TokenInfo, expr0 : int, _rightBracket : TokenInfo, _spaces2 : TokenInfo) : int
    {
      expr0
    }

    // этот обработчик вызывается после окончания разбора правила "opAdd"
    opAdd(expr1 : int, _pluseTok : TokenInfo, _spaces : TokenInfo, expr0 : int) : int
    {
      expr1 + expr0
    }
  
    // Остальные правила опущены ...
  }


На сегодня реализовано:
1. Разбор PEG-грамматики приведенной выше.
2. Генерация простого сопоставления.

На сегодня не реализовано:
1. Распознавание обработчиков и подстановка их вызовов в код парсера (генерируемый в процессе работы макроса).
2. Обработка ошибок (распознавание ошибочных ситуаций и вывод информации о них для пользователя конечного парсера).
3. Разного рода оптимизации и то что пока даже представить себе сложно .

Основной код парсера написан WolfHound. Код распознавания грамматики — мной.

Описание файлов:
1. Тесты.
2. Macro.n — описание макросов grammar и PegGrammar, а так же GrammarImpl в котором сведена низкоуровневая логика генерации парсера (т.е. логика работы макроса PegGrammar). Макрос grammar — это небольшой трюк заставляющий немерловый компилятор не парсить код грамматики по правилам немерле, а хранить ее в виде токена. Данный токен извлекается и обрабатывается макросом PegGrammar (а точнее функций Parsing.ParseRules).
3. Parsing.n — код производящий парсинг токена из макроса grammar и преобразующий его в AST-парсера описываемое вариантным типом Rule. Это обычный нисходящий рекурсивный парсер написанный врукопашную. Единственная его особенность он разбирает токены немерле, а не входную строку.
4. Rule.n — variant Rule — можно сказать AST парсера (внутреннее представление правил). Вот как он выглядит:
  internal variant Rule
  {
    | Choice         { rules : list[Rule]; }
    | Sequence       { rules : list[Rule]; }
    | Call           { name : string; }
    | RepeatMin      { minCount : int; rule : Rule; }
    | RepeatMinMax   { minCount : int; maxCount : int; rule : Rule; }
    | Chars          { chars : list[RangeSet]; }
    | Not            { rule : Rule; }
    | And            { rule : Rule; }
    | Capture        { name : string; argType : RuleType; retType : RuleType; rule : Rule; }
    | ExtensionPoint { name : string; }
...

5. RangeSet.n — описание класса RangeSet хранящего (и управляющего) диапазонами символов.
6. Grammar.n — класс в котором формируется грамматике (не уверен, лучше спросить WolfHound-а).
7. Optimizer.OptimizeGrammar.n — оптимизация грамматики (сокращение путем обледенения с другими правилами и выбрасывания лишнего). Фактически просто формирует новую грамматику помещая в нее оптимизированные правила (см. пункт 8).
8. Optimizer.OptimizeRule.n — оптимизация правил.
9. RuleCompiler.CompileRule.n — преобразование грамматики (в виде AST на базе вариантного типа Rule) в код парсера, т.е. генерация кода парсера. Собственно самый недописанный кусок.

Задача простая — довести все это до кондиции (т.е. до того момента когда генератор парсеров можно будет использовать в реальных проектах).

ЗЫ

Клятвенно обещаю, что как только макрос заработает как надо, я напишу, с его помощью, грамматику для C# 3.0 (точнее его подтипа не использующего небезопасный код) и сделаю так, чтобы немерле мог компилировать большую часть C#-код!
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.