formal_languages_translation_theory (Формальные грамматики), страница 8

Диаграмма состояний M1.Пример 2. Дана регулярная грамматика G   T, N, P, S P:S → Sb | Aa | aA → Aa | Sb | b,которой соответствует НКА. С помощью преобразования НКА в ДКА построить грамматику,по которой возможен детерминированный разбор.РешениеПостроим функцию переходов НКА:(H, a)  {S}(H, b)  {A}(A, a)  {A, S}(S, b)  {A, S}Процесс построения функции переходов ДКА удобно изобразить в виде таблицы,начав ее заполнение с начального состояния H, добавляя строки для вновь появляющихсясостояний:символabHSASASAASASASASсостояниеПереходы ДКА:1(H, a)  S1(H, b)  A1 (S, b)  AS1(A, a)  AS1(AS, a)  AS1(AS, b)  AS32появились сотояния S и A ,они рассматриваются в следующих строкахтаблицыЭлементы теории трансляции / Разбор по регулярным грамматикамПереобозначим сотояния: A  A, H  H, AS  Y, S  X.

Два заключительныхсостояния X и Y сведем в одно заключительное состояние S, используя маркер конца цепочки . После такой модификации получаем ДКА с единственным заключительным состоянием S и функцией переходов:1(H, a)  X1(H, b)  A1(X, b)  Y1(X, )  S1(A, a)  Y1(Y, a)  Y1(Y, b)  Y1(Y,)  SПо ДКА строим грамматику G1, позволяющую воспользоваться алгоритмом детерминированного разбора:G1:S → X | YY → Ya | Yb | Aa | XbX →aA →bВ заключение раздела о регулярных языках приведем пример использования автоматов в решении теоретических задач.Задача.n nДоказать, что контекстно-свободный язык L = { a b | n ≥ 0} нерегулярен.Доказательство (от противного).Предположим, что язык L регулярен. Тогда существует конечный автомат ( ДКА илиНКА ) A  ( K , ,  , I , F ) , допускающий язык L : L( A)  L .

( Согласно утверждению 10, любой регулярный язык может быть задан конечным автоматом). Пусть число состояний автоk kk kмата A равно k (k  0). Рассмотрим цепочку a b  L. Так как L =L (A), a b  L (A). Этоk kозначает, что в автомате A есть успешный путь T с пометкой a b :aaaabbbbp1 p2  pk pk 1 pk 2  p2k p2k 1 ,где pi  K для i  1, ,2k  1 .

Так как в автомате A всего k состояний, среди p1, p2, …, pk  1найдутся хотя бы два одинаковых. Иными словами, существуют i, j, 1  i < j  k, такие что   p j пути T является циклом. Пусть длинаpi  pj. Таким образом, участок pi aaэтого цикла равна m (m  0, так как цикл — это непустой путь).

Рассмотрим успешный путьaaT , который отличается от T тем, что циклический участок pi  p j присутствуетв нем дважды:aaaaaabp1  pi  ( pi  p j ) pj  pk 1  p2k 1 .33Элементы теории трансляции / Разбор по регулярным грамматикамПометкой пути T  является цепочкаk m kПоскольку T  — успешный путь,k m kb  L , получаем, что L  L(A) . Это противоречит равенству L  L(A) . Следовательно, предположение о том, что L регулярен, неверно ab  L(A) . Так как aa k mb k .Регулярные выраженияКроме регулярных грамматик и конечных автоматов, существует еще один широкоиспользуемый в математических теориях и приложениях формализм, задающий регулярныеязыки.

Это регулярные выражения. Они позволяют описать любой регулярный язык над заданным алфавитом, используя три вида операций:  (объединение),(итерация). 15) (конкатенация),Определение. Пусть L, L1, L2 — языки над алфавитом . Тогда будем называть языкL1  L2 объединением языков L1 и L2 ; язык L1L2  {|   L1,   L2} — конкатенацией (сцеплением) языков L1 и L2 (содержит всевозможные цепочки, полученные сцеплением цепочек из L1 с цепочками из L2);*для i  0, L0 = {}. Язык L n 0ii-ой степенью языка L назовем язык L  LLni 1Lназовем итерацией языка L.Определение. Пусть  — алфавит, не содержащий символов , , , , (, ). Определим рекурсивно регулярное выражение  над алфавитом  и регулярный язык L(), задаваемый этим выражением:1) a    {, } есть регулярное выражение; L(a)  {a} для a    {}; L()  ;2) если  и  — регулярные выражения, то:а) ()  () — регулярное выражение;L ( ()  () )  L ()  L ();б) ()() — регулярное выражение;L ( ()() )  L () L ();*в) () — регулярное выражение;**L ( () )  ( L () ) ;3) все регулярные выражения конструируются только с помощью пунктов 1 и 2.Если считать, что операция «» имеет самый низкий приоритет, а операция «» —наивысший, то в регулярных выражениях можно опускать лишние скобки.Примеры регулярных выражений над алфавитом {a, b}:a  b,*(a  b) ,**(aa (ab) bb) .Соответствующие языки:L( a  b )  {a}  {b}  {a, b},15)34Операцию итерации называют также звездочкой Клини, в честь ученого, предложившего регулярные выражения для описания регулярных языков.

«Регулярность» в названии этого класса языков означает повторяемость некоторых фрагментов цепочек. На примере диаграмм конечных автоматов видно, что повторяемость фрагментов обусловлена наличием циклов в диаграмме.Элементы теории трансляции / Задачи лексического анализа**L( (a  b) )  {a, b} ,**nL( (aa (ab) bb) )  {}{ aa x1bb aa x2bb... xkbb | k  1, xi  {(ab) | n  0} для i  1, ..., k }.Существуют алгоритмы построения регулярного выражения по регулярной грамматике или конечному автомату и обратные алгоритмы, позволяющие преобразовать выражение в эквивалентную грамматику или автомат [3].Регулярные выражения используются для описания лексем языков программирования, в задачах редактирования и обработки текстов; подходят для многих задач сравненияизображений и автоматического преобразования. Расширенные их спецификации (эквивалентные по описательной силе, но более удобные для практики) входят в промышленныйстандарт открытых операционных систем POSIX и в состав базовых средств языка программирования Perl.Задачи лексического анализаЛексический анализ (ЛА) — это первый этап процесса компиляции.

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

Обычно принято выделять следующиетипы лексем: идентификаторы, служебные слова, константы и ограничители. Каждой лексеме сопоставляется пара: тип_лексемы, указатель_на_информацию_о_ней .Соглашение: эту пару тоже будем называть лексемой, если это не будет вызыватьнедоразумений.Таким образом, лексический анализатор — это транслятор, входом которого служитцепочка символов, представляющих исходную программу, а выходом — последовательностьлексем.Очевидно, что лексемы перечисленных выше типов можно описать с помощью регулярных грамматик. Поскольку лексемы не пусты, для описания лексического состава любогоязыка программирования достаточно автоматных грамматик без -правил.Например, идентификатор (I ) описывается так:35Элементы теории трансляции / Задачи лексического анализаI → a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9Целое без знака (N):N → 0 | 1 |...| 9 | N0 | N1 |...| N9и т.

д.Для грамматик этого класса, как мы уже видели, существует простой и эффективныйалгоритм анализа того, принадлежит ли заданная цепочка языку, порождаемому этой грамматикой. Однако перед лексическим анализатором стоит более сложная задача: он должен сам выделить в исходном тексте цепочку символов, представляющуюлексему, и проверить правильность ее записи; зафиксировать в специальных таблицах для хранения разных типов лексем фактпоявления соответствующих лексем в анализируемом тексте; преобразовать цепочку символов, представляющих лексему, в пару  тип_лексемы,указатель_на_информацию_о_ней ; удалить пробельные литеры и комментарии.Для того чтобы решить эту задачу, опираясь на способ анализа с помощью диаграммысостояний, введем на дугах дополнительный вид пометок — пометки-действия. Теперь каждая дуга в ДС может выглядеть так:t1, t2,…, tnABD1; D2;…;DmСмысл ti прежний: если в состоянии A очередной анализируемый символ совпадает с tiдля какого-либо i  1, 2, …, n, то осуществляется переход в состояние B, при этом необходимо выполнить действия D1, D2, ..., Dm.Задача.

По заданной регулярной грамматке, описывющей целое число без знака, построить диаграмму с действиями по нахождению и печати квадрата данного числа.S → NN → 0 | 1 |...| 9 | N0 | N1 |...| N9РешениеПеревод числа во внутренне представление (переменная n типа int) будем осуществлять по схеме Горнера: распознав очередную цифру числа, умножаем текущее значениие nна 10 и добавляем числовое значение текущей цифры (текущий символ хранится в переменной c типа char). Встретив маркер конца, печатаем квадрат числа n.0, 1,…, 9Hn = c–’0’;Ncout << n*n;0, 1,…, 9n = n10  c –’0’;36SЭлементы теории трансляции / Задачи лексического анализаЛексический анализатор для М-языкаОписание модельного языкаPD1DBSEE1TFLINCR→→→→→→→→→→→→→→program D1; Bvar D {,D}I {, I}: [ int | bool ]begin S {;S} endI  E | if E then S else S | while E do S | B | read (I) | write (E)E1 [  |  |  | ! ] E1 | E1T {[  |  | or ] T}F {[  | / | and ] F}I | N | L | not F | (E)true | falseC | IC | IRR | NRa | b | ...