Классовая иерархия токенов и проверка их типа в парсере - PullRequest
Новая
       16

Классовая иерархия токенов и проверка их типа в парсере

10 голосов
/ 09 сентября 2011

Я пытаюсь написать многократно используемую библиотеку (для забавы).

Я написал класс Lexer, который генерирует последовательность Tokens.Token - это базовый класс для иерархии подклассов, каждый из которых представляет отдельный тип токена со своими собственными специфическими свойствами.Например, существует подкласс LiteralNumber (производный от Literal и через него от Token), который имеет свои собственные специальные методы для работы с числовым значением своей лексемы.Методы для работы с лексемами в целом (получение их символьного представления строки, положения в источнике и т. Д.) Находятся в базовом классе Token, поскольку они являются общими для всех типов токенов.Пользователи этой иерархии классов могут получить свои собственные классы для определенных типов токенов, которые я не предсказал.

Теперь у меня есть класс Parser, который читает поток токенов и пытается сопоставить их с определением синтаксиса.Например, у него есть метод matchExpression, который в свою очередь вызывает matchTerm, а этот - matchFactor, который должен проверить, является ли текущий токен Literal или Name (оба получены из Token baseкласс).

Проблема: Мне нужно проверить, какой тип текущего токена в потоке и соответствует ли он синтаксису или нет.Если нет, выведите исключение EParseError.Если да, действуйте соответствующим образом, чтобы получить его значение в выражении, сгенерировать машинный код или сделать все, что нужно парсеру, когда синтаксис совпадает.

Но я много читал об этой проверке типа во время выполнения,и, исходя из этого, это плохой дизайн ™ , и он должен быть реорганизован как полиморфные виртуальные методы.Конечно, я согласен с этим.

Итак, моей первой попыткой было поместить некоторый виртуальный метод type в базовый класс Token, который будет переопределен производными классами и вернет некоторое значение enum свведите id.

Но я уже вижу недостатки этого подхода: пользователи, производные от Token своих собственных классов токенов, не смогут добавлять дополнительные идентификаторы в enum, который находится в библиотеке.источник!: - / И целью было дать им возможность расширить иерархию для новых типов токенов, когда им это понадобится.

Я мог бы также вернуть немного string из метода type, что позволило быдля простого определения новых типов.

Но, тем не менее, в обоих этих случаях информация о базовых типах теряется (из метода type возвращается только листовой тип), и класс Parser не сможетобнаруживать производный тип Literal, когда кто-то будет наследовать его, и переопределять type, чтобы возвращать что-то отличное от "Literal".

И, конечно, класс Parser, который также предназначен для расширенияпользователи (то есть пишущие собственные парсеры, распознающие собственные токены и синтаксис) не знают, какие потомки класса Token появятся в будущем.

Многие часто задаваемые вопросы и книги по дизайну рекомендуютв этом сценарии нужно взять поведение из кода, который необходимо определить по типу, и поместить его в виртуальный метод, переопределенный в производных классах.Но я не могу себе представить, как я могу поместить это поведение в потомков Token, потому что это не их бизнес, например, генерировать машинный код или оценивать выражения.Более того, есть части синтаксиса, которые должны соответствовать более чем одному токену, поэтому нет ни одного конкретного токена, в который я мог бы поместить это поведение.Скорее, это ответственность отдельных синтаксических правил , которые могут соответствовать более чем одному токену в качестве терминальных символов.

Есть идеи, как улучшить этот дизайн?

1 Ответ

3 голосов
/ 10 сентября 2011

RTTI хорошо поддерживается всеми основными компиляторами C ++. Это включает как минимум GCC, Intel и MSVC. Проблемы переносимости действительно остались в прошлом.

Если это синтаксис, который вам не нравится, вот хорошее решение RTTI: 

class Base {
public:
  // Shared virtual functions
  // ...

  template <typename T>
  T *instance() {return dynamic_cast<T *>(this);}
};

class Derived : public Base {
  // ...
};

// Somewhere in your code
Base *x = f();

if (x->instance<Derived>()) ;// Do something

// or
Derived *d = x->instance<Derived>();

Распространенной альтернативой RTTI для анализатора AST, использующего перегрузку виртуальных функций, без сохранения собственного перечисления типов, является использование шаблона посетителя, но, по моему опыту, он быстро становится PITA. Вы все еще должны поддерживать класс посетителя, но это может быть подклассом и расширено. В итоге вы получите много стандартного кода, чтобы избежать RTTI.

Другой вариант - просто создать виртуальные функции для интересующих вас синтаксических типов. Например, isNumeric (), который возвращает false в базовом классе Token, но переопределяется ТОЛЬКО в числовых классах для возврата true. Если вы предоставляете реализации по умолчанию для своих виртуальных функций и позволяете подклассам переопределять только тогда, когда это необходимо, большая часть ваших проблем исчезнет.

RTTI не так плох, как раньше. Проверьте даты на статьях, которые вы читаете. Можно также утверждать, что указатели - очень плохая идея, но в итоге вы получите языки, подобные Java.

...