Содержание
- 2. Методы построения трансляторов Тема № 5 Цепочки вывода
- 3. Цепочки вывода Вывод процесс порождения предложения языка на основе правил определяющей язык грамматики Цепочка β=δ1γδ2 непосредственно
- 4. Цепочки вывода Вывод Последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода. Каждый переход от одной
- 5. Цепочки вывода Вывод Пример: задана грамматика G для целых десятичных чисел со знаком: G({0,l,2,3,4,5,6,7,8,9,-,+},{S,T,F},P,S): Р: S
- 6. Цепочки вывода Вывод называется законченным, если на основе цепочки β, полученной в результате вывода, нельзя больше
- 7. Цепочки вывода Вывод Вывод называется левосторонним, если в нем на каждом шаге вывода правило грамматики применяется
- 8. Цепочки вывода Дерево вывода Дерево вывода грамматики G(VT,VN,P,S) – это дерево (граф), которое соответствует некоторой цепочке
- 9. Цепочки вывода Дерево вывода Деревья вывода для цепочек вывода 1 и 3: S S Для того
- 10. Цепочки вывода Дерево вывода Дерево вывода можно построить двумя способами: сверху вниз – построение начинается с
- 11. Цепочки вывода Дерево вывода снизу вверх – построение начинается с листьев дерева. В качестве листьев выбираются
- 12. Цепочки вывода Дерево вывода Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой,
- 14. Скачать презентацию
Методы построения трансляторов
Тема № 5
Цепочки вывода
Методы построения трансляторов
Тема № 5
Цепочки вывода
Цепочки вывода
Вывод
процесс порождения предложения языка на основе правил определяющей язык грамматики
Цепочка
Цепочки вывода
Вывод
процесс порождения предложения языка на основе правил определяющей язык грамматики
Цепочка
в грамматике G(VT,VN,P,S), V=VT∪VN, δ1, γ, δ2∈V*, ω∈V+,
если в грамматике G существует правило: ω→γ∈Р
α⇒β
Цепочка β выводима из цепочки α (обозначается: α⇒*β), если выполняется одно из двух условий:
β непосредственно выводима из α (α⇒β);
∃γ такая, что: γ выводима из α и β непосредственно выводима из γ
(α⇒*γ и γ⇒β).
Цепочки вывода
Вывод
Последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода.
Каждый
Цепочки вывода
Вывод
Последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода.
Каждый
Если цепочка вывода из α к β содержит одну или более промежуточных цепочек (два или более шагов вывода), то она обозначается:
α⇒+β или α⇒*β
цепочка β нетривиально выводима из цепочки α.
Если количество шагов вывода известно, то его можно указать непосредственно,
например, α⇒3β – цепочка β выводится из цепочки α за 3 шага вывода.
шагов вывода в цепочке вывода всегда на один больше,
чем промежуточных цепочек – если цепочка β непосредственно
выводима из цепочки α: α⇒β, то имеется всего один шаг вывода
Цепочки вывода
Вывод
Пример: задана грамматика G для целых десятичных чисел со знаком:
Цепочки вывода
Вывод
Пример: задана грамматика G для целых десятичных чисел со знаком:
G({0,l,2,3,4,5,6,7,8,9,-,+},{S,T,F},P,S):
Р: S → T| +T| -T
T → F| TF
F → 0|1|2|3|4|5|6|7|8|9.
Р: 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
Цепочки вывода
Вывод называется законченным, если на основе цепочки β, полученной в
Цепочки вывода
Вывод называется законченным, если на основе цепочки β, полученной в
вывод называется законченным, если цепочка β, полученная в результате вывода, пустая или содержит только терминальные символы грамматики G(VT,VN,P,S): β∈VT*.
Вывод
Цепочка β, полученная в результате законченного вывода, называется конечной цепочкой вывода.
Цепочка символов α∈V* называется сентенциальной формой грамматики G(VT,VN,P,S), V=VT∪VN, если она выводима из целевого символа грамматики S:
S⇒*α.
Если цепочка α∈VT* получена в результате законченного вывода, то она называется конечной сентенциальной формой.
Цепочки вывода
Вывод
Вывод называется левосторонним, если в нем на каждом шаге вывода
Цепочки вывода
Вывод
Вывод называется левосторонним, если в нем на каждом шаге вывода
Вывод называется правосторонним, если в нем на каждом шаге вывода правило грамматики применяется всегда к крайнему правому нетерминальному символу в цепочке (на каждом шаге вывода происходит подстановка цепочки символов на основании правила грамматики вместо крайнего правого нетерминального символа в исходной цепочке).
Для КС-грамматик и регулярных грамматик
для любой сентенциальной формы всегда можно
построить левосторонний или правосторонний выводы.
Для грамматик других типов это не всегда возможно,
так как по структуре их правил не всегда можно выполнить
замену крайнего левого и крайнего правого
нетерминального символа в цепочке.
Цепочки вывода
Дерево вывода
Дерево вывода грамматики G(VT,VN,P,S) – это дерево (граф),
Цепочки вывода
Дерево вывода
Дерево вывода грамматики G(VT,VN,P,S) – это дерево (граф),
каждая вершина дерева обозначается символом грамматики A∈(VT∪VN);
корнем дерева является вершина, обозначенная целевым символом грамматики S;
листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки λ;
если некоторый узел дерева обозначен символом A∈VN, а связанные с ним узлы – символами b1,b2,…, bn; n>0, ∀ n≥ i > 0: bi∈(VT∪VN∪{λ}),
то в грамматике G(VT, VN, P, S) существует правило A→ b1,b2,...,bn ∈Р.
По структуре правил дерево вывода в указанном виде
всегда можно построить только
для КС-грамматик и регулярных грамматик.
Для грамматик других типов дерево вывода
в таком виде можно построить не всегда
(либо же оно будет иметь несколько иной вид).
Цепочки вывода
Дерево вывода
Деревья вывода для цепочек вывода 1 и 3:
Цепочки вывода
Дерево вывода
Деревья вывода для цепочек вывода 1 и 3:
S
S
Для того чтобы построить дерево вывода, достаточно иметь цепочку вывода.
Цепочки вывода
Дерево вывода
Дерево вывода можно построить двумя способами:
сверху вниз
Цепочки вывода
Дерево вывода
Дерево вывода можно построить двумя способами:
сверху вниз
Затем в грамматике выбирается необходимое правило, и на первом шаге вывода корневой символ раскрывается на несколько символов первого уровня.
На втором шаге среди всех концевых вершин дерева выбирается крайняя (крайняя левая – для левостороннего вывода, крайняя правая – для правостороннего) вершина, обозначенная нетерминальным символом, для этой вершины выбирается нужное правило грамматики, и она раскрывается на несколько вершин следующего уровня.
Построение дерева заканчивается, когда все концевые вершины обозначены терминальными символами, в противном случае надо вернуться ко второму шагу и продолжить построение;
для строго формализованного построения
дерева вывода всегда удобнее пользоваться
строго определенным выводом:
либо левосторонним, либо правосторонним
Цепочки вывода
Дерево вывода
снизу вверх – построение начинается с листьев
Цепочки вывода
Дерево вывода
снизу вверх – построение начинается с листьев
В качестве листьев выбираются терминальные символы конечной цепочки вывода, которые на первом шаге построения образуют последний уровень (слой) дерева (построение дерева идет по слоям).
На втором шаге построения в грамматике выбирается правило, правая часть которого соответствует крайним символам в слое дерева (крайним правым символам при правостороннем выводе и крайним левым при левостороннем). Выбранные вершины слоя соединяются с новой вершиной, которая выбирается из левой части правила. Новая вершина попадает в слой дерева вместо выбранных вершин.
Построение дерева закончено, если достигнута корневая вершина (обозначенная целевым символом), а иначе надо вернуться ко второму шагу и повторить его над полученным слоем дерева.
Так как все известные языки программирования
имеют нотацию записи «слева – направо»,
компилятор также всегда читает
входную программу слева направо
(и сверху вниз, если программа разбита на несколько строк),
то для построения дерева вывода методом «сверху вниз»,
как правило, используется левосторонний вывод,
а для построения «снизу вверх» – правосторонний вывод.
Цепочки вывода
Дерево вывода
Грамматика называется однозначной, если для каждой цепочки символов
Цепочки вывода
Дерево вывода
Грамматика называется однозначной, если для каждой цепочки символов
Однозначность – это свойство грамматики, а не языка.
В общем виде невозможно проверить, является ли заданная грамматика однозначной или нет.
Однако для КС-грамматик существуют определенного вида правила, по наличию которых во множестве правил грамматики G(VT,VN,P,S) можно утверждать, что она является неоднозначной (отсутствие правил указанного вида (всех вариантов) есть необходимое, но не достаточное условие однозначности грамматики) A∈VN; α, β, γ∈(VN∪VT)*):
А → АА | α;
А → АαА | β;
А → αА| Аβ| γ;
А → αА| αАβА | γ.