Хочу привлечь желающих к проекту "макроса построителя парсеров на основе 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#-код!