пятница, 24 сентября 2010 г.

Простейший компилятор простейшего языка C в Assembler. Часть 1. Транслитератор

Два слова в общем

Для общего развития, никогда не помешает написать компилятор языка. Я не ставлю перед собой задачу написать компилятор c++ или c#, задачу которую я перед собой ставлю - это необходимый минимум для ознакомления с теорией компиляции.

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

Суть компиляции заключается в переводе одного языка в другой, я бы назвал это трансляцией или просто переводом. То есть компилятор не исполняет код, а он его переводит.

Наш простейший компилятор языка C (далее TheSimpliestCCompiler - tsico), будет разбит на четыре блока или более: transliteration unit, lexical unit, syntax unit, generation unit. Получатся четырех-проходной компилятор. Чем же занимаются эти блоки?

Transliteration Unit


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

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

Lexical Unit

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

Syntax Unit 

Получает набор лексем, проверяет синтаксис. Определяет набор атомов(простейших единичных
конструкций языка).

Generation Unit

Получает набор атомов и по ним строит программу на выходному языке. Это достаточно простой блок.

Транслитератор

Сегодня, мы приступим к транслитератору. Сразу оговорюсь, язык на котором, мы будем писать транслитератор - C#.

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

Определимся с символьными классами для простейшего прототипа языка C:

  • letter - [A-Za-z]
  • digit - [0-9]
  • whitespace - ' '
  • newline - '\n'
  • compare - [><=!]
  • arithmetic - [+-/*]
  • ( - '('
  • ) - ')'
  • ; - ';'
  • { - '{'
  • } - '}'
  • . - '.'
  • : - ':'

Символы, которые не вошли в данный перечень отнесем к классу other.

Я не буду приводить весь код транслитератор. Покажу лишь фрагмент:

class TransliterationUnit
{

    // ... 

    public void Transliterate(
        string input, string output)
    {
        // don't do this at production, 
        // reading string to memory can be 
        // so dangerous on files with larger size
        string code = File.OpenText(input).ReadToEnd().
                           Replace("\r", "").
                           Replace("\t", "").Trim().
                           ClearExtraWhitespaces();
        List<Symbol> symbols = new List<Symbol>();

        foreach (char c in code)
        {
            
            if (GetSymbolClass(c) != "other")
            {
                symbols.Add(new Symbol() { 
                   Value = c, 
                   Class = GetSymbolClass(c)});
            }
            else
            {
                _logger.Log(String.Format(
                    "Unexpected symbol - '{0}'", c));
            }
        }

        SaveSymbols(output, symbols);
    }

    // ... 
}

Если у вас есть желание ознакомиться с полной работающей версии транслитератора компилятора tsico (я упоминал о названии выше), то вы можете скачать проект с исходным кодом для Visual Studio 2010.

Литература

В завершение я бы хотел посоветовать вам книгу "Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман: Компиляторы. Принципы, технологии и инструментарий".

Отражение точки относительно произвольной прямой - Windows приложение

Как следствие тема о "отражении точки относительно произвольной прямой" тема развилась в такое простое приложение:


Для чего я публикую код этого приложения? Возможно, это не лучший пример, но там затронуты такие темы, как:

  • Перетаскивание графических объектов используя события MouseUp, MouseDown, MouseMove формы. 
  • Изменение курсора мыши на любой другой. 
  • Анимация. 
  • Работа с координатами, перевод координат из одной системы в другую. 
Если вам интересны вышеперечисленные темы, то код для вас. Этот код не является лучшим, а всего лишь наброски идей. Проект для Visual Studio 2010, вы можете скачать отсюда

понедельник, 13 сентября 2010 г.

Отражение точки относительно произвольной прямой

Я уточню название поста - зеркальное отражение точки относительно произвольной прямой проходящей через начало системы координат. Вот стоит перед вами такая задача, вам дана точка с координатами x;y и прямая заданная уравнением ax + by = 0. Программа должна на входе получить a; b; x; y, а на выходе новые отраженные x;y.

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

Например, нам нужно повернуть объект на не который угол. В данном случае мы можем использовать так называемую матрицу поворота (Rotation Matrix или просто R). Как ее получить?






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

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






Сначала мы повернем объект до нуля, потом отразим его и вернем в конечное положение. Данные преобразования выполнить достаточно легко - необходимо использовать матрицу поворота и отражения. Для удобства все преобразования сведем к одной матрице, назовем ее Result Matrix и Result Matrix = Rotation Matrix * Reflection Matrix * Rotation Matrix. А уже потом результирующую матрицу мы применим к объекту, в данном случае к точке. 

Как же мы узнаем угол поворота до оси абсцисс, легко мы знаем, что y = kx + b; и мы знаем, что k - это угловой коэффициент, который как раз и показываем отклонение относительно оси абсцисс, k = tan(alpha). Угол мы легко получим, alpha = atan(k). Но у нас же уравнение вида ax + by = 0 - не проблема, приведем его к нужному нам виду y = -(a/b)x; Тогда угол поворота alpha = atan(-a/b), обратный угол поворота это просто -alpha. Итого, у нас есть угол поворота, осталось найти матрицу отражения. А это легко, она также заранее известна, матрица отражения относительно оси абсцисс равна:


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



Код проекта на C#, который демонстрирует решение данной задачи я выложил здесь. Внимание! Проект работает в Visual Studio 2010, желательно Premium. Если же проект вам не удастся открыть, то достаточно скопировать код из файла Program.cs и перенести его в другой проект. 

Если заметите ошибки - сообщите, спасибо и успехов вам! 

суббота, 4 сентября 2010 г.

Сколько времени пользователь провел на сайте?

Я знаю по крайней мере 3 способа, как узнать сколько времени человек провел на сайте, если вы знаете больше, обязательно напишите об этом в комментариях. 

Способ №1. 

До этого способа я уже думаю многие догадались, суть его заключается вот в чем: когда пользователь заходит на сайт, мы с помощью JavaScript на событие load объекта window запускаем таймер и в какой-нибудь переменной записываем время посещений. Когда пользователь выходит с сайта и происходит событие unload объекта window мы на сервер посылаем собранное время с использованием технологии AJAX. 

Внимание! В этом способе есть одна загвоздка и она существенна. Браузер Opera не поддерживает событие unload объекта window. А это значит, что с помощью этого способа вы ни  
как не узнаете сколько времени человек провел на сайте. 

Способ №2. 

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

Этот способ лишен недостатка первого способа связанного с браузером Opera. Но в этом методе есть другой недостаток, если пользователь посетит сайт лишь один раз, мы так и не сможем узнать, сколько времени он провел, так как не будет повторного посещения, при котором мы сможем отправить на сервер собранные данные. 

Способ №3. 

Этот способ можно назвать самым прямо-в-лобным, так как суть его заключается в следующем, пользователь заходит на веб-страницу и мы запускаем таймер, внимание!  Теперь мы каждые 1-3 секунды отправляем запрос на сервер с подсчитанным секундами.

У этого способа один большой недостаток - постоянное общение с сервером. Зато он лишен недостатков двух предыдущих. 

Я предлагаю вашему вниманию простую реализацию 3-го способа, которую выложил здесь. Хотя я вам советуют комбинировать 1, 2 способы и 3-ий использовать только в крайних случаях. 

Спасибо за внимание, удачного вам collecttiming`а!



четверг, 2 сентября 2010 г.

Обратная Польская Нотация

Мне больше нравится название на английском языке: Reverse Polish Notation (RPN), коим я и буду пользоваться.

Все мы с ранних классов, привыкли считать выражения такого вида 2 + 2 = ? или 2 * 2 + 2 = ?, может быть даже так (2 - 1) * 3 + 5 = ?. В нас буквально заложено понимание того, что каждая операция в приведенных выражениях имеет свой приоритет и это очень важно! В следствии чего дети всегда путали приоритеты или может быть вы не путали? Также усложняется читабельность ибо когда читал выражение, а потом увидел *, то сразу приходится в голове его перестраивать.

Более удобным видом описания мат. выражений является обратной польская запись (RPN), ее предложил польский математик Лукашевич. Она предлагает избавиться от приоритетов и убирает скобки. В общем выражение становится читать легче.

Давайте, попробуем перевести выше приведенные мной выражения в RPN, а делается это так:
2 + 2 в RPN будет 22+, то есть сначала идут операнды (их два), а затем операция, которую нужно над ними выполнить. Еще 2 * 2 + 2  22*2+, я знаю, что вам до сих привычней первый вид. Заметьте привычней, но не удобней. А теперь переведем (2 - 1) * 3 + 5 в RPN: 21-3*5+.

Помимо того, что мы избавились от скобок, так нам еще и не нужно запоминать приоритеты операций. Попробуем вычислить теперь последнее выражение 21-3*5+, по шагам:
  1. 21- = 1, в итоге получаем 13*5+
  2. 13* = 3, теперь rpn равняется 35+
  3. 35+ = 8, что и является результатом выражения. 
Помимо того, что мы облегчили способ чтения математических выражений для себя, так и компьютеру, теперь будет считать их легче. 

Теперь перейдем к нашей задаче. Нам необходимо реализовать калькуляцию выражений вида (A+B)*C/D-E используя язык программирования C#. Также вместо переменных (A, B, C  и т.д.) мы будем использовать простые цифры (0-9).

По крайнее мере есть два алгоритма перевода выражений в обратную польскую запись RPN:
  1. Используя бинарные деревья.
  2. Используя стек.
Я покажу перевод выражений в обратную польскую запись на примере стека, после чего продемонстрирую вычисление мат. выражений с использованием RPN.

Для перевода обычного мат. выражения в rpn я написал простой класс Converter, я не буду приводить весь код класса, его вы сможете скачать на code.google.com в конце статьи я указал ссылку, а приведу лишь метод ToRpn, ибо я считаю он более важен.

    public string ToRpn(string expression)
    {   
        // очищаем стек
        _stack.Purge();
        string output = "";
          
        // обходим строку посимвольно
        foreach (char c in expression)
        {   
            // если встретили закрывающую скобку
            if (c == ')')
            {  
                // вытаскиваем операции из стека
                // пока не дойдем до открывающейся скобки 
                char op = (char)_stack.Pop(); 
                while (op != '(') 
                {
                    output += op;
                    op = (char)_stack.Pop();
                }
            } 
            // если встретили цифру
            else if (Char.IsDigit(c))
            {
                // сразу добавляем ее к выходной строке
                output += c;
            } 
            // если открывающую скобку
            else if (c == '(')
            {
                // то помещаем ее в стек
                _stack.Push(c);
            }
            // если встретили арифметическую операцию
            else if (IsArithmeticOperation(c))
            {   
                // если стек - пуст
                if (_stack.IsEmpty)
                {
                    // помещаем операцию в стек
                    _stack.Push(c);
                }
                else
                {
                     // проверяем приоритеты 
                     if (GetPriority(c) > 
                         GetPriority((char)_stack.Top))
                     {
                         _stack.Push(c);
                     }
                     else
                     {
                         
                            while (!_stack.IsEmpty &&
                                   GetPriority(c) <= 
                                   GetPriority(
                                       (char)_stack.Top))
                            {
                                output += 
                                    (char)_stack.Pop(); ;
                            }                        
                            _stack.Push(c);
                     }
                }
            }
        }

        // добавляем в выходную строку оставшиеся символы
        while (!_stack.IsEmpty)
        {
            output += (char)_stack.Pop();
        }
   
        return output;
    }

Думаю, комментарии дадут вам понять шаги алгоритма, он достаточно прост. Visual Studio проект с использованием C# можно скачать отсюда.

Используемые материалы: 
Спасибо за внимание, вопросы и замечания принимаются в комментариях!