Продолжу рассказы о том, как программисты ходят по краю, даже не подозревая об этом. Поговорим об операциях сдвига <<, >>. Принципы работы операторов сдвига очевидны и многие программисты даже не знают, что их использование согласно стандарту Си/Си++ может приводить к неопределенному или к неуточненному поведению (undefined behaviour/unspecified behavior).
Читать полностью »
Рубрика «Компиляторы» - 57
Не зная брода, не лезь в воду. Часть третья
2012-04-11 в 11:34, admin, рубрики: c plus plus, c++, c++11, pvs-studio, битовые операции, Компиляторы, метки: c plus plus, c++, c++11, pvs-studio, битовые операцииСоздание конечного автомата для разбора HTTP запроса
2012-04-09 в 12:49, admin, рубрики: .net, DFA, http, parser, ДКА, Компиляторы, метки: DFA, http, parser, ДКАДетерминированный конечный автомат можно использовать для реализации очень быстрого способа разбора входной последовательности. Требуется всего один проход по входной последовательности, и минимальные действия на каждом шаге. К сожалению эта модель имеет ограничения — не всегда возможно построить ДКА, для имеющегося Недетерминированного конечного автомата (регулярного выражения, грамматики). Или даже если возможно построить, автомат может иметь слишком большое число состояний.
Тем не менее я решил попробовать создать парсер для HTTP запроса на основе ДКА. Основная задача не просто проверить корректность HTTP запроса, а именно выделить во входной строке элементы соответствующие определенным значениям полей HTTP запроса. Автомат должен генерироваться из BNF правил (разбросанных по) RFC2616. Реализовано все на C#, автомат на выходе тоже на C#. Хотя понятно что когда автомат готов, сгенерировать его на любом языке, в любом виде не проблема.
Читать полностью »
Релиз GCC-4.7
2012-03-23 в 7:47, admin, рубрики: c++, c++11, gcc, open source, Компиляторы, метки: c++11, gcc, open sourceСегодня ночью вышел долгожданный GCC 4.7, выпуск которого приурочен к 25-летию проекта.
Долгожданным этот выпуск является прежде всего для программистов C++, так как несет с собой обширную поддержку нового стандарта С++11.
Читать полностью »
Особенности написания и возможные фичи LR-генераторов
2012-03-21 в 12:48, admin, рубрики: ECMAScript, javascript, lalr, Алгоритмы, Компиляторы, парсеры, синтаксический анализ, метки: ECMAScript, javascript, lalr, компиляторы, парсеры, синтаксический анализВведение
Добрый день.
В заключительной части про написание собственного генератора LALR-парсеров я бы хотел описать возможные особенности и фичи. Кроме того я опишу чего мне не хватало в существующих решениях и ради чего я начал писать свой велосипед.
Дабы задать контекст, сообщу, что грамматика для анализа — это ECMAScript, так же известный как JavaScript. Конкретная спецификация — ECMA-262, редакция 5.1 от июня 2011 года.
Читать полностью »
Написание компилятора LALR(1)-парсеров. Часть 2
2012-03-20 в 12:41, admin, рубрики: lalr, Алгоритмы, Компиляторы, парсеры, синтаксический анализ, метки: lalr, компиляторы, парсеры, синтаксический анализПредисловие
Добрый день.
Это вторая часть статьи про написание своего генератора LALR-анализаторов. В этой части я расскажу про эволюции от примитивных восходящих синтаксических анализаторов до наиболее актуальных, хотя и не шибко новых, LALR-парсеров. Тем, кто не читал первую статью (ссылки — снизу), советую прочесть хотя бы первую половину последнего раздела. О том небольшом фрагменте кода я буду упоминать несколько раз.
В комментариях к прошлой статье несколько человек интересовались моими мотивами в написании своего компилятора компиляторов. К сожалению, они в этой статье не найдут ответов на этот вопрос. Не скрою, изначально я планировал написать статью без особой теории, но с оправданием задач и целей, ради которых я начал писать генератор, да и хотел поделиться нюансами и особенностями реализации. То есть по объему это довольно прилично: несколько экранов. Но затем я решил всё же описать базовую теорию популистским языком, поэтому статья разрослась до трех частей. Таким образом, дабы не ломать логику изложения, я сначала расскажу про LR/SLR/LALR-анализаторы, а завтра опубликую заключительную, и, думаю, самую интересную часть.
Читать полностью »
Извлекаем мета-информацию из Си/C++ кода при помощи (py)gccxml
2012-03-19 в 11:36, admin, рубрики: c++, python, Компиляторы gccxml.gif "Извлекаем мета информацию из Си/C++ кода при помощи (py)gccxml")
До появления gccxml, был только один способ извлечь мета-информацию из Си/С++ кода. Для начала, необходимо было написать парсер, способный справиться с грамматикой языка С++. Это не та задача, которую вы обычно решаете дома за выходные.
Теперь, писать парсер больше не нужно. Модифицированный компилятор gcc анализирует ваш код и выдает описание всех пространств имен, типов, классов и функций, встреченных в программе. Данные выдаются в формате XML и в принципе готовы для дальнейшего автоматического анализа и обработки.
Для разбора XML данных, полученных от gccxml, пригодится библиотека pygccxml. Это не просто ридер формата gccxml — библиотека предоставляет интерфейсы для изучения собранных метаданных; в частности есть готовые функции, отвечающие на вопросы вроде «совместимы ли типы T1 и T2?» или «наследует ли класс C1 от C2?». Библиотека написана на языке Python.
Разработка парсера PHP средствами ANTLR
2012-03-18 в 11:55, admin, рубрики: antlr, java, php, Компиляторы, Программирование, метки: antlr, java, PHPВ качестве хобби последние несколько месяцев я разрабатываю парсер языка PHP с помощью ANTLR. Сам проект для меня скорее просто Just for fun, но в ходе его реализации у меня, разумеется, возникали сложности. Тут сказывается как особенность языка PHP с полным отсутствием спецификаций, так и ограничения алгоритмов LL(k).
В этой статье я бы хотел поделиться техническими решениями и некоторыми хитростями в реализации парсера и процедуры его тестирования. Данная статья будет полезна тем, кто хочет подробнее разобраться в использовании средства ANTLR v2.Читать полностью »
Написание компилятора LALR(1)-парсеров. Часть 1
2012-03-15 в 15:27, admin, рубрики: c++, lalr, Алгоритмы, Компиляторы, парсеры, синтаксический анализ, метки: lalr, компиляторы, парсеры, синтаксический анализВведение, или зачем нужны синтаксические анализаторы
Добрый день.
Не так давно появилась у меня задача синтаксического анализа одной грамматики. Существующие решения мне увы не подходили, поэтому встала проблема написания собственного генератора парсеров. Несмотря на то, что тема довольно популярная и существует не так уж и мало статей и книг по данному сабжу, я всё-таки решил еще раз описать данный процесс, причём начать с самых базовых понятий.
Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.
Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.
Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.
Несколько проблем при создании собственного языка программирования
2012-03-15 в 13:26, admin, рубрики: грамматика, Компиляторы, метки: грамматикаНа форумах можно увидеть темы из разряда «Каким я вижу свой идеальный язык программирвоания». При этом создаются такие грамматики, которые анализатор никогда не сможет преобразовать в код. Под катом несколько опасностей, которые подстерегают разработчика нового понятного, изящного, гибкого языка программирования.
r
2012-03-14 в 15:43, admin, рубрики: генератор кода, Компиляторы, трансляторы, метки: генератор кода, трансляторыcoco/r генератор компиляторов и трансляторов, который по атрибутной грамматике генерирует сканер (лексический анализатор) и парсер (синтаксичсекий анализатор). Сканер строится как детерминированный конечный автомат, а парсер — рекурсивным спуском.