Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 35
Текст из файла (страница 35)
В первом случае Тяеу (они) относится к самолетам, а слово)1у)пй — это причастие, служащее определением самолетов. Во втором случае Тнеу относится к кому-то, кто летит на самолете, Неоднозначность часто является свойством не языка, а грамматики. Например, грамматика Сь которая определяет всевозможные цепочки из нулей и единиц, является неоднозначной: 01 . 5 «55 ) 0 ) 1 Мы знаем, что эта грамматика является неоднозначной, потому что в языке существуют цепочка, имеющая два различных дерева грамматического разбора (рнс. ЗА). Если любая грамматика для какого либо языка является неоднозначной, то говорят, что язык обладает наследственной неоднозначностью.
Но в нашем случае язык, состоящий из всех двоичных цепочек, не является наследственно неоднозначным, поскольку существует лишенная неоднозначности грамматика Сь которая определяет те же цепочки: 6г . 'Г -«ОП]т/ОП З.З. Формальные модели трансляции 121 Т /~ ! / /~ ! О О 1 о о о о 6: Однозначная грамматика б,: Неоднозначная грамматика Рмо. 3.4. Неоднозначность в грамматикак <целое со знакои> ::= +<целое> ( - целое> <цегое> ..= <цифра> ( <целое><цифра> Мы опишем некоторые расширения НФБ-нотации, которыс позволяют избежать подобных неестественных способов определения простых синтаксических свойств некоторых грамматик. Расширенная НФБ-нотация. Для расширения НФБ-потанин применяются следующие дополнительные обозначения, которые не ограничивают возможности НФБ-грамматики, но упрошают описания языков: + необязательный элемент может быть обозначен заключением его в квадратные скобки — (...1; + альтернативные варианты вводятся прн помощи вертикальной черты ( и в случае необходимости могут быть заключены в квадратные скобки г[,]); + произвольная последовательность экземпляров одного и того же элемента может бьггь обозначена заключением его в фигурные скобки, за которыми следует символ «звездочк໠— (...(*.
В качестве примеров рассмотрим следующие правила: цЕЛСЕ СО Знаиакг <ЦЕЛОЕ СО анаКОИ> .:= (+(-1<цЕЛОЕ>(<цЕГОЕ>( идентификатор: <идеитификатор> : - <буква>(<буква>(<цифра>(* В качестве другого примера можно привести более интуитивное определение арифметических выражений, как они описаны в табл. 3.1, с использованием расширенной НФБ-нотации, Расширения НФБ-нотации Несмотря на простоту, элегантность н мощность НФБ-грамматик, они не являются идеальным средством для сообщения программисту-практику правил конкретного языка программирования.
Основная причина этого заключается в простоте правил НФБ-грамматики, которая приводит к весьма неестественному представлению общих синтаксических конструкций для необязательных, альтернативных и повторяющихся элементов какого-либо синтаксического правила. Например, чтобы выразить простую синтаксическую идею «целое со знаком есть последовательность цифр, начинаюшаяся с необязательного символа плюс или минус», в НФБ-грамматике придется написать довольно сложный ряд рекурсивных правил, а именно; 122 Глава 3. Вопросы трансляции языка Оператор присваивания Переменная Арифметическое выражение Первичное Арифметическое Переменная Список ' индексов Идентификато Список и Рис.
ЗЛК Синтаксические схемы для простых операторов присваивания Таблица 3.3. Расширенная НФБ-грамматика для простых операторов присваивания <оператор присваивания>::= <переменная> = <арифметическое выражение> <терм> ([+ [ — ) <терм>)* <первичное выражение>([х[,т)<первичное выражение>)* <переменная> [ <чиспо> [ (<арифметическое выражение>) <идентификатор> [ <идентификатор> [<список индексов>] <арифметическое выражение> (,<арифметическое выражение>)* <арифметическое выражение>;:= <терм> с= <первичное выражение>::= <переменная> с= <список индексов> .= Синтаксические схемы. Синтаксическая схема гназыааемая также железнодорожной диигриматой, поскольку она напоминает расположение стрелок на же- Такие правила, как <арифиетическое выражение> .:= <тори> [ <арифиетическое вирахечие> + <гери> отражают тот факт, что арифметическое выражение может состоять из произвольногоо количества тсрмоа.
Используя расширенную НФБ-нотацию, можно это выраженно записать так: <арлфиетическое вирахеиие> .= <гери> ( «терн>]* Вся грамматика арифметических выражений может быть переформулирована прн помощи расширений НФБ-нотацин. Результат представлен в табл. 3.3. З.З. Формальные модели трансляции 123 лезной дороге) — это графический способ выражения правил грамматики с помошью расширенной НФБ-цотации. Каждое правило представляется в виде некоторой траектории от расположенной слева точки входа до расположенной справа точки выхода.
Любая траектория от входа к выходу представляет цепочку, генерируемую этим правилом. Если другие правила мы представим в виде прямоугольников, а терльипальные символы изобразим кружками, то для грамматики, представленной в табл. 3.3, получим синтаксические схемы, изображенные на рис. 3.5. Например, чтобы получить синтаксическую категорию < ьери>, следует двш аться слева от точки входа либо по траектории, проходящей через <перв изььое выражение> и выходящей справа через точку выхода, либо по траектории, также проходящей через <первичное выражение> н затем совершающей один или более циклов, проходя через кружки с операциями умножения или деления, а затем снова через <первичное выражение> и, наконец, также выходяшей справа через точку выхода.
Этому соответствует следующее правило, записанное с использованием расширенной НФБ-нотацьш: чьери> ;:= чпервиччае вырвнечие> ((х ( / 1чпервиччае выранеиие>)* 3.3.2. Конечные автоматы Все лексем ы языка и роь рамы и рован ил имеют простую структуру. Как было сказано ранее, этап лексического анализа прн компиляции заключается в том, что текст исходной програмльы разбивается на последовательность лексем. Теперь мы рассмотрим этот процесс с иной точки зрения, нежели в предыдущем разделе, посвященном НФБ-грамматике, а именно опишем машинную модель распознавания лексем. Любой идентификатор должен начинаться с буквы; пока символы, следующие за ней, являются цифрами или буквами, опи входят в имя этого идентификатора. Целое число — это просто последовательность цифр.
Зарезервированное слово ь1— это последовательность из двух букв, ь и г. Во всех подобных случаях для распознавания лексем применяется простая модель под названием конечный автомат (КА), или машина состотьий, Пока мы знаем, в каком из состояний находимся, мы можем определитьч является лн очередной вводимый символ частью лексемы, которую мы ищем. На рис. 3.6 схематически изображен простой КА, задача которого — распознавать двоичные цепочки с нечетным количеством единиц. Процесс начинается с состояния А (содержашего дугу ввода, не выходящую из другого состояния), затем в зависимости от следуюьцего введсшппо символа автомат переходит в одно из состояний, А или В, двигаясь вдоль дуги, помеченной этим символом. Очевидно, что состояние В (конечььое состояние, обозначенное двойным кружком) соответствует нечетному количеству единиц во введенной цепочке.
Поэтому, пока автомат находится в состоянии В, введенная на данный момент пеночка удовлетворяет предъявленному требованию и допускается этим автоматом, Когда автомат находится в состоянии А, такая цепочка це допускается. Последовательность действий КА для ввода цепочки 100101 будет следующен: 124 Глава 3. Вопросы трансляции языка Допускается ли цепочка Текущее состояние Ввод Нет Да Да Да Нет Нет Да А В В В А А В лов 1 10 1ОО 1001 10010 100101 Мы видим, что после ввода 1, 10, 100 и 1001001 автомат попадает в состояние Б, в цепочке содержишься нечетное количество единиц и, таким обраюм, ввод допустим.
А Рис. 3.6. КА, распознающий битовые цепочки с нечетным количеством единиц Бообще для любого КА определено одно начальное состояние, как минимум одно конечное состояние и ряд переходов между ними (нзображенных помеченными дугами). Говорят, что любая введенная цепочка символов, которая переводит автомат из начального состояния в конечное через ряд переходов, допускается этим автоматом. На рис. 3.7 изображен другой КА, распознающий цел1не числа со знаком. Если использовать расширенную НФБ-нотацию, рассмотренную нами в предыдущем разделе, то с ее помощью можно определить такие числа, как <целое со зна кои>: =(+ ( -)<целое> (<цепое>)*. Этот пример иллюстрирует еще одно важное свойство КА: между абстрактными машинами и грамматиками существует взаимное соответствие.
Б этой главе будет показано, что КА может быть смоделирован при помощи грамматики. Недетерминированный конечный автомат. До сих пор при обсуждении автоматов подразумевалоскч что все перехотпя между состояниями однозначно определены текущим состоянием и очередным введенным символом. То есть для каждого состояния КА н каждого введенного символа существует единственно возможный переход в некоторое следующее состояние (оно может совпадать или не совпадать с предыдущим). Подобный конечный автомат называется детерминированным.
Если автомат имеет и состояний н входной алфавит состоит из и символов, то количество переходов (помеченных дуг) будет равно и х а. На рис. 3.7 изображен такой З.З. Формальные модели трансляции 125 детерминированный конечный автомат. Отсутствие некоторых дуг (переходов) не представляет проблемы, так как мы всегда можем добавить дупт (переходы) к дополнительному поглощающему неконечному состояштю ошибки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
