Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия




НазваниеДерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия
Дата конвертации22.02.2013
Размер445 b.
ТипПрезентации



Дерево вывода (или дерево разбора) в КС-грамматике G = (T, N, P, S) – дерево, для которого выполнены следующие условия:

  • Дерево вывода (или дерево разбора) в КС-грамматике G = (T, N, P, S) – дерево, для которого выполнены следующие условия:

  • (1) дерево ориентировано и упорядочено;

  • (2) каждая вершина дерева помечена символом из множества N  T  {},

  • при этом корень дерева помечен символом S; листья - символами из T  {};

  • если вершина дерева помечена символом A  N, а ее непосредственные

  • потомки - символами a1, a2, ... , an , где каждое ai  T  N, то

  • A a1 a2 ... an - правило вывода в этой грамматике;

  • (4) если вершина дерева помечена символом A  N, а ее единственный непосредственный потомок помечен символом , то A  - правило вывода в этой грамматике.

  • Пример дерева вывода для цепочки a + b + a в грамматике G:

  • Дерево вывода можно строить нисходящим либо восходящим способом.



КС-грамматика G неоднозначная, если существует хотя бы одна цепочка   L(G), для которой может быть построено два или более различных деревьев вывода.

  • КС-грамматика G неоднозначная, если существует хотя бы одна цепочка   L(G), для которой может быть построено два или более различных деревьев вывода.

  • В противном случае грамматика является однозначной.

  • Если грамматика однозначная, то при любом способе построения, нисходящем или восходящем, будет получено одно и то же дерево разбора.

  • Пример неоднозначной грамматики:

  • G_if = ( { if, then, else, a, b }, { S }, P, S),

  • где P = { S if b then S else S | if b then S | a }.

  • В этой грамматике для цепочки

  • if b then if b then a else a

  • можно построить два различных дерева вывода.



Неоднозначность - это свойство грамматики, а не языка.

  • Неоднозначность - это свойство грамматики, а не языка.

  • Если грамматика используется для определения языка программирования, то она должна быть однозначной.

  • Можно преобразовать грамматику G_if, устранив неоднозначность:

  • S if b then S | T

  • T if b then T else S | a

  • Проблема определения, является ли заданная КС-грамматика однозначной, является алгоритмически неразрешимой.



  • Грамматика G_if неоднозначна, однако, это не означает, что язык L(G_if) неоднозначный.



Некоторые виды правил вывода, которые приводят к неоднозначности и некоторые способы эквивалентных преобразований неоднозначных грамматик к однозначным:

  • Некоторые виды правил вывода, которые приводят к неоднозначности и некоторые способы эквивалентных преобразований неоднозначных грамматик к однозначным:

  • 1. A AA |   A A | 

  • (док-во для ) – порождаются подцепочки n (n >= 1);

  • 2. A AA |   A A | 

  • (док-во для ) – порождаются подцепочки  ( )n (n >= 0);

  • 3. A A | A |   A A | B;

  • B B |  , B  VN

  • (док-во для ) – порождаются подцепочки n  m (n, m >= 0);

  • 4. A A | AA |   A A | В;

  • В ВA |  , B  VN

  • (док-во для ) – порождаются подцепочки δ = nm (δ)m (n,m >=0)

  • Таким приемом преобразована грамматика G_if :

  • ( ≡ if_b_then,  ≡ else, a ≡ , A ≡ S, B ≡ T).



Язык, порождаемый грамматикой неоднозначный, если он не может быть порожден никакой однозначной грамматикой.

  • Язык, порождаемый грамматикой неоднозначный, если он не может быть порожден никакой однозначной грамматикой.

  • Проблема определения, порождает ли данная КС-грамматика однозначный язык (т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой.

  • Пример неоднозначного КС-языка:

  • L = {ai bj ck | i = j или j = k} .

  • Одна из грамматик, порождающих L, такова:

  • S AB | DC ( док-во для цепочки abc )

  • A aA | 

  • B bBc | 

  • C cC | 

  • D aDb | 



Символ A  N является бесплодным в грамматике G = (T, N, P, S), если множество {   T* | A   } пусто.

  • Символ A  N является бесплодным в грамматике G = (T, N, P, S), если множество {   T* | A   } пусто.

  • Алгоритм удаления бесплодных символов:

  • Вход: КС-грамматика G  (T, N, P, S ),

  • Выход: КС-грамматика G'  (T, N', P', S ), не содержащая

  • бесплодных символов, для которой L(G) = L(G').

  • Метод:

  • Строим множества N0, N1, ...

  • 1. N0 : ; i : 1.

  • 2. Ni : Ni − 1  { A | A   P и   (  Ni − 1 )} .

  • Если Ni  Ni − 1, то i : i + 1 и переходим к шагу 2,

  • иначе N' :  Ni ; P' состоит из правил множества P,

  • содержащих только символы из Ni  T ; G' : (T, N', P', S).



S AC | Bb | 

  • S AC | Bb | 

  • A aCb

  • B bB

  • C cCc | c

  • D Aa | Bb | d

  • Шаг 0: N0 : ; i : 1.

  • Шаг 1: N1 : {S, C, D}; i : 2.

  • Шаг 2: N2 : {S, C, D, A}; i : 3.

  • Шаг 3: N3 : {S, C, D, A} = N2, т.е. искомое множество построено.

  • Удаляем все правила, содержащие нетерминал B, не вошедший в построенное множество:

  • S AC | 

  • A aCb

  • C cCc | c

  • D Aa | d



Символ x  (T  N) является недостижимым в грамматике

  • Символ x  (T  N) является недостижимым в грамматике

  • G = (T, N, P, S), если он не появляется ни в одной сентенциальной

  • форме этой грамматики.

  • Алгоритм удаления недостижимых символов:

  • Вход: КС-грамматика G  (T, N, P, S ),

  • Выход: КС-грамматика G'  (T', N', P', S ), не содержащая

  • недостижимых символов, для которой L(G) = L(G').

  • Метод:

  • Строим множества V0, V1, ...

  • 1. V0 : {}; i : 1.

  • 2. Vi : Vi − 1  { x | xT  N,   A → x  P, Vi − 1,  ,   ( )} .

  • Если Vi  Vi − 1, то i : i + 1 и переходим к шагу 2,

  • иначе N' : Vi  ; T' : Vi  ; P' состоит из правил множества P,

  • содержащих только символы из Vi ; G' : (T', N', P', S).



S AC | 

  • S AC | 

  • A aCb

  • C cCc | c

  • D Aa | d

  • Шаг 0: V0 : {S}; i : 1.

  • Шаг 1: V1 : {S, A, C, }; i : 2.

  • Шаг 2: V2 : {S, A, C, , a, b, c}; i : 3.

  • Шаг 3: V3 : {S, A, C, , a, b, c} = N3, т.е. искомое множество

  • построено

  • Удаляем все правила, содержащие символы D и d, не вошедшие в построенное множество:

  • S AC | 

  • A aCb

  • C cCc | c



Недостижимые и бесплодные символы в грамматике G = (T, N, P, S) называются бесполезными символами в этой грамматике.

  • Недостижимые и бесплодные символы в грамматике G = (T, N, P, S) называются бесполезными символами в этой грамматике.

  • КС-грамматика G называется приведенной, если в ней нет бесполезных символов.

  • Алгоритм приведения грамматики:

  • обнаруживаются и удаляются все бесплодные нетерминалы.

  • обнаруживаются и удаляются все недостижимые символы.

  • Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

  • Если в алгоритме переставить шаги 1) и 2), то не всегда результатом будет приведенная грамматика. Например, при такой перестановке шагов грамматика

  • S AB | а

  • A b

  • B BA останется неприведенной.



Вход: КС-грамматика G  (T, N, P, S ).

  • Вход: КС-грамматика G  (T, N, P, S ).

  • Выход: КС-грамматика G'  (TN'P'S' ) - неукорачивающая, L(G')  L(G).

  • Метод:

  • 1. Построить множество Х  {A  N | A  } ; N′:N .

  • 2. Построить P′, удалив из множества правил P все правила

  • с пустой правой частью.

  • 3. Если S  X, то ввести новый начальный символ S′, добавив его в N′,

  • и в множество правил P′ добавить правило S′ S | .

  • Иначе просто переименовать S в S′.

  • 4. Изменить P′ следующим образом. Каждое правило вида B → 1A12A2...n An+1, где Ai  X для  1,..., n, i  ( (N′ − X)  T )*

  • для  1,..., n + 1 (т. е. i — цепочка, не содержащая символов из X ),

  • заменить 2n правилами, соответствующими всем возможным

  • комбинациям вхождений Аi между i:

  • B → 12...n+ 1

  • B→ 12...nAn+ 1

  • ...

  • B → 12A2...nAn+ 1

  • B → 1A12A2...nAn+ 1

  • Если i   для всех i  1, ..., + 1, то получившееся на данном шаге правило

  • B →  не включать в множество P′.

  • 5. Удалить бесполезные символы и правила, их содержащие.



S BC | Ab | AB

  • S BC | Ab | AB

  • A Aa | 

  • B

  • C c

  • Шаг 1: N1 : { A, B };

  • Шаг 2: N2 : { A, B, S };.

  • S1 S | 

  • S BC | C | Ab | b | AB | A | B

  • A Aa | a

  • C c

  • Приводим грамматику:

  • S1 S | 

  • S C | Ab | b | A

  • A Aa | a

  • C c



Похожие:

Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconЭто глагол наст врем., 1 спр., 1-го лица
На могучее дерево, давняя встреча, увидеть дерево, пойти на встречу, колючие кусты, летнее облако, спрятаться в кустах, смотреть...
Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconДерево процессов Обзор главы Дерево процессов
Вводятся понятие дерева процессов и алгоритм построения дерева процессов- базовое понятие и базовый алгоритм метавычислений
Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconРастет это удивительное дерево в Африке, в Австралии, а также на тропических островах. В сезон дождей древесина Баобаба впитывает в себя воду как губка.
В засушливый период, дерево расходует накопленную воду и сбрасывает с себя всю листву. Местное население вовсю использует Баобабы...
Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconТо, на чем записывали информацию – камень, глина, дерево, папирус, пергамент, бумага то, на чем записывали информацию – камень, глина, дерево, папирус, пергамент, бумага
Появление компьютеров изменило технологию письма. С помощью специальных компьютерных программ можно набрать любой текст, внести в...
Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconКедр-дерево жизни кедр-дерево жизни

Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconЛекция 4 Задача «Минимальное остовное дерево»

Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconНе дерево, а с листочками, Не рубашка, а сшита, Не растение, а с корешком, Не человек, а с разумом

Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconХарвестерная головка может свалить дерево, очистить от сучьев и разрезать на участки необходимой длины

Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconСтолярный верстак Столярный верстак
Дерево, имеющее мягкую древесину, используемое для изготовления художественных изделий?
Дерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия iconСок гевеи индейцы называли «каучу» – слезы млечного дерева («кау» – дерево, «учу» – течь, плакать)
Сок гевеи индейцы называли «каучу» слезы млечного дерева («кау» дерево, «учу» течь, плакать)
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница