Первый блин – комом.
August 17th, 2007
Нахваливал я тут PLY, а зря. Разбор двух с половиной мегабайтного заголовка с построением синтаксического дерева занимает верных полторы минуты. И это на AMD Opteron 250 2.4GHz. Эталонный Althon XP, по всей видимости, будет делать то же самое минут десять. Это никуда не годиться.
В профайлере наблюдается вот такая картина:
Время съедает непосредственно разбор, а не анализ результатов разбора и создание синтаксического дерева. Python-ая природа PLY сделала свое черное дело. 
Вариантов видится пока два:
- Портировать парсер на С++ и GNU Bison;
- Разобраться таки с DParser.
Второй вариант намного предпочтительнее, так как всю логику можно будет по-прежнему писать на Python.
Почитал про DParser, понравилось… А что с ним под виндоус происходит? Нет машины дома протестировать, к сожалению :/.
По-моему это все “из пушки по воробьям”
Для C надо тогда делать еще полноценный препроцессор — не проще ли, если предполагается парсить только пару-тройку определенных заголовочных файлов из platform SDK, все сделать на тупых регулярных выражениях?
Он не собирается в Visual C++ 2005 без дополнительных телодвижений. Я на днях опубликую рецепт.
Проще взять готовый. cl.exe подойдёт.
Проще. Но хочеться:
а. Красиво;
б. Что б наверняка.
Кроме того, по трудоёмкости оба способа не сильно отличаются на самом деле.
если PLY – полный аналог Lex/Yacc (Flex/Bison), то время разбора (имеется ввиду стадия лексического анализа, а не синтаксического) также сильно зависит от набора регулярных выражений, которые осуществляют распознавание токенов. Можно попробовать каким либо образом их оптимизировать. Например:
letter [A-Za-z]
word letter+
{word} {
return hashfunc(matchedtext);
}
т.е. распознавать все ключевые слова при помощи одного правила, а тип лексемы определять при помощи хэш-функции (которую тоже к стати можно сгенерировать – для С++ я пользовался gperf, в gcc им тоже к стати пользуются).
Ну и также помнить что trailing context в правилах лексического анализатора увеличивает время стадии лексического анализа (по крайней мере для Flex это справедливо – исхожу из того что PLY – аналог)
По какой -то причине мой предыдущий комментарий не засабмитился. Вкратце: лексический анализатор можно оптимизировать убрав различные trailing context в правилах и используя хеш-функции для распознавания ключевых слов языка например.
Примерно так и делается, только вместо хеш функции используется поиск по словарю. Но это как мертвому припарки. Лексер в PLY – это одно длинное регулярное выражение. На этом фоне подобная оптимизация ничего не даёт. Ну а синтаксический разбор тормозит ещё больше.
Спам фильтр сработал почему-то.
а без построения дерева обойтись никак нельзя? при помощи только одного лексического анализатора? Например написать несколько специализированных лексических анализаторов и каскадировать их работу?
Наверняка можно извернуться, но в данном случае гораздо проще пересесть на более быструю лошадь: просто взять генератор парсера побыстрее.