Цепочки вывода

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра ТК
Тема:

грамматики
Цепочка β=δ1γδ2 непосредственно выводима из цепочки α=δ1ωδ2

в грамматике G(VT,VN,P,S),

α⇒β

Цепочка β выводима из цепочки α (обозначается: α⇒*β), если выполняется одно из двух условий:

β непосредственно выводима из α (α⇒β);

∃γ такая, что: γ выводима из α и β непосредственно выводима из γ
(α⇒*γ и γ⇒β).

Каждый переход от одной непосредственно выводимой цепочки к следующей в

Если цепочка вывода из α к β содержит одну или более промежуточных цепочек (два или более шагов вывода), то она обозначается:
α⇒+β или α⇒*β
цепочка β нетривиально выводима из цепочки α.

Если количество шагов вывода известно, то его можно указать непосредственно,

например, α⇒3β – цепочка β выводится из цепочки α за 3 шага вывода.

шагов вывода в цепочке вывода всегда на один больше,
чем промежуточных цепочек – если цепочка β непосредственно
выводима из цепочки α: α⇒β, то имеется всего один шаг вывода

знаком:
G({0,l,2,3,4,5,6,7,8,9,-,+},{S,T,F},P,S):

Р: S → T1| +T2| -T3
T → F4| TF5
F → 06|17|28|39|410|511|612|713|814|915

S⇒*575

-T ⇒* -9856

S ⇒*+32

+FT ⇒* +104

S⇒7575

-T⇒8-9856

S⇒5+32

+FT⇒5+104

в результате вывода, нельзя больше сделать ни одного шага вывода

Вывод

Цепочка β, полученная в результате законченного вывода, называется конечной цепочкой вывода.

Цепочка символов α∈V* называется сентенциальной формой грамматики G(VT,VN,P,S), V=VT∪VN, если она выводима из целевого символа грамматики S:
S⇒*α.

Если цепочка α∈VT* получена в результате законченного вывода, то она называется конечной сентенциальной формой.

вывода правило грамматики применяется всегда к крайнему левому нетерминальному символу

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

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

(граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

корнем дерева является вершина, обозначенная целевым символом грамматики S;

листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки λ;

если некоторый узел дерева обозначен символом A∈VN, а связанные с ним узлы – символами b1,b2,…, bn; n>0, ∀ n≥ i > 0: bi∈(VT∪VN∪{λ}),
то в грамматике G(VT, VN, P, S) существует правило A→ b1,b2,...,bn ∈Р.

По структуре правил дерево вывода в указанном виде
всегда можно построить только
для КС-грамматик и регулярных грамматик.
Для грамматик других типов дерево вывода
в таком виде можно построить не всегда
(либо же оно будет иметь несколько иной вид).

3:
S
S
Для того чтобы построить дерево вывода, достаточно иметь цепочку

сверху вниз – построение начинается с целевого символа грамматики, который

Затем в грамматике выбирается необходимое правило, и на первом шаге вывода корневой символ раскрывается на несколько символов первого уровня.

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

Построение дерева заканчивается, когда все концевые вершины обозначены терминальными символами, в противном случае надо вернуться ко второму шагу и продолжить построение;

для строго формализованного построения
дерева вывода всегда удобнее пользоваться
строго определенным выводом:
либо левосторонним, либо правосторонним

с листьев дерева.
В качестве листьев выбираются терминальные символы конечной

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

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

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

символов языка, заданного этой грамматикой, можно построить единственный левосторонний (и

Однозначность – это свойство грамматики, а не языка.

В общем виде невозможно проверить, является ли заданная грамматика однозначной или нет.

Однако для КС-грамматик существуют определенного вида правила, по наличию которых во множестве правил грамматики G(VT,VN,P,S) можно утверждать, что она является неоднозначной (отсутствие правил указанного вида (всех вариантов) есть необходимое, но не достаточное условие однозначности грамматики) A∈VN; α, β, γ∈(VN∪VT)*):
А → АА | α;
А → АαА | β;
А → αА| Аβ| γ;
А → αА| αАβА | γ.

знаком задана:
G({0,l,2,3,4,5,6,7,8,9,-,+},{S,T,F},P,S):

Построить дерево вывода для цепочки вывода