В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 13
Текст из файла (страница 13)
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год41Далее, как можно заметить, запись выражения в постфиксной записи получается приобходе построенного для выражения a*b+c*(d-e) дерева разбора (по приводившейся ранееграмматике) способом «снизу вверх слева направо» (т.е. при обходе вначале обходитсялевый потомок, затем правый, затем корень).
Соответствующее дерево разбора для нашеговыражения имеет вид+*ab*cde(для удобства в нем оставлены только элементы, соответствующие данным и операциямнад ними, другие узлы просто будут проигнорированы при обходе). Префиксная записьполучается при обходе сверху вниз (корень, левый операнд, правый операнд). Если незабыть про скобки и обходить дерево «левый потомок», «корень», «правый потомок» получим исходную инфиксную запись.Однако, как уже было сказано, вопрос построения дерева разбора остается за пределамикурса (при «стандартном» LR-разборе это неважно, дерево явно не строится, все нужныеоперации проходят прямо в процессе разбора, часто используется рекурсивный разбор – сего помощью можно довольно просто и очевидно получить префиксную запись, хотя в этомкурсе рекурсивный разбор и не рассматривается, к тому же при рекурсивном разборе всевычисления также обычно проводят сразу в процессе разбора).
Однако, можно привестиспособ LR(1) разбора выражения в постфиксную запись «вручную», «упрощенно» посравнению с автоматически генерируемым «стандартным»:1. Изначально стек разбора содержит только первый элемент выражения, очередь (всеравно свойства стека при разборе постфиксной записи не используются, а при работесо стеком стек пришлось бы потом «развернуть») постфиксной записи пуст2. Если вершина стека – терминальный метасимвол, свертываем его в <множитель>3. Если вершина стека - <+-> или <*/> - осуществляем сдвиг4. Если второй (нумерация идет от вершины – вершина – 1й, следующий за ним – 2й ит.д.) символ стека - <+->, первый непрочитанный символ - <+-> или прочитано всеили первый непрочитанный символ – то свертываем при необходимости 3й элементв <выражение>, вершину – в <терм>. Если уже свернуты - свертываем последние 3элемента стека в <выражение>.5.
Если второй символ стека - <+->, первый непрочитанный символ - <*/> тосвертываем при необходимости вершину стека в <терм>, если уже <терм> осуществляем сдвиг.6. Если второй символ стека - <*/>, то свертываем первые 3 элемента стека в <терм>.7. Если вершина стека – (, то осуществляем сдвиг.8. Если 2й элемент стека – (, то осуществляем сдвиг9.
Если вершина стека - ), 3й элемент стека – (, то при необходимости свертываем 2йэлемент до <выражения>, потом применяем свертку скобок в множитель.10. Во всех остальных случаях – входное выражение ошибочно.11. Свертка терминального метасимвола в <множитель>: если это <константа> записываем константу в очередь постфиксной записи, если <имя> - записываем вочередь постфиксной записи значение переменной с таким именем. В обоих случаяхпереименовываем название полученного объекта в стеке на <множитель>12.
Свертка <терма> в <выражение>, <выражения> в <терм>: просто переименовываемобъект в стекеЛекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год4213. Свертка <выражение><+-><терм> в <выражение>: записываем в очередьпостфиксной записи плюс или минус – что стоит, заменяем последние 3 элементастека на один <выражение>14.
Свертка <терм><*/><множитель> в <терм>: записываем в очередь постфикснойзаписи * или / соответственно, заменяем последние 3 элемента стека на один <терм>15. Свертка (<выражение>) в <множитель>: заменяем последние 3 элемента стека наодин <множитель>Запомнить такой алгоритм нереально, поэтому лучше понять основную его идею. Идеяв следующем: на каждом шагу иметь в стеке что-то вида <выражение илитерм><операция><множитель>.
Скобки игнорировать до тех пор, пока не возникнетконструкция (<выражение>). Легко видеть, что префиксная форма записи не меняет порядокследования операндов по сравнению с инфиксной – значит, в стек постфиксной записиможно «скидывать» данные по мере их поступления в стек, после чего о них «забывать» - впостфиксной записи все равно операнды идут перед операцией, а операция будет добавленапоследней – когда оба ее операнда будут уже прочитаны – просто по самой методике.Кстати, этого свойства уже достаточно, чтобы в итоге получилась корректная постфикснаязапись. В остальном – как легко проверить, описанный разбор полностью соответствуетопределению LR(1) разбора приводившейся выше формальной грамматики арифм.выражений.Следующая тема – модельный компилятор. Рассмотрим общие принципы компиляциипрограмм для процессора на простейших примерах.
Входной язык возьмем, например,простейшим диалектом BASIC:Модельный язык:1. Все переменные имеют одинаковый тип (целое число) и не требуют объявлений –как только встретилась новая переменная, она считается объявленной2. Существуют линейные массивы таких переменных. Объявляются как dimимя_переменной[длина_массива].Обращениекэлементумассива–имя_переменной[номер_в_массиве]3. Каждая команда языка пишется в отдельной строке (т.е. разделителем командслужит перевод строки), команда есть только одна - оператор присваивания,который имеет вид имя_переменной = выражение, выражение строится изпеременных, констант, обращений к элементам массива и 4х арифм. действийПример программы:dim a[3]b = 45 + 2a[2] = b + a[1]*3Процессор мы тоже возьмем упрощенный, - т.н.
стековый процессор. Он обладаетнекоторым бесконечным стеком и набором простых команд, которые он может выполнятьпоследовательно. Кроме этого, процессор умеет работать с памятью, организованной в виделинейного массива. Команды у нас будут следующие:add, sub, mul, div – извлечь из стека 2 числа и соответственно, сложить, вычесть,умножить, поделить их, результат записать обратно в стекpush – извлечь из стека число x, записать в стек число из памяти по адресу xpop – извлечь из стека число a и число x и записать a в память по адресу xconst x – положить в стек число xstop – остановить процесс вычисленийПример программыpush 0const 2const 1pushdivaddЛекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год43const 2pushsubconst 3popstop- программа вычисляет d=a+b/2-c, где c – ячейка памяти №2, a - №0, b - №1, d - №3.Наша задача – написание модельного компилятора, переводящего программу намодельном языке в программу для стекового процессора. Легко видеть, что код можнокомпилировать построчно, затем состыковывать строчки. А можно и не состыковывать – влюбом случае, наш язык несложно формализуется в виде НФБН, а значит, программаподдается LR-разбору.
Но для простоты будем все же компилировать программу построчно.На его основе мы и будем строить наш компилятор. Наша задача в этом случае сводится куказанию, каким образом осуществлять свертку. Отметим ключевые моменты.Приведем для начала формальную грамматику, подходящую для компиляции (здеськвадратные скобки, конечно, не означают необязательного параметра, а означают наличиеквадратных скобок)<объявление> ::= dim <имя>[<константа>]<присваивание> ::= <lvalue> = <выражение><lvalue> ::= <имя> | <имя>[<выражение>]<выражение> ::= <терм> | <выражение> <+-> <терм><терм> ::= <множитель> | <терм> <*/> <множитель><множитель> ::= <имя> | <константа> | <имя>[<выражение>] | (<выражение>)<+-> ::= +|<*/> ::= *|/Первый момент – общая организация компиляции.
Пока что у нас в модельном языкекаждая строчка – либо объявление новой переменной / массива, либо операторприсваивания. Объявление новой переменной не создает никакого кода, однако необходимоотслеживать все ранее объявленные переменные и где-то их хранить в ходе работыпрограммы.
Разбор будем производить по написанной выше грамматике.Итак, организация памяти. Будем хранить специальную таблицу переменных вида«имя» - «ячейка памяти». Когда в коде встретится очередное объявлениепеременной/массива, (<объявление> после разбора очередной строчки либо ненайденнаяпеременная) то запишем эту переменную в таблицу и выделим ей очередной кусок памяти.Первая переменная получит адрес 0, вторая – 1, массив длины 3 – адреса 2-4 и так далее.Разбор очевиден – если текущий указатель на свободную память – x, встретилось <имя>[<константа>] – добавляем запись <имя> - x и увеличиваем x на <константу>Разбор оператора присваивания: распределим приоритеты следующим образом:индексирование – высший, затем – умножение и деление, затем – сложение и вычитание,низший приоритет у операции присваивания.
После LR-разбора получим дерево разбора. Ввершине дерева окажется операция присваивания (в силу ее низшего приоритета). Вначалеразберем правое поддерево – оно у нас является <выражением>. Выражение это мы легкозапишем по дереву в постфиксной форме (напомним – постфиксная запись фактическиявляется обходом такого дерева снизу вверх), а постфиксная форма фактически ужереализует наш стековый процессор. Действительно, идем по выражению слева направо.Если встретилась константа – дописываем в кодconst <значение константы>Если встретилось имя – ищем имя в таблице имен, находим соответствующую запись.Если запись есть - определяем по ней адрес переменной и дописываем в код.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
