гулярных определений, регулярны. Доказательство оставляем в качестве упражнения.

Пример 3.18. Идентификаторы Фортрана задаются последовательностью регулярных определений

<буква> = /1 В ... Z <цифра>=:0 11 ... 9

<идеитификатор> = <буква> (<буква> <цифра>)*-

Если мы не хотим допустить, чтобы в качестве идентификаторов использовались ключевые слова Фортрана, то нам придется пересмотреть определение <идентификаторов>, чтобы исключить соответствующие цепочки. Тогда оно должно читаться так:

<идентификатор>(<буква> (<буква> <цифра>)*-)-(DOIF...) П

Пример ЗЛО. Общепринятый вид записи вещественных констант (например, 3.14159, -682, 6.6Е-29 и т.д.) задается следующей последовательностью регулярных определений):

<цифра>-=0 11 ... 9 <зиак> = + I - 1 <целое> = <зиак> <цифра>

<десятичиое><знак>(<цифра>*. <цифра>+ <цифра> + . <цифра>*) <константа> = <целое> <десятичное> <десятичное> Е <целое> П

3.3.2. Непрямой лексический анализ

При непрямом лексическом анализе требуется, прочитав цепочку знаков, определить, появилась ли подцепочка, образующая некоторую конкретную лексему. Если множество возможных цепочек, которые могут образовывать эту лексему, обозначается, как это обычно бывает, регулярным выражением, то проблему построения непрямого лексического анализатора для данной лексемы можно представлять себе как проблему реализации конечного преобразователя. Конечный преобразователь-это почти конечный автомат (распознаватель) в том смысле, что он читает вход, не производя выхода, пока не обнаружит присутствие лексемы данного типа (т. е. достигнет заключительного состояния). Тогда оп сигнализирует о том, что эта лексема появилась, н выдает на выходе пеночку символов, образующих эту лексему.

Сигналом, очевидно, служит само заключительное состояние. Однако лексическому анализатору, возможно, требуется иссле

овать один или более символов, стоящих после правого конца лексемы. Простой пример: мы не можем определить правый конец идентификатора Алгола, пока не встретим символ, который ие является ни буквой, ни цифрой, т. е. обычно не считается частью идентификатора.

При непрямом лексическом анализе можно получить выход лексического анализатора, говорящий о появлении некоторой лексемы, а если позднее обнаружится, что лексема на самом деле отсутствует, то алгоритм синтаксического анализа осуществляет возврат к данной цепочке, обеспечивающий в конце концов работу анализатора для подходящей лексемы. Используя непрямой лексический анализ, нужно заботиться о том, чтобы с таблицами имен не выполнялись ошибочные операции. Обычно идентификатор не помещают в таблицу, пока не убедятся в том, что он действительно встречается. (В противном случае надо обеспечить механизм, удаляющий из таблиц ненужные элементы.)

Проблема непрямого лексического анализа является, таким образом, по существу проблемой построения детерминированного конечного автомата по заданному регулярному выражению и его программной реализации. Результаты гл. 2 убеждают нас в том, что такое построение возможно, хотя и требует немало работы. Нетрудно, оказывается, прямо перейти от регулярного выражения к недетерминированному конечному автомату. Затем по теореме 2.3 можно превратить этот автомат в детерминированный либо моделировать его работу, прослеживая параллельно всевозможные последовательности тактов. При прямом лексическом анализе тоже удобно начинать построение прямого лексического анализатора с компактного недетерминированного конечного автомата для каждой из лексем.

Недетерминированный автомат можно строить с помощью алгоритма, подобного тому, который в разд. 2.2 применялся для построения праволинейной грамматики по регулярному выражению. Распространить эту процедуру на все расширенные регулярные выражения ие так-то просто, особенно потому, что операции пересечения и вычитания множеств требуют коиструк-и.ий, связанных с детерминированными автоматами. (Очень трудно доказать, что R,f\R и Ry - Ri регулярны, если регу-ярны R и R, не обращаясь так или иначе к детерминированным автоматам. С другой стороны, для доказательства замкнутости относительно операций О , и детерминированные автоматы не требуются.) Однако операции и обрабатываются есте-

твенным образом.

) Конкретная реализация языка обычно налагает ограничения на длин\ и величину констант.

Алгоритм 3.2. Построение и е д ете р м и н и р ов а н н ого конечного автомата по расширенному регулярному выражению.

Вход, Расширенное регулярное выражение R в алфавите 2, не содержаш.ее символа 0 и операций Пи -.

Выход. Недетерминированный конечный автомат М, для которого L(M) = R.

Метод.

(1) Выполнять шаг (2) рекурсивно, начиная с выражения R. Пусть М - автомат, построенный в результате данного обращения к шагу (2).

(2) Пусть Rq - расширенное регулярное выражение, к которому применяется этот шаг. Строится недетерминированный конечный автомат М. Возможны следующие случаи:

(а) Re. Тогда M = {{q}, 2, 0, q, {q}), где g -новое состояние.

(б) R = a, где а£1.. Тогда Mdq, gJ, 2, Ь, q, {qJ), где (1, а) = {J; в остальных случаях не определена, q-

и q - новые состояния.

(в) R = R\R. Тогда можно применить шаг (2) к R я R я получить соответственно M = (Q-, 2, б, q, Fj) я М--(Qg, 2, 62, q, F2), где и не пересекаются, а затем построить VHofQiUQaU {(?o}» 2. бц, q,, F), где

(i) q, - новый символ,

(ii) бо включает 6 и б, и б, й) = б(д1, а) U б J/, а),

(iii) F, = F,UF,, если q,F, я q,F, и F,= F\j F\j {q,\ в противном случае.

(г) RRR. Применить шаг (2) к R- я R и получить

и Мз, как в случае (в). Построить М, = {QUQ.i, 2, б,,, q, Fo), да

(i) бц включает б; б (, a) = 6{q, а) для всех q£Q и а € 2, если qF, я б (q, а) - б [q, а) U б [q, а) в противном случае,

(ii) F(f = Fs, если qF, я FqFUF в противном случае.

(д) RRl. Применить шаг (2) к и получить Mj - (Qi. 2, 6i, F). Построить M,r={Q[j\qo}, 2, 6„ q, F,\J {Яо}) где (/о - новый символ и 6 определяется соотношениями

(i) бо(*7о, a) = 6i(?i, а),

(ii) если qfF,, то (q, a) = 6{q, а),

(iii) если qF, то бо (g, а) = б (, a)u6jL((7i, а).

(е) R = R+. Применить шаг (2) к R я получить М, как в (д). Построить M = {Q„ 2, б, q, Л), где бДд, a)=&(q, а), если g/i, и бо(д, a) = 6i((?, a)u6i((?i, а), если tyC/i-

; применить шаг (2) к R я получить М, как

в (д)."Построить Mo-(QiX{l, д},2,6„,[7„ 1],о),где

(i) если qF или i = n, то 6 ([д, /], а) = {[р, /] 6,{q, а) содержит /?},

(ii) если qF я i<n, то b{[q, /], а)-{[р. /] б (<7, а) содержит р\и{[р, i+l]6i(i, а) содержит р},

(iii) -{[9. t]\qF„ i<i<n}U{[qr, U}-

(з) /?о~ 1"-Д* " шаге (ж), но пункт (iii) заменить на

(iii) F,{[q, i]\g€F,, 1</<д}. П

Теорема 3.9. Алгоритм 3.2 дает такой недетерминированный конечный автомат М, что L{M) = R,

Доказательство. Упражнение на индукцию. П

Заметим, что в пунктах (ж) и (з) алгоритма 3.2 вторую компоненту состояния автомата М часто можно эффективно реализовать при программировании в виде счетчика (в том числе и при переходе к детерминированному автомату). Это возможно потому, что во многих случаях R обладает префиксным свойством и цепочку из Rt"- можно тривиально разбить на цепочки из Например, R. может быть <цифрон>, как в примере 3.18, а длина каждого элемента множества <цифра> равна I.

Пример 3.20. Сконструируем недетерминированный автомат для идентификаторов, определенных в примере 3.18. Чтобы применить шаг (2) алгоритма 3.2 к выражению, названному <иден-тификатором), надо применить его к выражениям <буква> и (<буква> <цифра>)*ь. Построение автомата для первого из этих выражений фактически содержит 26 применении шага (26) и 25 применений шага (2в). Однако заметим, что после очевидного отождествления состояний) получится автомат ({j, q\, 2, 6,

tel). где 2== {Л.....Z, О, 9} и 6,(q,, A) = 6,(q„ В)-...

•~\{д,, Z) = {q,}.

Чтобы получить автомат для выражения (<буква> <цифра>)* нужен еще один автомат для <буквы>, скажем ({173, q}, 2, б, 3, {4}), и аналогичный автомат для <цифры>, скажем (\q, qJ, 3» 5, {Vn}). Изготавливая автомат для объединения двух Последних выражении, мы добавляем новое начальное состояние 9, обнаруживаем, что из него нельзя достичь состояний q я q. Ароме того, очевидно, что q и / можно отождествить. В ре-

дегт состояния недетерминированного конечного автомата можно отож-д"" если они оба либо заключительные, либо незаключительные, и каж-тп "Д переводит их в одно и то же множество состояний. Это все, что Суется здесь, но состояния недетерминированного конечного автомата можно *Дествлять н при иекоторы.х других условиях.

10 А.

Ахо. Дж. Ульман. Ф. 1

зультате получаем автомат ({q, д}, 2, 6, {4}). г"Дб б, (9„ Л)=...=б, {д„ Z) = б, {q„ 0) = ... - 6, (9,, 9) - {д,}.

Чтобы применить uiar (2ж), введем состояния [q, i] и [9,, q для 1<1<5. Заключительными состояниями будут [д, i] для 1</<5 и [97, 1]. Последнее состояние является также началь-ным. Получаем автомат (Q, 2, 6,, [g,, I], F), где P то же, что и выше, а

b([q„ 1], а)-{[9„ 1]}, б([9„ il)={[q,, i+l]} Для всех aS

и i£{l, 2, 3, 4}. Таким образом, состояния [д, 2], ...,[д„Щ недостижимы и не должны быть в Q. Следовательно, Q = F.

напало

о.....9

Рнс. 3.7. Недетерминированный конечный автомат для идентификаторов.

Чтобы построить окончательный автомат для <идентифика-тора>, применим шаг (2г). В результате получим

2. [4. 1].....L?4. 5]}, 2, 6, {72 [4, I], . •» [4. 5]})

где б определяется соотношениями

(1) b{qy,o = {gJ для всех а 2, которые являются буквами,

(2) 6(2, а)-{[4- 1]} Д-я scex а€2,

(3) б([74, г], а) = {[4, для всех аХ и 1<г<5.

Заметим, что состояние [/,, 1] недостижимо и его можно устранить из М. Кроме того, автомат М. оказался здесь детерминированным, хотя в общем случае этого может и не быть.

Диаграмма автомата М показана на рис. 3.7, □

3.3.3. Прямой лексический анализ

При прямом лексическом анализе требуется найти одну из многих лексем. Наиболее эффективный способ заключается, вообще говоря, в том, чтобы вести поиск параллельно, так как он при этом часто довольно быстро сужается. Таким образоМ)

оделью прямого лексического анализатора служит множество паботающих параллельно конечных автоматов, или, точнее, один конечный преобразователь, моделирующий много конечных автоматов и выдающий сигнал о том, какой из них распознал цепочку.

Если нужно моделировать параллельно несколько недетерминированных автоматов, причем множества их состояний не пересекаются, то можно объединить эти множества состояний и функции переходов, построив один недетерминированный конечный автомат, который можно превратить в детерминированный по теореме 2.3. (Начальным состоянием детерминированного автомата будет при этом множество всех начальных состояний составляющих автоматов.) Таким образом, удобнее объединить множества состояний до перехода к детерминированному автомату, а не после.

Объединенный детерминированный автомат можно рассматривать как конечный преобразователь простого типа. Он выдает имя лексемы и, возможно, информацию, локализующую вХож;-дение этой лексемы. В каждом состоянии объединенного автомата представлены состояния всех составляющих автоматов. Понятно, что когда объединенный автомат попадает в состояние, содержащее заключительное состояние одного составляющего автомата и не содержащее никаких других состояний, он должен остановиться и выдать имя лексемы, соответствующей этому составляющему автомату. Однако часто дело обстоит не так просто.

Например, если идентификатором может быть любая цепочка, за исключением ключевых слов, то на практике нецелесообразно определять идентификатор в точности как это регулярное множество, поскольку такое определение сложно и требует много состояний. Вместо этого пользуются простым определением идентификатора (одно из таких дано в примере 3.18) и предоставляют объединенному автомату принять правильное решение.

В этом случае, если объединенный автомат попадает в состояние, которое содержит заключительное состояние одного из автоматов, соответствующих ключевым словам, и состояние автомата, соответствующего идентификаторам, а следующий вход-нон символ (это может быть пробел нли специальный знак) указывает на окончание лексемы, то предпочтение отдается клю-

ому слову н выдается указание о том, что обнаружено ключевое слово.

ТР""? 3.21. Рассмотрим несколько абстрактный пример. До-ста идентификаторы представляют собой цепочки, со-вленные из четырех символов D, F, I и О, за которыми дол-следовать пробел (Ь), причем DO и IF-ключевые слова.