Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 68
Неплохо было бы сделать это все ввиде плагина к браузеру.
Что-то я не смог понять почему вас не устроил Pygments для подсветки кода.
Велосипеды делаются по незнанию и, реже, от избытка энтузиазма.
А что плохого в изобретении велосипедов? Фарадей не знал, что электромагнитные явления могут описываться уравнениями и изобрел силовые линии. Так теперь силовым линиям учат школьников, а полные уравнения дают только студентам физмата. И таких примеров полно. Любая задача может быть — и должна! — быть решена несколькими способами. Так что на мой взгляд велосипеды — это хорошо
На мой взгляд лучше, если велосипедостроение начинается после изучения сущесвующих альтернатив.
Обычно такое изучение заканчивается словами «Че я буду париться, все ведь уже придумано». Если конечно это не научная работа. Мое мнение — сначала сформируй идею, а потом ищи альтернативные решения, на случай если такая идея уже была и получила (а если не получила — то почему) развитие.
Понимаете ли, программирование — моя профессия. Я этим себе на хлеб с маслом зарабатываю.
И предпочитаю быть честным с заказчиком. Сначала смотрю, не сделано ли желаемое кем-то другим.
Разбираюсь в имеющихся реализациях (это практически всегда быстрее, чем писать с нуля).
Чтобы можно было выдать какое-то подобие экспертной оценки: есть варианты А и Б, для каждого приложить список достоинств и недостатков. Если свой велосипед выглядит привлекательным решением — он тоже прикладывается. Очевидный недостаток — на изобретение требуется время и, соответственно, деньги. Иногда (не слишком часто) — достоинства перевешивают.
Как-то так. Оба подхода: «чё я буду париться, все ведь уже придумано» или «свой велосипед любой ценой» — выглядят одинаково непрофессионально, вы уж извините. Основывать работу на них не стоит.
И предпочитаю быть честным с заказчиком. Сначала смотрю, не сделано ли желаемое кем-то другим.
Разбираюсь в имеющихся реализациях (это практически всегда быстрее, чем писать с нуля).
Чтобы можно было выдать какое-то подобие экспертной оценки: есть варианты А и Б, для каждого приложить список достоинств и недостатков. Если свой велосипед выглядит привлекательным решением — он тоже прикладывается. Очевидный недостаток — на изобретение требуется время и, соответственно, деньги. Иногда (не слишком часто) — достоинства перевешивают.
Как-то так. Оба подхода: «чё я буду париться, все ведь уже придумано» или «свой велосипед любой ценой» — выглядят одинаково непрофессионально, вы уж извините. Основывать работу на них не стоит.
Программирование — неотъемлемая часть и моей профессии. И я с Вами согласен — но только для крупных проектов, где собственно успех зависит от качества модели предметной области. А в решении небольших подзадач использование готовых «хороших» или «популярных» решений — это далеко не всегда так хорошо. Да, на изобретение требуется время, но лучше потерять немного времени чем потерять хорошую идею
И уж простите, но честность с заказчиком не исключает возможность предложить свое решение. А если ориентироваться на других — всегда будешь только догонять
Что-то я потерял нить разговора.
Насколько вижу, всё начиналось с максимы: «Перед созданием своего решения изучи существующие альтернативы».
Похоже, вы с этим не согласны — рассматривать готовые решения следует только для мегапроектов, а во всех случаях нужно изобретать колесо с шашкой наголо. Мне такой подход чужд.
Насколько вижу, всё начиналось с максимы: «Перед созданием своего решения изучи существующие альтернативы».
Похоже, вы с этим не согласны — рассматривать готовые решения следует только для мегапроектов, а во всех случаях нужно изобретать колесо с шашкой наголо. Мне такой подход чужд.
Не совсем. Я хочу сказать, что изобретения велосипедов не надо чураться, это не зло в последней ипостаси и уж никак не признак непрофессиализма. Я не знал о существовании pygments. Сейчас знаю — и вижу, что в перспективе он может не дать того результата, который мне нужен. Если бы знал о нем до того, как начал искать решение, вероятно, его бы и использовал. И грабли вылезли бы позже, когда что-то переделывать стало бы влом — программа-то бытовая
Я не пытаюсь навязать свою точку зрения, просто говорю, что если есть библиотека N, которая решает эту задачу (т.н. «существующее решение») — не надо ее закрыв глаза использовать, даже если граблей пока не видно. Может ваш велосипед окажется лучше созданного до тебя
Я не пытаюсь навязать свою точку зрения, просто говорю, что если есть библиотека N, которая решает эту задачу (т.н. «существующее решение») — не надо ее закрыв глаза использовать, даже если граблей пока не видно. Может ваш велосипед окажется лучше созданного до тебя
Не знал о таком. Вероятно, устроил бы
Тут еще такой момент. В мои планы не входило делать описания для всех языков, описываю синтаксические конструкции только тех, которыми владею. А пользователю может потребоваться подсветить код на другом языке, может, даже собственного производства. И этот абстрактный пользователь может и не быть спецом в питоне. Тогда pygments не устроит. А регулярки — вещь известная большинству IT-специалистов
Открываем исходники pygments…
О чудо! Внутри лексеров тоже — регулярки!
Или у вас они какие-то особенные, понятные детям и домашним животным?
О чудо! Внутри лексеров тоже — регулярки!
Или у вас они какие-то особенные, понятные детям и домашним животным?
у вас ведь опенсорс?
так поместите его в гитхаб!
так поместите его в гитхаб!
Еще один одаренный человек пытается делать парсинг кода регулярками.
Есть другие предложения?
Описать грамматику в терминах БНФ и сделать нормальный парсер.
Чудесное предложение. ЗАЧЕМ? Вы предлагаете собрать автомобиль только чтоб на радиаторе яичницу пожарить
Парсеров в сети — жопой жуй, описания грамматик тоже можно легко и непринужденно найти. Собрать парсер на генераторе — дело пяти минут, а работать будет быстрее и эффективнее — допустима будет подсветка ключевых слов в контексте (например, в C# value является ключевым словом только в контексте объявления свойства).
Я могу сказать только одно — действуйте. И посмотрим, после скольки языков у вас руки отсохнут. А вот что работать будет эффективнее — это откровенная ложь. Потрудитесь посмотреть сложность алгоритмов синтаксического разбора и сравнить со сложностью сопоставления с регулярным выражением.
А парсеров в сети — много, да. Но вы уверены в их качестве, устойчивости к ошибкам, соответствии стандартам? Я нет. И не для всех языков они есть. Составите, к примеру, по-быстрому за пять минут в генераторе полный парсер для Haskell — лично сниму перед Вами шляпу.
А парсеров в сети — много, да. Но вы уверены в их качестве, устойчивости к ошибкам, соответствии стандартам? Я нет. И не для всех языков они есть. Составите, к примеру, по-быстрому за пять минут в генераторе полный парсер для Haskell — лично сниму перед Вами шляпу.
И в основе ЛЮБОГО парсера все те же регулярные выражения. Читайте теорию
Tell me moar, plz
В статье после слов «Вспомним теорию». Не верите тому что там написано — Вирт вам в руки, «Построение компиляторов», или Книгу Дракона Ахо и Ульмана
Вот из Дракона цитату пожалуйста.
Я не буду Вам цитировать Дракона. Просто ответьте на вопрос: как парсер вытаскивает лексемы языка из исходной последовательности символов. Ну и про иерархию грамматик Хомского хотя бы в Википедии прочитайте
То есть вам все-таки имеет смысл напомнить, что КС-грамматики и автоматные грамматики — это два разных класса грамматик, и большинство языков программирования описываются первой, а не второй?
А слово «иерархия» вам не о чем не говорит? По иерархии Хомского КС-грамматики — 2-й тип, а регулярные — 3-й. Множество грамматик с большим номером по иерархии Хомского входит в множество грамматик с меньшим номером как подмножество. Советую все-таки перечитать теорию.
Ключевое слово — подмножество.
Именно. Регулярное выражение определяет один-единственный класс лексем. А КС-грамматики описываются в БНФ как раз с использованием этих самых лексем. Посему повторяю вопрос: как парсер вытаскивает лексемы языка из исходной последовательности символов. Если Вы знаете способ без использования регулярных выражений — просветите меня
Эммм… по-моему вы слегка запутались.
Парсер вытаскивает лексемы из исходной последовательности символов простым сравнением текущей лексемы с возможными вариантами. Никаких регулярных выражений здесь никогда и не было, а если бы они были тут — даже простейшая программа компилировалась бы до третьего пришествия.
Следствием большей мощности КС-грамматик относительно автоматным является тот факт, что с помощью КС-грамматик можно описать любые автоматные грамматики, а обратное в свою очередь неверно. Причем тут БНФ, которая является лишь способом задания КС-грамматики?
Видимо, вас запутала фраза из википедии
> Они являются контекстно-свободными, но с ограниченными возможностями.
Так вот, регулярные грамматики не являются контекстно-свободными.
Парсер вытаскивает лексемы из исходной последовательности символов простым сравнением текущей лексемы с возможными вариантами. Никаких регулярных выражений здесь никогда и не было, а если бы они были тут — даже простейшая программа компилировалась бы до третьего пришествия.
Следствием большей мощности КС-грамматик относительно автоматным является тот факт, что с помощью КС-грамматик можно описать любые автоматные грамматики, а обратное в свою очередь неверно. Причем тут БНФ, которая является лишь способом задания КС-грамматики?
Видимо, вас запутала фраза из википедии
> Они являются контекстно-свободными, но с ограниченными возможностями.
Так вот, регулярные грамматики не являются контекстно-свободными.
Нет, я не запутался. Похоже, запутались Вы. Поясните пожалуйста фразу «вытаскивает лексемы из исходной последовательности символов простым сравнением текущей лексемы с возможными вариантами». Что за варианты такие?
Приведу пример. Хочу я сделать такой вот странный язык, в котором имена переменных должны соответствовать правилу (20-50 букв, цифра, подчеркивание или символ '$'). Попробуйте описать это в БНФ
а какой из существующих языков имеет такие лексемы?
PS: в статье я описывал хоть простенький лексер, но который может быть легко расширен и до плюсового/java'вского, причём без всяких регулярок. Зачем стрелять из пушки по воробьям?
PS: в статье я описывал хоть простенький лексер, но который может быть легко расширен и до плюсового/java'вского, причём без всяких регулярок. Зачем стрелять из пушки по воробьям?
Из существующих — надеюсь, никакой. Только это значения не имеет. Вот захотелось мне сделать, допустим, диалект того же питона с такими странными идентификаторами переменных. Язык порождается КС-грамматикой. Сможете его описать в БНФ?
смогу. даже не очень трудно.
претензии к тому что выглядит не очень не принимаются, ибо:
1. Сами придумали корявые идентификаторы.
2. В коде это будет довольно просто и компактно из-за использования таблиц парсинга.
3. Грамматика раздута для наглядности, нетерминалы ten, five_less, eleven_less, six_less не нужны.
4. Работать будет скорее всего быстрее чем regexp.
Но я не понимаю зачем вам нужно задавать БНФ для лексем, когда чаще всего достаточно простого анализа входного потока, без заморочек?
претензии к тому что выглядит не очень не принимаются, ибо:
1. Сами придумали корявые идентификаторы.
2. В коде это будет довольно просто и компактно из-за использования таблиц парсинга.
3. Грамматика раздута для наглядности, нетерминалы ten, five_less, eleven_less, six_less не нужны.
4. Работать будет скорее всего быстрее чем regexp.
Но я не понимаю зачем вам нужно задавать БНФ для лексем, когда чаще всего достаточно простого анализа входного потока, без заморочек?
Статью посмотрел, спасибо. И про воробьев правильно — я об этом говорил выше. Только вы несколько не правы в том, что «без всяких регулярок». Простите, если выше я допускал неточность в формулировках, но тут основная мысль в том, что лексемы языка с образующими КС-грамматиками — это не что иное, как регулярные языки. Каждый регулярный язык может быть описан одним регулярным выражением. И строка — это тоже регулярное выражение, просто в вашем случае прямо их использовать не требуется (хотя никто не мешает) — они атомарны, составлены с использованием только одной операции — конкатенации символов алфавита
ну вы смешали в кучу лексер и синтаксический анализатор, насколько я понял к вам претензия в том, что вы используете регулярки при синтаксическом анализе, а вы упираете на то, что они удобны для лексического.
Как бы оба этих утверждения правда — для лексического анализа проще не применять БНФ, а юзать regexp'ы или вовсе без сложных структур обойтись, а работать посимвольно, но и выполнять синтаксический анализ через регекспы — извращение, и лучше использовать КС-грамматики + анализатор.
Как бы оба этих утверждения правда — для лексического анализа проще не применять БНФ, а юзать regexp'ы или вовсе без сложных структур обойтись, а работать посимвольно, но и выполнять синтаксический анализ через регекспы — извращение, и лучше использовать КС-грамматики + анализатор.
Вы напрасно столь категорично разделяете лексический и синтаксический анализаторы на два разных класса. Лексический анализатор — это синтаксический анализатор для языков с регулярной грамматикой. А они, как писалось выше, составляют подмножество КС-грамматик
Да и претензии ко мне, собственно, в том, что уважаемый bobermaniac не приемлет регулярные выражения в парсерах КС-грамматик, что, простите, просто глупо если вы строили хоть один транслятор для языка программирования
выполнять синтаксический анализ текста на языке с КС-грамматикой через регексы — не просто извращение. Это в принципе невозможно. Только я упираю на то, что в данном случае вообще не нужен синтаксический анализатор языка программирования. Это как микроскопом гвозди заколачивать
Дело даже не в принципиальной невозможности описать такие изотерические случаи в БНФ. Можно, даже не в расширенной нотации. Только продукция будет километровая — в конце 30 закрывающих квадратных скобок! Вся соль в том, что эта продукция будет описывать один единственный регулярный язык («Язык регулярен, если его синтаксис может быть выражен единственным выражением РБНФ (расширенной нотации Бекуса-Наура)» Н.Вирт «Построение компиляторов»). А если язык регулярен — так и давайте его описывать как регулярное выражение, а не плодить ненужные продукции для терминалов языка
Для подсветки кода достаточно лексического разбора, с которым обычно справляются регулярные выражения. Другое дело, что автор реализовал разбор не самым лучшим образом :)
Возможно. Укажите недочеты
Посмотрите, как делаются классические лексические анализаторы: после выделения очередной лексемы они сдвигают указатель сразу после выделенной лексемы, так что следующая лексема оказывается в начале буфера. Таким образом before и after становятся не нужны. before не нужен, т.к. мы и так в начале буфера, а after не нужен, если писать «regexpr» правильно.
Насколько я понимаю, Вы имеете ввиду семейство lex-подобных программ. Так там, если я правильно помню, после считывания символа последовательности делается сдвиг по всем конечным автоматам, то бишь проверяются сразу все классы лексем, поэтому когда один из них срабатывает — дает лексему — указатель оказывается у начала следующей. Здесь такая штука не прокатит, поскольку не имеется таких методов у объектов-регулярок стандартной библиотеки
> не имеется таких методов у объектов-регулярок стандартной библиотеки
А если найду? :)
Продвигать «указатель» (просто целое число) можно и руками. Перебирать регулярки — тоже. А поиск от нужного места делается методом match класса re.RegexObject:
А если найду? :)
Продвигать «указатель» (просто целое число) можно и руками. Перебирать регулярки — тоже. А поиск от нужного места делается методом match класса re.RegexObject:
>>> rr = re.compile('[0-9]+')
>>> rr.match('aa00', 0) # ничего
>>> rr.match('aa00', 1) # ничего
>>> rr.match('aa00', 2)
<_sre.SRE_Match object at 0x7fb315eb66b0>
Вы считаете этот выход оптимальным? Я искренне удивлен. Ваша регулярка длиной 4 символа, т.е. каждый вызов match заглядывает вперед от текущей позиции (во втором аргументе) на 4 символа. Т.е. для строки в 20 символов вам нужно будет прочитать (20-4)*4 символа. Это для каждого выражения. В Вашем примере реализован самый дорогой алгоритм сопоставления с шаблоном с асимптотической сложностью N^2 для каждого регулярного выражения.
В lex-подобных анализаторах считывается символ и производится сдвиг (там где это возможно) на одно СОСТОЯНИЕ конечного автомата.
В lex-подобных анализаторах считывается символ и производится сдвиг (там где это возможно) на одно СОСТОЯНИЕ конечного автомата.
Для подсветки кода я считаю это вполне оптимальным. Для компилятора — конечно, нет.
Странное понимание оптимальности. Вы предлагаете увеличить сложность алгоритма непонятно зачем. В Вашем варианте в сравнении с тем, что уже реализован, сложность будет в лучшем случае такая же, а в худшем на один порядок выше. Простите, но Вы не правы
Для упрощения описания языка. Разве один regexpr не проще regexpr+before+after?
Не лучше. Они просто не подходят, и этот случай описан под словами «Блин первый». Ваше предложение неприемлемо для данной ситуации по следующим причинам:
1. Предложенный метод — самый дорогой из всех возможных, его сложность оценивается как O(n^2) для строки длины n. Не могу сказать точно (не глядел исходники модуля re), но поиск соответствия регулярному выражению в строке в стандартной библиотеке всяко лучше Вашего метода посимвольного сдвига по строке. Во всяком случае он не хуже — потому что хуже некуда.
2. Этот способ вообще не подходит, потому что данная программа, в общем, не является лексическим анализатором (и тем более, синтаксическим) в полном смысле этого слова. Лексический анализатор преобразует исходную последовательность символов в список символов словаря абстрактных терминальных символов языка. Именно поэтому в «классических» лексических анализаторах после прочтения одной лексемы начинается другая. В данной задаче между выделяемыми словами может стоять любое количество символов, которые не составляют лексему, а значит, устойчивый к ошибкам лексический анализатор их просто пропускает. В данном случае (и это написано в статье), такой подход приведет к нахождению лексемы там, где ее на самом деле нет — например, внутри слова. Так что без описания предстоящих и постстоящих символов просто не обойтись. Или потребуется описание всех существующих в конкретном языке лексем — а это уже задача на порядок выше и для данного случая решать ее не вижу смысла.
Если Вы с этим не согласны — напишите свой вариант и докажите, что Ваша идея жизнеспособна. Тогда буду рад признать свою неправоту
1. Предложенный метод — самый дорогой из всех возможных, его сложность оценивается как O(n^2) для строки длины n. Не могу сказать точно (не глядел исходники модуля re), но поиск соответствия регулярному выражению в строке в стандартной библиотеке всяко лучше Вашего метода посимвольного сдвига по строке. Во всяком случае он не хуже — потому что хуже некуда.
2. Этот способ вообще не подходит, потому что данная программа, в общем, не является лексическим анализатором (и тем более, синтаксическим) в полном смысле этого слова. Лексический анализатор преобразует исходную последовательность символов в список символов словаря абстрактных терминальных символов языка. Именно поэтому в «классических» лексических анализаторах после прочтения одной лексемы начинается другая. В данной задаче между выделяемыми словами может стоять любое количество символов, которые не составляют лексему, а значит, устойчивый к ошибкам лексический анализатор их просто пропускает. В данном случае (и это написано в статье), такой подход приведет к нахождению лексемы там, где ее на самом деле нет — например, внутри слова. Так что без описания предстоящих и постстоящих символов просто не обойтись. Или потребуется описание всех существующих в конкретном языке лексем — а это уже задача на порядок выше и для данного случая решать ее не вижу смысла.
Если Вы с этим не согласны — напишите свой вариант и докажите, что Ваша идея жизнеспособна. Тогда буду рад признать свою неправоту
кстати, эка незадача, в Вашем примере нашлось число внутри строки. Будем подсвечивать?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
PDF-принтер Хабра с подсветкой кода на Python