Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов (1082244), страница 9
Текст из файла (страница 9)
При автоматизированном преобразовании грамматик проще применитьграфическую модификацию этого метода. С этой целью каждому нетерминальному символуи каждой правой части правил из множества Р2 поставлена в соответствие вершина графа.Из вершины с меткой U в вершину с меткой V направлено ребро, если в грамматикесуществует правило U → V.aFbaAaSb bFcSABbcFВ эквивалентную грамматику будут включены правила вида А → w, A∈VN; w∈(VT ∪VN)*, если из вершины с меткой А существует путь в вершину с меткой w.S → aFb | aSb | аА;А → аА | aSb | aFb;В → аА | aSb | aFb;F → bc | bFc.Получено то же множество правил Р, что и аналитическим методом.4.5.2. Построение неукорачивающей грамматикиГрамматика, не содержащая правил с пустой правой частью, называетсянеукорачивающей грамматикой.В грамматике с правилами вида А→ε длина выводимой цепочки при переходе от k-гошага к (k+1)-му уменьшается.
Поэтому грамматики с правилами вида А→ε называютсяукорачивающими. Восходящий синтаксический разбор в укорачивающих грамматикахсложнее по сравнению с разбором в неукорачивающих грамматиках, т.к. при редукциинеобходимо отыскать такой фрагмент входной цепочки, в которую можно вставить пустойсимвол.Покажем, что для произвольной КС-грамматики, порождающей язык без пустойцепочки, можно построить эквивалентную неукорачивающую КС-грамматику.Построим множество всех нетерминальных символов грамматики G=(VT, VN, P, S), изкоторых выводится пустая цепочка, выделив следующие множества:W1= {A | A→ε ∈ P},Wn+1 = Wn ∪{B | B→ϕ ∈ P, ϕ ∈ W*n }.Затем найдем множество правил эквивалентной грамматики в два этапа:а) удалив из множества P исходной грамматики правила с пустой правой частью P1' = P\{A→ε | A→ε ∈ P};б) получив новые правила A→ϕ' после удаления из каждого правила исходнойграмматики A→ϕ ∈ P те нетерминалы, которые вошли в множество Wn по правилу:P1" = { A→ϕ' | A→ϕ ∈ P'; ϕ =ϕ1Bϕ2 | B∈Wn; ϕ'=ϕ1Bϕ2}.Повторив п.б) для каждого нетерминала, принадлежащего множеству Wn, получимэквивалентную грамматику G = (VT, VN, Pэ, S).Пример.
Пусть задана грамматика G со следующими правилами вывода: S → АbА | сАb |Bb; А → аАb | ε; В→АА|а. Необходимо:1) построить множество нетерминалов, из которых выводится ε;2) построить неукорачивающую грамматику, эквивалентную исходной.Для того чтобы построить множество всех нетерминалов грамматики, из которыхвыводится пустая цепочка, выделим следующие множества:W1 = {А | А → ε ∈ P};Wm+1 = Wm ∪ {В | В → ϕ ∈ Р, ϕ ∈ W*m}.Так как мы имеем правило А → ε ∈ Р, то можно построить множество W1 = {A},включающее нетерминал А.Построим множество W2. С нетерминалом А связан нетерминал В, т.е. существуетправило В → АА и А ∈ W1.
Следовательно, W2={A,B}.W3 = W2, т. к. множество W3={В|В → ϕ ∈ Р, ϕ ∈ W*m } является пустым.Исключив правило, содержащее пустую цепочку в правой части, получимнеукорачивающую грамматику G1 следующего вида:S → АbА | сАb | Bb | bA | Ab | cb | b;A → aAb | ab;В → АА | A | a.4.5.3. Построение грамматики с продуктивными нетерминаламиНетерминальный символ А называется непродуктивным (непроизводящим), если он непорождает ни одной терминальной цепочки, т.е.
не существует вывода А →* х, где х∈V*T.Поэтому представляет интерес удаление из грамматикивсех непродуктивныхнетерминальных символов. Рассмотрим, как для произвольной КС-грамматики можнопостроить эквивалентную КС-грамматику, все нетерминальные символы которойпродуктивны. С этой целью выделяется множество W1={A | A → ϕ ∈ P, ϕ ∈ V*T}.
Затемстроится множество W1, W2, . . . , Wn+1 по следующим правилам:Wn+1 = Wn ∪{BB → x ∈ P, x ∈ (VT ∪ Wn)*}.Пусть задана грамматика G со следующими правилами вывода: S → SA | BSb | bAb; A →aSa | bb; B → bBb | BaA. Построим множество продуктивных нетерминалов:W1 = {A}, т.к. в множестве P есть правило A → bb;W2 = {A, S}, т.к. имеется правило S → bAb и A ∈ W1;W3 = W2.Все символы множества VN\Wn являются непродуктивными, не используются в выводеникакой терминальной цепочки и их можно удалить из грамматики вместе со всемиправилами, в которые они входят.
Грамматика G1, эквивалентная исходной грамматике,будет включать следующее множество правил:S → SA | bAb; A → aSa | bb.В грамматике G1 все нетерминалы продуктивны.4.5.4. Построение грамматики, аксиома которой зависит от всех нетерминаловСуществует еще один тип нетерминальных символов, которые можно удалять изграмматики вместе с правилами, в которые они входят. Например, в грамматике G, заданноймножеством правил P: S → aSb | ba; A → aAa | bba, нетерминал А не участвует ни в какомвыводе, т.к. из аксиомы нельзя вывести цепочку, содержащую этот нетерминал.
Поэтому иззаданной грамматики можно удалить нетерминал А. Рассмотрим, как для произвольной КСграмматики можно построить эквивалентную КС-грамматику, аксиома которой зависит отвсех нетерминальных символов.Для этого построим множество нетерминалов, от которых зависит аксиома. С этойцелью выделим множества W1, W2, . . . , Wn+1 по следующим правилам:W1 = {S},Wn+1 = Wn ∪{B | A → xBy ∈ P, A ∈ Wn}.Нетерминал B∈Wn тогда и только тогда, когда аксиома S зависит от B.
Все нетерминалы,не содержащиеся в Wn, можно удалить из грамматики вместе с правилами, в которые онивходят.Пример. Пусть дана КС-грамматика G:S → abS | ASa | ab; A → abAa | ab; B → bAab | bB.Найдем нетерминалы, от которых зависит аксиома:W1 = {S},W2 = {S, A}, т.к. имеется правило S → Asa и S ∈ W1;W3 = W2.Эквивалентная грамматика G1, аксиома которой зависит от всех нетерминальныхсимволов:S → abS | ASa | ab; A → abAa | ab.4.5.5. Удаление правил с терминальной правой частьюПусть в грамматике G имеется с терминальной правой частью A→β, где β ∈ V*T.
Тогдалюбой вывод с использованием этого правила имеет вид: S →* xAy → xβy. Здесьнетерминал А в сентенциальной форме xAy появился на предыдущем шаге вывода B → uAv.Если в это правило вместо А подставить β, получим правило B → uβv. Тогда длина выводанекоторой цепочки сократится на один шаг. Следовательно, для того чтобы удалитьтерминальное правило грамматики A→β, необходимо учесть следующие правила:а) если для нетерминала А больше нет правил, тогда во всех правых частях А заменяетсяна β;б) если для нетерминала А есть другие правила, тогда добавляются новые правила, вкоторых А заменяется на β.Пример.
Пусть дана КС-грамматика G:S → aSb | bAa | B; A → ABa | b | ε; B → ab | ba.Удалим правила для нетерминала В. Тогда эквивалентная грамматика G1 будет включатьследующие правила:S → aSb | bAa | ab | ba;A → Aaba | Abaa| b | ε.4.5.6. Построение эквивалентной праворекурсивной КС-грамматикиНекоторые специальные методы грамматического разбора неприменимы клеворекурсивным или праворекурсивным грамматикам, поэтому рассмотрим устранениелевой или правой рекурсии. В общем случае избавиться от рекурсии в правилах грамматикиневозможно, т.к. бесконечные языки порождаются грамматиками с конечным числом правилтолько благодаря рекурсии.
Поэтому можно говорить лишь о преобразовании одного видарекурсии в другой. Рассмотрим, как для любой леворекурсивной КС-грамматики построитьэквивалентную праворекурсивную КС-грамматику.Пусть нетерминал А - леворекурсивен, т.е.
для него имеются правила следующего вида:A → Ax1 | Ax2 | . . . | Axp | w1| . . . | wk, где xi и wj - цепочки над множеством VT ∪ VN.Введем дополнительные нетерминалы B и D и указанные правила заменим наэквивалентные им:A → AB | D;B → x1 | x2 | . . . | xp;D → w1| w2 | . . . | wk.В результате замены получим вывод, который имеет вид:A → AB→ ABB → ABBB → . . . → AB* → DB*.Таким образом, для нетерминала А можно определить эквивалентные правила:A → DK;K → BK | ε.Выполняя подстановку D и B в эти правила, получим следующие праворекурсивныеправила:A → w1K| w2K | .
. . | wkK;K → x1K | x2K | . . . | xpK | ε.Пример. Пусть задана грамматика G со следующими правилами вывода: S → Sa | ba.Требуется построить эквивалентную ей праворекурсивную грамматику.Для решения задачи воспользуемся рассмотренным выше алгоритмом. В исходнойграмматике один леворекурсивный нетерминал S.
Построим для него вывод:S → SB | D;B → a; D → ba. Вывод из S имеет вид: S → SB→ SBB→ . . . →DB*.Запишем эквивалентные правила для S:S → DK; K → BK | ε.Подставим в эти правила B и D и получим эквивалентную праворекурсивнуюграмматику G1:S → baK; K → aK | ε.Рассмотрим вывод цепочки baaaa в исходной леворекурсивной грамматике G:S → Sa → Saa → Saaa → baaaa.Эту же цепочку можно вывести в эквивалентной праворекурсивной грамматике G1:S → baK → baaK → baaaK → baaaaK → baaaa.4.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
