Topshiriq; Mavzungiz mundarijasi va birinchi nazariy bob bo’yicha hisobotni topshirish (10 ball)

Компилятор с точки зрения теории формальных языков выполняет две основные функции:

1. 
   он является распознавателем для языка исходной программы.
   

Получает на вход цепочку символов входного языка, проверяет ее принадлежность языку и выявляет правила, по которым эта цепочка построена;

2. 
   он генерирует результирующую программу. На выходе создается цепочка выходного языка по определенным правилам. Распознавателем сгенерированной цепочки объектной программы будет выступать вычислительная система.
   

Лексический анализ. Эту часть компилятора выполняет сканер, который читает литеры программы (символы) на исходном языке и строит из них слова (лексемы) исходного языка. На входе сканера (лексического анализатора) текст исходной программы, выходная информация передается для дальнейшей обработки на этап синтаксического разбора.
Синтаксический разбор − это основная часть компилятора на этапе анализа. Здесь в тексте исходной программы выделяются синтаксические конструкции. Кроме того, проверяется синтаксическая правильность программы.
Семантический анализ − это часть компилятора, проверяющая часть текста исходной программы с точки зрения семантики входного языка.
Оптимизация − это процесс, связанный с обработкой уже порожденного текста и оказывающий существенное влияние на качество и эффективность результирующей программы.
Генерация кода − это фаза, на которой непосредственно порождаются команды, составляющие предложения выходного языка и текст результирующей программы в целом. Фаза генерации кода основная на этапе синтеза результирующей программы. Кроме этого, генерация обычно включает в себя и оптимизацию.
Глава 1. Генерация случайных чисел
1.1. Генерация случайных чисел
Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) – алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).
Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии.
Если генератор выдает числа, смещенные в какую-то часть интервала (одни числа выпадают чаще других), то результат решения задачи, решаемой статистическим методом, может оказаться неверным. Поэтому проблема использования хорошего генератора действительно случайных и действительно равномерно распределенных чисел стоит очень остро.
Строго говоря, правильным названием для этого раздела было бы "генерация псевдослучайных чисел", т.к. все алгоритмы, представленные здесь, генерируют числа, не являющиеся случайными в строгом смысле этого слова. Вместе с тем, на практике слово "псевдо" часто опускают по соображениям удобства, и также исходя из того, что в большинстве случаев достаточно и той степени случайности, которую обеспечивают такие "не совсем случайные" числа. Для простоты изложения так поступим и мы.
Существует ряд алгоритмов для генерации случайных чисел. В состав стандартных библиотек практически всех языков программирования входит линейный конгруэнтный генератор, использующий для генерации очередного случайного числа Xk+1 константы a, c и m, а также предыдущее случайное число: Xk+1 = (aXk +c) mod m. Несмотря на свою простоту, этот генератор иногда оказывается достаточно хорош. Однако в сложных задачах у него выявляется ряд недостатков, которые здесь нет смысла подробно рассматривать (анализ некоторых из них можно найти в ссылках в конце статьи). Большинство алгоритмов генерации случайных чисел довольно-таки сильно привязаны к конкретному языку программирования и конкретной вычислительной платформе (главным образом в части работы с целыми числами, обработкой переполнений и т.д.). Однако Пьером Л'Экайером (Pierre L'Ecuyer) был приведен портируемый алгоритм, пригодный для реализации. Данный алгоритм по своему качеству намного выше линейного конгруэнтного генератора. Хотя он не проходит некоторые сложные статистические тесты (мало какой алгоритм пройдет ВСЕ эти тесты), на мой взгляд, он достаточно хорош для применения в большинстве практических задач.