В топе про pdbdump to IDC (http://www.wasm.ru/forum/viewtopic.php?id=18698) я рассказывал о способах перевести листинг pdbdump в IDC. Теперь, собственно, рассмотрим 3-й вариант перевода. Что тут можно сделать: 1. парсить регекспами. прочитал строку до "\n", пропустил ее через набор регулярок, извлек, что нужно, распечатал 2. парсить ее при помощи лексера (lex) Сразу подчеркну, что цель тут - это не поднимать holy war на тему, что круче: regexp vs lexer. Все определяется целесообразностью. Очевидно, если требования - это просто построчно перевести pseudo-C в IDC, то регулярок хватит за глаза. Если бы требования стояли жестче - например, требовалось бы, скажем, проверить на корректность члены структур или выполнить развертывания typedef, то регулярки стали бы уж слишком монструозными и весь код бы стал ... ммм ... неизящным Поскольку русский человек легких путей не ищет, то, как легко догадаться, я выбрал путь посложнее и решил заюзать лексер. Поскольку одна из целей была выучить питон, то лексер я решил заюзать какой-нить питоновский. Этих лексеров там для питона, дай бог, штук 20. Поискав какое-то время, я выбрал PLY - чистый питон, достаточно удобно, достаточно шустро. Что-нить совсем монструозное брать желания не было. А дальше пошли шишки Лексер был написан примерно за 2 часа, а вот дальше я с удивлением увидел, что логика НАД лексером получается уж СЛИШКОМ сложной. Возьмем, например, что-нить вида: Код (Text): void (KernelRoutine*)(struct _KAPC*, void (**)(void*, void*, void*), void**, void**, void**); И что тут делать? Что пихать в IDC? Очевидно, KernelRoutine и обозначать ее как поинтер. А если ситуация посложнее? Например, вот такая: Код (Text): long (*)(struct _DEVICE_OBJECT*, struct _IRP*) MajorFunction[28]; то что делать тут? Брать MajorFunction? Эт правильно, вот только как узнать, что брать надо именно MajorFunction, а не, скажем, _DEVICE_OBJECT? И вот тут начинается самая веселуха. Если логика над лексером становится слишком сложной, то требуется писать уже свой анализатор синтаксиса. Слава богу, PLY имеет не только lex, но и yacc. Пришлось разбираться еще и с yacc И это было уже, скажем так, совсем весело.
Люди с опытом говорят, что отладка грамматики в наиболее сложных своих случаях имеет поганое свойство растягиваться в месяцы именно в силу дикой сложности отладки. Грамматика YACC в PLY описывается при помощи BNF: http://en.wikipedia.org/wiki/Backus-Naur_form И, действительно, начав набрасывать что-то свое самопальное в EmEditor, я очень быстро понял, что проект из хобби рискует перерости в нешуточный девелопмент длительностью эдак в месяцок. А месяца у мя на эту блажь нету... Пришлось идти по двум направлениям: 1. Взять The C Programming Language, ANSI C (2nd Edition) и буквально просмотреть ее под микроскопом. 2. Попытаться найти какие-нить тулзы, как МИНИМУМ, хотя бы для визуализации грамматики. Щедро нарипав терминалов из K&R 2nd edition и загнав их все в блокнотик, я сам очень скоро в них запутался. Пришлось чертить диаграммки на бумажке. После того как я таким макаром извел пару-тройку листов, мне это надоело и я принялся искать тулзу всерьез. Такую тулзу удалось найти. Путешествие началось отсюда: http://blog.nicksieger.com/articles/2006/10/27/visualization-of-rubys-grammar Парень нагенерил визуализаций различных грамматик. Особенно жутко выглядит Ruby. Меня заинтересовало, как выглядит Питон или, скажем, тот же С и я разрыл линки. Поглядите: http://flickr.com/photos/nicksieger/281055530/ - ANSI C http://flickr.com/photos/nicksieger/281055485/ - Python Посмотрите, как чисто, например, в сравнении с тем же Ruby. Лист грамматик языков можно найти на antlr.org: http://www.antlr.org/grammar/list Т.е. парень действовал так: 1. берет грамматику 2. засовывает ее в ANTLRWorks (http://www.antlr.org/works/index.html) - ИЗУМИТЕЛЬНАЯ тулза! 3. просит сгенерировать граф - наглядно, но достаточно бестолково Итак. Теперь, имея тулзу для отладки грамматик и книжку с этими самыми грамматиками, жизнь стала веселее. Появились шансы уложиться в недельку. Поскольку мы имеем дело лишь с подмножеством С, то смысла брать всю грамматику не было. Надо было выкинуть все ненужное, отладить это дело и засунуть в питон. Просто было на бумаге, да забыли про овраги...
Овраги заключаются в следующем. ANTLRWorks основан на ANTLR 3.0+. А это своя специфика, которая в первый день, буквально оторвала крышу. Там свой лексер + EBNF-грамматика (http://www.garshol.priv.no/download/text/bnf.html). И, если к EBNF привыкнуть достаточно просто, то от лексера в первом приближении оторвало крышу. Слишком уж много непривычных моментов. Кончилось все тем, что пришлось пойти на список грамматик и выдрать лексер из грамматики С, да присобачить его к моему. Присобаченный лексер, естественно, тоже не заработал. Закончилось это тем, что путем длительного чтения wiki с antlr.org и обработки лексера из c.g напильником, удалось получить внятный и рабочий результат для pdbdump.g. Дальше оставалось только выполнить перевод BNF из K&R 2nd edition => EBNF, чтобы можно было отлаживаться. ANTLRWorks - это просто сказка. Тулза автоматически детектит левую рекурсию и делает перевод BNF => EBNF практически автоматом. Сложностей с переносом BNF => EBNF не было никаких. Просто перегнал то, что нарипал из книжки и начал отладку. Согласитесь, одно дело смотреть на что-то вида: Код (Text): direct_declarator : (ID | '<unnamed-tag>' | '(' (type_specifier)* declarator ')') ('[' DECIMAL_LITERAL ']' | '(' parameter_type_list? ')')* ; в блокнотике, а второе дело видеть рисунок:
Но и это фигня. Самый блеск начинается при отладке. Чего, например, стоит вот этот рисунок. Был создан для кастрированой структурки: Код (Text): struct _KAPC { // static data ------------------------------------ // non-static data -------------------------------- /*<thisrel this+0x0>*/ /*|0x2|*/ short Type; /*<thisrel this+0x2>*/ /*|0x2|*/ short Size; /*<thisrel this+0x4>*/ /*|0x4|*/ unsigned long Spare0; /*<thisrel this+0x8>*/ /*|0x4|*/ struct _KTHREAD* Thread; /*<thisrel this+0xc>*/ /*|0x8|*/ struct _LIST_ENTRY ApcListEntry; /*<thisrel this+0x14>*/ /*|0x4|*/ void (KernelRoutine*)(struct _KAPC*, void (**)(void*, void*, void*), void**, void**, void**); /*<thisrel this+0x18>*/ /*|0x4|*/ void (RundownRoutine*)(struct _KAPC*); /*<thisrel this+0x1c>*/ /*|0x4|*/ void (NormalRoutine*)(void*, void*, void*); /*<thisrel this+0x20>*/ /*|0x4|*/ void* NormalContext; /*<thisrel this+0x24>*/ /*|0x4|*/ void* SystemArgument1; /*<thisrel this+0x28>*/ /*|0x4|*/ void* SystemArgument2; /*<thisrel this+0x2c>*/ /*|0x1|*/ char ApcStateIndex; /*<thisrel this+0x2d>*/ /*|0x1|*/ char ApcMode; /*<thisrel this+0x2e>*/ /*|0x1|*/ unsigned char Inserted; // base classes ----------------------------------- // friends ---------------------------------------- // static functions ------------------------------- // non-virtual functions -------------------------- // virtual functions ------------------------------ }; // <size 0x30> где была оставлена только KernelRoutine. Просто страшно было бы подумать, сколько пришлось бы отлаживать такую грамматику без таких наглядных деревьев разбора.
Ну а дальше были долгие и нудные сеансы отладки. Огромное спасибо Стиверу, энциклопедические знания которого не перестают меня поражать. Кстати, в ходе анализа был обнаружен баг в оригинальной грамматике от K&R. Я утверждаю, что грамматика в The C Programming Language, ANSI C (2nd Edition) не способна пропарсить поинтер на функцию. И файл c.g, созданный Теренсом на ее основе, так же содержит этот же самый баг. Мой парсер от такого избавлен. Спасибо ANTLRWorks за сеансы Собственно, грамматика сдалась за 4 полных дня работы. Что, разумеется, без ANTLRWorks было бы невозможно для меня в принципе. Человек опытный с уровнем знаний, например, того же Стивера, возможно, смог бы сделать чудо за 4 дня и без отладчика. С моим же опытом в таких делах, без отладчика туда не стоило бы и лезть. Итак, создав и отладив pdbdump.g на реальных данных, собсно, захотелось опять вернуться к питону и перевести добро туда. Чтобы уже можно было привинтить плевалку IDC и закончить, наконец, начатую работу. Тут, однако, немедленно встала проблема перевода EBNF => BNF. Ведь ANTLR работает в EBNF, а PLY кушает только BNF. Естественным решением казалось найти какую-нить тулзу для перегона EBNF => BNF. После недолгих блужданий была найдена Harmonia (http://www.cs.berkeley.edu/~harmonia/harmonia/index.html). По утверждениям ее многоуважаемых создателей, в ее состав входит Ladle (http://harmonia.cs.berkeley.edu/harmonia/projects/tools/index.html) => Ladle: An EBNF Translator. Среди фич которого гордо заявлена "EBNF to BNF Translation". Ну, думаю, класс. BNF => EBNF получил на халяву. Если еще и EBNF => BNF на халяву получу, то вообще лафа, а не жизнь. Попытался эту гармонию собрать... Ну, разумеется, дефолтная инструкция (http://harmonia.cs.berkeley.edu/harmonia/download/build-windows.html) оказалась некорректной и весь проект пришлось перестраивать. Поскольку у меня была 2005-студия, а проект был создан в 2003, то студия выполнила конверт и, естественно, все поломала. Приходилось доходить до того, что править vcproj ручками. Через часа 2 мучений я, таки, сумел сбилдить половину того, что необходимо для билда Ladle. Терпение мое кончилось тогда, когда astdef, который вызывается на очередном шаге, упал с AV. Вот тогда я рассвирипел и плюнул. Если кто хочет юзать эту поделку для конвертации - милости прошу, а с меня хватит. Словом, пришлось переводить руками. Руками перевел, получил конфликт shift-reduce. Там, где ANTLR выплывал на Код (Text): options {k=3;} PLY выплывать было не на чем. Как заяснил мне Стивер, не любой shift-reduce-конфликт - это обязательно плохо. Конфликты - часть жизни :-D Просто мои конфликты, как всегда, оказались самыми веселыми конфликтами. Для этого пришлось как следует, в очередной раз, перелопатить документацию PLY и написать таблицу приоритетов для разрешения таких конфликтов: Код (Text): precedence = ( ('left', 'LPAREN'), ('left', 'ENUM', 'STRUCT', 'UNION'), ) Парсер теперь собирается с 7-ю конфликтами shift-reduce, но эти конфликты уже ни на что не влияют. Собсно, на этом более или менее все.
Код парсера в аттаче. Устанавливать следующим образом: 1. http://www.activestate.com/store/download.aspx?prdGUID=b08b04e0-6872-4d9d-a722-7a0c2dea2758 - ActivePython. Например, этот: http://downloads.activestate.com/ActivePython/windows/2.4/ActivePython-2.4.3.12-win32-x86.msi 2. PLY - http://www.dabeaz.com/ply/ 3. Установить Ply. Жутко сложно Топаем внутрь пакета и давим python setup.py install 4. Собсно, распаковать архивчик и юзать pdbdump_parser.py. Наберите из командной строки и тулза сама покажет, как ее юзать. Два известных бага: 1. не знаю как обрабатывать битовые поля. как надо - так и сделаю 2. не знаю, как хендлить такой случай: Код (Text): struct vasya { struct <unnamed-tag> u } Пока что вместо unnamed-tag просто подставляется GUID. Я даже в принципе не представляю, что тут можно сделать. Такое проявляется на pdb-файлах от висты. В аттаче приложен и pdbdump.g. С ним играться при помощи ANTLRWorks. Конфигурировать ANTLRWorks так: Код (Text): java -Xms256M -Xmx512M -jar antlrworks-1.0b8.jar
Немножко теории есть тут: http://www.ddj.com/dept/database/196603535?pgno=1 О принципах действия синтаксического анализа можно почитать здесь: http://www.dabeaz.com/ply/ply.html#ply_nn22 http://en.wikipedia.org/wiki/LR_parser Что же до логики НАД yacc, то тут тоже есть над чем пофилософствовать. Если взять в качестве примера XML, то существуют два класса парсеров XML: 1. SAX 2. DOM DOM парсят весь файл целиком и дают доступ к любому узлу дерева. SAX основаны на другом принципе. На коллбеках. Произошло событие - вызать коллбек. У каждой модели есть свои плюсы и свои минусы. Yacc в PLY основан именно на принципе коллбеков, т.е. SAX. Хотя, если смотреть по истории, то сначала был yacc, а уж потом SAX Скажем более расплывчато - принцип один и тот же. И, если задача сложна, то и логика над yacc может не справится со своими обязанностями. Самая большая проблема - это то, что коллбек, в принципе, не владеет достаточной информацией обо всем дереве. Стек и глобальные переменные - вот и все, что у нас есть. Однако, если бы задача действительно была бы жутко сложной, то пришлось бы строить DOM. Для этого можно было бы использовать AST (как, собственно, компиляторы и поступают). Более подробно об AST расписано в доках PLY: http://www.dabeaz.com/ply/ply.html#ply_nn34
