А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 33
Текст из файла (страница 33)
Простейшей стратегией в этой ситуации будет восстановление в "режиме паники". Мы просто удаляем входные символы до тех пор, пока лексический анализатор не встретит распознаваемый токен в начале оставшейся входной строки. Этот метод восстановления может запутать синтаксический 161 3.1. Роль лексического анализатора анализатор, но для интерактивной среды данная методика может быть вполне адекватной. Существуют и другие возможные действия по восстановлению после ошибки. 1. Удаление одного символа из оставшегося входного потока, 2. Вставка пропущенного символа в оставшийся входной поток.
3. Замена символа другим. 4. Перестановка двух соседних символов. Преобразования наподобие перечисленных пытаются исправить входной поток. Простейшая стратегия исправления состоит в выяснении, не может ли префикс оставшейся входной строки быть преобразован в корректную лексему при помощи одного действия. Такая стратегия имеет смысл, поскольку на практике большинство лексических ошибок вызываются единственным символом. Более глобальная стратегия состоит в поиске наименьшего количества трансформаций, необходимых для преобразования исходной программы в программу, состоящую только из корректных лексем, но на практике зто слишком дорогой подход, не оправдывающий затрачиваемых усилий. 3.1.5 Упражнения к разделу 3.1 Упражнение 3.1.1. Разделите приведенный ниже фрагмент на языке программирования С на лексемы, используя материал раздела 3.1.2 в качестве руководства.
Какие из лексем должны сопровождаться связанными лексическими значениями? Каковы эти значения? й1оас 11тйтес(Вс(иаге(х) Г1оас х ( /* Возвращает х в квадрате, но не более 100 */ теситп (х<=-10.0))х>=10.0)?100:х*х; ! Упражнение 3.1.2. Языки разметки наподобие НТМ(. и ХМ(. отличаются от обычных языков программирования тем, что либо количество дескрипторов в них очень велико (как в НТМ(.), либо дескрипторы определяются пользователем (как в ХМ(.). Кроме того, дескрипторы часто могут иметь параметры. Предложите разделение приведенного далее фрагмента НТМ(.-документа на лексемы. Какие лексемы должны быть со связанными лексическими значениями и какими должны быть эти значения? Это фотография <В>моего дома</В>: <Р><1ИВ ВВС = ")зоила.пей"><ВВ> 162 Глава 3.
Лексический анализ Если она вас заинтересовала, можете посмотреть <А НЕЕЕ = "звогеР1х.1з1т1">и другие фотографии</А> наподобие этой.<Р> 3.2 Буферизация ввода Перед тем как перейти к распознаванию лексем во входном потоке, рассмотрим несколько способов ускорения простой, но важной задачи — чтения исходной программы.
Эта задача усложняется тем, что нам часто надо "заглянуть" на один или несколько символов вперед, за очередную лексему, чтобы убедиться в корректности распознавания. Пример, приведенный во врезке "Тонкости распознавания токенов" в разделе 3.1, конечно, экстремален, но имеется множество ситуаций, когда требуется просмотреть как минимум один символ за текущим считанным символом. Например, нельзя быть уверенным, что достигнут конец идентификатора, пока не встретится символ, не являющийся ни буквой, ни цифрой, а значит, не являющийся частью лексемы для токена 1д. В С односимвольный оператор наподобие —, = или < может быть началом двухсимвольного оператора наподобие ->, == или <ьч Таким образом, мы начнем с двухбуферной схемы, способной безопасно работать с большими предпросмотрами.
Затем будет рассмотрено усовершенствование, заключающееся в применении "ограничителей"„экономящих время проверки концов буферов. 3.2.1 Пары буферов Поскольку для больших исходных программ количество времени, затрачиваемого на обработку всех их символов, может быть достаточно большим, для уменьшения накладных расходов на обработку одного входного символа были разработаны специальные буферизующие методы. Одна из важных схем буферизации включает два по очереди загружаемых буфера, как показано на рис.
3.3. 1ехетевечтп Рис. 3.3. Использование пары входных буферов Оба буфера имеют один и тот же размер Х, причем Х обычно равно размеру дискового блока, например 4096 байт. При этом можно считать Ю символов в буфер одной командой чтения, не используя системный вызов для каждого символа по отдельности. Если во входном файле осталось менее Х символов, конец ис- 1бз 3.2. Буферизация ввода ходного файла маркируется специальным символом еоГ, отличным от любого из возможных символов исходной программы.
При этом поддерживаются два указателя. 1. Указатель 1ехелзеВецзп, маркирующий начало текущей лексемы, протяженность которой мы пытаемся определить. 2. Указатель йогиагс1, который сканирует символы до тех пор, пока выполняется соответствие шаблону. Точная стратегия проверки выполнения соответствия рассматривается ниже в этой главе. Как только определена очередная лексема, указатель йогиагс1 устанавливается таким образом, чтобы указывать на символ, являющийся ее правым концом. Затем, после того так лексема записана в качестве значения атрибута токена, возвращаемого синтаксическому анализатору, указатель 1ехезпеВедзп устанавливается на символ, непосредственно следующий за только что обнаруженной лексемой. На рис. 3.3 указатель йогиагг1 указывает на символ за концом текушей лексемы ** (оператор возведения в степень в языке программирования гогзгап) и должен быть перемезцен на одну позицию влево.
При перемещении указателя йогиагс1 первоначально необходимо выполнить проверку, не достигнут ли конец одного из буферов, и, если достигнут, заполнить другой буфер символами из входного потока, и перенести йогиагг1 в начало этого только что заполненного буфера. Если нам не потребуется просматривать столько символов за фактической лексемой, что сумма длины лексемы и количества просматриваемых символов превышает зч', то перезаписывания лексемы в буфере до ее определения не произойдет. 3.22 Ограничители Если воспользоваться схемой из раздела 3.2.1 в том виде, в котором она описана, всякий раз при перемещении указателя йогиагс1 придется проверять, не выходит ли он за пределы буфера, и, если выходит„загружать содержимое второго буфера.
Таким образом, для каждого считанного символа необходимо выполнить два теста: один — не достигнут ли конец буфера, второй — какой именно символ считан (здесь возможно дальнейшее ветвление). Однако проверку конца буфера можно совместить с проверкой считанного символа, если расширить каждый буфер для хранения в его конце специального ограничителя (зеп1ше1). Ограничитель представляет собой специальный символ, который не может быть частью исходной программы; естественным выбором является использование в качестве ограничителя символа еой На рис. 3.4 показана та же ситуация, что и на рис.
3.3, но с добавленными ограничителями. Обратите внимание, что символ еоГ используется не только в качестве ограничителя, но и, как и ранее, в качестве маркера конца входного потока. 164 Глава 3. Лексический анализ Может ли ие хватить размера буфера? В большинстве современных языков лексемы достаточно коротки, и одного или двух символов предпросмотра вполне достаточно. Таким образом, размера буфера АГ порядка тысяч символов вполне достаточно и схема с двумя буферами из раздела 3.2.1 работает без каких-либо проблем.
Однако имеются и рискованные ситуации. Например, если символьные строки могут быть очень длинными, распространяющимися на много строк исходного текста, то мы можем оказаться в ситуации, когда длина лексемы превысит АГ. Чтобы избежать такой проблемы с длинными строками, их можно рассматривать как конкатенацию компонентов, по одному на каждую строку исходного текста. Например, в Гача удобно представлять длинные строки путем записи в каждой строке исходного текста части большой строки с оператором + в конце. Более сложная проблема возникает при необходимости предпросмотра на произвольную глубину.
Например, некоторые языки наподобие РГЛ не рассматривают ключевые слова как зарезервированные; это значит, что можно использовать идентификаторы с именами, совпадающими с ключевыми словами наподобие РЕСЬАЕЕ. Если лексический анализатор встречает исходный текст программы на языке программирования РГЛ, который начинается с РЕСЬАЕЕ ( АК61, АК62,..., он не в состоянии определить, является ли РЕСЬАВЕ ключевым словом, а АКО1 и далее — объявляемыми переменными, или это процедура с именем РЕСРАЕЕ и ее аргументы. По этой причине современные языки программирования тяготеют к резервированию своих ключевых слов.
В указанной ситуации, однако, можно рассматривать ключевое слово РЕСГ АЕЕ как неоднозначный идентификатор и позволить решить этот вопрос синтаксическому анализатору (вероятно, с использованием поиска в таблице символов). На рис. 3.5 приведена схема алгоритма перемещения указателя йогнагсГ. Обратите внимание на то, что для каждого символа, на который указывает ЙогнаксГ, выполняется только один тест, приводящий к множественному ветвлению. Ис- 1ехевевелгп Рис.
3.4. Ограничитель в конце каждого буфера 165 3.3. Спецификация токенов ключением является только случай, когда указатель достигает конца буфера или конца входного потока. язт11сЪ ( *~оги птН ч- ) ( саве еой И (гоги ага в конце первого буфера ) ( Загрузка второго буфера; (гпзгагй = начало второго буфера; е!яе И (Гоги ап1 в конце второго буфера ) ( Загрузка первого буфера; 7огиап1 = начало первого буфера; е1яе /* ео1 в буфере маркирует конец входного потока *! Завершение лексического анализа; Ьгевй; Действия для прочих символов Рис.
3.5. Прелпросмотр с применением ограничителей 3.3 Спецификация токенов Регулярные выражения представляют собой важный способ записи спецификации шаблонов лексем. Хотя они и не в состоянии выразить все возможные шаблоны, тем не менее регулярные выражения очень эффективны при определении реально используемых для токенов типов шаблонов. В этом разделе мы изучим формальную запись регулярных выражений, а в разделе 3.5 узнаем, как они используются в генераторе лексических анализаторов.
Затем в разделе 3.7 будет показано, как построить лексический анализатор путем преобразования регулярных выражений в автомат для распознавания конкретных токенов. 3.3.1 Строки и языки Термин алфавит означает любое конечное множество символов. Типичными примерами символов могут служить буквы, цифры и знаки препинания. Множество (О, Ц представляет собой бинирный алфавит. Важным примером алфавита является код АЯС11, использующийся во многих программных системах. 1)п1соде, включающий примерно 100 000 символов из алфавитов всего мира, — еще один важный пример алфавита.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
