Учимся "говорить" (Part 3 - Анализаторы)

     Перед тем, как начать какие-либо телодвижения в соответствии с заданной программой (написанной на Small Basic), в начале необходимо проанализировать её исходный код.
     Этап анализа состоит из трёх фаз: Лексический анализ (ЛА), Синтаксический анализ (СА) и Семантический анализ (СмА).
     Теперь кратко пройдёмся по ним.
     В ходе Лексического анализа из исходного набора знаков (исходный код) формируются символы языка (или лексемы - это переменные, ключевые слова языка for, if и т.п.). ЛА не работает с контекстом, т.е. последовательность символов значения не имеет.
     ЛА решает следующие задачи:
1. Преобразование знаков в символы.
2. Обработка пробелов.
3. Удаление комментариев.
     На сегодняшний день существуют уже готовые инструменты для построения ЛА. Одним из таких мы и воспользуемся в дальнейшем.
     В ходе Синтаксического анализа определяется структура программы. СА работает с контекстом, используя символы полученные при ЛА. Результатом работы СА является описание программы в форме дерева (синтаксическое дерево).
     СА считывает символы и проверяет получаемую последовательность на ошибки. В дальнейшем рассмотрим два метода СА: метод рекурсивного спуска и SLR(1).
     СА так же как и ЛА может быть построен автоматически:
     В ходе Семантического анализа решаются проблемы совместимости типов переменных, области видимости и т.д.

     P.S. В следующий раз немного поговорим о грамматике и языке. И более подробно изучим Лексический анализатор: сделаем свои первые наброски этого чуда, а так же попробуем автоматизировать данный процесс.

info

Постараюсь обновляться не реже одного раза в неделю)

Учимся "говорить" (Part 2 - Цель)

Попробую более чётко сформировать цель. Буду (в перспективе надеюсь скажу "БУДЕМ", но пока я один) писать интерпретатор языка Basic под микроконтроллер AVR ATmega16 (если места не хватит, перелезу на более ёмкий контроллер, просто этот под рукой оказался). Под Basic'ом понимается диалект Small Basic (см. книжку Герберта Шилдта "С для профессиональных программистов" 1989 г.). Маленькое отступление по поводу этой книжки. В ней представлен подход к разработке интерпретатора Small Basic со всеми исходниками. Текст программы в ней написан на K&R C (я естественно только за ANSI С). Но копировать чужой код как-то не хочется (мы же учимся, результат не особо важен, сам процесс - ВОТ ЧТО ГЛАВНОЕ) поэтому из неё будут взяты только правила Small Basic.
Вот особенности этого языка (перечислю пока то, что нужно знать для построения синтаксического анализатора (подробности потом)):
1. Все переменные обозначаются одной буквой. Т.е. мы имеем двадцать шесть переменных (A-Z).
2. Переменные разных регистров не отличаются друг от друга.
3. Все числа являются целыми.
4. Символьные переменные не поддерживаются.
Пока этого хватит, остальное буду добавлять по мере необходимости. (Когда все правила языка будут сформулированы, объединю их в одном посте).

В качестве языка программирования (как уже было сказано выше), на котором этот интерпретатор будет писаться, возьму ANSI C.
Компилятор: WinAVR (+ все дополнительные приблуды к нему).
Среда разработки: AVR Studio.
Отладка будет происходить в VMLab и Proteus (иногда, для тренировки, на реальном железе).
Отдельные моменты будут тестироваться на PC (работа всяких анализаторов). В таком случае компилятор: gcc под Linux.

Все исходные коды, файлы проектов и модели буду так же выкладывать в общий доступ.
P.S. "Счастья для всех, Даром, и пусть никто не уйдёт обиженным" (с) Стругацкие

Интересные поделки (шасси)

Представляю вам творение одного моего товарища "Тахиона експлужена" (да-да именно так его звать). Чувак просто мастер творить всякие срывающие мозг шасси для разных робототехнических штук. Причём (как видно из фоток ниже) предпочитает детский железный конструктор. Это одна из его поделок: мини-фрезерный станок. Правда на нём нет одной детали: шпинделя (фрезерной головки) и привода с редуктором для неё. И отсутствует очень важная вещь!!! Это контроллер! Вот сижу и думаю, может потратить драгоценное время и сварганить для фрезера "мозги" и софта для них написать... (у создателя видать лень не дала этим заниматься, Тахионыч! это камень в твой огород). Кстати, на нём можно по-координатно привода подключать)))) прикольно))).
Если интересно, могу более подробно описать его особенности.
P.S. У чувака есть ещё прикольные поделки... сфоткаю - выложу)

Учимся "говорить" (Part 1 - Pilot)

В последнее время стал всё чаще думать о написании интерпретатора какого-либо языка. Спрашиваете: ЗАЧЕМ! это мне нужно? Я отвечу! Есть две причины. Первая, ну и, наверное, для этого блога самая важная – это любопытство. Всегда было интересно разобраться в том, как работают эти самые лексические, синтаксические и т.п. анализаторы. Да и вообще сам процесс построения такой программы как интерпретатор (ну или компилятор) завораживает и позволяет прикоснуться к чему-то новому и доселе неизвестному. Вторая причина достаточно практическая. Мне довольно много приходится заниматься микропроцессорными системами, и часто попадаются такие, в которых встроен, например интерпретатор BASIC’а, а то и вообще полноценный язык технологического программирования. Это в разы сокращает время разработки прикладной программы для проектируемой системы, по сравнению, что если бы софт требуемой функциональности писался на C или Assembler.
Значит, утверждаем проект! Написать интерпретатор языка программирования (с этим мы определимся чуть позднее) для микроконтроллера (я буду делать под AVR).
Ну вот! Начало положено! Осталось только дерзать!
Все свои наработки, идеи, решения, предложения и мысли буду писать здесь по мере формирования и накопления.
Доживёт ли идея до своей конечной реализации: НЕИЗВЕСТНО! В этом и состоит особенность этого блога! Всё что здесь начинается, не обязательно тут и закончится!
P.S. Материал буду стоить на основании информации из следующих книг:
Опалева Э. А., Самойленко В. П. Языки программирования и методы трансляции. – СПб.: БХВ-Петербург, - 2005.
Карпов Ю. Г. Теория и технология программирования. Основы построения трансляторов. – СПб: БХВ-Петербург, 2005.
Хантер Робин. Основные концепции компиляторов.: Пер. с англ. – М.: Издательский дом Вильямс, 2002.
Ну и, конечно же ''Книга Дракона'', которая в принципе в представлении не нуждается, но я всё равно напишу:
Ахо, Сети, Ульман. Компиляторы: принципы, технологии и инструменты.: Пер. с. англ. – М. : Издательский дом Вильямс, 2003.
Ну что же… пожелаем себе удачи! :))

... по Инерции

Хотелось бы внести некоторые пояснения к предыдущему сообщению.
Под средой моделирования я скорее понимаю некоторую CAD систему. Т.е. в идеале у нас получается этакая Система Автоматизированного ПРоектирования для любителей создавать свои новые формы жизни. Результатом разработки в такой системе является законченные прототипы сущностей с набором свойств и определённым поведением, а так же карта начального расселения особей разработанных ранее прототипов. При этом можно описать особенности местности и т.п. После этого проект загружаем в симулятор и наслаждаемся!!!
P.S. Я знаю, что существует масса игр на подобную тему. Но здесь есть прекрасная возможность окунуться самому в интересные научные дебри этого вопроса))) (имею ввиду математику, искусственный интеллект, нечёткую логика, генетические алгоритмы и многое многое другое)
P.S.S В следующий раз думаю осветить более земную и более практическую вещь)

Мысли об искусственном

Некоторый порядок по теме искусственного интеллекта и искусственного разума у меня сложится после начала чтения одной замечательной книжки: М. Арбиб "Метафорический мозг". Долго не мог определиться с этими понятиями и подходами, на которых они строятся.
Теперь более или менее всё ясно. Человека, а точнее его мозг (поведение, мышление и т.п.), можно рассматривать с двух позиций:
1. Человек - это животное.
2. Человек - это компьютер.
Первая метафора сравнивает человека с животным. Изучая наших меньших братьев, мы пытаемся найти у них сходства и различия с человеком, в надежде, что сможем понять как устроены мы сами.))

Вторая метафора сравнивает человека с ЭВМ. Т.е. мозг - это одна большая программа с кучей различных подзадачь (упрощенно конечно, это просто делается для того, чтобы попытаться понять работу мозга). Другими словами мы создаём модель. Если при разработке какого-либо программно-аппаратного комплекса, придерживаться этого направления, то в ходе построения мы должны тем или иным образом имитировать человека. Т.е. брать во внимание физико-химические провецессы происходящие в головном мозге, пытаться имитировать работу рецепторов органов чувств насколько это возможно и т.д.
НО!!! Это только одна сторона медали метафоры Человек - это компьютер. И есть ещё вторая, имя ей - Искусственный Интеллект. Эта область кибернетики очень хорошо прижилась в нашем современном мире. Главная её особенность - это сделать поведение программы (или устройства) "разумным" только на вид. Внутренняя структура при этом может не иметь ничего общего со строением мозга. (На ум сразу приходят системы распознования образов и речи).
Очень интересной так же является тема: Искусственная Жизнь)).
В голове всё вертятся идеи, по поводу создания какой-нибудь песочницы, для моделирования подобных систем (типа игры "Жизнь" или http://www.electricjungle.ru/).
Вопросы самоорганизации и взаимодействия искусственных сообществ вызывают обильное слюноотделение))) :)
Ура! Вот и наш первый мини проект: Среда моделирования поведения сущностей. Каждая сущность относится к определённому классу. Они (сущности) могут взаимодействовать между собой и с внешней средой. Ну и живут по своим законам. Можно например моделировать работу и общение группы нанороботов, летящих ядерных ракет и т.п. У кого на что фантазии хватит))) Дерзайте!

P.S. Буду Очень благодарен за любые комментарии)

Стартуем!

Предлагаю вашему вниманию свои "попытки видеть"))) Что всё это значит, я думаю вы поймёте со временем, читая этот блог. :))

Опубликовать сообщение