Как собственно реализуется сабж?
Вопрос задан больше из любопытства, чем необходимости.
Есть некий скриптовый язык tkscript.
http://tkscript.de
Который похож по синтаксису на C++.
Компиляция проходит как обычно: сначала лексичекий анализатор разбирает текст на лексемы,
потом синтаксический анализатор строит дерево синтаксического разбора, потом дерево оптимизируется(Самими нодами дерева).
В лексический анализатор я не вдавался, вероятно там ничего особенного нет.
Дерево разбора тоже вполне осязаемо. Реализзовано ввиде классов. Корень всего class PTNode;
Далее class PTNExpression или PTNStatement. PTNExpression, как я понял то что имеет результат.
PTNStatement то что просто выполняется.
Но вот внести какие-то изменения в синт. анализатор сложно, т.к. он реализован ввиде автомата (я так думаю)
Выглядит это примерно так:
for(int toki=0;i<num_token;toki++)
{
...
tok=tokens[toki];
...
switch(state)
{
case ST_SEQ:
...
case ST_SSEQ: // single statement with TERM token ";"
switch(state_index)
{
case 0:
...
switch(tok)
{
case DXT1_BREAK:
Dpushstate;
state=ST_BREAK;
state_index=0;
break;
...
}
...
}
...
case ST_BREAK:
....
case ST_EXPRSTAT:
...
case ST_CLASSDECL:
...
}
}
Т.е. у чувака есть машина состояний у каждого из состояний есть своё собственное состояние.
В нём и происходит анализ текущеё лексемы. Есть ещё у него логический стек состояний.
В результате разбор выливается в 9000 строк кода, похожие куски встречаются по нескольку раз в разных местах
и это всё очень трудно анализировать.
Вопрос:
Почему нельзя всё это заменить цепочкой вызовов функциональных объектов(или даже просто функций), с их внутренем содержанием
которое известно только им и тем кто их использует? Если разбор на каком-то моменте не удался — генерить исключение.
Перекладывая на плечи компилятора гарантированый и корректный выход из текущей цепочки разбора.
У меня только 3 версии:
1. Машина состояний по каким-то причинам быстрее.
2. Функиональный вариант по каким-то причинам не возможен.
3. Чуваку на момент написания не хватало практики проектирования в C++
P.S.
Вообще какая-то дурная мода делать идеолагически неплохие объектные языки на C или с посредственным
использованием C++. Как пример все реализации JavaScript. даже интерпритатор плюсов (есть такой) тоже на С написан
Неужели компилятор C++ внутри такой же.
Начну с того, что чаще всего парсеры не пишутся руками, а судя по приведенному коду, это именно тот случай- парсер написан с помощью генератора парсеров. Т.е. создается формальная грамматика языка, по которой затем спец. программа генерит исходник анализатора. Делается так по нескольким причинам:
1. Генератор осуществляет проверку грамматики на возможность построения парсера, т.к. не для каждой грамматики можно создать парсер. Если ты будешь все делать руками, то можно допустить ошибку и твой парсер будет анализировать неправильно.
2. Парсер работающий на автоматах быстрее.
3. Удобство- как ты сам заметил анализировать код парсера- занятие не доля слабонервных, зато если посмотреть на формальную грамматику- все намного понятнее.
Здравствуйте, Шебеко Евгений, Вы писали:
ШЕ> Как собственно реализуется сабж?
ШЕ> Вопрос задан больше из любопытства, чем необходимости.
ШЕ> Но вот внести какие-то изменения в синт. анализатор сложно, т.к. он реализован ввиде автомата (я так думаю)
Я как-то задумался о способах реализации конечного автомата.Насчитал следующие:
1. Смотри
статью Кодта на RSDNАвтор(ы): Николай Меркин
Дата: 19.01.2002
- там описано 3 способа
2. Вместо переключателя в цикле использовать прием, который Герб Саттер упоминает: функция, возвращающая указатель на себя. Я тут уже про это писал в форуме по алгоритмам. Кстати, существенно улучшает инкапсуляцию и последующий рефакторинг, так как добавление нового состояния — это просто написание новой функции. А сам цикл в автомате — не изменяется.
3. Тот же Саттер продолжает: вместо функций, возвращающих указхатель на себя, попробуйте использовать функциональный объект. Сам не пока не пробовал, но должно получиться, поскольку ФО как раз для замены указателей на функцию придуманы были.
4. Реализуем паттерн "Интерпретатор" по регулярной грамматике — смотри книжку Банды четырех
5. И совсем уж изврат — использовать в качестве состояний секции-ловушки catch. Переход в новое состояние тогда естественно совершается посредством throw, а именем состяния является исключение.
Итого 7 способов.
Наверное, в разных случаях можно применять разные способы.
Нечто аналогичное можно придумать и для синтаксического анализатора. Просто чаще всего СА реализуются автоматически с помощью YACC/BIZON. И скорее всего эти инструменты по заявленной грамматике банально генерируют эквивалентный МП-автомат (который вы и наблюдаете)
