Лексический анализ включает в себя сканирование компилируемой программы и распознавание лексем, составляющих предложения исходного текста. Сканеры обычно строятся таким образом, чтобы они могли распознавать ключевые слова, операторы и идентификаторы так же, как целые числа, числа с плавающей точкой, строки символов и другие аналогичные конструкции, встречающиеся в исходной программе. Точный перечень лексем, которые необходимо распознавать, зависит, разумеется, от языка программирования, на который рассчитан компилятор, и от грамматики, используемой для описания этого языка. Такие объекты, как идентификаторы и целые числа, обычно распознаются сканером как отдельные лексемы. Однако возможен и другой подход, в рамках которого эти лексемы описываются правилами грамматики. Например, идентификатор может быть определен следующим набором правил:
<ident> ::= <letter> \ <iderit> <letter> I <ident> <digit>
<letter> ::=A | B | C | D | ... | Z
<digit> ::= 0 | 1 | 2 | 3 | ... | 9
В этом случае сканер будет распознавать в качестве отдельных лексем единичные символы А, В, 0,1 и т.д. Далее в процессе грамматического разбора последовательность этих символов будет интерпретирована как конструкция языка <ident>. Однако в рамках такого подхода распознавание простых идентификаторов должны осуществлять общие алгоритмы грамматического разбора (например, описанные в следующем разделе). Специализированные программы сканера могут выполнить эту функцию гораздо более эффективно. Поскольку основная часть программы состоит из подобных многосимвольных идентификаторов, сокращение времени компиляции может быть весьма существенным. Кроме того, такие ограничения, как максимальная длина идентификатора, гораздо легче учесть в сканере, чем в общих алгоритмах грамматического разбора.
Аналогично сканер обычно распознает непосредственно как односимвольные, так и многосимвольные лексемы. Например, строку символов READ предпочтительнее рассматривать как отдельную лексему, нежели чем последовательность, состоящую из четырех лексем R, Е, A, D. Строка := будет распознана как оператор присваивания, а не как символ :, за которым следует =. Возможен, конечно, и такой подход, когда многосимвольные лексемы рассматриваются как состоящие из отдельных лексем —символов, но это существенно усложняет процесс грамматического разбора.
Результатом работы сканера является последовательность лексем. Для повышения эффективности последующих действии; каждая лексема обычно представляется некоторым кодом фиксированной длины (например, целым числом), а не в виде строки символов переменной длины. При подобной записи для грамматики, приведенной на рис. 2, лексеме program 1 соответствует целое число 1, идентификатору id соответствует число 22 и т. д.
Если распознанная лексема является ключевым словом или оператором, такая схема кодирования дает всю необходимую информацию. В случае же идентификатора дополнительно необходимо конкретное имя распознанного идентификатора. То же относится к целым числам, числам с плавающей точкой, строкам символов и т. д. Этого можно добиться за счет хранения не только кода лексемы соответствующего тина, по II дополнительного спецификатора лексемы. Спецификатор должен содержать имя идентификатора, значение целого числа и т. д.— всю информацию, распознанную сканером. Некоторые сканеры устроены таким образом, что записывают идентификатор, когда он встретился впервые, в таблицу символов, аналогичную таблице символов, используемой в ассемблере. В этом случае спецификатором лексем-идентификаторов может служить указатель на соответствующий элемент таблицы символов, что позволяет избежать дополнительного поиска по таблицам на последующих этапах компиляции.
На рис. 6 изображен результат обработки сканером программы, приведенной на рис. 1, с использованием кодировки лексем, представленной на рис. 5.5. Для лексем типа 22 (идентификаторы) соответствующими спецификаторами являются указатели на таблицу символов (обозначаемые ^SUM, ^SUMSQ и т. д.). Для лексем, имеющих тип 23 (целые числа), спецификаторами являются значения соответствующих чисел (обозначаемые #0, #100 и т. д.).
Мы изобразили результат работы сканера в виде списка кодов лексем; однако это вовсе не означает, что сканер обрабатывает целиком нею программу до начала каких-либо других действий. Чаще сканер является процедурой, вызываемой в процессе грамматического разбора для получения очередной лексемы. В этом случае результатом каждого вызова сканера будет код очередной лексемы исходной программы (и, если необходимо, ее спецификатор). При этом задача сохранения всей информации о лексемах, которая может понадобиться впоследствии, ложится на процесс грамматического разбора. Подобный пример работы сканера приведен в следующем разделе,
В дополнение к своей основной функции — распознаванию лексем — сканер обычно также выполняет чтение строк исходной программы и, возможно, печать листинга исходной программы. Комментарии игнорируются сканером, за исключением того случая, когда они должны быть напечатаны и, таким образом, эффективно удаляются из исходной программы до начала процесса грамматического разбора.
Процесс лексического разбора в том виде, как мы его описали, является весьма простым. Однако многие языки имеют специфические особенности, которые должны учитываться при программировании сканера. Например, сканер должен учитывать информацию, связанную с соглашениями по формату расположения строк исходной программы. Так, в языке Фортран число в колонках 1—5 в исходном предложении должно рассматриваться как номер предложения, а не как целое число. Сканер должен учитывать также следующую языково-зависимую информацию: являются ли пробелы ограничителями лексем ,(как в Паскале) или нет (как в Фортране), могут ли предложения свободно размещаться в нескольких строках входного текста (как в Паскале) или же для этого требуются специальные признаки продолжения (как в Фортране).
Правила распознавания лексем могут различаться в разных частях программы. Так, например, фрагмент READ не должен распознаваться в качестве ключевого слова, если он встречается внутри строки символов, заключенной в кавычки. Пробелы же оказываются существенными именно внутри таких закавыченных строк, даже если они не существенны в остальных частях программы. Аналогично в программе на Фортране строка F6.3 должна интерпретироваться по-разному в зависимости от того, расположена ли она в предложении FORMAT или в каком-то другом месте программы.
В некоторых языках встречаются также нетипичные случаи, которые должны учитываться сканером. Например, в предложении на языке Фортран
DO 10 1=1, 100
сканер должен распознавать DO как ключевое слово, 10 как номер предложения, 1 как идентификатор и т. д. Однако в предложении DO 10 I == 1 сканер должен распознать DO 10 I как идентификатор, а все предложение как предложение присваивания переменной DO10I значения 1. В этом случае сканер должен посмотреть вперед, есть ли запятая, прежде чем он сможет сделать вывод о правильной интерпретации фрагмента предложения DO. Языки, в которых зарезервированные слова могут употребляться в другом смысле, представляют для сканера еще больше трудностей. В ПЛ/1, например, любое ключевое слово также может использоваться в качестве идентификатора. Такие слова, как IF, THEN, ELSE, могут являться как ключевыми словами, так и именами переменных, определенных программистом. Так, например, предложение
IF THEN = ELSE THEN IF = THEN; ELSE THEN=IF
является формально правильным, хотя и весьма экзотическим предложением ПЛ/1. В этом случае сканер должен как-то взаимодействовать с процессом грамматического разбора, чтобы правильно интерпретировать каждое слово, или же он может считать, что идентификаторы и ключевые слова являются элементами одного и того же класса лексем, оставляя задачу их различения процессу грамматического разбора.
В настоящее время разработан ряд средств для автоматического конструирования лексических анализаторов по спецификациям, записанным на специальном языке. Описание одного из таких средств, обладающих возможностями обработки рассмотренных выше нестандартных ситуаций, содержится в работе Ахо [1977].
0 коммент.:
Отправить комментарий