Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
Замечание Если в этом алгоритме приведения поменять местами шаги (1) и (2), то не всегда результатом будет приведенная грамматика. Для описания синтаксиса языков программирования стараются использовать одно- значные приведенные КС-грамматики. Некоторые применяемые на практике алгоритмы разбора по КС-грамматикам требу- ют, чтобы в грамматиках не было правил с пустой правой частью, т. е. чтобы КС-грамматика была неукорочивающей. Для любой КС-грамматики существует эквивалентная неукорачи- вающая (см. утверждение 2). Ниже приводится алгоритм, позволяющий преобразовать любую КС-грамматику в неукорачивающую. На первом шаге алгоритма строится множество X, состоящее из нетер- миналов грамматики, из которых выводима пустая цепочка. Построение этого множества можно провести по аналогии с шагами алгоритма удаления бесплодных символов: (1) X 1 : { A | (A → ) P }; i : 2; (2) X i : {A | (A → ) P и X i − 1 * } X i − 1 . Далее, пока X i X i − 1 увеличиваем i наединицуи повторяем (2). Последнее X i — искомое множество X. Алгоритм устранения правил с пустой правой частью Вход: КС-грамматика G T, N, P, S Выход: КС-грамматика G' T, N', P', S' , G' — неукорачивающая, L(G') L(G). Метод: 1. Построить множество Х {A N | A } ; N′: N . 2. Построить P′, удалив из множества правил P все правила с пустой правой частью. 3. Если S X, то ввести новый начальный символ S′, добавив его в N′, и в множество правил P′ добавить правило S′ S | . Иначе просто переименовать S в S′. 4. Изменить P′ следующим образом. Каждое правило вида B → 1 A 1 2 A 2 n A n n 1 , где A i X для i 1,..., n, i ( (N′ X) T ) * для i 1,..., n 1 (т. е. i — цепочка, не содержащая символов из X ), заменить 2 n правилами, соответствующими всем возможным комбинациям вхождений А i между i : B → 1 2 n n 1 B → 1 2 n A n n 1 B → 1 2 A 2 n A n n 1 B → 1 A 1 2 A 2 n A n n 1 11) Если начальный символ S — бесполезный в грамматике, то грамматика порождает пустой язык. Множество P после приведения такой грамматики будет пустым, однако S не следует удалять из N,так как алфавит N не может быть пустым и на последнем месте в четверке, задающей грамматику, должен стоять нетерминал — начальный символ. / Введение 21 Замечание Если i для всех i 1, ..., n 1, то получившееся на данном шаге правило B → не вклю- чать в множество P′. 5. Удалить бесплодные и недостижимые символы и правила, их содержащие. (Кроме изначально имеющихся (в неприведенной грамматике), бесполезные символы могут возник- нуть в результате шагов 2–4). Замечание Если применить данный алгоритм к регулярной (автоматной) грамматике, то результатом будет неукорачивающая регулярная (автоматная) грамматика. Далее везде, если не оговорено иное, будем рассматривать только приведенные грам- матики. Элементы теории трансляции Введение В этом разделе будут рассмотрены некоторые алгоритмы и технические приемы, при- меняемые при построении трансляторов. Практически во всех трансляторах (и в компилято- рах, и в интерпретаторах) в том или ином виде присутствует большая часть перечисленных ниже процессов: лексический анализ, синтаксический анализ, семантический анализ, генерация внутреннего представления программы, оптимизация, генерация объектной программы. В конкретных компиляторах порядок этих процессов может быть несколько иным, какие-то из них могут объединяться в одну фазу, другие могут выполняться в течение всего процесса компиляции. В интерпретаторах и при смешанной стратегии трансляции часть этих процессов может вообще отсутствовать. В данном разделе мы рассмотрим некоторые методы, используемые для построения анализаторов (лексического, синтаксического и семантического), язык промежуточного представления программы, способ генерации промежуточной программы, ее интерпретацию. Излагаемые алгоритмы и методы иллюстрируются на примере модельного паскалеподобного языка (М-языка). Приводится реализация в виде программы на Си Информацию о других методах, алгоритмах и приемах, используемых при создании трансляторов, можно найти в [1, 2, 3, 4, 5, 8]. Элементы теории трансляции / Разбор по регулярным грамматикам 22 Разбор по регулярным грамматикам Рассмотрим методы и средства, которые обычно используются при построении лекси- ческих анализаторов. В основе таких анализаторов лежат регулярные грамматики, поэтому рассмотрим грамматики этого класса более подробно. Соглашение: в дальнейшем, если особо не оговорено, под регулярной грамматикой будем понимать леволинейную автоматную грамматику G T, N, P, S без пустых правых частей 12) . Напомним, что в такой грамматике каждое правило из Р имеет вид A → Bt либо A → t, где A, B N, t T. Соглашение: предположим, что анализируемая цепочка заканчивается специальным символом — признаком конца цепочки. Для грамматик этого типа существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора): (1) первый символ исходной цепочки a 1 a 2 ...a n заменяем нетерминалом A, для кото- рого в грамматике есть правило вывода A → a 1 (другими словами, производим свертку терминала a 1 к нетерминалу A) (2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполня- ем следующие шаги: полученный на предыдущем шаге нетерминал A и располо- женный непосредственно справа от него очередной терминал a i исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B → Aa i (i 2, 3, .., n); Это эквивалентно построению дерева разбора методом снизу-вверх: на каждом шаге алгоритма строим один из уровней в дереве разбора, поднимаясь от листьев к корню. При работе этого алгоритма возможны следующие ситуации: (1) прочитана вся цепочка; на каждом шаге находилась единственная нужная свертка; на последнем шаге свертка произошла к символу S. Это означает, что исходная цепочка a 1 a 2 ...a n L(G). (2) прочитана вся цепочка; на каждом шаге находилась единственная нужная свертка; на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка a 1 a 2 ...a n L(G). (3) на некотором шаге не нашлось нужной свертки, т. е. для полученного на преды- дущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала a i исходной цепочки не нашлось нетерминала B, для кото- рого в грамматике было бы правило вывода B → Aa i . Это означает, что исходная цепочка a 1 a 2 ...a n L(G). (4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки, т. е. в грамматике разные нетерминалы имеют правила вывода с одина- ковыми правыми частями, и поэтому непонятно, к какому из них производить свертку. Это говорит о недетерминированности разбора. Анализ этой ситуации будет дан ниже. Допустим, что разбор на каждом шаге детерминированный. 12) Полное отсутствие -правил в грамматике не позволяет описывать языки, содержащие пустую цепочку. Для наших целей в данном разделе это ограничение оправдано — мы будем применять автоматные грамматики для описания и разбора лексических единиц (лексем) языков программирования. Лексемы не могут быть пу- стыми. Элементы теории трансляции / Разбор по регулярным грамматикам 23 Для того, чтобы быстрее находить правило с подходящей правой частью, зафиксиру- ем все возможные свертки (это определяется только грамматикой и не зависит от вида ана- лизируемой цепочки). Сделаем это в виде таблицы, столбцы которой помечены терминаль- ными символами. Первая строка помечена символом Н (Н N), а значение каждого элемента этой строки — это нетерминал, к которому можно свернуть помечающий столбец терми- нальный символ. Остальные строки помечены нетерминальными символами грамматики. Значение каждого элемента таблицы, начиная со второй строки — это нетерминальный сим- вол, к которому можно свернуть пару «нетерминал-терминал», которыми помечены соответ- ствующие строка и столбец. Например, для леволинейной грамматики G left {a, b, }, {S, A, B, C}, P, S , где P: S → C C → Ab | Ba A → a | Ca B → b | Cb , такая таблица будет выглядеть следующим образом: a b H A B — C A B S A — C — B C — — S — — — Знак «—» ставится в том случае, если соответствующей свертки нет. Но чаще информацию о возможных свертках представляют в виде диаграммы состо- яний (ДС) — неупорядоченного ориентированного помеченного графа, который строится следующим образом: (1) строим вершины графа, помеченные нетерминалами грамматики (для каждого не- терминала — одну вершину), и еще одну вершину, помеченную символом, от- личным от нетерминальных, например, H. Эти вершины будем называть состоя- ниями. H — начальное состояние. (2) соединяем эти состояния дугами по следующим правилам: а) для каждого правила грамматики вида W → t соединяем дугой состояния H и W (от H к W ) и помечаем дугу символом t; б) для каждого правила W → Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t; Диаграмма состояний для грамматики G left (см. пример выше) изображена на рис.4: H A B C S a b b a b a Рис. 4. Диаграмма состояний для грамматики G left Элементы теории трансляции / Разбор по регулярным грамматикам 24 Алгоритм разбора по диаграмме состояний (1) объявляем текущим начальное состояние H; (2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполня- ем следующие шаги: считываем очередной символ исходной цепочки и перехо- дим из текущего состояния в другое состояние по дуге, помеченной этим симво- лом. Состояние, в которое мы при этом попадаем, становится текущим. При работе этого алгоритма возможны следующие ситуации (аналогичные ситуациям, которые возникают при разборе непосредственно по регулярной грамматике): 1) Прочитана вся цепочка; на каждом шаге находилась единственная дуга, помечен- ная очередным символом анализируемой цепочки; в результате последнего пере- хода оказались в состоянии S. Это означает, что исходная цепочка принадлежит L(G). 2) Прочитана вся цепочка; на каждом шаге находилась единственная «нужная» дуга; в результате последнего шага оказались в состоянии, отличном от S. Это означает, что исходная цепочка не принадлежит L(G). 3) На некотором шаге не нашлось дуги, выходящей из текущего состояния и поме- ченной очередным анализируемым символом. Это означает, что исходная цепочка не принадлежит L(G). 4) На некотором шаге работы алгоритма оказалось, что есть несколько дуг, выходя- щих из текущего состояния, помеченных очередным анализируемым символом, но ведущих в разные состояния. Это говорит о недетерминированности разбора. Анализ этой ситуации будет приведен ниже. Диаграмма состояний определяет конечный автомат, построенный по регулярной грамматике, который допускает множество цепочек, составляющих язык, определяемый этой грамматикой. Состояния и дуги ДС — это графическое изображение функции переходов ко- нечного автомата из состояния в состояние при условии, что очередной анализируемый сим- вол совпадает с символом-меткой дуги. Среди всех состояний выделяется начальное (счита- ется, что в начальный момент своей работы автомат находится в этом состоянии) и заключи- тельное (если автомат завершает работу переходом в это состояние, то анализируемая це- почка им допускается). На ДС эти состояния отмечаются короткими входящей и соответ- ственно исходящей стрелками, не соединенными с другими вершинами. Определение: детерминированный конечный автомат (ДКА) — это пятерка K, T, , H, S , где K — конечное множество состояний; T — конечное множество допустимых входных символов; — отображение множества K T в K, определяющее поведение автомата; H K — начальное состояние; S K — заключительное состояние (либо множество заключительных состояний S K). Замечания к определению ДКА: (1) Заключительных состояний в ДКА может быть более одного, однако для любого регулярного языка, все цепочки которого заканчиваются маркером конца ( ), су- Элементы теории трансляции / Разбор по регулярным грамматикам 25 ществует ДКА с единственным заключительным состоянием. Заметим также, что ДКА, построенный по регулярной грамматике рассмотренным выше способом, всегда будет иметь единственное заключительное состояние S. 13) (2) Отображение : K T → K называют функцией переходов ДКА. (A, t) B означа- ет, что из состояния A по входному символу t происходит переход в состояние B. Иногда определяют лишь на подмножестве K T (частичная функция). Если значение (A, t) не определено, то автомат не может дальше продолжать работу и останавливается в состоянии «ошибка». Определение: ДКА допускает цепочку a 1 a 2 ...a n , если (H, a 1 ) A 1 ; (A 1 , a 2 ) A 2 ; … ; (A n − 2 , a n − 1 ) A n − 1 ; (A n − 1 , a n ) S, где a i T, A j K, j 1, 2, ..., n 1; i 1, 2, ..., n; H — начальное состояние, S — заключительное состояние. Определение: множество цепочек, допускаемых ДКА, составляет определяемый им язык. Для более удобной работы с диаграммами состояний введем несколько соглашений: если из одного состояния в другое выходит несколько дуг, помеченных разными символами, то будем изображать одну дугу, помечая ее списком из всех таких сим- волов; непомеченная дуга будет соответствовать переходу при любом символе, кроме тех, которыми помечены другие дуги, выходящие из этого состояния; введем состояние ошибки (ER); переход в это состояние будет означать, что исход- ная цепочка языку не принадлежит. По диаграмме состояний легко написать анализатор для регулярной грамматики. Например, для грамматики G left {a, b, }, {S, A, B, C}, P, S с правилами P: S → C C → Ab | Ba A → a | Ca B → b | Cb анализатор будет таким: #include { enum state { H, A, B, C, S, ER }; // множество состояний 13) Нетрудно указать и обратный способ — построения грамматики по диаграмме состояний автомата, — при- чем получившаяся грамматика будет автоматной. Каждой дуге из начального состояния Н в состояние W, помеченной символом t, будет соответствовать правило W → t; каждой дуге из состояния V в состояние W, помеченной символом t, будет соответствовать правило W → Vt. Заключительное состояние S объявляется начальным символом грамматики. Если в вершину Н входит некоторая дуга (это возможно в произвольно построенном автомате), то алго- ритм модифицируется так: каждой дуге из начального состояния Н в состояние W, помеченной символом t, будет соответствовать правило W →Ht, и в грамматику добавляется правило Н→ε; затем к построенной грамматике применяется алгоритм удаления правил с пустыми правыми частями. Элементы теории трансляции / Разбор по регулярным грамматикам 26 state CS; // CS —— текущее состояние CS = H; do { gc (); switch (CS) { case H: if ( c == 'a' ) { CS = A; } else if ( c == 'b' ) { CS = B; } else CS = ER; break; case A: if ( c == 'b' ) { CS = C; } else CS = ER; break; case B: if ( c == 'a' ) { CS = C; } else CS = ER; break; case C: if ( c =='a' ) { CS = A; } else if ( c == 'b' ) { CS = B; } else if ( c == ' ' ) CS = S; else CS = ER; break; } } while ( CS != S && CS != ER); return CS == S; // true, если CS != ER, иначе false } Элементы теории трансляции / Разбор по регулярным грамматикам 27 Пример разбора цепочки Рассмотрим работу анализатора для грамматики G на примере цепочки abba . При анализе данной цепочки получим следующую последовательность переходов в ДС: S C B C A H a b b a Вспомним, что каждый переход в ДС означает свертку сентенциальной формы путем замены в ней пары «нетерминал-терминал» Nt на нетерминал L, где L → Nt правило вывода в грам- матике. Такое применение правила в обратную сторону будем записывать с помощью обрат- ной стрелки Nt ← L (обращение правила вывода). Тогда получим следующую последова- тельность сверток, соответствующую переходам в ДС: abba |