Есть ли какие-либо документы, описывающие, почему flex быстрее, чем lex?
flex называется "быстрым" лексическим анализатором, но я не могу найти ни одного документа, объясняющего, почему он быстрее, чем lex. У flex есть руководство, но оно сфокусировано на его использовании, а не на внутреннем. Могут ли какие-нибудь эксперты в этой области оказать некоторую помощь, пожалуйста? Приветствуется либо объяснение улучшения производительности flex, либо ссылка на него.
3 ответа
Этот ответ от Верна Паксона, и он разрешает поделиться им здесь.
Увы, это заняло бы совсем немного времени, чтобы набросать какие-либо полезные детали, так как есть ряд методов, которые способствуют его производительности. Я написал статью об этом довольно давно (в середине 80-х!), Но у меня нет ее копии. Очевидно, вы можете купить его у:
http://www.ntis.gov/search/product.aspx?ABBR=DE85000703Извините, что не помогу...
Чтобы добавить к утверждению Верна, flex намного лучше справляется со сжатием таблиц, обеспечивая несколько различных компромиссов между пространством и временем, и его внутренний цикл также значительно быстрее, чем у lex.
Согласно статье (Usenet?), Написанной van Jacobsen в 1980-х годах, lex был в значительной степени написан стажером AT&T. VJ описал, как его внутренний цикл может быть уменьшен с нескольких десятков инструкций до трех.
Верн Паксон написал flex для того, что он в то время назвал самыми быстрыми приложениями для сбора данных в мире. Не уверен, стоит ли мне вдаваться в подробности.
Я имел честь помочь Верну с 8-битной версией, так как я работал в компиляторах, которые должны были сканировать кандзи и катакана в то время.
Я не уверен flex намного быстрее, чем версия AT&T lex, Обе программы были разработаны независимо друг от друга, и во избежание путаницы с официальной версией авторы flex вероятно, выберите немного другое имя. Возможно, они намеревались генерировать более быстрые сканеры, что также предлагается несколькими вариантами, чтобы обменять пространство на время. Также они мотивируют создание %option yylineno (и несколько других функций) опционально со скоростью генерируемого сканера.
Вопрос о том, актуальны ли небольшие различия в скорости для таких сканеров, остается спорным. Я не смог найти никакого официального заявления о выборе имени, так что, я думаю, вам нужно спросить оригинальных авторов Джефа Посканзера и / или Верна Паксона. Если вы найдете их и получите ответ, пожалуйста, сообщите нам об этом здесь. История программного обеспечения интересна, и вы все равно можете получить ответ из первых рук.