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]


 

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

65103. УТВЕРЖДЕНИЕ ИСЛАМА КАК ГОСУДАРСТВЕННОЙ РЕЛИГИИ В ЗОЛОТОЙ ОРДЕ 163.5 KB
  Стремление задобрить служителей культа всех известных монголам религий создавало у современников-монотеистов мусульман и христиан впечатление будто завоеватели принадлежат всем верам. Усманов ранние чингизиды демонстрируя свою верность шаманизму исконной вере предков...
65104. РАСПРОСТРАНЕНИЕ ИСЛАМА В ЗОЛОТОЙ ОРДЕ (НА МАТЕРИАЛАХ ПОГРЕБАЛЬНЫХ ПАМЯТНИКОВ) 2.13 MB
  Халикова также разбирает проблему идентификации исламских погребений и делает попытку выделить типично мусульманские признаки в погребальном обряде опираясь на предписанные шариатом правила и на анализ археологических материалов...
65105. К ВОПРОСУ О РОЛИ СУФИЗМА В ИСЛАМИЗАЦИИ ЗОЛОТОЙ ОРДЫ 71 KB
  Однако проникновение ислама в Золотую Орду началось намного раньше ещё с момента её образования поэтому связывать исламизацию лишь с волевыми решениями ханской администрации было бы ошибочно.
65106. ГОРОДИЩЕ АК-САРАЙ 43.5 KB
  На восток охранная зона памятника включающая городище и мавзолеи протянулась на расстояние около 2250 метров от берега р. В природном отношении территория занимаемая городищем и комплексом мавзолеев представляет собой всхолмлённую слабозадернованную песчаную полупустыню.
65107. ИСЛАМ В ЗОЛОТОЙ ОРДЕ (ИСТОРИКО-АРХЕОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ) 4.28 MB
  С течением времени уменьшается число как богатых так и бедных погребений с признаками всадничества. Однако при соблюдении ряда основных признаков мусульманской погребальной обрядности по остальным признакам данные захоронения часто мало...
65109. Кыпчаки и Кимакский каганат. Йемеки 47 KB
  Легендарные сведения подтверждают указанное направление движения кыпчаков: согласно легенде о предке уйгуров Огузкагане последний послал кыпчаков чтобы они поселились между страной итбараков предположительно киргизов. Повидимому более раннее или параллельное название кыпчаков сиры.
65110. КНЯЗЬЯ КАЗАНСКИЕ, КНЯЗЬЯ БОЛГАРСКИЕ 103 KB
  Осенью этого года великий князь суздальский и нижегородский Дмитрий Константинович послал рать на Болгарского князя Асана вариант написания: Блъгарского князя Осана 4. высказана следующим образом: на Болгарского князя Асана еже ныне глаголются Казанцы выделено нами.
65111. Модель Татарстана: «За» И «Против» 134.5 KB
  Обычно Модель Татарстана противопоставляется опыту других регионов суверенизация которых была сопряжена с острыми кризисами Абхазия Чеченская республика Ичкерия и др. Но сам опыт Татарстана при этом рассматривается весьма однобоко в основном с точки зрения мирного характера...