Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 45
Так и не увидел за весь пост фразы" LR-грамматика"
К сожалению, российские вузы уделяют мало внимания сей интереснейшей теме
не, ну ты смотри какие подлецы. и дисциплины «теория компиляторов» наверное нет нигде?
Если не секрет, чем обусловлен выбор lex а не antlr?
lex по православнее будет. а вобще я пользуюсь другим средством — ragel
Отличная статья! По-моему тема создания компиляторов, или точнее, более узкая тема source-to-source преобразований должна быть близка всем разработчикам на крупных проектах. Меня до сих пор не отпускает идея создания Domain-specific языка для предметной области своего проекта. Но знаний по компиляции пока не хватает.
С нетерпением жду продолжения. :)
С нетерпением жду продолжения. :)
Для создания DSL есть много готовых решений и подходов, вроде MPS для внешних DLS или Scala для внутренних. Вовсе не требуется знать про компиляторы или, ещё хуже, писать их.
Хм.
У нас (ВМК МГУ) был отдельный курс Системы Программирования, где половина материала была как раз о Формальных грамматиках и теории компиляции.
+ у одного из потоков еще отдельный курс Конструирование Компиляторов.
Материал рассказывался довольно хорошо, хотя многие не понимали, зачем им это нужно будет. Ну, это как всегда)
У нас (ВМК МГУ) был отдельный курс Системы Программирования, где половина материала была как раз о Формальных грамматиках и теории компиляции.
+ у одного из потоков еще отдельный курс Конструирование Компиляторов.
Материал рассказывался довольно хорошо, хотя многие не понимали, зачем им это нужно будет. Ну, это как всегда)
если хочется начинать не с нуля, а на базе какого-нибудь современного языка, рекомендую посмотреть в сторону Scala.
Scala позволяет писать плагины к компилятору, имеющие достаточно широкий простор действий.
сам компилятор очень хорошо устроен, имеет чёткие стадии работы и вообще представляем из себя отличную иллюстрацию того, как надо работать =)
Scala позволяет писать плагины к компилятору, имеющие достаточно широкий простор действий.
сам компилятор очень хорошо устроен, имеет чёткие стадии работы и вообще представляем из себя отличную иллюстрацию того, как надо работать =)
Автор, статья неплохая, но дайте перварительно общую картину — классы языков. Ту ж иерархию Хомского
К примеру, не очень понятно почему регекспами нельзя обрабатывать вложенность (а если ими нельзя, то чем можно?).
2Nostromo: читал какие-то мгушные лекции, не очень-то понятно. Не могли бы назвать хорошего лектора (по формальным языкам)?
К примеру, не очень понятно почему регекспами нельзя обрабатывать вложенность (а если ими нельзя, то чем можно?).
2Nostromo: читал какие-то мгушные лекции, не очень-то понятно. Не могли бы назвать хорошего лектора (по формальным языкам)?
Почему нельзя, и чем можно — обещаю во втором посте.
Теорию собирался касаться по минимуму, всё-таки целюсь в программистов, а не в математиков.
Теорию собирался касаться по минимуму, всё-таки целюсь в программистов, а не в математиков.
Волкова. У нее, кстати, есть прекрасная (имхо) методичка конкретно по формальным грамматикам и языкам и элементам теории трансляции.
Все это можно найти, например, вот здесь:
cmcmsu.no-ip.info/2course/ в материалах за 4 семестр.
там еще много полезной информации.
Все это можно найти, например, вот здесь:
cmcmsu.no-ip.info/2course/ в материалах за 4 семестр.
там еще много полезной информации.
Свердлов С. З. Языки программирования и методы трансляции, Питер, 2007, ISBN 978-5-469-00378-6.
Отличная книга на данную тему, где хорошо и доступно раскрыты как исторические предпосылки, так в необходимом объеме теория, а так же практическая реализация на примере реализации минимального подмножества языка Оберон, на различных языках программирования (Паскаль, Ява, Си шарп, Сам оберон и прочие). Рекомендована российским мин. образования. Одна из немногих известных мне достойных книг, российского авторства, а не перевод, на тему АйТи.
Отличная книга на данную тему, где хорошо и доступно раскрыты как исторические предпосылки, так в необходимом объеме теория, а так же практическая реализация на примере реализации минимального подмножества языка Оберон, на различных языках программирования (Паскаль, Ява, Си шарп, Сам оберон и прочие). Рекомендована российским мин. образования. Одна из немногих известных мне достойных книг, российского авторства, а не перевод, на тему АйТи.
www.ozon.ru/context/detail/id/3829076/
Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман
Компиляторы. Принципы, технологии и инструментарий
Compilers: Principles, Techniques, & Tools
Издательство: Вильямс, 2008 г.
Твердый переплет, 1184 стр.
ISBN 978-5-8459-1349-4, 0-321-48681-1
Лучшая книга про разработку компиляторов.
Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман
Компиляторы. Принципы, технологии и инструментарий
Compilers: Principles, Techniques, & Tools
Издательство: Вильямс, 2008 г.
Твердый переплет, 1184 стр.
ISBN 978-5-8459-1349-4, 0-321-48681-1
Лучшая книга про разработку компиляторов.
Неужели следующая статья будет про yacc? Настоятельно не рекомендую.
Вернее так — Вы определитесь, про какой подход рассказывать. Можно долго делать очень быстрый компилятор, а можно в разы быстрее сделать компилятор, который будет работать с приемлемой скоростью. Так вот lex/yacc для второго подхода использовать не советую — отлаживать замучаетесь. К тому же в больших языках всегда есть какие-нибудь исключительные ситуации, когда возможностей генератора сканеров/парсеров не хватает и приходится выкручиваться. В этой ситуации я тоже предпочту какой-нибудь antlr.
В общем, задача настолько хорошо изучена, что есть смысл рассказывать только про современные технологии её решения, которые охватывают все этапы разработки. И тестирование, кстати.
Вернее так — Вы определитесь, про какой подход рассказывать. Можно долго делать очень быстрый компилятор, а можно в разы быстрее сделать компилятор, который будет работать с приемлемой скоростью. Так вот lex/yacc для второго подхода использовать не советую — отлаживать замучаетесь. К тому же в больших языках всегда есть какие-нибудь исключительные ситуации, когда возможностей генератора сканеров/парсеров не хватает и приходится выкручиваться. В этой ситуации я тоже предпочту какой-нибудь antlr.
В общем, задача настолько хорошо изучена, что есть смысл рассказывать только про современные технологии её решения, которые охватывают все этапы разработки. И тестирование, кстати.
Да, рассказываю о хорошо изученных вещах, и на первооткрывательство не претендую. Цель была — изложить популярно.
Да, у меня нет опыта с antlr и с LL-парсерами вообще.
В чём их преимущество? в удобстве отладки?
Да, у меня нет опыта с antlr и с LL-парсерами вообще.
В чём их преимущество? в удобстве отладки?
Гораздо больше возможностей и удобства для программиста. В частности, поддерживается работа с деревом, которое является результатом разбора. Впрочем, я предпочитаю пользоваться своим инструментом TreeDL. Также есть поддержка кодогенерации.
Извините за некоторую резкость, «ревную» близкую мне тему :) Давайте лучше дополню статью примерами из реальной жизни. Вот наши фронтенды для расширений С и Java, написанные на JavaCC+TreeDL и Antlr/Java+TreeDL соответственно:
сканер+парсер расширенного С
дерево расширенного С
сканер Java
Извините за некоторую резкость, «ревную» близкую мне тему :) Давайте лучше дополню статью примерами из реальной жизни. Вот наши фронтенды для расширений С и Java, написанные на JavaCC+TreeDL и Antlr/Java+TreeDL соответственно:
сканер+парсер расширенного С
дерево расширенного С
сканер Java
Давайте лучше дополню статью примерами из реальной жизни.
С удовольствием бы прочитал, если будет не сухой код, а с пояснениями, откуда что и зачем.
Особенно интересует «сравнительный анализ» yacc vs. antlr. (Зарылся в гугл.)
Так это писалось не один год и не одним человеком :) Я ещё могу ответить на конкретные вопросы, но всё прокомментировать нереально.
Главное отличие lex/yacc от antlr — вид используемой грамматики. regexp/LR(1) (или точнее LALR(1), если я правильно помню) vs LL(k)/LL(k). Да, для сканеров на antlr используется та же грамматика, что и для парсеров. k — произвольный размер lookahead, причем в отдельных сложных местах его можно увеличивать задавая синтаксические предикаты (а еще есть семантические!). LL парсеры похожи на те, которые пишутся руками — рекурсивные. Сгенерированный код легко читать и отлаживаться по нему.
Disclaimer: моё плотное знакомство с antlr закончилось на 2й версии, 3я может отличаться.
Главное отличие lex/yacc от antlr — вид используемой грамматики. regexp/LR(1) (или точнее LALR(1), если я правильно помню) vs LL(k)/LL(k). Да, для сканеров на antlr используется та же грамматика, что и для парсеров. k — произвольный размер lookahead, причем в отдельных сложных местах его можно увеличивать задавая синтаксические предикаты (а еще есть семантические!). LL парсеры похожи на те, которые пишутся руками — рекурсивные. Сгенерированный код легко читать и отлаживаться по нему.
Disclaimer: моё плотное знакомство с antlr закончилось на 2й версии, 3я может отличаться.
Вечер добрый. Пытаюсь родить pmd-rule (http://pmd.sourceforge.net/) для примитивного случая sql injection:
ResultSet rs = null;
PreparedStatement ps = null;
/* some code… */
ps = con.prepareStatement(mySQL);
/* again some code… */
Как я понял, pmd основан на JavaCC.
Я без проблем нахожу вызов «prepareStatement», но никак не могу получить доступ к аргументу метода, чтоб поискать его usage в method scope (упрощаю задачу).
В общем, идея следующая: если аргумент метода «prepareStatement» является производным (через конкатенацию или StringBuilder, StringBuffer) от строкового (String) аргумента метода класса, внутри которого готовится стейтмент, то надо выдать предупреждение о потенциальном SQL-injection.
Понятное дело, озвученный кейс — самый примитивный, тем не менее подрядчики этим занимаются постоянно. К счастью, до чего-то более изощренного они не додумываются.
Есть ли у вас опыт написания подобного, где можно посмотреть, почитать? форум pmd скорее мертв, чем жив.
ResultSet rs = null;
PreparedStatement ps = null;
/* some code… */
ps = con.prepareStatement(mySQL);
/* again some code… */
Как я понял, pmd основан на JavaCC.
Я без проблем нахожу вызов «prepareStatement», но никак не могу получить доступ к аргументу метода, чтоб поискать его usage в method scope (упрощаю задачу).
В общем, идея следующая: если аргумент метода «prepareStatement» является производным (через конкатенацию или StringBuilder, StringBuffer) от строкового (String) аргумента метода класса, внутри которого готовится стейтмент, то надо выдать предупреждение о потенциальном SQL-injection.
Понятное дело, озвученный кейс — самый примитивный, тем не менее подрядчики этим занимаются постоянно. К счастью, до чего-то более изощренного они не додумываются.
Есть ли у вас опыт написания подобного, где можно посмотреть, почитать? форум pmd скорее мертв, чем жив.
Правил для PMD писать не приходилось, но общий принцип понятен. Самое главное — JavaCC практически ни при чем. Вы имеете дело с готовым деревом (AST), в котором надо найти узел, соответствующий вызову метода, проверить, что имя метода «prepareStatement» и в этом случае выполнить необходимую проверку типа параметра.
Судя по примеру
pmd.sourceforge.net/howtowritearule.html
Вызову метода соответствует PrimaryExpression с детьми PrimaryPrefix и PrimarySuffix. Объект и имя метода сидят в префиксе, а аргументы — в суффиксе.
Удобного описания дерева я что-то сходу не нашел (даже исходного *.jj в дистрибутиве не вижу), так что проще пользоваться предлагаемым дизайнером, который показывает дерево входного файла).
Если вопросы останутся — пишите ICQ 740187 или allex@all-x.net
Судя по примеру
pmd.sourceforge.net/howtowritearule.html
Вызову метода соответствует PrimaryExpression с детьми PrimaryPrefix и PrimarySuffix. Объект и имя метода сидят в префиксе, а аргументы — в суффиксе.
Удобного описания дерева я что-то сходу не нашел (даже исходного *.jj в дистрибутиве не вижу), так что проще пользоваться предлагаемым дизайнером, который показывает дерево входного файла).
Если вопросы останутся — пишите ICQ 740187 или allex@all-x.net
Прочитал статью «Редкая профессия» Евгения Зуева, про то, как чуваки писали компилятор
с++ когда-то давно. Как переводили стандарты, с какими проблемами сталкивались, про проблемы грамматики с++ и прочее.
Вот нашел ссылку: www.interstron.ru/upload/images/pubs/Redkaya_professiya.pdf
Тем, кто интересуется компиляторами рекомендую, можно узнать интересные вещи.
с++ когда-то давно. Как переводили стандарты, с какими проблемами сталкивались, про проблемы грамматики с++ и прочее.
Вот нашел ссылку: www.interstron.ru/upload/images/pubs/Redkaya_professiya.pdf
Тем, кто интересуется компиляторами рекомендую, можно узнать интересные вещи.
> Практический пример
> В стандартные утилиты GNU входит flex, совместимый с lex, — его мы и будем использовать для примеров.
> По традиции, первым примером станет написание калькулятора:
Товарищ, ты слишком быстро перепрыгнул.
Во-первых, ты не сказал толком, какой язык мы будем обрабатывать в примере. В нашем случае, мы будем обрабатывать «простейший язык математических выражений». В нем будут только цифры 0-9, четыре знака математических операций "+", "-", "*", "/"), символ завершения выражения ";".
Во-вторых, ты ни слова не сказал, что вообще такое lex / flex.
Коль рассказываешь основы, надо было бы пояснить, что lex — это генератор лексического анализатора, который на основе файла описания языка, создает c-файл с лексическим анализатором. Этот c-файл можно скомпилировать, после чего полученный бинарник сможет выполнять текст программы на придуманном нами языке. Грубо говоря, полученный бинарник находит в тексте программы на «придуманном» языке куски, попадающие под заданные нами маски, и вместо найденных кусков выполняет заданный нами код на языке C.
Кроме того, надо сразу сказать (а не после), что первый листинг в статье — это код lex-файла, в котором описываются маски для поиска кусочков текста, и С-код, кторый должен выполняться вместо этих масок. Данный файл скармливается программе lex, на выходе имеем C-файл с лексическим анализатором. Компилируем этот файл, и получаем бинарник лексического анализатора.
Этот бинарник как раз и умеет выполнять программы на придуманном нами языке. Он берет текст программы из стандартного ввода, и помещает результат выполнения программы в стандартный вывод. То есть, с помощью этого бинарника мы можем выполнять программы на «простейшем языке математических выражений» прямо в консоли.
После таких пояснений можно уже и код lex-файла показывать, и все остальное объяснять.
> В стандартные утилиты GNU входит flex, совместимый с lex, — его мы и будем использовать для примеров.
> По традиции, первым примером станет написание калькулятора:
Товарищ, ты слишком быстро перепрыгнул.
Во-первых, ты не сказал толком, какой язык мы будем обрабатывать в примере. В нашем случае, мы будем обрабатывать «простейший язык математических выражений». В нем будут только цифры 0-9, четыре знака математических операций "+", "-", "*", "/"), символ завершения выражения ";".
Во-вторых, ты ни слова не сказал, что вообще такое lex / flex.
Коль рассказываешь основы, надо было бы пояснить, что lex — это генератор лексического анализатора, который на основе файла описания языка, создает c-файл с лексическим анализатором. Этот c-файл можно скомпилировать, после чего полученный бинарник сможет выполнять текст программы на придуманном нами языке. Грубо говоря, полученный бинарник находит в тексте программы на «придуманном» языке куски, попадающие под заданные нами маски, и вместо найденных кусков выполняет заданный нами код на языке C.
Кроме того, надо сразу сказать (а не после), что первый листинг в статье — это код lex-файла, в котором описываются маски для поиска кусочков текста, и С-код, кторый должен выполняться вместо этих масок. Данный файл скармливается программе lex, на выходе имеем C-файл с лексическим анализатором. Компилируем этот файл, и получаем бинарник лексического анализатора.
Этот бинарник как раз и умеет выполнять программы на придуманном нами языке. Он берет текст программы из стандартного ввода, и помещает результат выполнения программы в стандартный вывод. То есть, с помощью этого бинарника мы можем выполнять программы на «простейшем языке математических выражений» прямо в консоли.
После таких пояснений можно уже и код lex-файла показывать, и все остальное объяснять.
> Мне кажется, что все перечисленные факты в тексте есть.
> Хоть и не в таком порядке.
В человеческой речи, в отличие от операции сложения в классической математике, от перестановки мест слагаемых результат меняется.
У вас вся статья написана задом-наперед. К середине статьи накапливается куча необъяснённых вопросов, которые кое-как разрешаются в конце. Это сложно для понимая обычному человеку. Такое впечатление, что вы перепрограммировали на каком-то функциональном языке, и функциональное мышление повлияло на стиль вашей речи.
> Хоть и не в таком порядке.
В человеческой речи, в отличие от операции сложения в классической математике, от перестановки мест слагаемых результат меняется.
У вас вся статья написана задом-наперед. К середине статьи накапливается куча необъяснённых вопросов, которые кое-как разрешаются в конце. Это сложно для понимая обычному человеку. Такое впечатление, что вы перепрограммировали на каком-то функциональном языке, и функциональное мышление повлияло на стиль вашей речи.
Если не секрет, по каким соображениям была выбрана связка c+lex+yacc? Чем не понравились такие инструменты как Ocaml или Haskell на пример? К тому же они вроде как получили некое распространение на поприще компилятора-строения.
У меня не осталось, но остались на https://web.archive.org/web/*/tyomitch.net.ru/*
У меня есть задача распознать минимальный тип данных (uint8_t, char, double и т п) из строки.
Очень не хочется писать си-парсер вручную.
Может ли мне помочь в этом утилита flex?
А что это за язык такой инопланетный
коим нужно писать конфиг для утилиты lex?
И как понять, что надо написать в конфиге для lex, чтобы получился хотя бы интерпретатор формулы, как у калькулятора CASIO FX-991EX?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Компиляция. 1: лексер