А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 34
Текст из файла (страница 34)
166 Глава 3. Лексический анализ Реализация множественного ветвления Может показаться, что инструкция внфссЬ на рис. 3.5 требует для выполнения мною шагов и помещение первым случая ео1 — не самый разумный выбор. В действительности порядок перечисления конструкций саве значения не имеет. На практике множественное ветвление, зависящее от значения символа, выполняется за один шаг путем перехода по адресу, указанному в проиндексированной символами таблице адресов.
Строка над некоторым алфавитом — это конечная последовательность символов, взятых из этого алфавита. В теории языков термины предложение (зеп1епсе) и слово (~чогг)) часто используются как синонимы термина строка (яозпд). Длина строки в, обычно обозначаемая как (а(, равна количеству символов в строке. Например, длина строки Ьапапа равна шести. Пустая строка, обозначаемая как е, представляет собой строку нулевой длины. Язык представляет собой любое счетное множество строк над некоторым фиксированным алфавитом. Это определение весьма широко.
Абстрактные языки наподобие О (пустое множество) и и (множество, содержащее только пустую строку) также являются языками согласно этому определению. Точно так же языками являются и множество всех синтаксически корректных программ на языке С, и все грамматически корректные предложения английского языка, хотя два последних множества существенно сложнее точно определить.
Обратите внимание, что определение "языка" не требует, чтобы строкам языка был приписан какой- либо смысл. Методы описания "смысла" строк обсуждаются в главе 5. Если х и у — строки, то конкатенация строк х и у, записываемая как ху, является строкой, образованной путем добавления у к х. Например, если х =- с1од, а у = Ьопве, то ху = г1ог3Ьоцве. Пустая строка представляет собой единичный элемент по отношению к операции конкатенации, т.е. для любой строки а справедливо соотношение са = ае = а. Если рассматриват ь конкатенацию как умножение, то можно определить "возведение в степень" следующим образом.
Определим а~ как е, а для всех 1 > О определим а' как в' а. Поскольку га = в, то а~ = я. Соответственно, я = вя, 2 8 = Бяя и т.д. 3.3.2 Операции иад языками В лексическом анализе наиболее важными операциями над языками являются объединение, конкатенация и замыкание, формально определенные на рис. 3.6.
Объединение — привычная операция над множествами. Конкатенация языков 167 3.3. Спецификация токенов Термины для частей строк Обычно используются следующие связанные со строками термины. Ъ Префиксол~ (ргебх) строки л является любая строка, полученная удалением нуля или нескольких последних символов строки в. Например, Ъап, Ъапапа и с являются префиксами строки Ьапапа.
2. Суффиксом (зп(бх) строки в является любая строка, полученная удалением нуля или нескольких первых символов строки в. Например, папа, Ьапапа и с являются суффиксами строки Ьапапа. 3. Подстрока (ацЫппд) строки в получается путем удаления произвольного префикса и произвольного суффикса из строки в. Например, Ьапапа, пап и г являются подстроками Ьапапа. 4. Правговьнылви, или истинныии (ргорег), префиксами, суффиксами и подстроками в являются соответственно префиксы, суффиксы и подстроки в, которые не являются пустыми строками с и не совпадают с самой строкой л.
5. Подпоследовательностью (зцЬзеццспсе) строки л является любая строка, образованная удалением нуля или нескольких не обязательно смежных позиций из строки в. Например, Ьаап является подпоследователььюстью Ьапапа. представляет собой все строки, образованные путем взятия строки из первого языка и строки из второго языка всеми возможными способами с их последующей конкатенацией. Замыкание Клики языка Ь, обозначаемое как 1*, представляет собой множество строк, которые можно получить путем конкатенации З. нуль или несколько раз. Заметим, что т,о, "конкатенация 2, нуль раз", по определению равна (с) и по индукции Р' равно Р' 'Е,. Наконец, положительное замыкание, обозначаемое как Л ь, представляет собой то же, что и замыкание Клини, но без члена 1.о, т.е, е отсутствует в г,+, если только оно не является частью самого Л.
Пример 3.3. Пусть 1, — множество букв (й,В,..., Е,а, Ъ,..., а), а Р— множество цифр (О, 1,.... 9'1. Можно рассматривать множества Х и 0 двумя по сути одинаковыми способами. С одной стороны, Е и Р представляют собой алфавиты, состоящие соответственно из прописных и строчных букв и из цифр. С другой стороны, множества Ь и Р представляют собой языки, все строки которых имеют 168 Глава 3. Лексический анализ Рис. 3.6.
Определения операций над языками единичную длину. Вот несколько примеров других языков, построенных из 1, и Р с применением операторов, приведенных на рис. 3,6. !. 1, 0 Р представляет собой множество букв и цифр — строго говоря, язык с 62 строками единичной длины, каждая из которых состоит либо из одной буквы, либо из одной цифры. 2. ЬР— множество из 520 строк длиной 2, каждая из которых состоит из буквы, за которой следует цифра. 3. Ь4 — множество всех четырехбуквенных строк.
4. т",' — множество всех строк из букв, включая пустую строку г. 5. 1,(Ь 0 Р)* — множество всех строк из букв и цифр, начинающихся с буквы. 6. Р~ — множество всех строк из одной или нескольких цифр. 3.3.3 Регулярные выражения Предположим, что мы хотим описать множество корректных идентификаторов С. Они почти точно описаны в п. 5 предыдущего подраздела; единственная неточность в том, что в множество букв включается также символ подчеркивания.
В примере 3.3 нам удалось описать идентификаторы, давая имена множествам букв и цифр и используя языковые операторы объединения, конкатенации и замыкания. Этот процесс оказался настолько практичным, что система обозначений, называющаяся регулярными выражениями, стала широко использоваться для описания всех языков, которые могут быть построены путем применения указанных операторов к символам некоторого алфавита.
В этих обозначениях, если 1епег означает любую букву или подчеркивание, а й81à — любую цифру, мы можем описать идентификаторы языка программирования С как 1еггег (1епег ~ ~Й88)* 169 3.3. Спецификация токенов Вертикальная черта здесь означает обьединение, скобки используются для груп- пирования подвыражений, звездочка означает "нуль или несколько вхождений", а непосредственное соседство 1епег с остальной частью выражения означает конкатенацию. Регулярные выражения рекурсивно строятся из меньших регулярных выражений с использованием описанных ниже правил.
Каждое регулярное выражение г описывает язык Ь(г), который также рекурсивно определяется на основании языков, описываемых подвыражениями г. Вот правила, которые определяют регулярные выражения над некоторым алфавитом Е, и языки, описываемые этими регулярными выражениями. Блзис: Базис образован двумя правилами. 1. т является регулярным выражением, а Ь(с) представляет собой (с), т.е. язык, единственный член которого — пустая строка. 2.
Если а — символ в Е, то а представляет собой регулярное выражение, а х,(а) = (а), т.е. язык с одной строкой единичной длины, с символом а в единственной позиции. Заметим, что по соглашению для символов используется курсив, а для соответствующих им регулярных выражений— полужирный шрифт. Индукция: Имеется четыре правила индукции, посредством которых регулярные выражения строятся из более мелких. Предположим, что г и в являются регулярными выражениями, описывающими соответственно языки Л (г) и Ь (в). Е (г) ~ (л) — регулярное выражение, описывающее язык Х (г) 0 Б (в). 2. (г) (л) — регулярное выражение, описывающее язык Ь (г) Б (а).
3, (г)' — регулярное выражение, описывающее язык (Л (г))'. 4. (г) — регулярное выражение, описывающее язык Л(г). Это правило говорит о том, что можно заключить выражение в скобки без изменения описываемого им языка. Как было сказано, регулярные выражения часто содержат лишние пары скобок. Эти скобки можно опустить, если принять следующие соглашения.
а) Унарный оператор * левоассоциативен и имеет наивысший приоритет. б) Конкатенация имеет второй по величине приоритет и также левоассоциативна. 'Однако, поворя о конкретных символах из набора АоС!1, мы обычно будем использовать моноширинный шрифт как для символов, так и для их рсзбиярных выражений. 17О Глава 3. Лексический анализ в) Оператор ~ левоассоциативен и имеет наименьший приоритет. При этих соглашениях, например, можно заменить регулярное выражение (а) ~ ИЬ) (с)) выражением а ~ Ь*с. Оба выражения описывают множество строк, которые представляют собой либо единственный символ а, либо нуль или несколько 6, за которыми следует единственный г.
Пример 3.4. Пусть Е = 1а, 6). 1. Регулярное выражение а ~ Ь описывает язык 1а, 6). 2. Регулярное выражение (а ( Ь) (а ~ Ь) описывает 1аа,а6,6а,66) — множество всех строк из а и 6 длиной 2 над алфавитом Е. Другое регулярное выражение для того же языка — аа ~ аЬ ~ Ьа ~ ЬЬ. 3. Регулярное выражение а* описывает язык, состоящий из всех строк из нуля или более а, т.е. 1г, о, аа, ааа,...). 4. Регулярное выражение (а ~ Ь)* описывает множество всех строк, состоящих из нуля или нескольких экземпляров о или 6, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
