А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 49
Текст из файла (страница 49)
+ Расширенная запись регулярных выражений. В регулярных выражениях для упрощения может использоваться ряд дополнительных операторов, представляющих собой сокращения имеющихся регулярных выражений. Примерами таких операторов могут служить оператор + (одно или несколько вхождений), ? (нуль или одно вхождение), а также классы символов. + Диаграммы переходов. Повеление лексического анализатора часто можно описать с использованием диаграмм переходов.
Эти диаграммы включают состояния, каждое из которых представляет определенную историю просмотренных входных символов в процессе поиска текущей лексемы, соответствующей одному из возможных шаблонов. Из одних состояний в другие ведут стрелки, или переходы, каждая из которых соответствует некоторому возможному входному символу, приводящему к изменению состояния лексического анализатора. + Конечные автоматы. Существует формализация диаграмм переходов, которая включает указание одного начального и одного или нескольких принимающих состояний, а также множества состояний, входных символов и переходов между состояниями. Принимающие состояния указывают, что найдена лексема для некоторого токена.
В отличие от диаграмм переходов конечные автоматы могут осуществлять переходы как для входных символов, так и для пустой входной строки. + Детерминированные конечные автоматы. ДКА представляет собой специальный вид конечного автомата, у которого из каждого состояния для каждого входного символа имеется ровно один переход. Кроме того, запрещены переходы для пустых строк. ДКА легко моделируются и обеспечивают хорошую реализацию лексических анализаторов, аналогичную диаграммам переходов. + Оедетврминированные конечные автоматы.
Автомат, не являюп>ийся детерминированным, называется недетерминированным. НКА часто сушественно проще спроектировать, чем ДКА. Еще одной возможной архитектурой лексического анализатора является табуляция лля каждого возмож- 247 3.11. Список литературы к главе 3 ного шаблона всех состояний НКА, в которых он может оказаться при сканировании входного потока. + Преобразования представлений шаблонов.
Можно преобразовать любое регулярное выражение в НКА примерно того же размера, распознающий определяемый этим регулярным выражением язык. Далее, любой НКА может быть преобразован в ДКА для того же шаблона, хотя в наихудшем случае (не встречающемся при работе с обычными языками программирования) размер ДКА может экспоненциально зависеть от размера НКА. Можно также преобразовать любой недетерминированный или детерминированный конечный автомат в регулярное выражение, которое определяет тот же язык, что и распознаваемый этим автоматом.
+ Еех. Существует семейство генераторов лексических анализаторов, включающее 3.ех и Г1ех. Пользователь такого генератора определяет шаблоны для токенов с применением расширенной записи регулярных выражений. Ьех преобразует эти выражения в лексический анализатор, который, по сути, представляет собой детерминированный конечный автомат, распознающий каждый из шаблонов. + Минимизация конечного автомата. Для каждого ДКА существует ДКА с минимальным количеством состояний, принимающий тот же язык. Более того, ДКА с минимальным количеством состояний для данного языка является единственным с точностью до имен состояний автомата.
3.11 Список литературы к главе 3 Впервые регулярные выражения были разработаны Клини (К!еепе) в 1950-х годах [9]. Клини интересовало описание событий, которые могли быть представлены конечно-автоматной моделью нервной деятельности Мак-Каллока (МсСп!- 1оцдй) и Питтса (Р1Пв) [121. С того времени регулярные выражения и конечные автоматы стали широко использоваться в информатике. Регулярные выражения в различных формах используются во многих популярных утилитах ()п1х, таких как ам1с, ес1, едгер, атер, 1ех, вес1, в1т и чх.
Стандарты 1ЕЕЕ 1003 и БОЛЕС 9945 системного интерфейса переносимых операционных систем (Рог1аЫе Орегаг(пя Зуя1еш 1п1егРасе — РОБ1Х) определяют расширенные регулярные выражения РОЯХ, аналогичные оригинальным регулярным выражениям 1)шх с небольшими исключениями, такими как мнемонические представления классов символов. Многие языки сценариев, такие как Рег!, Ругпоп и Тс!, используют регулярные выражения, хотя зачастую и с нестандартными расширениями. 248 Глава 3. Лексический анализ Привычная модель конечного автомата, как и его минимизация (алгоритм 3.39), появилась благодаря работам Хаффмана (Нпйгпап) [6] и Мура (Мооге) [14].
Недетерминированные конечные автоматы были предложены Рабином (КаЬ1п) н Скоттом (Всоп) [15); они же предложили метод построения подмножеств (алгоритм 3.20) и показали эквивалентность детерминированных и недетерминированных конечных автоматов. Мак-Нотон (МсЫап8Ьгоп) и Ямада (гашаг)а) [!3] описали алгоритм преобразования регулярных выражений непосредственно в детерминированные конечные автоматы.
Алгоритм 3.36, описанный в разделе 3.9, был впервые использован Ахо (АЬо) при создании утилиты едкер в ()п(х. Этот алгоритм применялся также и в подпрограммах проверки соответствия строк регулярным выражениям в утилите ам!с [3). Подход с использованием промежуточного недетерминированного конечного автомата предложен Томпсоном (ТЬошраоп) [17]. Эта же статья содержит и алгоритм непосредственного моделирования недетерминированного конечного автомата (алгоритм 3.22), использованный Томпсоном в текстовом редакторе ЯЕ1Э. Первая версия 1.ех была разработана Леском (Еез!г), после чего во второй версии Еех Леска и Шмидта (ЗсЬшЫ1) был применен алгоритм 3.36 [10).
Впоследствии было реализовано множество различных вариантов ! ех, ПЫ()-версию, Е1ех вместе с документацией можно найти на %еЬ-сайте [4]. Популярные версии Еех для 1ача включают 7Е1ех [7] и 71.ех [8]. Алгоритм КМП, описанный в разделе 3.4 перед упражнением 3.4.3, разработан в [! 1). Его обобшение для многих ключевых слов описано в [2] и использовано Ахо в его первой реализации утилиты ()п(х гдкер. Теория конечных автоматов и регулярных выражений излагается в [5], а хороший обзор методов поиска подстрок можно найти в [!]. 1. АЬо, А. У., "А!8опгЬгпз Гог бшйп8 рацепгя ш ялтпйз", ш Напг/Ьоок о~'ТЬеогейса1 Сотригег Бпепсе (1 чап 1.еешчеп, ед.), Уо!. А, СЬ.
5, М1Т Ргезз, СагпЬг(г(8е, 1990. 2. АЬо, А. Ъ'. аль М. 1 Согагйс)г, "Ейс!епг зГппй шассЬ(п8; ап аЫ Го Ь(Ы!ойгарЬ(с яеагсЬ", Сотт. АСМ 18:6 (1975), рр. 333 — 340. 3. АЬо, А. ч', В. %. Кепп8Ьап, апг( Р. Х. %ешЬегйег, ТЬе АИК Рго8гатт/п8 1ап8иаде„АЙИзоп-%еа!еу, Воз!оп, МА, 1988. 4. Начальная страница Р!ех Ьтпр://мчгм.дпц.огд/вогсчгаге/й1ех/, Ргее ЕоГпчаге Роппг!агюп. 5. НорсгоГг, 1 Е., К.
Могтчап(, апб 1 Р. ()1!шап, /пггог/исгюп го Аиготага Тйеогу, 1апдиадез, апг( Сотригаг/оп, Адйзоп-%ез1еу, Воя!оп МА, 2006. 249 3.1 1. Список литературы к главе 3 б. Но%пап, Р. А., "ТЬе вупсЬеяв ор вес)цепс!а! шасЬспев",,У. ЕгапЫ~л!пвп 257 (1954), рр. 3-4, 161, 190, 275-303. 7. Начальная страница 1Г!ех Ьеср: //3 й1ех. сСе/. 8. Ьсср: //сгсгсг. се . рт1псеПоп. есСц/-арре1/лсосСехп/3 ача/ 71 ех. 9. К!еепе, Я. С., "Кергевепгайоп оГечепсв !п пегче песв", сп [16), рр. 3-40. 1О. 1.ев!с, М.
Е., "1.ех — а 1ехьса! апа!угег 8епегасог", Согпрпбп8 8ссепсе ТесЬ. Керогс 39, ВеП 1.аЬогасопев, Мппау Н!И, ЫЛ, 1975. Аналогичный документ с тем же названием, но с участием Е. ЗсЬгп!с!с в качестве соавтора, имеется в Чо!. 2 ор СЬе 1/лсх Рго8гаттегв Малиас, Ве1! 1аЬогагопев, Мштау Нс!1 Я, 1975; см. Ьсср: //Жпозапх.
сопср11етсоо1з. пес/1ех/Епс)ех. Ьссп1. 11. КппСЬ, Р. Е., У. Н. Могпв, апс) Н. К. Рган, "Гав! рацегп шагсЫп8 сп вгпп8в", ЯАМИ. Сотринл8 6:2 (1977), рр. 323 — 350. 12. МсСп11оп8Ь, %. Б. апд ЧСг. Рспв, "А 1о81са1 са1сп!пв оГ сЬе 1с)еав ппшапепс ш пегчопв асйчйу", Ви)1. Маг/г. Всорлувгсю 5 11943), рр. 115 — 133. 13. МсЫап8Ьсоп, К. апд Н. Нашасса, "Ке8п!аг ехргевяопв апг) всаге 8гарЬв Гог аогошага", /ЯЕ Тгалв.
оп Е!се!котс Сотригегв ЕС-9:1 (1960), рр. 38-47. 14. Мооге, Е. Р., "Оес1ап1сеп ехрепшепсв оп вес)цепс!а! псасЬспев", ш 1161, рр. 129— 153. ! 5. КаЬсп, М. О. апсс Р. 8соСС, "Гш!Се апгошага апс1 СЬе!г с)ес!в!оп ргоЫешв", /ВМ ./. Рею, алг/Печеб 3:2 (1959), рр. 114-125. 16.
ЯЬаппоп, С. агк1 Я. МсСапйу (е<Ь.), Аиготага Ягийею, Рппсесоп 11шч. Ргевв, 1956. 17. ТЬошрвоп, К., "Ке8ц1аг ехргевяоп веагсЬ а!8опСЬш", Сотт. АСМ 11:6 (1968), рр. 419-422. ГЛАВА 4 Синтаксический анализ Эта глава посвяшена методам синтаксического анализа, обычно используемым в компиляторах. Сначала здесь будут представлены базовые концепции, затем — методы, подходящие для реализации вручную, и наконец — алгоритмы, используемые в автоматизированном инструментарии.
Поскольку программы могут содержать синтаксические ошибки, здесь же будут рассмотрены и методы синтаксического анализа для восстановления после распространенных ошибок. В соответствии с дизайном каждый язык программирования имеет точные правила, которые предписывают синтаксическую структуру корректных программ. В С, например, программа создается из функций, функция — из объявлений и инструкций, инструкции — из выражений и т.д. Синтаксис конструкций языка программирования может быть описан с помощью контекстно-свободных грамматик или записи БНФ (Василя-Хацг гопп — форма Бэкуса — Наура), о которой шла речь в разделе 2.2. Грамматики обеспечивают значительные преимущества разработчикам языков программирования и создателям компиляторов.
° Грамматика дает точную и при этом простую для понимания синтаксическую спецификацию языка программирования. ° Для некоторых классов грамматик мы можем автоматически построить эффективный синтаксический анализатор, который определяет синтаксическую структуру исходной программы. Дополнительным преимуществом автоматического создания анализатора является возможность обнаружения синтаксических неоднозначностей и других сложностей, которые иначе могли бы остаться незамеченными на начальных фазах создания языка и его компилятора. ° Правильно построенная грамматика придает языку программирования структуру, которая способствует облегчению трансляции исходной программы в корректный объектный код и выявлению ошибок. ° Грамматика позволяет языку итеративно эволюционировать, обогащаясь новыми конструкциями для решения новых задач. Добавление этих новых конструкций в язык оказывается более простой задачей, если сушествующая реализация языка основана на его грамматическом описании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
