Иванова Г.С., Ничушкина Т.Н. - Основы конструирования компиляторов, страница 5

Грамматики предшествованияLR(k)-грамматики – это класс КС-грамматик, гарантирующих существование детерминированных восходящих распознавателей (L – левосторонний просмотр, R – правосторонний разбор, k – количество символов, просматриваемых для однозначного определения следующего правила). В грамматиках этого класса отсутствуют правила с правосторонней рекурсией, и обеспечивается однозначное выделение основы. К этому классу,например, относятся грамматики с операторным предшествованием, простым предшествованием и расширенным предшествованием, обеспечивающие еще более простые алгоритмы распознавания.При восходящем разборе стек используют для накопления основы. Автомат приэтом выполняет две основные операции: свертку и перенос.

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

Основная проблемаметода заключается в нахождении способа выделения очередной основы. Проще всегооснову выделить для грамматик, получивших название «грамматики предшествования».Рассмотрим эти грамматики.Если два символа α, β ∈V расположены рядом в сентенциальной форме, то междуними возможны следующие отношения, названные отношениями предшествования:- α принадлежит основе, а β – нет, т. е. α – конец основы: α ⋅> β;- β принадлежит основе, а α – нет, т. е. β – начало основы: α <⋅ β ;- α и β принадлежит одной основе, т.

е. α =⋅ β;- α и β не могут находиться рядом в сентенциальной форме (ошибка).Грамматикой с предшествованием называется грамматика, в которой существуетоднозначное отношение предшествования между соседними символами. Это отношениепозволяет просто определить очередную основу, т. е. момент выполнения каждой свертки.Различают:1) грамматики с простым предшествованием, для которых α, β ∈V;2) грамматики с операторным предшествованием, для которых α, β ∈VТ; т.

е. отношение предшествования определено для терминальных символов и не зависит от нетерминальных символов, расположенных между ними;Оглавление383) грамматики со слабым предшествованием, для которых отношение предшествования не однозначно – оно требует выполнения специальных проверок.Пример. Грамматика описания арифметических выражений, представленная ниже,относится к классу грамматик с операторным предшествованием:<Выражение> ::= <Терм> | < Терм > + <Выражение> | <Терм> - <Выражение><Терм> ::= <Множитель> | <Множитель>* <Терм> | <Множитель> / <Терм><Множитель> ::= (<Выражение>) | <Идентификатор>Отношения предшествования терминалов (знаков операций), полученные с учетомприоритетов операций, сведены в таблицу 9.Таблица 9 – Таблица предшествования+► <⋅+ ⋅>* ⋅>( <⋅) ⋅>*<⋅<⋅⋅><⋅⋅>Обозначения:? – ошибка;< - начало основы;> - конец основы;= - принадлежат одной основе;►- начало выражения;◄ - конец выражения.( )◄<⋅ ? Выход<⋅ ⋅>⋅><⋅ ⋅>⋅>?<⋅ =? ⋅>⋅>В соответствие с этой таблицей при разборе выражения:►d+c*(a+b) ◄содержимое стека будет выглядеть следующим образом:СодержимоеАнализируе-стекамыеОтношение ОперацияТройкаРезультатсверткисимволыd+<⋅Переносc*<⋅Перенос►d+ c*(<⋅Перенос►d+ c*(a+<⋅Перенос►d+ c*( a+b)⋅>СверткаR1:= a + b<Выражение>►d+ c*(R1)=⋅СверткаR1:= (R1)<Множитель>►d+ c*R1◄⋅>СверткаR2:= c* R1<Терм>►d+R2◄⋅>СверткаR3:= d+ R2<Выражение>►R3◄Конец►►d+Оглавление394.4 Польская запись.

Алгоритм Бауэра-ЗамельзонаРезультат синтаксического анализа – дерево грамматического разбора – представляют в виде таблицы или обратной польской записи.Польская запись (в честь польского математика Лукасевича, предложившего этотвид записи выражений) представляет собой последовательность команд двух типов:1)КI, где I – идентификатор операнда – выбрать число по имени I и заслатьего в стек операндов;2)Kξ, где ξ – операция – выбрать два верхних числа из стека операндов, произ-вести над ними операцию ξ и занести результат в стек операндов.Рассмотрим алгоритм Бауэра-Замельзона, по которому осуществляется представление выражений в виде польской записи.Алгоритм Бауэра-Замельзона.

Грамматика, описывающая правила записи арифметических выражений, относится к классу грамматик операторного предшествования, т. е.порядок следования терминальных символов (знаков операций), однозначно определяетпорядок выделения троек, причем нетерминальные символы (имена операндов) на этотпорядок не влияют.Синтаксический распознаватель выражений в процессе разбора должен формироватьзапись, по которой затем выполняется генерация кода. В качестве такой записи часто используют обратную польскую запись.Согласно алгоритму Бауэра-Замельзона разбор выражения и формирование польской записи выполняется в два этапа:1)разбор выражения и построение эквивалентной польской записи;2)выполнение (или трансляция) польской записи.При этом используется два стека: стек операций – на первом этапе и стек операндов– на втором этапе.Построение польской записи выполняется следующим образом: транслятор читаетвыражение слева направо и вырабатывает последовательность команд по следующемуправилу:а) если символ – операнд, то вырабатывается команда КI,б) если символ – операция, то выполняются действия согласно таблице 10:Оглавление40Таблица 10 – Таблица генератораη\ξ+IIIIVI→+*(*IIIII(IIII)?IVIVIII←ВыхIVIV?Обозначения:? - ошибка;η - верхний символ в стеке операций;ξ - текущий символ.Операции:I – заслать ξ в стек операций и читать следующий символ;II – генерировать Kη , заслать ξ в стек операций и читать следующий символ;III – удалить верхний символ из стека операций и читать следующий символ;IV – генерировать Kη и повторить с тем же входным символом.На этапе выполнения польская запись читается слева направо и выполняется.Польская запись может использоваться как промежуточная форма не только для выражений, но и для других операторов.

Соответственно при этом для получения записидолжен использоваться модифицированный алгоритм Бауэра-Замельзона.Пример. Построить тройки для выражения (a+b*c)/d.1.Построение польской записи:Стек операций Символ Действие►(I►(a►(+I►(+b►(+*I►(+*c►(+*)IV►(+)IV►()III►/I►/d►/IV←►Конец←В результате получаем:Ka Kb Kc K* K+ Kd K/или abc*+d/ОглавлениеКомандаKaKbKcK*K+KdK/41Теперь необходимо выполнить польскую запись в соответствии с ее определением.2.

Выполнение операций:Стек операндовКоманда∅KaaKbabKcabcK*T1= b*ca T1K+T2= a+T1T2KdT2 dK/T3ОглавлениеТройкаT3= T2/d42Контрольные вопросы1. Определите, автомат c магазинной памятью. В чем особенность его использованияпри грамматическом разборе?Ответ.2.

Как построить автомат с магазинной памятью по синтаксическим диаграммам? Вчем заключается особенность полученной программы?Ответ.3. Определите LL(k) грамматики. Какими особенностями они обладают? В чем заключается метод рекурсивного спуска?Ответ.4. Определите LR(k) грамматики. Какими особенностями они обладают? В чем заключается стековый метод?Ответ.5. Какой вид имеет польская запись? Для чего она используется?Ответ.6.

В чем заключается алгоритм Бауэра-Замельзона?Ответ.Оглавление435Распределение памяти под программы и данныеПосле распознавания конструкций и определения таблиц переменных, именованныхконстант и временных переменных осуществляют распределение памяти под эти данные ипрограммы. При этом могут использоваться разные типы распределения памяти.Различают:1) статическое;2) автоматическое;3) управляемое;4) базированное.Статическое распределение памяти выполняется:а) во время компиляции – для подпрограмм и для инициализированных переменных;б) во время компоновки – для неинициализированных переменных.Автоматическое распределение памяти может выполняться для переменных подпрограмм, используемых только при активации подпрограммы. Эти переменные обычноразмещаются в стеке.Управляемое распределение памяти выполняется во время выполнения программыспециальными подпрограммами, например, new и delete.Базированное распределение памяти выполняется во время выполнения программыиз выделенного буфера.

Доступ к такой памяти осуществляется через вычисляемые адреса.Кроме этого, различают:1) локальную память;2) глобальную память.Локальная память предполагает ограниченный доступ (из подпрограммы, из файлаи т. п.). В универсальных языках программирования локальная память чаще всего отводится в стеке, т.е. для нее используется автоматическое распределение.

Однако статическая память С++ распределяется статически, но программно в нее ограничивается доступиз других подпрограмм.Глобальная память предполагает неограниченный доступ из любого места программы. Как правило эта память распределяется статически.Оглавление44Контрольные вопросы1.

Какие виды распределения памяти Вы знаете? Чем они различаются и для чего используются?Ответ.2. Чем различаются локальная и глобальная виды памяти программы?Ответ.Оглавление456Генерация и оптимизация кодовГенерация машинного кода выполняется заменой распознанной конструкции соответствующими машинными командами, например, тройка сложения целых чисел можетзаменяться последовательностью команд:MovAX, <Op1>AddAX, <Op2>Mov AX, <Result>В такой последовательности команд выполняется подстановка адресов операндов и результата.Очевидно, что код, полученный таким образом, является не оптимальным.

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

п.Оба типа оптимизации предполагают разработку соответствующих семантическихмоделей для представления результатов распознавания конструкций. Обычно с этой целью используют разного типа таблицы.Оглавление46Контрольные вопросы1. Назовите машинно-независимые способы оптимизации кода. Почему они так названы?Ответ.2. Назовите машинно-зависимые способы оптимизации кода. Почему они так названы?Ответ.Оглавление47Литература1. Д. Грис. Конструирование компиляторов для цифровых вычислительных машин –М.: Мир, 1975. – 544 с.2.

Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты.Пер. с англ. – М.: «Вильямс», 2003.3. В. Дж. Рейуорд–Смит. Теория формальных языков. Вводный курс. – М.: Радио исвязь, 1988. – 128 с.Оглавление.