Спец часть (часть 2) (3 поток) (2015) (by Кибитова) (1161602), страница 38
Текст из файла (страница 38)
Функции nullable, firstpos и lastpos определены на узлахfirstpos, lastpos и followpos. Функции nullable, firstpos и lastpos определены на узлахдерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable,дерева, а followpos - на множестве позиций. Значением всех функций, кроме nullable,является множество позиций. Функция followpos вычисляется через три остальныеявляется множество позиций. Функция followpos вычисляется через три остальныефункции. Функция firstpos(n) для каждого узла n синтаксического дерева регулярногофункции. Функция firstpos(n) для каждого узла n синтаксического дерева регулярноговыражения дает множество позиций, которые соответствуют первым символам ввыражения дает множество позиций, которые соответствуют первым символам вподцепочках, генерируемых подвыражением с вершиной в n.
Аналогично, lastpos(n)подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n)дает множество позиций, которым соответствуют последние символы в подцепочках,дает множество позиций, которым соответствуют последние символы в подцепочках,генерируемых подвыражениями с вершиной n. Для узлов n, поддеревья которых (т.е.генерируемых подвыражениями с вершиной n. Для узлов n, поддеревья которых (т.е.дерево, у которого узел n является корнем) могут породить пустое слово, определимдерево, у которого узел n является корнем) могут породить пустое слово, определимnullable(n)=true, а для остальных узлов false.nullable(n)=true, а для остальных узлов false. узел nnullable(n)firstpos(n)lastpos(n)узел nnullable(n)firstpos(n)lastpos(n)----------------------------------------------------------------------------------------------------------------листе |true|0|0листе |true|0|0--------+-------------+------------------+---------------------+-------------+------------------+-------------листiлистi||falsefalse||{i}{i}||{i}{i}--------+-------------+------------------+---------------------+-------------+------------------+-------------UU//| nullable(a) || nullable(a) |\\aa||oror||b | nullable(b) |b | nullable(b) |firstpos(a)firstpos(a)| lastpos(a)| lastpos(a)UU||firstpos(b)firstpos(b)UU| lastpos(b)| lastpos(b)--------+-------------+------------------+---------------------+-------------+------------------+-------------..//| nullable(a) | if nullable(a)| nullable(a) | if nullable(a)\\||andandthen firstpos(a)firstpos(a) |then|then lastpos(a)lastpos(a)|| then||aabb|if nullable(b)|if nullable(b)||firstpos(b) || UU lastpos(b)lastpos(b)UU firstpos(b)nullable(b) || elseelse firstpos(a)firstpos(a) |else|else lastpos(b)lastpos(b)|| nullable(b)--------+-------------+------------------+---------------------+-------------+------------------+--------------aa**||||||||||truetrue||||||firstpos(a)firstpos(a)lastpos(a)|| lastpos(a)|| {1}a{1} {2}b{2}{1}a{1} {2}b{2}Пример 2.3.
Функции firstpos и lastpos для выражения (a+b)abb#Пример 2.3. Функции firstpos и lastpos для выражения (a+b)abb#Слева от каждой вершины значение firstpos, справа - lastpos.Слева от каждой вершины значение firstpos, справа - lastpos.Заметим, что эти функции могут быть вычислены за один обход дерева. Если i - позиция,Заметим, что эти функции могут быть вычислены за один обход дерева. Если i - позиция,то followpos(i) есть множество позиций j таких, что существует некоторая строка ...cd...,то followpos(i) есть множество позиций j таких, что существует некоторая строка ...cd...,входящая в язык, описываемый РВ, такая, что i - соответствует этому вхождению c, а j входящая в язык, описываемый РВ, такая, что i - соответствует этому вхождению c, а j вхождению d. Функция followpos может быть вычислена также за один обход дерева повхождениюd.
Функцияfollowposможет бытьвычисленатакже за один обход дерева помножествузначенийfollowpos(i)множествоfirstpos(b).следующимдвумправиламследующимдвум правилам2. Пустьn - внутренний узел с операцией "*" (итерация), a - егоТогда для узелкаждойпозициивходящей в a,blastpos(a),добавляемк1.потомок.Пусть n - внутреннийс операцией"." i,(конкатенация),- его потомки.Тогда для1. Пусть n - внутренний узел с операцией "." (конкатенация), a,b - его потомки. Тогда длякаждойпозицииi,входящейвlastpos(a),добавляемкмножествузначениймножествузначенийfollowpos(i)множествоfirstpos(а).каждой позицииi, входящейв lastpos(a),добавляемк множеству значенийfollowpos(i)множествоfirstpos(b).Для примера2.3значения функции followpos приведены на рис.
2.8.followpos(i)множествоfirstpos(b).2. ПустьПустьФункциявнутреннийfollowposузелс соперациейоперацией"*"(итерация),- егопотомок.Тогдапозволиттеперьсразу Тогдапостроить2.nn--внутреннийузел"*"(итерация),a -aегопотомок.длядлякаждойпозицииi,входящейвlastpos(a),добавляемкмножествузначенийкаждой позиции i, входящейв lastpos(a),добавляемс к помощьюмножеству значенийдетерминированныйконечныйавтоматследующегоfollowpos(i)множествоfirstpos(а).followpos(i)множествоfirstpos(а).алгоритма.ПрямоепостроениеДКАпорегулярномурегулярномувыражению.ПрямоепостроениеДКАповыражению.Алгоритм2.2. ПрямоепостроениеДКАпо регулярному выражению.Будем строитьстроить множествомножествосостоянийсостоянийавтоматаавтоматаDstatesи помечатьСостоянияБудемDstatesи помечатьих.их.СостоянияДКАДКАБудем строитьмножество состоянийавтоматаDstatesи помечатьих.соответствуютмножестваммножествампозиций.позиций.НачальнымНачальнымсостояниембудетсостояниесоответствуютсостояниембудетсостояниеСостояния ДКА соответствуют множествам позиций.
Начальнымfirstpos(root),гдегде root- -вершинавершинасинтаксическогосинтаксическогодереварегулярноговыражения,firstpos(root),дереварегулярноговыражения,состоянием rootбудет состояниеfirstpos(root),где root- вершинаконечными--всевсесостояния,состояния,содержащиесодержащиепозиции,позиции,связанныес символомСначалавконечнымисвязанныес символом"#"."#".Сначаласинтаксического дерева регулярного выражения, конечными- ввсеDstatesсостояниеfirstpos(root).Dstatesимеетсяимеетсятолькотолькооднооднонепомеченноенепомеченноесостояниеfirstpos(root). состояния, содержащие позиции, связанные с символом "#".
Сначала в Dstates имеется только одно непомеченное состояниеfirstpos(root).while (в Dstates есть непомеченное состояние R){пометить R;for (каждого входного символа a, такого, что в Rимеется позиция, которой соответствует a){пусть символ a в R соответствует позициямp1,...,pi, и пусть S=U followpos(pi);iif (S не пусто и S не принадлежит Dstates)добавить непомеченное состояние S в Dstates(рис. 2.9);Функцию перехода Dtran для R и a определить какDtran(R,a)=S;}}Для примера 2.3 вначале R={1(a),2(b),3(a)}.
Последовательность шагов{p b }Sb{p a }SaSРис. 2.928 Рассмотрим теперь алгоритм построения ДКА с минимальным числомсостояний, эквивалентного данному ДКА [2].Алгоритм 2.3. Построение ДКА с минимальным числом состояний.Шаг 1. Строим начальное разбиение П множества состояний из двухгрупп: заключительные состояния Q и остальные Q-F.Шаг 2. Применяем к П следующую процедуру и получаем новое разбиениеПnew (рис. 2.12):for (каждой группы G в П){разбиваем G на подгруппы так, чтобысостояния s и t из G оказались в однойгруппе тогда и только тогда, когда для каждоговходного символа a состояния s и t имеютпереходы по a в состояния из одной и той жегруппы в П;заменяем G в Пnew на множество всех29полученных подгрупп;} GG3aaG1s1t1abG4G5G2s2at2bbG6b Рис.
2.12Шаг 3. Если Пnew=П, полагаем Пres=П и переходим к шагу 4, иначеповторяем шаг 2 с П:=Пnew.bba1b2bb3aa4abbab{2,3,4,5}{1}b5bbaababb{2,3} a{1}aaa{4}{5}b bРис. 2.13Шаг 4. Выберем по одному состоянию из каждой группы в разбиении П resв качестве представителя для этой группы. Представители будут 66 4 55 7 действийдля LR(1)грамматик.действийииипереходовпереходовдействийпереходовдлядляLR(1)LR(1)грамматик.грамматик.Основные понятияпонятияииопределенияопределенияОсновныеОсновныепонятияиОсновныепонятия и определенияопределения13. Построениеканонической системы множеств LR(1) ситуаций итаблиц действий и переходов для LR(1) грамматик. Пусть G=<N,T,P,S>G=<N,T,P,S> - контекстно-свободнаяграмматика,грамматика, гдеNN- множество- множество нетерминальныхПустьПусть G=<N,T,P,S>- -контекстно-свободнаяконтекстно-свободная грамматика,гдегде N - множество нетерминальныхнетерминальныхПустьG=<N,T,P,S>контекстно-свободнаяграмматика,гдеN- множествонетерминальныхсимволов, TT -- множествомножествотерминальныхтерминальныхсимволов,символов,PP- -множествомножествоправилвыводавыводаиSсимволов,правилсимволов, T - множество терминальных символов, P - множество правил вывода ии SS -символов,Tмножествотерминальныхсимволов,PмножествоправилвыводаикакSаксиома.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
