Меню

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

Деревья вывода

Для представления вывода в грамматике применяют деревья вывода. Корень дерева – начальный символ грамматики. Внутренние вершины дерева – нетерминалы. Листья дерева – терминалы. Если в дереве имеется некоторый узел, например

то в грамматике имеется правило X®Y1Y2Y3.

R: S®AaB; A®Bbc; B®ab.

В дереве вывода отражается, какие правила были применены и к каким вхождениям нетерминалов. Однако дерево не несет никакой информации о порядке применения правил (подстановок).

В данном примере имеется два вывода левосторонний (1) и правосторонний (2). Для каждого дерева существует единственный левый вывод, так как благодаря условию выбора самого левого нетерминала, место каждой подстановки устанавливается единственным образом, а по дереву можно определить то единственное правило, которое должно применяться при этой подстановке.

Аналогично, существует единственный правосторонний вывод. Многие методы обработки языков рассчитаны исключительно на левые, или правые выводы, так как они очень удобны для систематической обработки.

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

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

1) Каждой цепочке, выводимой в данной КС-грамматике, соответствует одно или несколько деревьев вывода.

2) Каждому дереву соответствует один или несколько выводов.

3) Каждому дереву соответствует единственный правый или единственный левый выводы.

4) Если каждой цепочке, выводимой в данной КС-грамматике, соответствует единственное дерево вывода, эта грамматика называется однозначной в противном случае её называют неоднозначной.

Вопросы и упражнения

Источник

Дерево вывода. Методы построения дерева вывода

Левосторонний и правосторонний выводы

Сентенциальная форма грамматики. Язык, заданный грамматикой

Вывод называется законченным, если на основе цепочки b, полученной в результате вывода, нельзя больше сделать ни одного шага вывода. Иначе говоря, вывод называется законченным, если цепочка b, полученная в результате вывода, пустая или содержит только терминальные символы грамматики G(T,N,P,S):

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

В рассмотренном выше примере все построенные выводы являются законченными, а, например, вывод SÞ*-4FF(из первой цепочки в примере) будет незаконченным.

Сентенциальная форма грамматики G(T,N,P,S), V=TÈN – это цепочка символов aÎV* выводимая из стартового символа грамматики S:

SÞ*a. Если цепочка aÎT* получена в результате законченного вывода, то она называется конечной сентенциальной формой или предложением языка, порождаемого данной грамматикой.

Читайте также:  За сколько построили бурдж халифа

В рассмотренном выше примере цепочки символов «-479» и «18» являются конечными сентенциальными формами грамматики целых десятичных чисел со знаком, так как существуют выводы SÞ*-479 и SÞ* 18 (примеры 1 и 2). Цепочка F8 из вывода 2 является сентенциальной формой, поскольку справедливо SÞ* F8, но она не является конечной цепочкой вывода.

Две грамматики G(T,N,P,S) и G’(T’,N’,P’,S’) называются эквивалентными, если эквивалентны заданные ими языки: L(G)=L(G’). Эквивалентные грамматики должны иметь пересекающиеся множества терминальных символов VTÇVT’¹ Æ (как правило, эти множества совпадают VT=VT’), а вот множества нетерминальных символов, правила грамматики и стартовый символ у них могут кардинально отличаться.

Левосторонний вывод – вывод, в котором на каждом шаге правило грамматики применяется всегда к крайнему левому нетерминальному символу в цепочке.

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

В цепочках вывода из того же примера, вывод 1 является левосторонним, выводы 2,3 – правосторонними.

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

Деревом вывода грамматики G=(T,N,P,S) называется дерево (граф), которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

· каждая вершина дерева обозначается символом грамматики А Î(TÈN);

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

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

· если некоторый узел дерева обозначен символом AÎN, а связанные с ним узлы – символами b1b2,…,bn; n>0, » n ≥ i > 0; bi (TÈNÈ<λ>), то в грамматике G=(T,N,P,S) существует правило A→b1,b2,…bnÎP.

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

На основе рассмотренного выше примера деревья вывода для цепочек вывода 1 и 2. Эти деревья приведены на рис.20.

Рис. 20. Примеры деревьев вывода для грамматики

целых десятичных чисел со знаком

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

Читайте также:  Как построить брюки по мюллеру

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

Дата добавления: 2014-12-27 ; Просмотров: 4124 ; Нарушение авторских прав?

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник

Дерево вывода грамматики. Алгоритм построение дерева вывода

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

· каждая вершина дерева обозначается символом грамматики;

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

· листьями дерева являются вершины, обозначенные терминальными символами грамматики или символом ε;

· если некоторый узел обозначен символом AÎN, а связанные с ним узлы – символами b1, b2,…, bn|n > 0, 0 b1b2…bn ÎP.

Алгоритм построения дерева вывода сверху вниз:

· целевой символ грамматики помещается в вершину дерева;

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

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

· для нее выбирается нужное правило и она снова раскрывается на несколько вершин следующего уровня;

· если все концевые вершины обозначены терминальными символами, процесс закончен. Иначе – возврат на шаг 3.

Алгоритм построения дерева вывода снизу вверх:

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

· далее в грамматике выбирается соответствующее правило, согласно которому крайние символы в слое дерева соединяются с новой вершиной;

· и так до тех пор, пока все вершины не окажутся соединены в корневой вершине.

Читайте также:  Игры роблокс построить тюрьму

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

Однозначность и эквивалентность грамматик.

Грамматика, в которой для любой цепочки порождаемого языка существует единственная цепочка вывода, называется однозначной.

Грамматики называют эквивалентными, если порождают один и тот же язык.

Классификация грамматик по Хомскому.

Тип 0. Произвольные грамматики (грамматики с фразовой структурой, или без ограничений)

· Это самый общий тип грамматик. Грамматики, которые относятся только к этому и не могут быть отнесены ни к какому другому типу, являются самыми сложными по структуре.

Тип 1– Контекстно-зависимые (КЗ) (неукорачивающие грамматики)

· В КЗ-грамматиках при построении предложений заданного языка один и тот же нетерминальный символ может быть заменен различными терминальными цепочками в зависимости от контекста, в котором он встречается.

· При построении компиляторов такие грамматики не применяются, поскольку языки программирования имеют более простую структуру и могут быть построены с помощью грамматик других типов.

Тип 2 – Контекстно-свободные (КС) грамматики

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

· КС-грамматики широко используются при описании синтаксических конструкций языков программирования.

Тип 3 – Автоматные (регулярные) грамматики

· К этому типу относятся два эквивалентных класса грамматик: леволинейные и праволинейные.

· Леволинейные грамматики могут иметь правила двух видов:

· Праволинейные грамматики имеют правила тоже двух видов:

· Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т.д.

Любая регулярная грамматика является также КС-грамматикой и КЗ-граматикой и произвольной грамматикой.

Самыми простыми являются грамматики типа 3, самыми сложными – типа 0.

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

Формулировка задачи разбора. Построение дерева разбора.

Работа любого транслятора основана на распознавании структуры предложений транслируемого языка.

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

Задача разработчиков состоит в построении распознавателя данного языка, который является основой синтаксического анализатора (основной части транслятора).

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

Фактически заключается в восстановлении дерева вывода для заданной сентенции или иными словами разбор – это вывод, прослеженный в обратном порядке.

Источник

Adblock
detector