Деревья вывода предложений. (до 45 минут)

На практике вывод слов языка a(s) в виде последовательности цепочек часто оказывается громоздким. Кроме того, такой способ не позволяет получить в удобном виде информацию о синтаксических конструкциях. Наилучшим способом компактного представления вывода слов в таком случае является дерево вывода (дерево синтаксического анализа, дерево грамматического разбора). Говорят, что задано стандартное дерево вывода, если правилу r_i: x₁Ax₂®x₁qx₂ (здесь x₁, x₂ – контекст, x₁, x₂ Î(TÈH)^*), АÎН, qÎ(TÈH)^*) поставлено в соответствие элементарное поддерево t(r_i) с вершиной А и кроной x₁qx_2.

Пример 1: Пусть s1=<ía, b, cý, íA, B, C, D, Jý, J, íJ®AAB, AB®DBB, aBB®abB, A®a, D®a, B®C, C®cý>.

Вывод J, AAB, aAB, aDBB, aaBB, aabB, aaaBC, aabc представим деревом:

A

Здесь J – корень дерева, J A, A a - поддеревья.

B

aabc – крона дерева синтаксического вывода(a, b, b, c – листья дерева).

Лекция №18.

ФОРМАЛЬНЫЕ ГРАММАТИКИ. (продолжение)

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

Нефункциональная К. С. грамматика

Текст лекции

Пример 2: Арифметическое выражение a*b+c в К.С. грамматике с продукциями P=íJ®B, J®J+B, B®C, B®BC, C®D, D®a, D®b, D®c ý имеет следующий вывод: J, J+B, B+B, BC+B, CC+B, DC+B, aC+B, ab+B, ab+C, ab+D, ab+c (этот вывод содержит 52 символа). Дерево этого вывода имеет вид:

J

J + B

B C

B * C D

C D c

D b

a

В этом дереве синтаксического вывода 16 вершин, из них 5 помечены терминальными символами (крона а, *, b, +, с), а 11 – нетерминальными (равно числу применения правил в выводе терминальной цепочки a*b+c).

Примечание:

1. Однозначное соответствие между выводом и его синтаксическим деревом не означает однозначность обратного – одному дереву, может соответствовать несколько выводов. Так, в рассмотренном примере арифметическое выражение в грамматике может иметь и другой вывод: J, J+B, B+B, Bc+B, BD+B, Bb+B, Cb+B, Db+B, ab+B, ab+C, ab+D, ab+c, а его дерево тоже самое, что в рассмотренном примере.

К.С. грамматика s₂ может быть нефункциональной, если в ней существует хотя бы одно предложение языка, имеющее более одного дерева синтаксического вывода.

Так К.С. грамматика порождает язык

, цепочки, которого с n>1 имеют несколько выводов и соответственно несколько деревьев синтаксического вывода. Действительно, предложение a⁷ представимо двумя деревьями вывода

3) Поскольку дерево синтаксического вывода является средством вывода терминального слова, что наличие нескольких деревьев для вывода влечет за собой семантическую неоднозначность (т. е. различные интерпретации одного и того же слова).

Так, нефункциональная К. С. грамматика

позволяет для выравнивания a∙b+c задать два дерева синтаксического вывода

Интерпретацией этих двух деревьев для цепочки a∙b+c являются различные расстановки скобок – в первом случае (a∙b)+c, а во втором a∙(b+c), что означает включение в терминальный алфавит Т грамматики σ скобок (левой и правой).

Теорема: не существует алгоритма распознавания для произвольной К. С. грамматики, ее функциональности или не функциональности.

4) Процесс распознавания правильности цепочки (слова, предложения), т. е. определения ее принадлежности к рассматриваемому языку,

называют синтаксическим анализом (в ЭВМ этот анализ осуществляет распознаватель – один из основных блоков современных трансляторов t(α_ех) = α_объект, где t – транслирующая программа). При анализе цепочек используется либо стратегия “развертки” (т. е. сверху вниз – от корня дерева вывода к его кроне), либо стратегия “свертки” (т. е. снизу вверх – от кроны к корню дерева вывода).

Пример.: провести синтаксический анализ предложения

методом “развертки” и “свертки”, если продукции σ₂ имеет вид: Р={J→Ca, C→bA, C→aB, A→a, B→b, B→bC}.

Решение:

а)

б)

1) 2) 3)

4) 5) 6)

Пояснения к построению дерева методом “свертки”:

- входная цепочка (предложение) является кроной (полагаем);

- получаемые в процессе свертки подстроки сравниваются с правыми частями продукций грамматики σ₂, а при их совпадении приводятся к нетерминальному символу, стоящему в левой части таких продукций.

Отметим, что грамматика Хомского представляет практический интерес потому, что они порождают распознаваемые языки. В противном случае, нельзя бы было обнаружить ошибки при отладке программ.

Лекция №19.

РЕГУЛЯРНАЯ ГРАММАТИКА И КОНЕЧНЫЙ АВТОМАТ.

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

Текст лекции

Дата добавления: 2015-12-01