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

Опитвам се да напиша библиотека за многократно анализиране (за забавление).

Написах Lexer клас, който генерира последователност от Tokens. Token е базов клас за йерархия от подкласове, всеки от които представлява различен тип токен, със свои специфични свойства. Например, има подклас LiteralNumber (произлизащ от Literal и чрез него от Token), който има свои собствени специфични методи за работа с числената стойност на неговата лексема. Методите за работа с лексемите като цяло (извличане на тяхното представяне на символен низ, позиция в източника и т.н.) са в базовия клас, Token, тъй като те са общи за всички типове токени. Потребителите на тази йерархия на класове могат да извлекат свои собствени класове за конкретни типове токени, които не са предвидени от мен.

Сега имам клас Parser, който чете потока от токени и се опитва да ги съпостави със своята дефиниция на синтаксис. Например има метод matchExpression, който от своя страна извиква matchTerm, а този извиква matchFactor, който трябва да тества дали текущият токен е Literal или Name (и двата получени от Token базов клас).

Проблемът е:
Сега трябва да проверя какъв е типът на текущия токен в потока и дали съответства на синтаксиса или не. Ако не, хвърлете EParseError изключение. Ако отговорът е да, действайте съответно, за да получите стойността му в израза, генерирайте машинен код или направете всичко, което анализаторът трябва да направи, когато синтаксисът съвпада.

Но съм чел много за това, че проверката на типа по време на изпълнение и вземането на решение от него е лош дизайн и трябва да се преработи като полиморфни виртуални методи. Разбира се, съгласен съм с това.

Така че първият ми опит беше да поставя някакъв type виртуален метод в Token базовия клас, който да бъде заменен от производните класове и да върне някои enum с идентификатор на тип.

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

Бих могъл също да върна някои string от метода type, което би позволило лесно дефиниране на нови типове.

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

И, разбира се, класът Parser, който също е предназначен за разширяване от потребителите (тоест, писане на техни собствени парсери, разпознаване на техните собствени токени и синтаксис) не знае какви наследници на класа Token ще има в бъдеще.

Много често задавани въпроси и книги за дизайн препоръчват в този сценарий да се вземе поведението от кода, който трябва да реши по тип, и да се постави във виртуалния метод, заменен в производни класове. Но не мога да си представя как мога да вкарам това поведение в Token потомците, защото не е техен бизнес, например, да генерират машинен код или да оценяват изрази. Освен това има части от синтаксиса, които трябва да съвпадат с повече от един токен, така че няма конкретен токен, в който да вложа това поведение. Това е по-скоро отговорност на определени синтаксични правила, които могат да съпоставят повече от един токен като техните терминални символи.

Някакви идеи как да подобря този дизайн?


c++ types parsing tokenize class-design
person SasQ    schedule 09.09.2011    source източник
comment
+1, задавам си един и същ въпрос всеки път, когато пиша анализатор (и съм написал няколко).   -  person Konrad Rudolph    schedule 09.09.2011
comment
Бих цитирал стилово ръководство на Google: Не внедрявайте ръчно заобиколно решение, подобно на RTTI. Аргументите срещу RTTI се отнасят също толкова за заобиколни решения като йерархии на класове с маркери за тип. Лично аз не съм съгласен, че проверката на типа по време на изпълнение е винаги лошо нещо.   -  person user396672    schedule 09.09.2011
comment
Знам обосновката зад предпочитането на RTTI вместо ръчно изработени етикети. Това е точно проблемът, който описах в моя въпрос по-горе (макар и вероятно не достатъчно подробен). Търся начин да заменя този подход тип маркер с нещо по-добро и по-гъвкаво, което вече е в езика. Но също така чух за несъответствия при използването на тези вградени RTTI механизми (непреносимост, загуба на производителност и т.н.), така че съм любопитен дали е много по-добре.   -  person SasQ    schedule 09.09.2011
comment
Не преоткривайте квадратно колело, проверете boost::spirit например.   -  person Gene Bushuyev    schedule 13.09.2011
comment
@Gene: Освен за учене или когато можете да го направите по-добър и по-подходящ за собствената си употреба (напр. пропуснах духа поради големи времена за компилиране за проста LISP-подобна граматика с основен диагностичен изход; LLVM беше най-подходящият, но пропуснах и това, тъй като инжектира огромна зависимост в моя проект)   -  person Sebastian Mach    schedule 14.09.2011
comment
@phresnel -- ако времето за компилиране е проблем, маркирайте AX тогава, компилирането е много бързо и дори е по-лесно за използване; но във всеки случай използването на полиморфизъм (или по-лошо изрична проверка на типа) е ужасна идея за анализатор.   -  person Gene Bushuyev    schedule 14.09.2011
comment
@Gene: Затова написах (за забавление) в самото начало на въпроса си. Бих използвал Spirit, ако не беше само за забавление и за учебни цели. Но благодаря за съвета. Пишете, че използването на полиморфизъм (или по-лошо изрична проверка на типа) е ужасна идея за анализатор (което също знам), но не сте написали кое е ПО-ДОБРО. Така че всъщност не отговорихте на въпроса ми, а само се опитахте да бъдете умник, което изобщо не ми помага.   -  person SasQ    schedule 15.09.2011
comment
@Gene: Доколкото виждам, AX не е нито безплатен софтуер, нито кръстосана платформа, което е жалко, тъй като мисля, че C++0x е подходящ за такива неща. Също така: Проверката на типове няма нищо общо с полиморфизма и мисля, че ако използвате правилно полиморфизма, това може да бъде страхотен инструмент за авторски анализатори, както и функционални парадигми или аспектно ориентирани. Дори boost::spirit е полиморфен и мисля, че AX е също.   -  person Sebastian Mach    schedule 15.09.2011

Отговори (1)


arrow_upward
3
arrow_downward

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, но се отменя САМО в класовете Numeric, за да върне true. Ако предоставите имплементации по подразбиране за вашите виртуални функции и позволите на подкласовете да отменят само когато трябва, тогава голяма част от вашите проблеми ще изчезнат.

RTTI не е толкова лош TM, колкото беше преди. Проверете датите на статиите, които четете. Човек може също да твърди, че указателите са много лоша идея, но тогава ще стигнете до езици като Java.

person jcoffland    schedule 09.09.2011