Дерево вывода лист дерева

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

1. целевой символ грамматики помещается в вершину дерева;
2. в грамматике выбирается необходимое правило и целевой символ раскрывается на несколько символов первого уровня;
3. среди всех концевых вершин дерева выбирается крайняя (левая для левостороннего вывода, правая – для правостороннего вывода) вершина, обозначенная нетерминальным символом;
4. для неё выбирается нужное правило и она снова раскрывается на несколько вершин следующего уровня;
5. если все концевые вершины обозначены терминальными символами, процесс закончен. Иначе – возврат на шаг 3.

При построении дерева снизу вверх процесс построения начинается с листьев, в качестве которых выбираются терминальные символы цепочки языка. Они образуют последний уровень дерева; далее в грамматике выбирается соответствующее правило, согласно которому один или несколько символов цепочки могут быть «свёрнуты» в нетерминальный символ – (при левостороннем или правостороннем выводе это крайние символы в слое дерева) они соединяются с новой вершиной; и так до тех пор, пока все вершины не окажутся соединены в корневой вершине. Поскольку компилятор читает программу сверху вниз и слева направо, для построения дерева сверху вниз обычно используется левосторонний вывод. Пример: Рассмотрим деревья вывода для сентенциальных форм (1) и (2). Подробно рассмотрим построение для формы (1). Дерево строится сверху вниз. Номера шагов обозначены цифрами. Процесс начинается с корня (он помечен целевым символом), далее при выводе применялось правило S  –T (первый шаг), следовательно, в следующем уровне будут две вершины («–» и «Т»). Вершина «–» помечена терминальным символом, значит, это лист. Вершина «Т» представляет собой нетерминал и вновь раскрывается по правилу T  TF согласно ранее построенному выводу (второй шаг). Поскольку вывод левосторонний, каждый раз в цепочке вывода очередное правило применяется к крайнему левому нетерминалу. Поэтому следующим заменяется нетерминал Т, как самый левый в цепочке вывода (она в настоящий момент имеет вид –TF), и это третий шаг… Процесс продолжается до тех пор, пока все вершины не получат в качестве меток терминальные символы. Для формы (2) построение отличается тем, что в качестве начального символа вместо целевого S взят нетерминал Т, а вывод использован правосторонний. Построение дерева снизу вверх является более неоднозначным процессом. Рассмотрим его для вывода формы (4). При этом будем двигаться по цепочке вывода от её конца к началу. Сначала строим листья «2», «6» и «3». Последним шагом было правило F  2. Оно позволяет заменить терминальный символ ‘2’ на ‘F’ (схема 1). Следующие правила T  F и F  6 (схема 2). Далее по правилу T  TF нетерминалы T и F сворачиваются в T (схема 3). И наконец после применения правил F  3, T  TF и S  T получается итоговое дерево (схема 4).

1. Контрольные вопросы

1. За сколько шагов выводима цепочка  из цепочки , если в правилах грамматики есть правило    ?
2. В чём заключается различие понятий выводимости и непосредственной выводимости?
3. Какая грамматика является однозначной?
4. Какой вывод называется законченным?
5. Что такое сентенциальная форма грамматики?
6. В чём состоит различие левостороннего и правостороннего выводов для регулярной грамматики?
7. Чем отличается дерево вывода от самого вывода?
8. Каким символом помечают корень дерева вывода и какими – его листья?

1. Распознаватели. Задача разбора
   1. Общая схема распознавателя

В числе прочих задач компилятор должен определить принадлежность некоторого текста к конкретному языку. В отношении исходной программы компилятор выступает в роли распознавателя, а человек, создавший программу – в роли генератора цепочек этого языка. Распознаватель – это специальный алгоритм, позволяющий для некоторой цепочки символов определить, принадлежит ли она заданному языку. Это один из способов задания языка. Распознаватель входит в состав компилятора и является частью программного обеспечения компьютера. Условная схема распознавателя имеет следующий вид: Основные компоненты распознавателя:

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

Алфавит распознавателя конечен; он включает в себя все допустимые символы входных цепочек, а также некоторый дополнительный алфавит символов, которые могут обрабатываться УУ и храниться в рабочей памяти распознавателя. В процессе своей работы распознаватель может выполнять некоторые элементарные операции, такие как чтение входного символа, сдвиг головки, доступ к рабочей памяти для чтения или записи информации, изменение состояния УУ. Работа распознавателя состоит из последовательности шагов, или тактов. То, каким должен быть этот такт, определяется текущим входным символом, состоянием УУ и символом, извлеченным из памяти. Итак, Такт состоит из следующих моментов:

• входная головка распознавателя сдвигается на одну ячейку вправо, влево или остается на месте;
• в память помещается некоторая информация;
• изменяется состояние УУ.

В процессе работы распознавателя происходит смена конфигураций. Конфигурация распознавателя (мгновенное описание) определяется следующими параметрами:

• состояние УУ;
• содержимое входной ленты и положение считывающей головки в ней;
• содержимое внешней памяти.

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

Источник

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

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

то в грамматике имеется правило X®Y₁Y₂Y₃.

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

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

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

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

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

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

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

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

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

1. Можно ли построить дерево вывода для грамматики G из упражнения 1 п.п.4.5.? Поясните.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник

Печать листьев бинарного дерева

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

Код написан, но все тесты программа не проходит.

Кому не очень лень, посмотрите, пожалуйста, и скажите, где криво или подскажите, на каких примерно тестах валится программа.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include using namespace std; struct node //узел { int val; node *left, *right; node(): val(0) {}; }; node *addNode (int val) { node *nnode = new node[sizeof(node)]; nnode->left = NULL; nnode->right = NULL; nnode->val = val; return nnode; } node *addTree (node *root, int val) { if (root == NULL) root = addNode (val); if (val > root->val) if (root->right == NULL) root->right = addNode (val); else addTree (root->right, val); if (val  root->val) if (root->left == NULL) root->left = addNode (val); else addTree (root->left, val); return root; } void printLeafs (node *root) { if (root != NULL) { printLeafs (root->left); if (root->left == NULL && root->right == NULL) cout  ->val  ; printLeafs (root->right); } } int main() { freopen ("input.txt", "r", stdin); freopen ("output.txt", "w", stdout); int n; cin >> n; node *tree = new node; tree = NULL; if (n != 0) tree = addNode (n); while (n != 0) { addTree (tree, n); cin >> n; } printLeafs (tree); return 0; }

Функция вывода листьев бинарного дерева
Написал функцию вывода всего что есть в дереве. помогите переделать ее так чтобы она выводила.

Вывод списка всех листьев бинарного дерева поиска
Нужно реализовать бинарное дерево поиска и вывести все его вершины, не имеющие потомков. Само.

Вывести разность значений всех листьев бинарного дерева
Дан указатель P1 на корень непустого дерева. Вывести разность значений всех листьев данного.

Запись бинарного дерева в файл и восстановление из него этого дерева
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя — 1 указатель на.

Источник