Карпов - Основы построения трансляторов (2005) (943926), страница 26
Текст из файла (страница 26)
д. С точки зрения синтаксического анализа они совершенно не различаются, для алгоритма синтаксического анализа важно только, что очередной элемент есть идентификатор. Какой именно это идентификатор, важно будет лишь на шаге генерации команды объектной программы. Точно так же все операции отношения не различаются с точки зрения синтаксиса, их обработка на этом этапе полностью идентична, а конкретную операцию отношения нужно будет учитывать только на этапе семантических вычислений. Поэтому для синтаксического анализа их тоже можно представить одной лексемой. Однако каждое из служебных слов ~Г, йеп ...
играет свою собственную роль с точки зрения синтаксиса. Поэтому имеет смысл всех их представлять различными лексемами. Такое различие в обработке служебных слов и имен разрешается обычно следующим образом. Синтаксическая единица — лексема — представляется своим типом (это просто перечислимый тип в языке, на котором пишется транслятор), а также номером внутри этого типа. В нашем простом фрагменте программы мы имеем пять лексем типа пдепгпг~фикалюр. Обозначим этот тип лексемы Ы, а его представителей Ййапсе, креед, епйипе, к1агйипе и с$ейа будем различать в программе индексами (номером). Удобно считать, что две операции — сложение и вычитание — образуют один тип лексемы, который можно назвать оиера~~ия ~пила слолсепия (обозначим этот тип ось), для умножения и деления можно ввести тип опериция тииа умиолсения (обозначим его опт). Во многих случаях лексема имеет только одного представителя— например, как уже говорилось, все служебные слова играют различную роль в синтаксисе, поэтому каждому служебному слову соответствует свой тип лексемы.
Таким образом, для нашего примера фрагмента программы мы имеем следующие типы лексем и представителей в этих типах (табл. 5.5). 170 Глава 5 Тяблица 5.5. Типы лексем и представителей в этих типах синтаксический анализатор получит на вход следующую строку лексем: Ы Ы ге1 Ы ойп 1Ь Ы о1я Ы гЬ 111еп Ы аы Ы оЬ Ы нет Итак, лексический анализатор должен выделить типы лексем и позаботиться об идентификации конкретных лексем, например, конкретных арифметических операций или идентификаторов. Для арифметических операций все достаточно просто: в типе оЬ операции сложения присвоим номер ~ = О, вычитания — номер ~ = 1.
Индекс ~ лексемы ой, будет использоваться при семантической обработке (при генерации кода). Обычным приемом для сохранения информации об идентификаторах является построение в процессе лексического анализа таблицы имен, которая будет хранить имя переменной и другую необходимую информацию, а лексема Ы будет иметь индекс, указывающий на вход, соответствующий конкретному идентификатору в таблице имен. Лексический анализатор может выполнять и другие функции, например, выбрасывать пробелы, комментарии, находить начало и конец символьных цепочек — констант и т. д.
При этом все символьные последовательности, при распознавании которых лексический анализатор должен выполнить семантические операции, обычно задаются автоматной грамматикой или другим эквивалентным способом (например, регулярными выражениями). На следующих этапах трансляции именно лексемы являются теми терминальными символами входной грамматики, о которых шла речь выше. После обработки лексическим анализатором нашего фрагмента программы ~Г Жя~апсе >= ярееб * ( епб~~гпе — я~агс~~гле) ~',~еп Жя~ гипсе: — — Жя~апсе— сне 1 ~с~; Нисходящие методы синтаксического анализа 5.4.1. Лексический анализ языка Милан Вернемся к грамматике входного текста языка Милан, который поступает на вход транслятора: П вЂ” +Ьерп Е епс1 Х В!.ВХ 5-+Х:= Е ! жЫ!е Всйо А ос4 ! гГВ йеп А Хг ! гХВйегг Х е!ае Х Хг ! жггге СЬ) В-+Е Д Е а =! !<! !< = !> = г- е~т ! е-т! т т- т*р ! ХХР!РР— +Х ! С ! сВг ! сеас$ Х-+б ! Х б ! Х гг С вЂ” эгг ! С гг В языке Милан встречаются следующие лексемы: ГЗ ключевые слова: Ьерп, епд, ~Ие, сто, ос1, 11, 111еп, е1ье, 11, чтйеа геад; соответствующие лексемы будем обозначать теми же словами, но выделенными жирным шрифтом Ьерп, епд и т.
д.; П идентификаторы: их будем представлять лексемой Ы, с индексом ~а показывающим номер идентификатора в таблице имен, которая будст строиться одновременно с выделением лексем; Г3 константы: их будем представлять далее лексемой соиМ; с индексом ~, показывающим номер константы в таблице констант, которая будет строиться одновременно с выделением лексем; П операторы '+' и '-' будем представлять лексемой оЬ, с индексом: пусть оЬ; при ~ = О соответствует '+', а при ~' = 1 соответствует ' — '; З операторы '*' и У будем представлять лексемой опт; с индексом: пусть ~ = О соответствует '*', а ~ = 1 соответствует '/'; П операторы отношения ' = ', '<>', '<', '»', ' = ', '< = ' будем обозначать далее лексемой ге1; с индексом, показывающим номер оператора в этом списке по порядку: оператору ' = ' присвоим номер О, оператору '<>' — номер 1 и т. д.
Таким образом, ' = ' будет представлен лексемой ге1о '<>' — лексемой ге11, '<' — ге12, '>' — ге1з '< = ' — ге14, '> = ' — ге1-; О остальные символы представляют собой простые лексемы. Будем их представлять так: присваивание '.= ' лексемой азу, скобки '(' и ')' лексемами 1Ь и гЬ соответственно, а знак ' — лексемой вел. гг Глава 5 Если в язык включить требование, что идентификатор не должен совпадать с ключевыми словами, то специальных средств для различения служебных слов от идентификаторов не нужно.
Обычно идентификатор распознается как такая максимальная последовательность букв и цифр, начинающаяся с буквы, которая не совпадает ни с одним ключевым словом (ключевых слов в языке всегда конечное число, и они могут быть заданы перечислением). Рис. 5.15. Синтаксическая диаграмма лексем языка Милан и соответствующий ей распознающий конечный автомат Синтаксическая диаграмма, выделяющая во входном потоке символов программ на языке Милан все указанные выше лексемы, и соответствующий распознающий конечный автомат с семью состояниями представлены на рис. 5.15. Построение распознающей процедуры по синтаксической диаграмме и конечному автомату не представляет трудностей. Распознавание потока символов происходит до символа 3, которым, как мы будем считать, помечается конец любой цепочки распознаваемого языка.
В процедуре вначале выбрасываются все белые символы (пробелы, символы перевода строки, символы табуляции и т. и.), после чего очередной входной символ сравнивается с теми, с которых могут начинаться лексемы. Если очередной символ — буква, то далее из входного потока выбираются все буквы или цифры до первого же символа, не являющегося буквой или цифрой.
Так распознаются служебные слова и идентификаторы. Если очередной символ — цифра, то выбираются все последующие цифры. Так распознаются константы. Если очередной символ — двоеточие "., то следующим символом должен быть только символ ' = ', т. е. распознана лексема аы — оператор присваивания, и т. д.
(рис. 5.15). Нисходящие методы синтаксического анализа МП-автомат остается в состоянии ь и вместо 5 записывает в стек цепочку из одного символа Р). Фактически МП-автомат, находясь всегда в одном и том же состоянии, хранит в магазине метку того состояния, в котором находится в каждый момент времени автомат А. Если в начале распознавания в магазин поместить метку начального состояния Я автомата А, то такой МП-автомат полностью имитирует работу конечного автомата А. Рис.
5.17. Автомат с магазинной памятью, моделирующий конечный автомат Автоматные грамматики имеют вид правил А-+аВ, причем для детерминированного распознавания у всех альтернатив одного и того же нетерминала первые терминальные символы различны. ь-грамматики (здесь У от слова ягпр1е — простой) являются самым простым обобщением автоматных грамматик. ь-грамматики имеют вид правил А-+ар, где а — терминал (ключ правила), а ~З вЂ” произвольная цепочка из терминалов и нетерминалов, причем у всех альтернатив одного и того же нетерминала ключи различны.
Это позволяет построить простой детерминированный нисходящий алгоритм распознавания для ь-грамматик. Пример ь-грамматики: 05 2'. Я-+асЛ'ЬА ~ ЬАЬ А — +ааВ ~ сИЬ В вЂ” эЬАа~ а Вывод в этой грамматике: 5 ==> асКЬА ==> асЬАЬЬА ~ асЬааВЬБА ==:~ асбаааббА ==> асбаааббааВ ==> асбаааббааа. Восстановление вывода выполним по шагам. аналогично восстановлению вывода в автоматных языках. На первом шаге Я =" ? ==~ асбаааббааа мы должны определить, какое из двух правил грамматики, 5-+асЯА или 5-+ЬАЬ, может быть использовано в выводе цепочки абаааббааа из Я. Очевидно, что это может быть только первое правило Я вЂ” +асЯ~А, потому что использование второго не может дать в начале окончательной цепочки терминал а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
