20619

Синтаксическое дерево

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Синтаксическое дерево. Синтаксическое дерево представляет собой дерево синтаксического разбора сжатом виде и может быть построено на основе синтаксически управляемых определений. Грамматическое правило Семантическое правило Синтаксическое дерево узлы которого могут иметь одного родителя называется направленным ациклическим графом выражений DAG. Для ускорения поиска используется ХЭШ – функция по сигнатуре op l r Пример: Построить дерево синтаксического разбора синтаксическое дерево и DAG для выражения.

Русский

2013-07-31

93.5 KB

15 чел.

Лекция № 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]


 

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

21461. Лазерный пинцет 957 KB
  Сила с которой свет действует на окружающие объекты невелика но ее оказывается достаточно чтобы ловить и контролируемо перемещать частицы размером от 10 нм до 10 мкм. В дальнейшем Эшкин и его коллеги продемонстрировали возможности оптической ловушки на основе инфракрасного лазера захватывать удерживать и перемещать в пространстве различные биологические объекты такие как вирусные частицы одиночные бактериальные и дрожжевые клетки и органеллы в живых клетках водорослей. Как будет вести себя частица в поле после Пишейпера В случаях...
21462. Прецизионные волоконно-оптические датчики 333 KB
  100 Мрад Последовательного и параллельного типа Распределение температуры и деформации Обратное рассеяние Релея Интенсивность обратного рассеяния Релея Многомодовое Разрешающая способность 1 м Условия реализации волоконных датчиков связаны с наличием оптической комплектации: оптическое волокно в различных спектральных диапазонах. Соединительные и разделительные фильтры Многослойники дифракционные решетки; модуляторы интенсивности на основе электрооптического эффекта ниобат лития обладающий электрооптическими свойствами которые...
21463. Импульсный оптический рефлектометр 479 KB
  Введение Импульсные оптические рефлектометры OTDR Opticl Time Domin Reflectometer различных типов широко используются практически на всех этапах создания волоконнооптических систем связи: от производства волокна и оптического кабеля до строительства волоконнооптических линий связи ВОЛС и их эксплуатации. Измерять средние потери оптического волокна на катушках равномерность распределения потерь в волокне и выявлять наличие локальных дефектов при производстве волокна. Обнаруживать постепенное или внезапное ухудшение качества волокна...
21464. Анализ современного состояния техники ранней диагностики ВОЛП 706 KB
  Очевидно что длины волн используемые для передачи данных и для рефлектометрического контроля волокна в этом случае должны быть разными. В этой точке устанавливается оптический коммутатор OTU который по очереди включает волокна всех направлений в оптический путь сигналов рефлектометра RTU. Другой подход предполагает одновременное распространение сигнала рефлектометра по всем ответвляющимся волокнам. Согласно данным фирмы Fujikur по степени опасности для волокна можно выделить три диапазона значений его относительного удлинения.
21465. Двухчастотные лазерные интерферометры 1.42 MB
  Все оснащение лазерной измерительной головки заключающееся в системе программного и инструментального обеспечения измерения предназначено для линейных и угловые измерений измерения плоскостности измерения прямолинейности измерения взаимоперпендикулярности и измерения скорости перемещения. Дискрет измерения равен  при статистической обработке сигнала fd его можно уменьшить в 10 раз. Таким образом дискретность измерения интерферометра не превышает 001 мкм. Чтобы исключить ошибку связанную с температурным расширением основания на...
21466. Частота и частотные характеристики лазерного излучения 168.5 KB
  Для одной моды в том случае когда реализуется одномодовый режим можно ввести такой параметр как ширина линии излучения . Время когерентности и длина когерентности вводятся также и для многочастотного излучения. Особенность свойств когерентности излучения фемтосекундного лазера.
21467. Стандарты частоты газовые 1.6 MB
  Лазеры точнее лазерное излучение позволили создать такие источники оптического излучения с такими узкими линиями излучения которые в принципе не могли существовать в естественных условиях. С развитием лазеров появилась возможность не только управлять но и стабилизировать частоту оптического излучения. В результате этого решения появилась возможность на базе лазеров у которых частота излучения и длина волны излучения в вакууме связаны простым соотношением создавать стандарты частоты и длины волны.
21468. Одночастотный лазерный интерферометр Майкельсона. Принципы измерения расстояний и линейных перемещений 395.5 KB
  1 Упрощенная схема интерферометра Майкельсона При рассмотрении двухлучевых интерферометров следует обратить внимание на временные и пространственные фазы излучения. Поскольку основным уравнением интерферометрии является уравнение для интенсивности излучения сформированного двумя полями 1 2...
21469. Лазерный доплеровский анемометр 610.5 KB
  Движущиеся вместе с газовым потоком частицы рассматриваются как приемники световых волн от неподвижного источника и одновременно как передатчикиретрансляторы оптического излучения к неподвижному наблюдателю. Частота рассеянного излучения в точке наблюдения равна: 1 где ν – частота излучения источника; с – скорость света; u – проекция скорости частицы в направлении на точку наблюдения. Итак Доплеровская частота сигнала на выходе фотоприемника зависит от длины волны лазерного излучения скорости частиц и геометрии оптической системы....