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]


 

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

84176. ОНКОГЕНЕЗ 24.74 KB
  Ультрафиолетовое излучение играет роль в возникновении различных видов рака кожи включая плоскоклеточный рак базальноклеточный рак и злокачественную меланому. Поэтому грудные дети с респираторным дистресссиндромом подвергались лучевой терапии шеи для уменьшения размеров тимуса что привело к возникновению у большого количества этих детей папиллярного рака щитовидной железы через 15 25 лет. Торотраст радиоактивный препарат накапливается в печени и увеличивает риск возникновения нескольких типов рака печени включая ангиосаркому...
84177. УЧЕНИЕ ОБ ОПУХОЛЯХ 25.15 KB
  Признаки дисплазии. Изменения цитоплазмы: цитоплазматические нарушения при дисплазии возникают изза нарушения нормальной дифференцировки; увеличение скорости деления клеток; нарушенное созревание диспластические эпителиальные клетки сохраняют сходство с базальными стволовыми клетками несмотря на продвижение их вверх в эпителии т. Риск возникновения инвазивного рака зависит от: выраженности дисплазии; продолжительности дисплазии; локализации дисплазии. Отсутствие инвазивности: аномальная ткань при дисплазии и crcinom in situ не...
84178. МОРФОЛОГИЯ ОПУХОЛЕЙ 27.97 KB
  Паренхима собственная ткань опухоли составляющая главную ее массу и определяющая ее рост и характер. Установлено что в клетках опухоли нарушена продукция кейлонов которые в нормальных условиях регулируют митотическую активность клеток и действуют как ингибиторы клеточного деления. Это своеобразие обмена опухоли усиливает ее сходство с эмбриональной тканью в которой также преобладают явления анаэробного гликолиза. они выступают в роли маркеров опухоли; они могут привести к возникновению клинических проявлений паранеопластических...
84179. МЕТАСТАЗЫ 23.43 KB
  Метастазирование складывается из пяти этапов: проникновение опухолевых клеток в просвет кровеносного или лимфатического сосуда; перенос опухолевых клеток током крови или лимфы; остановка опухолевых клеток на новом месте; выход опухолевых в периваскулярную ткань; рост метастаза. Попадание опухолевых клеток в кровоток как полагают происходит на ранних этапах развития многих злокачественных новообразований. Метастаз возникает только тогда когда в тканях остается в живых достаточное количество опухолевых клеток.
84180. ОБЩЕЕ УЧЕНИЕ ОБ ОПУХОЛЯХ 24.77 KB
  Различают три вида роста опухоли: экспансивный; инфильтративныи; аппозиционный. Экспансивный рост опухоли обычно медленный характерен для зрелых доброкачественных опухолей. При инфильтративном росте клетки опухоли врастают в окружающие ткани и разрушают их.
84181. ЭПИТЕЛИАЛЬНЫЕ ОПУХОЛИ. ПАПИЛЛОМА 25.39 KB
  Кроме того плотность папилломе может придавать характер строения паренхимы например папилломы в которых паренхима имеет строение плоскоклеточного ороговевающего эпителия всегда по консистенции плотные. вокализуются папилломы на коже слизистых оболочках выстланных переходным или неороговевающим эпителием. Наибольшее клиническое значение имеют папилломы гортани и мочевого пузыря. Папилломы детей и подростков или ювенильные папилломы чаще всего бывают множественными папилломатоз гортани.
84182. ЭПИТЕЛИАЛЬНЫЕ ОПУХОЛИ. АДЕНОМА. КИСТЫ 26.24 KB
  КИСТЫ Аденома Кисты Аденома зрелая доброкачественная опухоль из железистого эпителия. Иногда в опухоли обнаруживаются кисты в этих случаях говорят о кисто или цистоаденоме. Макроскопически они имеют вид кисты. Различают кисты: однокамерные однополостные; многокамерные многополостные.
84183. РАК, ИЛИ КАРЦИНОМА 24.31 KB
  Раки могут развиваться из покровного и из железистого эпителия. Основная классификация раков основана на гистологической картине которую копирует паренхима опухоли. Различают следующие раки из покровного эпителия: плоскоклеточный ороговевающий рак; плоскоклеточный неороговевающий рак; базальноклеточный рак; недифференцированный рак; переходноклеточный рак.
84184. НЕЭПИТЕЛИАЛЬНЫЕ ОПУХОЛИ. ОПУХОЛИ МЕЗЕНХИАЛЬНОГО ПРОИСХОЖДЕНИЯ 25.08 KB
  ОПУХОЛИ МЕЗЕНХИАЛЬНОГО ПРОИСХОЖДЕНИЯ Зрелые доброкачественные фибробластические опухоли Незрелые злокачественные фибробластические опухоли Зрелые доброкачественные опухоли из жировой ткани Незрелые злокачественные опухоли из жировой ткани Зрелые доброкачественные фибробластические опухоли. Незрелые злокачественные фибробластические опухоли. Зрелые доброкачественные опухоли из жировой ткани.