А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 53
Текст из файла (страница 53)
Вторым шагом порождения является — Е =ь — (Е). Соответственно, мы добавляем три дочерних узла, помеченных (, Е и ), к листу Е во втором дереве для получения третьего дерева с кроной — (Е). Продолжая построения описанным способом, мы получим в качестве полного дерева разбора шестое дерево последовательности.
и Поскольку дерево разбора игнорирует порядок, в котором производилось замещение символов в сентенциальной форме, между порождениями и деревьями разбора возникает соотношение "многие к одному". Например, и порождение (4.6), и порождение (4.7) связаны с одним и тем же окончательным деревом разбора, показанным на рис.
4.4. 265 4.2. Контекстно-свободные грамматики Е Е ( Е ) > Е Е г!' г ! Рис. 4.4. Последовательность деревьев разбора для пороящения (4.6) Далее мы зачастую будем выполнять синтаксический анализ при помощи левых или правых порождений, поскольку между деревьями разбора и левыми (как и правыми) порождениями существует взаимно однозначное соответствие. И левое, и правое порождения выбирают определенный порядок замещения символов в сентенциальной форме, так что все варианты с иным порядком отсеиваются. Нетрудно показать, что каждое дерево разбора связано с единственным левым и единственным правым порождением. 4.2.5 Неоднозначность Из раздела 2.2.4 мы знаем, что грамматика, которая дает более одного дерева разбора лдя некоторого предложения, называется неоднозначной (атЬ|япопз).
Иначе говоря, неоднозначная грамматика — это грамматика, которая для одного и того же предложения дает не менее двух левых или правых порождений. Пример 4.4. Грамматика для арифметических выражений (4,3) допускает два раз- ных левых порождения для предложения Ы + Ы * Ы: Соответствующие деревья разбора показаны на рис. 4.5. Е ~ Е+Е Ы+Е п$+ Е*Е Ы+Ы*Е = Ы+Ы*Ы Е =ь ЕяЕ Е+Е*Е Ы+Е*Е Ы+Ы*Е Ы+Ы*Ы г !' 1 266 Глава 4. Синтаксический анализ Обратите внимание, что дерево на рис. 4.5, а отражает обычно принимаемые приоритеты операторов + и *, в то время как дерево на рис.
4.5, б отражает обратное соотношение приоритетов. Иными словами, обычно считается, что приоритет оператора * выше, чем приоритет оператора +, так что обычно выражение наподобие а + Ь * с вычисляется как а + (Ь * с), а не как (а + Ь) * с. а б) а) Рис. 4.5. Два дерева разбора для предложения И + Ы * Ы Для большинства синтаксических анализаторов грамматика должна быть однозначной, поскольку, если это не так, мы не в состоянии определить дерево разбора для предложения единственным образом.
В некоторых случаях удобно использовать тщательно отобранную неоднозначную грамматику совместно с правилами устранения неоднозначностей (йзашЬ18ца)1пй гц)ез), которые "отбрасывают" нежелательные деревья разбора, оставляя для каждого предложения по одному дереву.
4.2.б Проверка языка, сгенерированного грамматикой Хотя разработчики компиляторов редко делают это для полной грамматики языка программирования, очень полезно иметь возможность убедиться, что данное множество продукций генерирует определенный язык. Проблемные конструкции можно изучить, написав сокращенный, абстрактный вариант грамматики и изучив генерируемый ею язык.
Ниже мы построим такую грамматику для условных инструкций. Для доказательства того, что грамматика С порождает язык Хч мы должны показать, что любая строка, генерируемая С, принадлежит А и, наоборот, что каждая строка из А может быть порождена грамматикой С. Пример 4.5. Рассмотрим грамматику Я вЂ” >(Я) Я)е (4.8) Хотя на первый взгляд это не очевидно, данная простая грамматика порождает все строки из сбалансированных скобок, и только такие строки. Чтобы убедиться 267 4.2. Контекстно-свободные грамматики в этом, вначале покажем, что каждое предложение, выводимое из Я, сбалансировано, а затем — что каждая сбалансированная строка может быть выведена из Я.
Для того чтобы показать, что каждое предложение, выводимое из Я, сбалансировано, воспользуемся индукцией по количеству шагов п в порождении. БАзис: и = 1. Единственная строка терминалов, порождаемая из 5 за один шаг,— это пустая строка, которая, само собой, является сбалансированной. Индукция: теперь предположим, что все порождения из менее чем п шагов приводят к сбалансированным предложениям, и рассмотрим левое порождение, состоящее ровно из и шагов.
Такое порождение должно иметь вид Я =~ (Я) Я => (х) Я =~ (х)у 1т Ьть 1т Порождения х и у из Я занимают менее и шагов и согласно гипотезе индукции х и а сбалансированы. Следовательно, строка (х) у должна быть сбалансированной, т.е. иметь одинаковое количество левых и правых скобок, причем любой префикс строки содержит как минимум столько же левых скобок, сколько и правых. Таким образом, любая строка, выводимая из Я, сбалансирована. Теперь нужно показать, что любая сбалансированная строка может быть получена нз Я. Для этого воспользуемся индукцией по длине строки. БАзнс: Если строка имеет длину О, это пустая строка е, являющаяся сбалансированной.
Индукция: Сначала заметим, что каждая сбалансированная строка имеет четную длину. Предположим, что любая сбалансированная строка длиной менее 2п порождаема из Я, и рассмотрим сбалансированную строку тс длиной 2п, где п ) 1. Несомненно, что ш начинается с левой скобки. Пусть (х) — кратчайший префикс и, имеющий одинаковое количество левых и правых скобок.
Тогда и можно записать как (х) у, где и х, и у сбалансированы. Поскольку и х, н у имеют длину менее 2п, они порождаемы из Я согласно гипотезе индукции. Таким образом, можно найти порождение вида Я - (о) Я ~ (х) Я =ь (х) у которое доказывает, что и = (х) у также порождаемо из Я. 4.2.7 Контекстно-свободные грамматики и регулярные выражения Перед тем как завершить этот раздел, посвященный грамматикам и их свойствам, мы убедимся, что грамматики представляют собой более мощные обозначения по сравнению с регулярными выражениями. Каждая конструкция, которая Глава 4. Синтаксический анализ 268 может быть описана регулярным выражением, может быть описана и грамматикой, но не наоборот. Говоря иначе, каждый регулярный язык является контекстно- свободным, но не наоборот. Например„регулярное выражение (а ~ Ь)* аЬЬ и грамматика Ао — аАо ( 6Ао ! аА1 А1 — ЬАз Аз — ЬАз Аз описывают один и тот же язык, множество строк из а и 6, заканчивающихся на аЬЬ.
Можно механически построить грамматику для распознавания того же языка, что и распознаваемый недетерминированным конечным автоматом (НКА). Приведенная выше грамматика построена на основе НКА на рис. 3.24 следующим образом. 1. Для каждого состояния з в НКА создается нетерминал А,. 2.
Если состояние г имеет переход в состояние з по символу а, добавляем в грамматику продукцию А; — аА . Если состояние г переходит в состояние З для пустой строки е, добавляем продукцию А; — А . 3. Если г — принимающее состояние, добавляем продукцию А, — г. 4. Если г — начальное состояние, делаем А, стартовым символом грамматики. С другой стороны, язык Л = (а"Ь" ~ п > 1) с одинаковым количеством а и 6 в строках является прототипичным примером языка, который может быть описан грамматикой, но не регулярным выражением. Чтобы убедиться в этом, предположим, что Т, — язык, определенный некоторым регулярным выражением.
Мы можем построить ДКА Р с конечным числом состояний, скажем, 6, который принимает Т. Поскольку Р имеет только 6 состояний, при входной строке, начинающейся более чем с 6 символов а, автомат Р должен войти в некоторое состояние дважды, скажем, в состояние ац как показано на рис. 4.6. Предположим, что путь из з; в себя же помечен последовательностью аэ '.
Поскольку строка а'Ь' принадлежит языку, должен существовать путь, помеченный 6', из гч в принимающее состояние Г". Однако в таком случае имеется путь нз начального состояния зо в принимающее состояние Г, проходящий через гч и помеченный азЬ', как показано на рис. 4.6. Таким образом, конечный автомат Р принимает также строку ауЬ', не принадлежащую языку, что противоречит предположению о том, что Т, — язык, принимаемый Р.
2б9 4,2. Контекстно-свободные грамматики Путь, помеченный а>-' Путь, помеченн Рис. 4.6. ДКА (З, принимающий как атЬ', так и атьт Говоря простым языком, "конечный автомат не умеет считать", а это означает, что конечный автомат не может принимать язык наподобие (а"Ь ~ п ) 1), в котором требуется запоминать количество символов а перед просмотром символов Ь.
Аналогично "грамматика может считать две вещи, но не три", как мы увидим при рассмотрении конструкций не контекстно-свободного языка в разделе 4.3.5. 4.2.8 Упражнения к разделу 4.2 Упражнение 4.2.1. Рассмотрим контекстно-свободную грамматику о'- о'о'+!о'о'*)а н строку па+а*. а) Приведите левое порождение строки. б) Приведите правое порождение строки.
в) Приведите дерево разбора строки. ! г) Является ли данная грамматика однозначной? Обоснуйте свой ответ. ! д) Опишите язык, генерируемый этой грамматикой. Упражнение 4.2.2. Повторите упражнение 4.2.1 для следующих грамматик и строк. а) Грамматика о — 0 о 1 ~ 0 1, строка 000111. б) Грамматика о - +о о ~ * о о ~ а, строка +*ааа. ! в) Грамматика о — о (5) о ~ е, строка ( ( ) ( ) ) . ! г) Грамматика о' — т о' + о' ( о' о' ) ф) ! о' е ) а, строка (а + а) * а. ! д) Грамматика Ь'- (Ь) ~ он Е- Ь,о') о', строка ((а,а),а,(а)). 1! е) Грамматика о' — а о' Ь о' ) Ь о' а о' ( е, строка ааЬЬаЬ. 270 Глава 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
