И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 8
Текст из файла (страница 8)
Тогда будем называть языкL1 L2 объединением языков L1 и L2 ; язык L1L2 {| L1, L2} — конкатенацией (сцеплением) языков L1 и L2 (содержит всевозможные цепочки, полученные сцеплением цепочек из L1 с цепочками из L2);*для i 0, L0 = {}. Язык L n 0ii-ой степенью языка L назовем язык L LLni 1Lназовем итерацией языка 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 → NN → 0 | 1 |...| 9 | N0 | N1 |...| N9РешениеПеревод числа во внутренне представление (переменная n типа int) будем осуществлять по схеме Горнера: распознав очередную цифру числа, умножаем текущее значениие nна 10 и добавляем числовое значение текущей цифры (текущий символ хранится в переменной c типа char).
Встретив маркер конца, печатаем квадрат числа n.0, 1,…, 9Hn = c–’0’;Ncout << n*n;0, 1,…, 9n = n10 c –’0’;36SЭлементы теории трансляции / Задачи лексического анализаЛексический анализатор для М-языкаОписание модельного языкаPD1DBSEE1TFLINCR→→→→→→→→→→→→→→program D1; Bvar 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 | ... | z | A | B | ... | Z0 | 1 | 2 | ... | 9Замечания к грамматике модельного языка:а) запись вида {} означает итерацию цепочки , т. е. в порождаемой цепочке вэтом месте может находиться либо , либо , либо , либо и т.
д.;б) запись вида [ | ] означает, что в порождаемой цепочке в этом месте можетнаходиться либо , либо ;в) P — цель грамматики; символ — маркер конца текста программы.Контекстные условия:1. Любое имя, используемое в программе, должно быть описано и только один раз.2.
В операторе присваивания типы переменной и выражения должны совпадать.3. В условном операторе и в операторе цикла в качестве условия возможно толькологическое выражение.4. Операнды операции отношения должны быть целочисленными.5. Тип выражения и совместимость типов операндов в выражении определяются пообычным правилам; старшинство операций задано синтаксисом.В любом месте программы, кроме идентификаторов, служебных слов и чисел, можетнаходиться произвольное число пробелов и комментариев в фигурных скобках вида { любые символы, кроме «}» и «» }.true, false, read и write — служебные слова (в М-языке их нельзя переопределять в отличие от аналогичных стандартных идентификаторов в Паскале).Разделители между идентификаторами, числами и служебными словами употребляются так же, как в Паскале.37Элементы теории трансляции / Задачи лексического анализаПерейдем к построению лексического анализатора.Вход лексического анализатора — символы исходной программы на М-языке; результат работы — исходная программа в виде последовательности лексем (их внутреннего представления).
В нашем случае лексический анализатор будет вызываться, когда потребуетсяочередная лексема исходной программы, поэтому результатом работы лексического анализатора будет очередная лексема анализируемой программы на М-языке.Лексический анализатор для модельного языка будем создавать поэтапно: сначалаопишем на языке Си классы объектов, которые будут использоваться при ЛА, затем построим ДС с действиями для распознавания и формирования внутреннего представлениялексем, а затем по ДС напишем программу ЛА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
