Предисловие

Добрый день.
Это вторая часть статьи про написание своего генератора LALR-анализаторов. В этой части я расскажу про эволюции от примитивных восходящих синтаксических анализаторов до наиболее актуальных, хотя и не шибко новых, LALR-парсеров. Тем, кто не читал первую статью (ссылки — снизу), советую прочесть хотя бы первую половину последнего раздела. О том небольшом фрагменте кода я буду упоминать несколько раз.

В комментариях к прошлой статье несколько человек интересовались моими мотивами в написании своего компилятора компиляторов. К сожалению, они в этой статье не найдут ответов на этот вопрос. Не скрою, изначально я планировал написать статью без особой теории, но с оправданием задач и целей, ради которых я начал писать генератор, да и хотел поделиться нюансами и особенностями реализации. То есть по объему это довольно прилично: несколько экранов. Но затем я решил всё же описать базовую теорию популистским языком, поэтому статья разрослась до трех частей. Таким образом, дабы не ломать логику изложения, я сначала расскажу про LR/SLR/LALR-анализаторы, а завтра опубликую заключительную, и, думаю, самую интересную часть.

В комментариях к блестящему топику «Как выглядит китайская клавиатура» высказали интересную идею: рассказать про набор текста в разных языках с необычной письменностью.

Арабам относительно повезло: у них лишь 28 букв — даже меньше, чем в русском. Каждой букве можно назначить отдельную клавишу, и ещё останутся свободные. Зато с их письменностью возникают свои сложности, неведомые китайцам.

Этот пост написан по мотивам лекции Джеймса Смита, профессора Висконсинского университета в Мадисоне, специализирующегося в микроэлектронике и архитектуре вычислительных машин.

История компьютерных наук в целом сводится к тому, что учёные пытаются понять, как работает человеческий мозг, и воссоздать нечто аналогичное по своим возможностям. Как именно учёные его исследуют? Представим, что в XXI веке на Землю прилетают инопланетяне, никогда не видевшие привычных нам компьютеров, и пытаются исследовать устройство такого компьютера. Скорее всего, они начнут с измерения напряжений на проводниках, и обнаружат, что данные передаются в двоичном виде: точное значение напряжения не важно, важно только его наличие либо отсутствие. Затем, возможно, они поймут, что все электронные схемы составлены из одинаковых «логических вентилей», у которых есть вход и выход, и сигнал внутри схемы всегда передаётся в одном направлении. Если инопланетяне достаточно сообразительные, то они смогут разобраться, как работают комбинационные схемы — одних их достаточно, чтобы построить сравнительно сложные вычислительные устройства. Может быть, инопланетяне разгадают роль тактового сигнала и обратной связи; но вряд ли они смогут, изучая современный процессор, распознать в нём фон-неймановскую архитектуру с общей памятью, счётчиком команд, набором регистров и т.п. Дело в том, что по итогам сорока лет погони за производительностью в процессорах появилась целая иерархия «памятей» с хитроумными протоколами синхронизации между ними; несколько параллельных конвейеров, снабжённых предсказателями переходов, так что понятие «счётчика команд» фактически теряет смысл; с каждой командой связано собственное содержимое регистров, и т.д. Для реализации микропроцессора достаточно нескольких тысяч транзисторов; чтобы его производительность достигла привычного нам уровня, требуются сотни миллионов. Смысл этого примера в том, что для ответа на вопрос «как работает компьютер?» не нужно разбираться в работе сотен миллионов транзисторов: они лишь заслоняют собой простую идею, лежащую в основе архитектуры наших ЭВМ.

Моделирование нейронов

Кора человеческого мозга состоит из порядка ста миллиардов нейронов. Исторически сложилось так, что учёные, исследующие работу мозга, пытались охватить своей теорией всю эту колоссальную конструкцию. Строение мозга описано иерархически: кора состоит из долей, доли — из «гиперколонок», те — из «миниколонок»… Миниколонка состоит из примерно сотни отдельных нейронов.



По аналогии с устройством компьютера, абсолютное большинство этих нейронов нужны для скорости и эффективности работы, для устойчивости ко сбоям, и т.п.; но основные принципы устройства мозга так же невозможно обнаружить при помощи микроскопа, как невозможно обнаружить счётчик команд, рассматривая под микроскопом микропроцессор. Поэтому более плодотворный подход — попытаться понять устройство мозга на самом низком уровне, на уровне отдельных нейронов и их колонок; и затем, опираясь на их свойства — попытаться предположить, как мог бы работать мозг целиком. Примерно так пришельцы, поняв работу логических вентилей, могли бы со временем составить из них простейший процессор, — и убедиться, что он эквивалентен по своим способностям настоящим процессорам, даже хотя те намного сложнее и мощнее.

Меня всегда завораживало таинство рождения программой программы. К сожалению, российские вузы уделяют мало внимания сей интереснейшей теме. Рассчитываю написать серию постов, в которых поэтапно создадим маленький работоспособный компилятор.

Первые посты серии уже подготовлены, и бета-тестировались в одном маленьком и наглухо закрытом сообществе. Тем не менее, я буду продолжать их править с учётом пожеланий почтенной хабрапублики.

Далее в посте:

1. С какой стати писать компиляторы?
2. Общий план
3. Анализ текста
4. Практический пример
5. Как это работает?

Если ты всегда мечтал написать свой язык программирования — добро пожаловать. Здесь ты наверняка найдёшь для себя что-нибудь интересное.

GitHub-юзер yawnt собрал чудесную подборку ссылок для любителей драконов, языков и прочих вкусных внутренностей. А знающие камрады в комментариях наверняка поделятся с тобой и другими яствами.

Пишет yawnt следующее:

С каждым днём мне всё интереснее тема компиляторов, интерпретаторов и дизайна языков программирования в целом. И я решил поделиться с народом ссылками на собранные мной материалы (большую часть мне самому ещё предстоит прочитать :<). Надеюсь, кому-нибудь они окажутся полезными.

Я не включил (и не собираюсь) в список ссылки на официальную документацию, т. к. считаю очевидным, что первым делом следует смотреть именно туда ;P.

Vala — это язык программирования, который создавался как замена языка C при разработке приложений для Gnome. При этом язык на мой взгляд удался, в своем синтаксисе взял многое из C# и Java. Прочитать подробнее о нем можно на Хабре или сайте Gnome. Захотев попробовать этот проект в деле столкнулся с тем, что по текущий момент для него не существует качественного IDE или плагина для IDE, которая позволила бы комфортно на нем разрабатывать.

В результате был создан плагин для NetBeans IDE, которая на мой взгляд является одной из лучших open source IDE (наряду с Eclipse). Тем не менее информация о том, как именно разрабатывать модули и плагины для NetBeans Plaform довольно разрознена, а на русском языке практически ничего нет.

Как и договаривались в первой части статьи, в этой мы будем рассматривать инструменты для изменения стандартного поведения Activity Stack.

Вся теория по сегодняшей теме присутствует на developer.android.com/guide/topics/manifest/activity-element.html, я буду кое-где на неё ссылаться, а мы постараемся разобраться как оно работает на деле и выяснить, в каких ситуациях это можно использовать в реальной жизни.

Пожалуй, самый популярный вопрос на собеседованиях на Android-разработчика звучит так: «расскажите нам про жизненный цикл Activity». На первый взгляд в этом нет ничего сложного, в каком только блоге об этом ещё не писали, и кандидат тут же начинает рисовать известную блок-схему и по ходу пояснять. Сферический life cycle в вакууме, которым изобилуют все уроки, действительно достаточно прост для понимания, но ведь activity — это только часть некой обобщающей их сущности. Сущность эта называется Activity Stack, и с его жизненным циклом мы сейчас постараемся разобраться.

Жизненный цикл Activity Stack (часть 2)

Данная статья является продолжением статьи Загрузка классов в Java. Теория.

В статье рассмотрена реализация каркаса приложения с плагино-модульной архитектурой. В качестве движка приложения будет использоваться пользовательский загрузчик классов, которым будут загружаться дополнительные плагины приложения.

Код приложения не претендует на оригинальность, а лишь объясняет подходы и принципы написания пользовательских загрузчиков классов и методы инвокации динамического кода.

При использовании популярного приложения Play Маркет многие обратили внимание на вкладки для переключения контента. Такое применение вкладок можно найти и в других приложениях от Google, таких как Play Музыка, Play Пресса.



На этой почве возникает интерес, а иногда и необходимость (если заказчик просит) реализовать увиденное. Я не стал исключением и при проектировании нового приложения, дизайн которого был набросан на черновике, присутствовал очень схожий дизайн, хотя и имел всего несколько вкладок. Казалось бы, что сложного? Сейчас откроем официальную документацию, просмотрим необходимые разделы и приступим к делу. Но, изучив документацию, не смог обнаружить соответствующих примеров — и тут же возник новый вопрос. Почему Android разработчики из компании Google по умолчанию не предоставляют примеров с необходимой функциональностью, чтобы сделать это довольно просто, ведь это реализовано в каждом их приложении? Также, погуглив, нашлись аналогичные вопросы на Stack Overflow. Исходя из этого, оказалось, что существует проблема или, по крайней мере, нераскрытый вопрос, в котором следует разобраться.

Ниже хочу рассказать о том, как всё же можно реализовать паттерн Navigation Drawer вместе с вкладками, как в популярных приложениях от Google.

Неправильное освобождение ресурсов — одна из наиболее часто допускаемых ошибок среди Java-программистов. Под ресурсом в данной статье я буду подразумевать всё, что реализует интерфейс java.io.Closeable. Итак, сразу к делу.

Будем рассматривать на примере OutputStream. Задача: получить на вход OutputStream, сделать некоторую полезную работу с ним, закрыть OutputStream.

При разработке приложения неизбежно приходится сталкиваться с ошибками в коде и/или окружении. И очень печально когда подобные ошибки встречаются не на тестовом телефоне/эмуляторе а у живых пользователей. Еще печальнее если это не ваш друг бета-тестер и толком никто не может объяснить что и где свалилось.

Обычно при внезапном падении приложения Android предлагает отправить отчет об ошибке, где будет и подробный стэк-трейс и информация о версии вашего приложения. К сожалению пользователи не всегда нажимают кнопку «отправить отчет» а для дебаг-приложений или приложений не из маркета такая функциональность и вовсе недоступна.

Что же делать? На помощь приедет возможность языка Java обрабатывать исключения (Exceptions), в том числе и непойманные (unhandled).

Эта статья о том, как подружить языки Java и C++ в одном приложение для операционной системы Android.

На С++ написано огромное количество кода. Мне хотелось бы как-то использовать этот код в своих приложения, но почему-то у меня процесс использования вызывал некий дискомфорт. Скорей всего, это, банально, было связано с тем, что основой моей рабочей средой является Android Studio, в которой работа с нативным кодом, скажем так, не самая лучшая. Но вот мысль о том, чтобы комфортно разрабатывать приложение с нативной частью не оставляла меня никогда. Поэтому я решил попробовать скрестить всю мощь библиотеки Qt и приложение, написаное на родном для Android языке — Java.

Перевод поста Стивена Вольфрама (Stephen Wolfram) "Frontiers of Computational Thinking: A SXSW Report".
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

На прошлой неделе я выступал на SXSW Interactive 2015 в Остине, штат Техас. Вот несколько отредактированная стенограмма моего выступления:

Содержание

Наиболее продуктивный год
Язык Wolfram Language
Язык для реального мира
Философия Wolfram Language
Программы размером в один твит
Вычислительное мышление для детей
Ввод запросов на естественном языке
Масштабная идея: Символьное программирование
Язык для развёртывания
Автоматизация программирования
Масштабные программы
Интернет вещей
Машинное обучение
Исследования Вычисляемой Вселенной
Вычислять, подобно тому, как это делает мозг
Язык как символьное представление
Пост-лингвистические понятия
Древняя история
Чем будет заниматься искусственный интеллект?
Бессмертие и за его пределами
Коробка триллиона душ
Обратно в 2015 год

Для чего Java-программисты прибегают к native методам? Иногда, чтобы воспользоваться сторонней DLL библиотекой. В других случаях, чтобы ускорить критичный алгоритм за счет оптимизированного кода на C или ассемблере. Например, для обработки потокового медиа, для сжатия, шифрования и т.п.

Но вызов native метода не бесплатен. Порой, накладные расходы на JNI оказываются даже больше, чем выигрыш в производительности. А всё потому, что они включают в себя:

1. создание stack frame;
2. перекладывание аргументов в соответствии с ABI;
3. оборачивание ссылок в JNI хендлы (jobject);
4. передачу дополнительных аргументов JNIEnv* и jclass;
5. захват и освобождение монитора, если метод synchronized;
6. «ленивую» линковку нативной функции;
7. трассировку входа и выхода из метода;
8. перевод потока из состояния in_Java в in_native и обратно;
9. проверку необходимости safepoint;
10. обработку возможных исключений.

Но зачастую native методы просты: они не бросают исключений, не создают новые объекты в хипе, не обходят стек, не работают с хендлами и не синхронизованы. Можно ли для них не делать лишних действий?

Да, и сегодня я расскажу о недокументированных возможностях HotSpot JVM для ускоренного вызова простых JNI методов. Хотя эта оптимизация появилась еще с первых версий Java 7, что удивительно, о ней еще никто нигде не писал.

Здравствуйте.

Как вы, наверное, уже догадались, речь пойдет о JNI. Для тех, кто не знает что это, объясняю: JNI (или java native interface) — это такая штука, которая позволяет делать вызовы нативного кода из java машины и наоборот.

Зачем это может потребоваться? Есть несколько причин: необходимость использовать код, который уже написан для нативной платформы, необходимость реализовать что-то такое, что невозможно сделать с помощью одной JVM (например, работа с какими-нибудь специфическими железками), ну и ускорение выполнения критических кусков кода (правда, это весьма спорный момент).

Статья о программе (iOS) для запоминания английских слов методом интервальных повторений, которая учитывает ваш распорядок дня.

На хабрахабре уже несколько раз освещался вопрос о методе интервальных повторений для запоминания информации: habrahabr.ru/post/246459, habrahabr.ru/post/196448, habrahabr.ru/post/240451. Если вкратце, то интервальные повторения — это подход к запоминанию информации, заключающийся в повторении изучаемого материала через определенные, постоянно возрастающие интервалы времени (например, через 5 минут, потом через 25 минут, потом через 2 часа и т.д.).

Табличный процессор (речь идет о MS Excel или LibreOffice Calc) — это довольно занятный и универсальный инструмент. Мне часто приходилось (и приходится) пользоваться его широкими возможностями: автоматизированные отчеты, проверка гипотез, прототипирование алгоритмов. Например, я использовал его для решения задач проекта Эйлер, быстрой проверки алгоритмов, реализовал парсер одного прикладного протокола (по работе надо было). Мне нравится наглядность, которую можно добиться в табличном процессоре, а еще мне нравится нестандартное применение всего, чего только возможно. На Хабре уже появлялись интересные статьи на тему нестандартного применения Excel:
«Assembler в 30 строк на Excel»
Чем заняться айтишнику в армии или как я на VBA игры писал
«RPG-игра в рабочей книге Excel»

В этой длинной статье я хочу поделиться своими экспериментами в реактивном программировании с помощью формул табличного процессора. В результате этих экспериментов у меня получился «компьютер» с процессором, памятью, стеком и дисплеем, реализованный внутри LibreOffice Calc при помощи одних только формул (за исключением тактового генератора), который можно программировать на неком подобии ассемблера. Затем, в качестве примера и proof-of-concept, я написал игру «Змейка» и бегущуюползущую строку для этого компьютера.

Продолжаем обзор деятельности нашего Хакспейс-клуба.

Мы давно мечтали купить в наш клуб ЧПУ станок. Но решили его сделать сами. С нуля, начиная от железа и кончая программного обеспечение (прошивка контроллера и управляющая программа). И у нас это получилось.

Детали для станка старались выбирать из доступных в свободной продаже, многие из которых даже не требуют дополнительной слесарной обработки.

Большинство литературы посвященной паттернам в ООП (объектно-ориентированном программировании), как правило, объясняются на примерах с самим кодом. И это правильный подход, так как паттерны ООП уже по-умолчанию предназначаются для людей, которые знают что такое программирование и суть ООП. Однако порой требуется заинтересовать этой темой людей, которые в этом совершенно ничего не понимают, например «не-программистов» или же просто начинающих «компьютерщиков». Именно с этой целью и был подготовлен данный материал, который призван объяснить человеку любого уровня знаний, что такое паттерн ООП и, возможно, привлечет в ряды программистов новых «адептов», ведь программирование это на самом деле очень интересно.
Статья предназначена исключительно для новичков, так что «старожилы» ничего нового для себя не узнают. В основном статья описывает известные паттерны из книги «Приемы объектно-ориентированного программирования. Шаблоны проектирования.», но более популярным и простым языком.