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]


 

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

1543. Затраты на обслуживание и ремонта плат форм-фактора ATX 209 KB
  Характеристика организации и анализ технико-экономических показателей деятельности предприятия. Расчет основных показателей деятельности предприятия. Краткое описание технологии обслуживания и ремонта материнской платы. Расчет материальных затрат и заработной платы.
1544. Экономические концепции. Предшественники: меркантилисты и физиократы 104 KB
  Предшественники: меркантилисты и физиократы. Экономическое учение А. Смита (1723 – 1790). К. Маркс как исследователь. Основы маржинализма. Дж. М. Кейнс. Возникновение кейнсианства. Монетаристы и неоклассики.
1545. Строительство вертикальных стволов 184.5 KB
  Определение нагрузок на крепь вертикального ствола. Расчетное сопротивление горных пород сжатию. Коэффициент влияния угла залегания породы. Выбор взрывчатых материалов. Расчет количества воздуха по наибольшей численности людей. Расход воздуха по минимальной скорости движения в призабойном пространстве. Фазы проведения ствола при совмещенной технологической схеме.
1546. Безопасность и экологичность строительного проекта 56.9 KB
  Мероприятия по охране окружающей среды при строительстве жилого дома. Мероприятия по исключению чрезвычайных ситуаций при возведении 9-ти этажного жилого дома. Возможные причины аварий, чрезвычайных ситуаций при строительстве объекта. Мероприятия по исключению чрезвычайных ситуаций при строительстве 9-ти этажного жилого дома.
1547. Моделирование программного обеспечения 100.15 KB
  Создание контекстной диаграммы (используя IDEF0). Выполнение процесса декомпозиции модели по результатам разработки контекстной диаграммы. Создание диаграммы вариантов использования и описание потоков. Построение диаграммы вариантов использования.
1548. Русская литература ХІХ века. Известные личности 227.16 KB
  Южные поэмы А.С. Пушкина. Драматургия А.П. Чехова. М.Ю. Лермонтов. Лирика. Новаторство драматургии Н.А. Островского. Новаторство прозы А.П. Чехова. Поэзия Ф.И. Тютчева. Л.Н. Толстой. Война и мир. Сюжет и образы. М.Ю. Лермонтов. Роман Герой нашего времени. Сюжет и композиция.
1549. Фінанси та фінансова система України 88.09 KB
  Сутність, особливості функціонування та інструменти грошового ринку. Попит на гроші: сутність, цілі та мотиви попиту на гроші. Чинники, що впливають на попит на гроші. Крива попиту на гроші. Поняття та призначення валютних систем. Елементи національної валютної системи. Розвиток валютної системи в Україні. Небанківські фінансово-кредитні установи, їх види, та особливості функціонування в Україні.
1550. Установка числа корней полинома (с учетом их кратности) 101.35 KB
  Бесконечная и конечная многоугольные области. Геометрические условия, определяющие распределение корней. Алгебраические соотношения, определяющие распределение корней.
1551. Психология и педагогика высшей школы 195 KB
  Психология и педагогика высшей школы: предмет, объект, задачи, категории. Связь с другими науками. Основные направления реформирования образования 21 века и проблемы современной высшей школы. Образовательные уровни и образовательно-квалификационные уровни. Уровни аккредитации и типы вузов. Развитие студенческой группы, характеристика студенческого коллектива. Межличностные отношения в студенческой группе.