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]


 

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

32798. Философия Платона, Теория познания Платона 14.35 KB
  Наиболее известные диалоги Платона: Государство Пир диалоги Софист и Федр посвящены проблеме души Тимей вопросу возникновения Космоса Протагор проблеме добродетели. Человек по Платону единство души и тела которые в то же время противоположны. Смертное тело только тюрьма для души оно источник страданий причина всех зол; душа гибнет если она слишком срослась с телом в процессе удовлетворения своих страстей. Стимулом к совершенствованию души является любовь к прекрасному.
32799. Философия эпохи эллинизма, ее основные направления 14.57 KB
  На развитие античной философии значительное влияние оказал распад империи А. Неоплатонизм получил распространение в период когда античный способ философствования уступал место философии основанной на христианской догматике. Это последняя попытка решить задачу создания целостного философского учения в рамках дохристианской философии. Главное отличие от философии Платона заключается в том что мир идей Платона это неподвижный безличный образец мира а в неоплатонизме появляется активное мыслящее начало Ум.
32800. Вклад Аристотеля в развитие мировой философской культуры (учение о материи и форме). Учение о душе 13.19 KB
  Аристотель 384 322 гг. Аристотель считается величайшим энциклопедистом древности и систематизатором всех философских и научных знаний накопленных до него в области логики физики биологии психологии этики экономии искусствознания и др. Высоко оценивая Платона Аристотель подверг его идеалистическое учение серьезной критике Платон мне друг но истина дороже. Аристотель формулирует свое представление о бытии.
32801. Условия формирования западноевропейской философии в Средние века. Роль христианства в развитии культуры 15.27 KB
  Условия формирования западноевропейской философии в Средние века. Этапы развития и характерные черты средневековой философии. В развитии философии Средних веков можно выделить несколько основных этапов: 1 апологетика II IV вв. В этот период не было создано философских систем но был намечен круг вопросов ставших центральными в средневековой философии: о Боге и соотношении Бога и мира о сотворении мира и структуре мироздания о сущности человека и его месте в мире; 2 патристика V IX вв.
32802. Философия Августина Аврелия (Блаженного). И Фомы Аквинского 14.95 KB
  Учение о Боге и мире. Бог рассматривается им как начало всего сущего как единственная причина возникновения вещей. Бог вечен и неизменен. Мир созданных богом вещей изменчив и пребывает во времени.
32803. Особенности философии Возрождения. Её связь с наукой и искусством. Учения о природе и познании 18.84 KB
  Особенности философии Возрождения. Эпоха Возрождения Ренессанса переходный период от Средних веков к Новому времени XV [в Италии с XIV] XVI вв. Возрождение художественноэстетическая эпоха провозгласившая что высшее призвание человека в мире быть творцом и созидателем Этапы развития и характерные черты философии Возрождения. В философии эпохи Возрождения можно выделить 3 этапа: гуманистический сер.
32804. Эмпиризм и сенсуализм в философии нового времени 16.32 KB
  Локк подчеркивает особую роль органов чувств в процессе познания.Бэкон сделал научное познание в центре его внимания вопросы о целях и методах научного познания.Однако он утверждает что на пути познания имеется множество заблуждений препятствующих получению достоверного знания. Бэкон выделяет 4 вида идолов познания: 1 идолы рода являются следствием ограниченности человеческого ума несовершенством органов чувств; 2 идолы пещеры обусловлены индивидуальными особенностями человека: каждый человек имеет свой внутренний субъективный мир...
32805. Рационализм в философии нового времени 17.35 KB
  Эти две субстанции пересекаются и активно взаимодействуют однако их взаимосвязь является лишь механической. В человеке материальная и духовная субстанции проявляются как тело и душа. В понятии единой субстанции т. Спиноза называет следующие свойства единой субстанции: независимое ни от чего существование; вечность; бесконечность; является внутренней причиной самой себя и всего сущего.
32806. Субъективный идеализм в философии Н.В. (Дж.Беркли, Д.Юм) 14.1 KB
  Джордж Беркли 1685 1753 гг. Беркли внес весомый вклад в теорию познания четко поставив вопрос о соотношении объективного и субъективного в ощущениях об объективности причинности и о видах существования. Беркли утверждал что мир не существует независимо от человека а представляет собой комплекс ощущений и восприятий. Философия Беркли основывается на следующих основных принципах: 1 существовать значит быть воспринимаемым; 2 я не в состоянии помыслить ощущаемые вещи или предмет независимо от их ощущения и восприятия; 3 мы никогда не...