20619

Синтаксическое дерево

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Синтаксическое дерево. Синтаксическое дерево представляет собой дерево синтаксического разбора сжатом виде и может быть построено на основе синтаксически управляемых определений. Грамматическое правило Семантическое правило Синтаксическое дерево узлы которого могут иметь одного родителя называется направленным ациклическим графом выражений DAG. Для ускорения поиска используется ХЭШ – функция по сигнатуре op l r Пример: Построить дерево синтаксического разбора синтаксическое дерево и DAG для выражения.

Русский

2013-07-31

93.5 KB

17 чел.

Лекция № 6.

Синтаксическое дерево.

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

Используется в качестве промежуточного представления после этапа синтаксического анализа.

Пример:

Пусть имеется выражение вида  2+3*4.

                                                                    

Каждый узел в синтаксическом дереве реализуется как запись с несколькими полями:

  •  Одно поле идентифицирует операцию
  •  Остальные поля содержат указатели на узлы операндов

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

Для описания конструирования деревьев могут быть использованы функции следующего вида:

  •  mknode(op, left, right) – содержит узел операции c меткой op  и указателями  left, right.
  •  mkleaf(id, entry) – создает узел идентификатора с меткой id и полем entry содержащим указатель на запись в таблице символов для этого идентификатора.
  •  mkleaf(num, val) – создает узел числа num c полем val содержащим значение числа.

Каждая из функций возвращает указатель на вновь созданный узел.

Пример:

Пусть имеется выражение a-4+b. Последовательность вызовов функций для построения дерева.

p1:=mkleaf(а,pa)

p2:=mkleaf(num,4)

p3:=mkleaf(-,p1 ,p2)

p4:=mknode(c, pc)

p5:=mknode(+, p3, p4)

Синтаксически управляемое определение для построения синтаксических деревьев.

Грамматическое правило

Семантическое правило

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

Пример:

а+(b-c)+a+d*(b-c)

Пример:

i:= i+3

DAG для этого выражения будет выглядеть следующим образом.

                          

Алгоритм метода номера значения построения узла DAGа.

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

Если узел описывается полями с метками op, l, r ( opоперация, l и  r левые и правые потомки этого узла), тогда список <op, l ,r> называется сигнатурой узла.

Метод состоит в поиске в массиве уже существующего узла сигнатуры <op, l ,r> и возвращении его номера, или если он отсутствует, создании нового узла.

Для ускорения поиска используется ХЭШ – функция по сигнатуре op, l ,r

Пример:

Построить дерево синтаксического разбора, синтаксическое дерево и DAG для выражения.

(a+b)*[(b-a*c)+b*b]


 

А также другие работы, которые могут Вас заинтересовать

66961. Воспитательный час «Учимся дружить» 36.5 KB
  Ребята выучим наш девиз. Ребята хором повторяют девиз Давайте дружно будем жить И дружбой нашей дорожить И никогда не ссориться Тогда дела все спорятся IΙΙ. Подготовленные ребята инсценируют стихотворения Друзья. Правильно ли поступили ребята Почему Посмотрите ещё одну историю.
66962. Поговоримо про дружбу 404.5 KB
  Наприклад: Правдивий друг любить за всякого часу в недолі ж він робиться братом Є товариші на розбиття та є й приятель більше від брата прив’язаний. Не смійся коли хтось говорить за винятком якщо хтось жартує Завдання № 1 На початку уроку звучить запис пісні Справжній друг муз.
66964. Заняття з елементами СПТ «Чи знаєш ти про вплив тютюнового диму?» 52 KB
  Йдеться про проблему куріння. Під час куріння кожен три чотири рази затягувався випускаючи дим через ніздрі. куріння проникло до Іспанії Португалії Франції Англії Голландії. Проте Холтер Ролі фаворит двора королеви Єлизавети популяризував куріння тютюну.
66965. Прощавай наш дитсадок! 77.5 KB
  Ведуча: Шановні мами і тата, дорогі бабусі і дідусі! Сьогодні ми всі трохи сумуємо, тому що настав час розставання. Незабаром для наших випускників продзвенить перший шкільний дзвінок. Позаду залишилися дні, наповнені цікавими подорожами у світ непізнаного, нерозгаданого...
66967. Свято 1 Дзвоника 61.5 KB
  І сьогодні радісний і світлий Він відкриє двері знань для нас. Увага Сьогодні 1 вересня 2010 року починається новий відлік часу для наших первачків В1. Зустрічайте наші першокласники Таке велике сьогодні свято Радіють мами бабусі й тата Усмішки всюди і гарні квіти Сьогодні в школу говорять діти.
66968. ТОРЖЕСТВЕННАЯ ЛИНЕЙКА, ПОСВЯЩЕННАЯ ПРАЗДНИКУ ПЕРВОГО ЗВОНОКА 51.5 KB
  Школа, здравствуй! Учеба, здравствуй! Идем за знаньями в поход. Сегодня праздник! Школьный праздник! Встречаем мы учебный год! ВЕДУЩИЙ 1. Настал поистине чудесный день, Которого мы долго ждали, Ведь в школе нашей – юбилей Поэтому мы здесь собрались!
66969. Spring. Easter 51.5 KB
  Teaching goals: engagement into intercultural communication acquiring knowledge about cultural traditions of other peoples mastering basic skills in listening, speaking Developing goals: development of speaking, intellectual and cognitive abilities...