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]


 

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

72438. Функциональные асимметрии больших полушарий мозга, как задатки специальных способностей 427.5 KB
  Природа задатков скрыта во врожденных конструктивных и функциональных особенностях головного мозга человека. Стараясь объяснить отличие между высшей нервной деятельностью человека и животного Павлов подчеркивал что в психике человека имеет место чрезвычайное приложение речь.
72440. СТАНДАРТЫ ВРАЧЕБНОЙ ПОМОЩИ ПРИ КАТАСТРОФАХ 253 KB
  В медицине катастроф необходима стандартизация действий врача, учитывая экстремальность ситуаций, массовый характер и однотипность поражений. Врач скорой помощи, первым прибывший на место катастрофы принимает руководство на себя. Основоположник сортировки Н.Н. Пирогов говорил, что при наличии большого количества...
72441. Лекции по деталям машин 63 KB
  Чтобы не потеряться в океане учебной и научной информации студенту необходим хотя бы простенький компас, которым, надеюсь, послужит предлагаемый конспект лекций. Именно для этого он и создавался. Учитывая же скромный объём, конспект является, образно говоря, путеводителем по незнакомой стране, и не может заменить само путешествие.
72442. История Курского края 1.11 MB
  Краеведение принадлежит к комплексным наукам. В самом термине «краеведение» заключено его определение. Оно изучает природу, историю, хозяйство, население края, его культуру, быт, то есть данная наука близка истории и географии, археологии и искусствоведению, этнографии и другим наукам.
72443. КОНСПЕКТ ЛЕКЦИЙ: ИСТОРИЯ 1.76 MB
  История в том числе история Отечества история России ставит своей целью показать место и роль её народов в мировом развитии помогает нам постигнуть свое особое место в длинной череде исторических поколений. К работе над курсом было привлечено еще одно дополнительное пособие для старшеклассников...
72445. История менеджмента 602.5 KB
  Управление — понятие широкое. Известно управление машинами, химическими или другими процессами. Оно основано на знании законов механики, физики, химии. Но в обществе происходит управление не только вещами, но и людьми, коллективами людей в процессе производства ими материальных благ.