Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 33 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

35
ет простой и эффективный алгоритм анализа того, принадлежит ли заданная
цепочка языку, порождаемому этой грамматикой, поскольку распознавателями
для регулярных языков являются конечные автоматы. Существуют правила, с
помощью которых для любой регулярной грамматики может быть построен не-
детерминированный конечный автомат, распознающий цепочки языка, задан-
ного этой грамматикой.
Однако, в общем случае задача сканера несколько шире, чем просто про-
верка цепочки символов лексемы на соответствие ее входному языку. Помимо
этого, сканер должен выполнить следующие действия:
четко определить границы лексемы, которые в исходном тексте явно не
заданы;
выполнить действия для сохранения информации об обнаруженной лек-
семе (или выдать сообщение об ошибке, если лексема неверна).
Выделение границ лексем представляет определенную проблему. Ведь во
входном тексте программы лексемы не ограничены никакими специальными
символами. Если говорить в терминах программы-сканера, то определение гра-
ниц лексем – это выделение тех строк в общем потоке входных символов, для
которых надо выполнять распознавание. В общем случае эта задача может быть
сложной, и тогда требуется параллельная работа сканера, синтаксического раз-
бора и, возможно, семантического анализа. Для большинства входных языков
границы лексем распознаются по заданным терминальным символам. Эти сим-
волы – пробелы, знаки операций, символы комментариев, а также разделители
(запятые, точки с запятой и т. п.). Набор таких терминальных символов может
варьироваться в зависимости от синтаксиса входного языка.
Как правило, сканеры действуют по следующему принципу: очередной
символ из входного потока данных добавляется в лексему всегда, когда он мо-
жет быть туда добавлен. Как только символ не может быть добавлен в лексему,
то считается, что он является границей лексемы и началом следующей лексемы
(если символ не является пустым разделителем – пробелом, символом табуля-
ции или перевода строки, знаком комментария). Такой принцип не всегда по-
зволяет правильно определить границы лексем в том случае, когда они не раз-
делены пустыми символами. Например, приведенная выше строка языка С
k=i+++++j будет разбита на лексемы следующим образом: k = i++ ++ + j – и это
разбиение неверное, компилятор должен будет выдать пользователю сообще-
ние об ошибке, хотя правильный вариант распознавания строки существует.
Однако разработчики компиляторов сознательно идут на то, что отсекают
некоторые правильные, но не вполне читаемые варианты исходных программ.
Попытки усложнить лексический распознаватель неизбежно приведут к необ-
ходимости его взаимосвязи с синтаксическим разбором. Это потребует органи-
зации их параллельной работы и неизбежно снизит эффективность работы все-
го компилятора. Возникшие накладные расходы никак не оправдываются дос-
тигаемым эффектом – чтобы распознавать строки с сомнительными лексемами,
достаточно лишь явно указывать с помощью пробелов (или других незначащих
символов) границы лексем, что значительно проще.

Страницы