Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 52
Текст из файла (страница 52)
Расскотрим только левые. Пример 5.28. Заметим, что оба дерева разбора, представленные на рис. 5.!8, жееют крону Е+ Е * Е. По ним получаются следующие соответствующие нм левые б) Е =» Е * Е =» Е м Е * Е =» Г м Е " Е ~ а ч- Е * Е =» / ! / ! М а-»У»Е ~ ама*Е ~ ача»1=» а+а»а / м м Заметим, что эти левые порождения различаются.
Данный пример не доказывает теорему, но демонстрирует, как различия в деревьях разбора влияют на выбор шагов в левом порождении. П Теорема 5.29. Для каждой грамматики О = ('г', Т, Р, 5) и»г из Т цепочка зг имеет два разных дерева разбора тогда и только тогда, когда»» имеет два разных левых порождения из 5. Доказательство. (Необходимость) Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве теоремы 5.14.
В любом случае, если у двух деревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, сле- довательно, являются различными. (Досиаточносгпь) Хотя мы предварительно не описали непосредственное построение дерева разбора по левому порождению, идея его проста. Начнем построение дерева с корня, отмеченного стартовым символом. Рассмотрим порождение пошагово. На каждом шаге заменяется переменная, и эта переменная будет соответствовать построенному крайнему слева узлу дерева, не имеющему сыновей, но отмеченному этой переменной.
По продукции, использованной на этом шаге левого порождения, определим, какие сыновья должны быть у этого узла. Если существуют два разных порождения, то на первом шаге, где они различаются, построенные узлы получат разные списки сыновей, что гарантирует различие деревьев разбора. П 5.4.4. Существенная неоднозначность Контекстно-свободный язык Е называется сущесгпвепно неоднозначным, если все его грамматики неоднозначны. Если хотя бы одна грамматика языка Е однозначна, то Е является однозначным языком. Мы видели, например, что язык выражений, порождаемый грамматикой, приведенной на рис. 5.2, в действительности однозначен. Хотя данная грамматика н неоднозначна, этот же язык задается еше одной грамматикой, которая однозначна — она изображена на рис.
5.19. Мы не будем доказывать, что существуют неоднозначные языки. Вместо этого рассмотрим пример языка, неоднозначность которого можно доказать, и объясним неформально, почему любая грамматика для этого языка должна быть неоднозначной: Ь = 1а" Ь"с Ы ~ п й 1, и й 1) 1) '1а"Ь с"»1" 1п > 1, и > 1). Из определения видно, что Ь состоит из цепочек вида а и с д, в которых поровну сим- волов а и Ь, а также с и Ы, либо поровну символов а и г1, а также Ь и с. ГЛАВА б.
КОНТЕКСТНО-СВОБОДНЫВ ГРАММАТИКИ И ЯЗЫКИ 226 Ь является КС-язгаком. Очевидная грамматика для него показана на рис. 5.22. Для порождения двух видов цепочек в ней используются два разных множества продукций. Эта грамматика неоднозначна. Например, у цепочки ааЬЬссгЫ есть два следующих левых порождения. !, 5 =з АВ =в аАЬВ =в ааЬЬВ =в ааЬЬссВг2 ~ ааЬЬссе)е2 1 ь и и 5 =з С =в аСез =в ааРг2г2 ~ ааЬРссЫ ~ ааЬЬссг2г2 Соответствующие деревья разбора показаны на рис. 5.23.
В -> АВ)С А -+ аАЬ|аЬ В вЂ” э сВа)) са) С -з аСс)) аРЫ Р -з ЬРс) Ьс Рис. 5 22. Грамматика для существенно неоднозначного языка и Ь Ь е б) Рис. 5.23. Два дерева разбора для ааЬЬссдд Доказательство того, что все грамматики для языка Ь неоднозначны, весьма непросто, однако сущность его такова. Нужно обосновать, что все цепочки (за исключением конечною пх числа), у которых поровну всех символов, должны порождаться двумя различными путями. Первый путь — порождение их как цепочек, у которых поровну символов а и Ь, а таке с и а), второй пуп — как цепочек, у которых поровну символов а и Ы, как и Ь и с.
227 ЬА. НЕОДНОЗНАЧНОСТЬ В ГРАММАТИКАХ И ЯЗЫКАХ Например, единственный способ породить цепочки, у которых поровну а и Ь, состоит в использовании переменной, подобной А в грамматике, изображенной на рис. 5.22. Конечно же, возможны варианты, но они не меняют картины в целом, как это видно из сле- дующих примеров. ° Некоторые короткие цепочки могут не порождаться после изменения, например, базисной продукции А — + аЬ на А †> аааЬЬЬ.
° Мы могли бы организовать продукции так, чтобы переменная А делила свою работу с другими, например, используя переменные А, и Ал из которых А, порождает нечетные количества символов а, а А, — четные: А, -э аАзЬ | аЬ; Аэ — ь аА,Ь ! аЬ ° Мы могли бы организовать продукции так, чтобы количества символов а и Ь, порождаемые переменной А, были не равны, но отличались на некоторое конечное число. Например, можно начать с продукции  — эАаВ и затем использовать А — э аАЬ ! а для порождения символов а на один больше, чем Ь.
В любом случае, нам не избежать некоторого способа порождения символов п, при котором соблюдается их соответстяие с символами Ь. Аналогично можно обосновать, что должна использоваться переменная, подобная В, которая порождает соответствующие друг другу символы с и а( Кроме того, в грамматике должны быть переменные, играющие роль переменных С и !э, порождающих соответственно парные а и д и парные Ь и с. Приведенные аргументы, если их формализовать, доказывают, что независимо от изменений, которые можно внести в исходную грамматику, она будет порождать хотя бы одну цепочку вида а"Ь"с"и" двумя способами, как и грамматика, изображенная на рис.
5.22. 5.4.5. Упражнения к разделу 5.4 5.4.1. Рассмотрим грамматику Б — > а5 ~ або ! и Она неоднозначна. Докажите, что для цепочки ааЬ справедливо следукнцее: а) для нее существует два дерева разбора; б) она имеет два левых порождения; в) она имеет два правых порождения. 5.4.2. (!) Докажите, что грамматика из упражнения 5.4.! порождает те, и только те цепочки из символов а и Ь, у которых в любом префиксе символов а не меньше, чем Ь.
5.4.3. (я!) Найдите однозначную грамматику для языка из упражнения 5.4.1. 5.4.4. (!!) В грамматике из упражнения 5.4.! некоторые цепочки имеют только одно дерево разбора. Постройте эффективную проверку, является ли цепочка одной 228 ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ из указанных. Проверка типа "проверить все деревья разбора, чтобы увидеть, сколько их у данной цепочки" не является достаточно эффективной. 54.5. (1) Воспроизведем грамматику из упражнения 5.1.2: — А!В А — ь ОА)в  — ь ОВ)!В1в а) докажите, что данная грамматика неоднозначна; б) найдите однозначную грамматику для этого же языка и докажите ее однозначность.
5.4.6. (в1) Однозначна ли ваша грамматика из упражнения 5.1.5? Если нет, измените ее так, чтобы она стала однозначной. - 5,4.7. Следующая грамматика порождает префиксные выражения с операндами т и у и операторами +, - и *: Е -+ + ЕЕ ! * ЕЕ ) - ЕЕ ( х ) у а) найдите левое и правое порождения, а также дерево разбора для цепочки -';*-хуху; б) (1) докажите, что данная грамматика однозначна. резюме Канменсмно-свободные грамматики. КС-грамматика — это способ описания языка с помошью рекурсивных правил, называемых продукциями. КС-грамматика состоит из множества переменных, терминальных символов, стартовой переменной, а также пролукций.
Каждая продукция состоит из головной переменной и тела — цепочки переменных и!или терминалов, возможно, пустой. ь Порождения и языки. Начиная со стартового символа, мы порождаем терминальные цепочки, повторяя замены переменных телами продукций с этими переменными в голове. Язык КС-грамматики — это множество терминальных цепочек, которые можно породить; он называется КС-языком.
ь Певые и правые порождении. Если мы всегда заменяем крайнюю слева (крайнюю справа) переменную, то такое порождение является левым (правым). Каждая цепочка в языке КС-грамматики имеет, по крайней мере, одно левое и одно правое порождения. ь Выводимые леночки. Любой шаг порождения дает цепочку переменных и~или терминалов.
Она называется выводимой цепочкой. Если порождение является левым (правым), то цепочка называется левовыводимой (правовыводимой). РЕЗЮМЕ 229 ь Деревья разбора. Дерево разбора — это дерево, показывающее сущность порождения. Внутренние узлы отмечены переменными, листья — терминалами или е. Для каждого внутреннего узла должна существовать продукция, голова которой является отметкой узла, а отметки сыновей узла, прочитанные слева направо, об- разуют ее тело. ь Эквивалентность деревьев разбора и порождений. Терминальная цепочка принадлежит языку грамматики тогда и только тогда, когда она является кроной, по крайней мере, одного дерева разбора.
Таким образом, существование левых порождений, правых порождений и деревьев разбора является равносильным условием того, что все они определяют в точности цепочки языка КС-грамматики. ь Неоднозначные грамматики. Для некоторых грамматик можно найти терминальную цепочку с несколькими деревьями разбора, нли (что равносильно) с несколькими левыми или правыми порождениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
