Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 38
Текст из файла (страница 38)
Хорошая модеть лексического апализатора — копечный преобразователь. Мы обсуждала конечные преобразователи и их применение к лексяческому анализу в разд. 3.3. Методы, ко~о. рыми можно потьвоваться для помещения информации в таблицы имен и извлечения ее оттуда, будут изложсны в гл, 1О.
Синтаксический анализагор воспринимаю выход лексического анализатора и разбнраег его в соответствии с некоторой вход. иой грамматикой. Эта грамматика аналогична грамматике, использованной при описании вход1гого языка. Однако грамматика входного языка обычно не уточняет, какие конструкции следует считать лексемами. Прпмсрамп некоторых конструкпий, которые обычно распознаются во время лексического анализа, служа~ ключевые слова, константы и такие идентификаторы, как метки и имена переиенных. Но эти же конструкции могут распознаваться и синтаксическим анализатором, и на практике ие существует жесткого правила, опрсделяюптего, какие конструкпии должны распознаваться на лексическом уровне, а какие надо оставить синтаксическому анализатору.
После синтаксического анализа можно считать, что исходная программа преобразована в дерево, называемое сиишохсическим. Синтаксическое дерево тесно свяаано с деревом вывода исходной программы и, как правило, является просто деревом вывода с удаленными цепочками цепных правил. В синтаксическом дереве виутрснние верщины в основном соответствуют операциям, а листья представляют операнды, состовщие из указателей вкодов в таблицу имен Структура синтаксического дерева отражает синтаксические правила яаыка программирования, на котором написапа исходная программа. Ллн физического представления сюн аксического дерева существует несколько способов, которые мы разберем в следующем разделе.
Представление синтаксиче- ского дерева мы будем называть лрожежуглочнои програльиой Фактическим выходом синтаксического анализатора может быть последовательность команд, необходимых для того, чтобы строить промежуточную программу, обращаться к таблице имен, изменять ее и вылавать, котла зто требуется, лнагностические спобпеения. В гл. 4 — 7 мы рассмотрели модель синтаксического анализатора, порождаюпгую левый или правый разбор. В то же время свойства свнгаксических деревьев, используемых на прак- югке, позволяют легко заменить номера правил в правои илн левом разборе командами построения сингаксическога дерева и выполнения операций иад твблипей вчен. Поэтому имеет смысл считать левые и правые разборы, порождаемые анализаторами, описанными в гл.
4 — 7, промежуточными программами, а между синтаксическим деревом и деревом разбора не делать сущест- венного различия. Компилятор должен также проверять, соблюдены ли опреде- ленные семантические соглашения входного языка. Приведем несколько общих примеров таких соглашений: (1) каждая операторная метка, на которую есть ссылка, должна фактически появляться в качестве метки некоторого оператора в исходной программе, (2) ннкакой идентификатор не может быть описан более од- ного раза, (3) все переменные должны определяться перел использова- нием, (4) при вызове функпии число аргументов и их атрибуты лолжны быть согласованы с определением функпии.
Процесс проверки компилятором этих соглашений называется еежанти«секим аицеизом, Часто семантический анализ произво- дится сразу после синтаксического анализа, но его также мож- но выполнить и на более поздних фазах компиляпии. Например, проверку того, что переменные опретеляются перед использо- ванием, можно произвести во время оптимизации кода, если такая фаза есть. Проверку согласованности атрибутов операн- дов можно отложить до фазы генерации кода. В гл.
10 мы изучич грамматики свойств, сеужащие фор- мальным аппаратом, с помогцью кспорого можно моделировать гл, ч, пиозвод и гине»линя кодл ».с Роль псе«вод» з пооцессе компнляссин разли сные аспекты синтаксического и семантического анализов. После синтаксического анализа промежуточная программа отображается генератором кода в объектную программу. Однако для того, чтобы сгенерировать правильный объектный код, генератор кода должен еще иметь доступ к информации, хранящейся в таблице имен. Например, свойства операндов данной операции определяют код, который нужно сгенерировать для втОЙ операции.
Так, если А и  — переменные с плавающей точкой, ю объектный код, сгенерированный для А -1-В, будет иным, нежели в случае, когда А н  — целые. Во время генерации када (или на некоторой ее подфазе) происходит и распределение памяти. Поэтому генератор када должен знать, представляет ли переменная ока.чяр, массив или структуру. Зта информации хранится в таблице имен. В некоторых компнлиторач генерации кода предшествует фаза оптимизации. На этой фазе промежуточная программа подвергается преобразованиям с целью привести ее к такой форме, нэ которой можно получить более эффективную объектную программу. Часто бывает трудно отличить некоторые преобразования оптимизации от хороших приемов генерации кода. Несколько приемов оптимизации, применимых после построения промежуточной программы или в процессе ее ~енерации, мы рассмотрим в гл.
11. Реальный коыпилятор может осуществлять фазу компиляции за один или более проходов Проход состоит в чтении входа из вне»пней памяти с последующей записью промежуточных результатов во внешнюю память. Объем работы, выполняемой за один проход, является функцией размера машины, на катпрой будет работать компилятор, языка, для которого разрабатывается компилятор, числа людей, занятых в разработке компилятора, и т.
д, Воаможно даже осуществление всех фаз компиляции за один проход. Обсуждение вопроса об оптимальном числе проходов для данного компилятора выходит за рамки нашей канги. 9Л.2. Прадстаапвння ярамвжуточнай программы В этом разделе мы рассмотрим неноторые возможные пред. ставлевия промежуточвой программы, вырабатываемой сичпаксическим анализатором.
Промежуточная программа должна огра»кать сннтзкспческ)ю структур) исходной программы. В то же время каждый оператор промежуточной программы должен относительнО просто транслироваться в машинный код. Компиляторы, осуществляющие значительную работу по шпимизвции кода, создасот детальное представление промежуточной программы, точно очражающее порядок выполнения исходной программы. В других компиляторах представлением промежу- точной программы служит простое представление синтаксического дерева, такое, как польская запись Некоторые компиляторы, неаначнтельно оптимизирующие ьод, генерируют объектный код яо мере разбора.
В этом случае «промежуточная» программа существует только условно в виде пос.чедовательностн шагов алгоритма разбора. Вот несколько общепринятык представлений промежуточной программы: (1) яостфиксная польская запись, (2) префиксная польская запись, (3) связные списочные структуры, представляющие деревья, (4) многоадресный код с явно именуемыми результатами, (5) многоадресный код с неявно именуемыми реву чьтатами. Рассмотрим примеры таких представлений. Польская запись дчя арифметических выражений была опре- делена в равд. 3.1.1. Например, оператор присваивания (9 1.!) А = ВФС« — -() с обычнылси приоритетами операций и знака присваивания (=) в постфиксной польской записи имеет вид') АВСΠ— о -1-— а в префиксной польской записи — вид =А-,В»С вЂ” П В постфиксной польской записи операнды выписаны слева направо в порядке их испогшзовання.
Знаки операций стоят справа от операндов в порядке выполнения операций. Постфнксная польская запись часто ясполлзуетгя интерпретаторами в качестве промежусачиого изыка. Фаза выполнения программы интерпретатором может состоять в вычислении оосчфиксного выражения с помсацью чагазана ири суммасоре (см пример 9.4). Оба типа польских выражений являются линейными представленними синтаксического дерева выражения (9.1.1), показанного из рнс 9.!. Зто дерево отражает синтаксическую структуру вырансенич с9.!.1).
Можно так»ке взять это дерево само в ка сестве промежуточной программы, закодировав его в виде связной списочной структуры 11ругон' метод кодирования синтаксического дерева †. применение многоадресного кода. Например, используя многоадресный ко!С с явно именуемыми рез)льтатами, можно представить выражение (9 1.1) последовательностью операторов присяаи- ') В этой »аоэсз олорзаия — аз»лето» уо»р ой, » очер»и»э Зззароылси, гзч гл ь пагязад и Гяняьлцив копь ванна Т вЂ” — Т) 1 Т, — СТ, т, +вт, А — Т,о — О вС(1) А. В (2) ='- А (3) Здесь число в скобках адресует выражение, помеченное этим числом. Представления в виде многоадресного кода удобны с вычислительной точки 3 н о ки зрения, если фаза оптимизации кода следует за фазой синтаксического анализа. В течение фазы оптимизации када представл авление программы может существенно меняться Внести существенные изменения в польское представление про- ец ю прцсввивепнз еугхис рьггнегряеать янезе, ьеи ') Заметим, что оцерецн цствльнью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
