20619

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

Лекция

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

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

Русский

2013-07-31

93.5 KB

14 чел.

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


 

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

26440. Плечевой пояс 21 KB
  В области лопатки располагаются мышцы действующие на плечевой сустав предостная supraspinatus дельтовидная заостная infraspinatus малая круглая teres minor клювовидноплечевая coracobrachialis подлопаточная subscapularis большая круглая напрягатель капсулы сустава а также часть мышц плечевого пояса трапециевидная ромбовидная зубчатая вентральная serratus ventralis. У птиц плечевой пояс имеет трёхчленное построение: саблевидная лопатка коракоид и ключица.
26441. ПНС 20 KB
  По дорсальным корешкам через лежащие на дорсальном корешке чувствительные ганглии происходит афферентная связь со всеми органами тела. Через вентральные корешки осуществляются: прямая эфферентная соматическая связь центров с оперечно исчерченной мускулатурой; прерывистая эфферентная связь с мышечной стенкой сосудов перерыв происходит в симпатических ганглиях; прерывистая эфферентная связь с мышечной стенкой внутренностей и железами перерыв происходит в экстра или интрамуральных ганглиях.
26442. Позвоночный столб (columna vertebralis) 21.5 KB
  cervicales грудной v. Соединение: тела – межпозвоночные хрящи фиброзное кольцо и пульпозное ядро дорсальная продольная связка внутри позвоночного канала на долсальной поверхности позвонков эпистрофей крестец вентральная продольная связка последний грудной крестец; дужки: жёлтые связки; остистые отростки: межостистые связки у плотоядных мышцы надостистая связка грудной поясничный крестцовый выйная связка канатиковая и пластинчатая части; у собак – канатик у свиньи и кошки – нет у КРС вместе с надостистой связкой в...
26443. Половые железы самцов и самок 20.5 KB
  При развитии организма в мужскую сторону мезотелий половой складки в виде клеточных тяжей врастает в толщу железы формируя извитые канальцы. Передние мочеотделительные трубочки промежуточной почки также врастают в семенник и образуют прямые канальцы сеть семенника и семявыносящие канальцы.
26444. Половые органы самок 21.5 KB
  Кровоснабжение осуществляют внутренние подвздошные артерии и вены, которые имеют париетальные и висцеральные ветви. Симпатическая иннервация сосудов осуществляется из боковых рогов...
26446. Почки (ren, nephros) 20.5 KB
  Структурная единица почки – эмбриональная долька – почечка а структурнофункциональная – нефрон. Степень сращения эмбриональных долек – тип почки: множественная медведь дельфин бороздчатая КРС гладкая свинья собака лошадь.
26447. Промежуточный мозг (diencephalon) 20 KB
  Зрительная часть включает в себя зрительные тракты перекрёст зрительных нервов в нём перекрещивается 2ая пера черепных нервов. Обонятельная часть гипоталамуса включает сосцевидное тело corpus mammilarae. Эпиталамус включает эпифиз подвешенный на уздечке – ЖВС которая регулирует ростовые и обменные процессы.
26448. Роговые производные. Копыта, копытца 20.5 KB
  Имеет все 3 слоя кожи формирует глазурь. Венчик corona состоит из 3 слоёв эпидермис формирует трубчатый рог. Эпидермис формирует листочковый рог. Подошва solla состоит из 2 слоёв эпидермис формирует мягкий трубчатый рог.