Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7

Вид материала

Конспект

Содержание 9. Преобразования КС-грамматик 9.1 Устранение непроизводящих правил А имеют следующий вид и других правил для А Алгоритм устранения непроизводящих нетерминалов. 9.2. Устранение недостижимых нетерминалов Алгоритм преобразования грамматики.

Подобный материал:

• Учебное пособие тверь 2008 удк 519. 876 (075. 8 + 338 (075. 8) Ббк 3817я731-1 + 450., 2962.9kb.
• Тексты лекций Москва 2008 удк 339. 9(075. 8) Ббк 65. 5я73-2, 1528.45kb.
• Программно-технический комплекс Учебное пособие Новочеркасск юргту (нпи) 2010. Удк, 3911.73kb.
• Удк 152. 27 (075. 8) + 157 (075. 8) + 152. 3 (075, 60.12kb.
• Краткий конспект лекций Кемерово 2002 удк: 744 (075), 1231.26kb.
• Методические указания по курсу Новосибирск 2004 ббк ю 937. 4 Удк 152. 26 (075), 802.63kb.
• Москва 2011 ббк 63. 3 (2)я 7 к 90 удк 947 (075) История России, 110.08kb.
• Курс лекций Гродно 2005 удк 631. 1 (075., 1193.16kb.
• Удк 070(075. 8) Ббк 76. 01я73, 5789.66kb.
• Удк 339. 9(470)(075. 8) Ббк, 7329.81kb.

9. Преобразования КС-грамматик

В данном разделе приводятся такие преобразования грамматик, которые не выводят нас из класса эквивалентности, т.е. грамматика G₁ таким образом преобразуется в грамматику G₂, чтобы L(G₁)=L(G₂).

9.1 Устранение непроизводящих правил

Непроизводящими правилами грамматики называются правила, применение которых никогда не приводит к построению терминальных цепочек.

Например, пусть правила для нетерминала А имеют следующий вид и других правил для А нет:

АА А В А

В этом случае, появившись в цепочке, нетерминал А никогда не будет заменен терминальной цепочкой. Естественно, в реальности ситуации бывают не столь простые.

Алгоритм устранения непроизводящих нетерминалов.

Пусть дана грамматика G = < V_N, V_T,S, R>, строится эквивалентная грамматика без непроизводящих символов G’ = < V_N’, V_T, S, R’>.

1. Построение множества производящих нетерминалов N_R:
   
   1. Строится множество N_R¹ = {A/ A_j, _jV_T*}
      
   2. Последовательно строятся множества N_Rⁱ⁺¹={ A/ A_j, _j(N_RⁱV_T)*}
      
   3. Построение продолжается до тех пор, пока не получим N_Rⁱ⁺¹= N_Rⁱ или же N_Rⁱ= V_N. Тогда N_R = N_Rⁱ.
      
2. Исключаем из грамматики все правила, в которых присутствуют нетерминалы из V_N\ N_R.
   

Например, рассмотрим грамматику G₁₄ с множеством правил

S ABBC;

A AAAB;

B bBa;

СсСd AC.

Построим множество N_R. N_R¹={B,C}, N_R²={S, B, C}, N_R³= N_R²= =N_R.

Правила преобразованной грамматики:

S BC;

B bBa;

СсСd .

9.2. Устранение недостижимых нетерминалов

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

Следует отметить, что такие нетерминалы в грамматиках встречаются в основном тогда, когда исключены некоторые непроизводящие символы, т.е. недостижимым нетерминал становится чаще всего после исключения некоторых непроизводящих символов. Например, если в грамматике правила для нетерминала А: АА А В А, и нетерминал В не встречается в других правых частях правил грамматики, то в этом случае, после устранения нетерминала А нетерминал В становится недостижимым, и, следовательно, его можно исключить из грамматики без изменения порождаемого ей языка. Построение множества недостижимых нетерминалов похоже на построение множества непроизводящих нетерминалов: строится множество всех достижимых нетерминалов, а затем исключаются все остальные нетерминалы грамматики.

Алгоритм преобразования грамматики.

Строится грамматика, в которой используются только достижимые нетерминалы (множество достижимых нетерминалов – D) , выглядит следующим образом:

Пусть дана грамматика G=< V_N, V_T, S, R>, строится эквивалентная грамматика без недостижимых нетерминалов G’ =< V_N’, V_T, S, R’>.

1. Построение множества достижимых нетерминалов:
   
   1. Начальное значение D₀=S.
      
   2. Итерационное построение множества D:
      

D_i+1= D_i  { A/B  AR B D_i}

1. Построение продолжается до тех пор, пока D_i+1= D_i или D_i+1= =V_N, в обоих случаях V_N’= D_i+1,
   
1. Построение множества правил преобразованной грамматики:
   

R’={ R_i / R_i=(A), A V_N’, ( V_N’ V_T)*}. Построенная грамматика не содержит недостижимых нетерминалов.

Например, рассмотрим грамматику G₁₅ с множеством правил

S A C B C;

A AD DF;

D aA  D A;

F b F;

B bBa;

СсСd.

Тогда здесь A и D непроизводящие нетерминалы, после их устранения нетерминал F становится недостижимым, поэтому нетерминалы A, D и F могут быть исключены из грамматики с сохранением языка, порождаемого грамматикой.

Правила преобразованной грамматики:

S B C

B bBa

СсСd