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]


 

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

39377. ОБЩАЯ ХАРАКТЕРИСТИКА РЫНОЧНОГО ХОЗЯЙСТВА 489 KB
  Общественное разделение труда предполагает специализацию, обособление отдельных видов конкретного труда (труда в особой целесообразной форме - например, труд пекаря, гончара). Развитие общественного разделения труда выражается в увеличении числа профессий и специальностей
39378. Процесуальний порядок оскарження постанови про порушення кримінальної справи 539.75 KB
  Кожна кримінальна справа може бути порушена лише за на- явності приводу і достатньої підстави за відсутності обставиш що виключають провадження у справі.
39379. Структурно-функциональная теория социальных систем Т. Парсонса 15.3 KB
  Из бесчисленного множества человеческих действий и взаимодействий (интеракций), соответствующих определенным социальным ролям, складывается социальная система. Парсонс сформулировал положение о трехкомпонентной структуре социальной системы...
39380. Расчет привода 518 KB
  Выбор двигателя. От типа двигателя его мощности частоты вращения и прочего зависят конструктивные и эксплуатационные характеристики рабочей машины и ее привода. Мощность двигателя зависит от требуемой мощности рабочей машины а его частота вращения от частоты вращения приводного вала рабочей машины.3 Определяем требуемую мощность двигателя по формуле 3 2.
39381. Г. Зиммель о принципе понимания и социологии конфликтов 15.78 KB
  Принцип понимания занимает особое место в социологии Зиммеля. Он позволяет разрушить барьер бесстрастного объективизма-рационализма, отделяющий познающего субъекта от познаваемого объекта
39382. ПРОБЛЕМА ЭКОНОМИЧЕСКОЙ ЗАВИСИМОСТИ КАНАДЫ ОТ США 93 KB
  Библиографический фон исследования включает в себя достаточно широкий круг отечественных и иностранных исследовательско-аналитических работ, посвященных экономической зависимости Канады от США, выражающейся в особой чувствительности к изменению экономической и политической ситуации в США
39383. Процент, прибыль и рента 70 KB
  Сущность процента. Механизм процента. Выбор вариантов инвестирования. Прибыль и рентабельность. Показатели прибыльности. Ценные бумаги. Дивиденд. Курс акций. Рента. Цена земли.
39384. Расчет привода электрической лебедки 283.5 KB
  Привод к электрической лебедке предназначен для передачи необходимой тяговой силы от двигателя к барабану. Рассмотренный нами привод обеспечивает надёжную, долговечную, производительную работу, что подтверждают расчёты на прочность и долговечность.
39385. Учет финансовых вложений как объект внеоборотных активов и отражение их в бухгалтерской отчетности 195.5 KB
  Изучение теоретической и нормативно-правовой базы бухгалтерского учета финансовых вложений, их оценки и выбытия, выявление особенностей учета финансовых вложений, изучение методики составления бухгалтерской отчетности по учету финансовых вложений, проведения инвентаризации.