А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 16
Текст из файла (страница 16)
Рнс. 2.3. Модель начальной стадии компилятора Лексический анализатор позволяет транслятору в процессе синтаксического анализа работать с многосимвольными конструкциями наподобие идентификаторов, которые записываются как последовательность символов, но рассматриваются как единицы трансляции, называющиеся токенами. Например, в выражении соппс + 1 идентификатор соппс рассматривается как отдельная единица трансляции. Лексический анализатор из раздела 2.6 позволяет выражениям состоять из чисел, идентификаторов и "пробельных символов" (пробелов, символов табуляции и новой строки). Затем мы рассмотрим генерацию промежуточного кода.
Два вида промежуточного кода продемонстрированы на рис. 2.4. Первый вид называется абстрактными синтаксическими деревьями или просто синтаксическими деревьями, представляющими иерархическую синтаксическую структуру исходной программы. В модели на рис. 2.3 синтаксический анализатор порождает синтаксическое дерево, которое позже транслируется в трехадресный код. Некоторые простые компиляторы объединяют синтаксический анализ и генерацию промежуточного кода в один юмпонент. 78 Глава 2.
Простой синтаксически управляемый транслятор во-нв)1е ЬМу < 1:т=та 1 2: о1 = а 3: 1Г <1 < ч со<о 1 б) а) Рис. 2.4. Промежуточный код для фрагмента "<)о 1=1+ 1; н)а11е ( а[1] <ч);" Корень абстрактного синтаксического дерева на рис. 2.4, а представляет собой весь цикл по-тчЬПе. Левый дочерний узел корня представляет тело цикла, состоящее из единственного присваивания 1=1+11. Правый дочерний узел корня представляет условие цикла а [1] <ч. Реализация синтаксических деревьев рассматривается в разделе 2.8. Второе распространенное промежуточное представление, показанное на рис.
2.4, б, является последовательностью "трехадресных" команд. Более полный пример приведен на рис. 2.2. Этот вид промежуточного кода получил свое название от команд вида х = у ор е, где ор — бинарный оператор, у и е — адреса операндов, а т — адрес результата операции.
Трехадресные команды выполняют не более одной операции, обычно вычисления, сравнения или ветвления. В приложении А мы применим методы из этой главы для построения начальной стадии компилятора на языке программирования 5ача, юторая транслирует инструкции в команды ассемблерного уровня. 2.2 Определение синтаксиса В этом разделе мы рассмотрим запись — "контекстно-свободную грамматику" или для краткости просто "грамматику", — юторая используется для определения синтаксиса языка программирования.
Грамматики будут использоваться как часть спецификации начальной стадии компилятора на протяжении всей книги. Грамматика естественным образом описывает иерархическую структуру множества конструкций языка программирования. Например, инструкция и-е!яе в 3ача имеет вид и (выражение) инструкция е]яе инструкция 79 22.
Определение синтаксиса Таким образом, инструкция !г"-е)ае представляет собой ключевое слово (г", за которым следуют открывающая круглая скобка, выражение, закрывающая скобка, инструкция, ключевое слово еие и еще одна инструкция. Используя переменную ехрг для обозначения выражения и переменную лгтг для обозначения инструкции, можно записать это структурное правило как вгггг! — и ( ехрг ) в(т! е!яе вгт! Здесь символ "- " можно прочесть как "может иметь вид". Такое правило называется продукцией! (ргог(пег(оп). В продукции лексические элементы наподобие ключевого слова Н' и скобок называются терминалами (гегпппа!). Переменные наподобие ехрг и вттг представляют последовательности терминалов и называются нетерииналами (поп!спи)па!8). 2.2.1 Определения грамматик Контекстно-свободная граясиатика имеет четыре компонента.
!. Множество терминальных символов, иногда именуемых токенами. Терминалы представляют собой элементарные символы языка, определяемые грамматикой. 2. Множество нетерминалов, иногда называемых синтаксическими переменными. Каждый нетерминал представляет множество строк терминалов способом, который будет описан далее.
3. Множество продукций, каждая из которых состоит из нетерминала„ называемого заголовком или левой частью продукции, стрелки и последовательности терминалов и!или нетерминалов, называемых телом или правой частью продукции. Интуитивно назначение продукции — определить один из возможных видов конструкции; если заглавный нетерминал представляет конструкцию, то тело представляет записываемый вид конструкции. 4. Один из нетерминальных символов, указываемый как стартовый или начальный. Грамматика определяется перечислением ее продукций, причем первой указывается продукция для стартового символа.
Цифры, знаки наподобие < или <= и выделенные полужирным шрифтом строки наподобие импе являются терминальными символами. Выделенные курсивом имена являются нетерминалами, 'Возможно, зго не самый удачный перевод данного термина, однако он традиционно используется а русскоязычной компькгтерной литературе (см., например, ВДж, Рейуорд-Смят. Теория формальных юыков. — Мз Радио н связь, 1988).
— Прим. лер. 80 Глава 2. Простой синтаксически управляемый транслятор Токены и терминалы Лексический анализатор компилятора считывает символы исходной программы, группирует их в лексически осмысленные единицы, которые называются лексемами, и в качестве выходных данных возвращает токены, представляющие эти лексемы.
Токен состоит из двух компонентов — имени токена и значения атрибута. Имена токенов — это абстрактные символы, используемые синтаксическим анализатором при выполнении анализа. Зачастую мы будем называть эти имена токенов терминалами, поскольку они появляются в грамматике языка программирования в виде терминальных символов. Значение атрибута, если таковое имеется, представляет собой указатель на запись в таблице символов, в которой содержится дополнительная информация о токене. Эта дополнительная информация не является частью грамматики, так что в нашем рассмотрении синтаксического анализа мы будем считать токены и терминалы синонимами. а все имена или символы без выделения могут рассматриваться как терминалы.'- Для удобства записи правые части продукций с одними и теми же нетерминалами слева могут быть сгруппированы с помощью символа ~ ("или").
Пример 2.1. В примерах этой главы используются выражения, состоящие из цифр и знаков "плюс" и "минус", например 9-5+2, 3-1 или 7. Поскольку знаки "плюс" и "минус" должны располагаться между двумя цифрами. такие выражения можно рассматривать как списки цифр, разделенных знаками "плюс" и "минус". Синтаксис используемых выражений описывает грамматика из следующих продукций: йзг — 11яг + й81г 11з1 — ~ юг — йя1г 1пн — ~ Жег йя1г — ~ О ! 1 ( 2 ! 3 ! 4 (5 ) б ~ 7 ) 8 ) 9 (2.1) (2.2) 12.3) (2.4) Тела трех продукций с нетерминалом Ляг в качестве заголовка могут быть сгруппированы: 11яг — 11яг + й81г ~ !1яг — й811 ~ й811 зОтдельиые символы, выделенные курсивом, будут использоваться и для других целей при детальном изучении грамматики в главе 4.
Например, мы будем использовать Х, У и У при указании символов, которые могут предсгаьчять собой как терминалы, гак и иегермииалы. Однако выделенное курсивом имя из двух или более символов будет всегда означать иетермииал. 2.2. Определение синтаксиса В соответствии с нашими соглашениями терминалами грамматики являются символы 01234 5б78 9 Нетерминальными символами являются выделенные курсивом имена !!ьг и с(!я!д прн этом нетерминал !!к! — стартовый; именно его продукция дана первой. г1 Продукция называется лродукг!ней нетерминала ((ог поп1епшпа1), если ее заголовок представляет собой нетерминал.
Строка терминалов является последовательностью из нуля или нескольких терминалов. Строка, содержащая нуль терминалов и записываемая как е, называется пустой строкой.з 2.22 Выведение Грамматика выводит, или порождаегн (депсе), строки, начиная со стартового символа и неоднократно замещая нетерминалы телами продукций этих нетерминалов.
Строки токенов, порождаемые из стартового символа, образуют язык, определяемый грамматикой. Пример 2.2. Язык, определяемый грамматикой нз примера 2.1, состоит из списков цифр, разделенных знаками "плюс" и "минус". Десять продукций для нетерминала с(!8!! позволяют ему быть любым из терминалов О, 1,..., 9. Из продукции (2.3) следует, что цифра сама по себе является списком. Продукции (2.!) и (2.2) выражают то правило, что любой список, за которым следует знак "плюс" или "минус" с последующей цифрой, образует новый список. Продукции (2.1) — (2.4) — это все, что нужно для определения требующегося языка.
Например, можно вывести, что 9-5+2 является списком, следующим образом. а) 9 — !!тг в соответствии с продукцией (2.3), поскольку 9 — Й8!!. б) 9-5 — !!з! в соответствии с продукцией (2,2), гак как 9 — !!зг, а 5 — с(!8!и в) 9-5+2 — !гкг в соответствии с продукцией (2.! 1, поскольку 9-5 — !гвд а 2— !!81!. га Пример 2.3. Несколько отличающимся видом списков является список параметров в вызове функции.
В )ача параметры находятся внутри круглых скобок; так, птах(х, у) означает вызов функции гвах с параметрами х и у. Единственный нюанс в таком списке заключается в том, что между терминалами ( и ) может находиться пустой список. Мы можем начать разработку грамматики для таких последовательностей с продукций Технически с может быть строкой нз нуля символов любого алфавита (коллекцнн символов). 82 Глава 2. Простой синтаксически управляемый транслятор саП вЂ” (й ( орграгатз ) ор(рагатз — рагатз ~ е рагатз — рагатз, рогат ~ рагат Обратите внимание, что второе возможное тело для орграгатз (орйопа) рагаше(ег 1пй — необязательный список параметров) представляет собой е, что означает пустую строку символов. То есть орграгатз можно заменить пустой строкой, так что саП может состоять из имени функции, за которым следует двухтерминальная строка ( ).
Заметим, что продукции для рагатз аналогичны продукциям для Пз( из примера 2.1, если заменить арифметические операторы + и — запятой, а йяй заменить на рагат. Мы не приводим продукции для рагат, поскольку параметры функции могут в действительности быть произвольными выражениями. Всюре мы рассмотрим продукции для различных языковых конструкций, таких как выражения, инструкции и т.п. и Синтаксический анализ, или разбор (рапйпй), представляет собой выяснение для полученной строки терминалов способа ее вывода из стартового символа грамматики. Если строка не может быть выведена из стартового символа, синтаксический анализатор сообщает об ошибке в строке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
