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

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

45. Синтаксический разбор
Вывод цепочки с помощью правил грамматики может быть задан не только в виде синтаксического дерева. Если пронумеровать правила грамматики, то последовательность номеров используемых правил также задает вывод.
Определение. Последовательность номеров правил грамматики Г, применение которых позволяет построить вывод рассматриваемой цепочки s из начального символа грамматики, называется синтаксическим разбором s.
Например, в следующей грамматике
Г1. 9:
Vт = { i, +, * , (, ) }, Va = {<E>, <T>, <P>}
R ={ (1) <E> →<E> +<T>,
(2) <E> →<T>,
(3) <T> →<T> *<P>, 
(4) <T> →<P>,
(5) <P> → (E),
(6) <P> → i },
правила которой пронумерованы, вывод
<E> → <E> +<T> → <T> +<T> → <T> *<P> +<T> →
<P> *<P> +<T> → i * <P> +<T> → i * i +<T> →
i * i +<P> → i * i + i
имеет синтаксический разбор [1,2,3,4,6,6,4,6].
Если в процессе построения вывода появляются промежуточные цепочки, содержащие несколько нетерминальных символов, то можно продолжать вывод, заменяя любой из них. Таким образом, одни и те же правила могут быть использованы при выводе цепочки в разном порядке.
Например, вывод цепочки i + i в грамматике Г1. 9 может быть получен десятью различными способами.
44. Лексический анализатор
Первая стадия работы компилятора называется лексическим анализом, а программа, её реализующая, - лексическим анализатором (ЛА). На вход лексического анализатора подаётся последовательность символов входного языка. ЛА выделяет в этой последовательности простейшие конструкции языка, которые называют лексемами. Примерами лексем являются идентификаторы, числа, символы операций, служебные слова и т.д. ЛА преобразует исходный текст, заменяя лексемы их внутренним представлением - токенами. Токен может включать информацию о типе лексемы указатель на её символьное значении. Кроме того, для некоторых типов лексем ЛА строит таблицы, например, таблицу идентификаторов, констант, которые используются на последующих стадиях компиляции.
Требования к лексике исходного языка
К пробельным символам относятся: пробел (ASCII 32), перевод строки (ASCII 13), возврат каретки (ASCII 10). Исходный язык должен иметь свободный синтаксис, т. е. пробельные символы служат только для разделения лексем, их количество и вид символов не влияет на смысл программы.
Язык должен поддерживать комментарии двух видов: однострочные и многострочные, например /* ... */ и //.
Классы лексем:
1. идентификаторы
o ключевые слова
2. числа
o целые
o вещественные
3. строки
o escape-последовательности -- включая кавычку и перевод строки
4. разделители
o скобки
5. знаки операций
o односимвольные
o многосимвольные -- использовать "жадный" алгоритм
Требования к лексическому анализатору
Лексический анализатор, оформленный в виде отдельной программы, должен:
1. Работать как консольное приложение Windows.
2. При запуске без аргументов выдавать краткую информацию об использовании, а также фамилию и номер группы автора.
3. Принимать в качестве аргумента в командной строке имя входного файла.
4. Считывать из входного файла текст, производить его лексический анализ.
5. Выдавать результаты на стандартный вывод (stdout).
6. В случае обнаружения ошибки выводить сообщение об ошибке включающее номер строки и номер символа, после прочтения которого была обнаружена ошибка.
7. Выводить список распознанных лексем, по одной лексеме в строке.
8. Для каджой лексемы указывать её класс и исходный текст. При наличии выводить также значение лексемы (для лексем классов "число" и "строка").
9. Рекомендуется все сообщения выводить на правильном английском языке. В случае недостаточных знаний следует все сообщения выводить на транслите. Не допускается смешивать английский язык с транслитом.
Исходный код лексического анализатора должен:
1. Содержаться в отдельном модуле.
2. Состоять из классов (абстрактных типов данных), описывающих лексический анализатор (Scanner), лексему (Token), класс лексем (TokenClass)
3. В классе Scanner поддерживать методы для инициализации (с параметром -- именем исходного файла), перехода к следующей лексеме, поручения текущей лексемы, получения текущей позиции в исходном файле
4. В классе Token поддерживать методы для получения класса, исходного кода и значения лексемы.
5. Сообщать об ошибках либо при помощи механизма исключений, либо путём возврата кода ошибки. Не допускается непосредственный вывод на консоль или прекращение выполнения программы из подсистемы лексического анализа.

46. Общие принципы нисходящего и восходящего методов разбора
Как уже было сказано, задача синтаксического анализа применительно к ФГ состоит в построении синтаксического дерева, соответствующего входному предложению языка. В нисходящем синтаксическом анализе дерево строится «сверху -вниз» от предка к потомкам, что соответствует замене нетерминала левой части на правую часть. Рассмотрим этот процесс подробнее.
1.    Дерево строится «сверху-вниз» и «справа-налево», т.е. на каждом шаге выбирается очередная, самая левая «незакрытая»  нетерминальная вершина, для которой строится поддерево.
2.    Каждому шагу соответствует замена нетерминального символа, соответствующего левой части правила, на его правую часть.
3.    Единственная «свобода выбора» и сущность алгоритма нисходящего распознавания заключается в выборе для группы правил с одинаковой левой частью соответствующей правой части.
4.    Появляющиеся в процессе построения терминальные вершины «закрывают» соответствующие символы входного предложения (в каждый момент имеет место «незакрытая» часть входного предложения).
5.    Единственным основанием для выбора, обозначенного в п.3, является очередной «незакрытый» символ входного предложения (в общем случае это может быть k символов от начала незакрытой части.
6.    Алгоритм должен быть однозначным и жадным, т.е. каждый очередной шаг построения дерева не должен быть отменен последующими шагами, а выбор одного из нескольких правил должен быть однозначным.
Перечисленные идеи нисходящего разбора соответствуют классу грамматик, именуемому LL(k), т.е. идеи эти «работают» на грамматиках соответствующего класса:
• •        Первая L обозначает принцип просмотра входного предложения (цепочки) в направлений слева-направо (left) c последовательным «закрытием» символов терминальными вершинами дерева;
• •        k – обозначает глубину просмотра «незакрытой» части  цепочки для принятия решения о выборе одной из правых частей правила, соответствующего очередному нетерминалу. Обычно k=1;
• •        Вторая L соответствуют термину «левосторонний вывод» (left), т.е. нисходящий разбор с заменой левой части правила на правую.
Какими свойствами должны обладать LL(1)-грамматики, будет ясно позднее, после того, как будет изложены принципы организации и алгоритм работы нисходящего распознавателя. Однако основное принцип должен быть соблюден всегда: для каждого нетерминала и очередного незакрытого символа входной строки должна быть обеспечена возможность однозначного и окончательного (безвозвратного) выбора правой части правила, содержащего этот нетерминал в левой части.

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

T = {a,*,+,#} N = {Z,U,B,A}
Z :: U#    // 1
U :: U+B    // 2
U :: B    // 3
B :: *B    // 4
B :: A    // 5
A :: Aa    // 6
A :: a    // 7
Приведенная грамматика продуцирует цепочки вида **aa+aa+*aaa. Из правил грамматики видно, что первая замена производится по правилу A::a, иначе в цепочке просто нет необходимых нетерминалов для подстановки. Затем в нетерминалу A справа «присоединяются» терминалы a из входной строки, а уже затем – символы * слева.
Теперь нужно обсудить, как будет выглядеть распознаватель и каковы будут принципы его работы. Во-первых, по аналогии с нисходящим разбором можно предположить, что для обнаружения основы достаточно пары символов – последнего символа основы и следующего символа строки (в нашем примере это сочетание aa). Т.е. для каждой пары символов грамматики однозначно можно сформулировать утверждение, является ли эта пара концом основы или нет. Опять-таки это связано с глубиной просмотра вперед входной строки – она равна 1.
Во-вторых, распознавателю необходим стек, и для него требуется определить функциональное назначение. Поскольку просмотр строки в поисках основы требует сохранения пройденных символов, резонно это делать в стеке. Тогда замена правой части правила (основы) на левую будет также производиться в вершине стека. Сам стек будет хранить «недосвернутую» просмотренную часть цепочки, для которой еще не накоплена основа.
Теперь можно сформулировать основные принципы восходящего разбора c использованием магазинного автомата (МА), именуемого также методом «свертка-перенос»:
•        Первоначально в стек помещается первый символ входной строки, а второй становится текущим;
•        МА выполняет два основных действия: перенос (сдвиг - shift) очередного символа из входной строки в стек (с переходом к следующему);
•        Поиск правила, правая часть которого хранится в стеке и замена ее на левую – свертка (reduce);
•        Решение, какое из действий – перенос или свертка выполняется на данном шаге, принимается на основе анализа пары символов – символа в вершине стека и очередного символа входной строки. Свертка соответствует наличию в стеке основы, при ее отсутствии выполняется перенос. Управляющими данными МА является таблица, содержащая для каждой пары символов грамматики указание на выполняемое действие (свертка, перенос или недопустимое сочетание -ошибка) и сами правила грамматики.
•        Положительным результатом работы МА будет наличие начального нетерминала грамматики в стеке при пустой входной строке.
Как следует из описания, алгоритм не строит синтаксическое дерево, а производит его обход «снизу-вверх» и «слева-направо». В соответствии с этим, грамматика, допускающая распознавание подобным методом, называется LR(1) – ( left –просмотр входной строки слева направо,  right-правая подстановка – замена правой части на левую, восходящий разбор,  1-глубина просмотра входной строки для принятия решения).
Для начала заполним управляющую таблицу неформально, просто рассматривая, как должен себя вести автомат в предыдущем примере, включающем достаточное разнообразие вариантов синтаксиса. Столбцы таблицы соответствуют возможным текущим символам входной строки (естественно, только терминальным). Строки – символам в вершине стека (как терминальным, перенесенным из входной строки, так и нетерминальным – результатам предыдущих сверток). Около каждого действия укажем порядковый номер шага алгоритма, выполняемого для этого примера (в таблице отмечены только первые 10 шагов, соответствующие построению изображенной на рисунке части дерева). Для свертки перечислим также номера правил, по которым она может производиться. Явно недопустимые сочетания обозначим через минус.

a * + #
A С3(6,7) - С5(6,7) С(6,7)
* П2 П1 - -
+ П10 П - -
A П4 - С6(5) С(5)
B - - С7,8(2-4) С(2-4)
U - - П9 П
Z - - +
Понятно, что содержательное заполнение управляющей таблицы можно выполнить только для простых грамматик. Следующим шагом является разработка формальных методов заполнения таких таблиц, которые основаны на анализе свойств и соотношений между символами, имеющим место в формальной грамматике.