Езици без контекст
Редуцирани(или граматикив канонична форма) са граматики, които не съдържат непостижими и стерилни символи, цикли и празни правила (l-правила).
Разгледайте някаква граматика G(VT,VN,P,S) и дайте необходимите определения.
Нетерминален символ AÎVN се наричастерилен(илибезполезен), ако от него не може да бъде извлечен низ от терминални символи, т.е. =Æ.
В най-простия случай даден символ е стерилен, ако във всички правила, където се появява от лявата страна, се среща и от дясната страна. В по-сложни случаи безполезните символи могат да бъдат в някаква взаимна зависимост, пораждайки един друг. Ако такива знаци бъдат премахнати от граматическите правила, тогава тези правила стават по-прости.
СимволxО(VTÈVN) се наричанедостъпен, ако не се среща в никоя изреченска форма на граматиката G. Това означава, че не може да се появи в нито една верига от изводи. За да изключите всички недостъпни знаци, не е необходимо да разглеждате всички изреченски форми на граматиката, достатъчно е да използвате специален алгоритъм за премахване на недостъпни знаци. След премахването на такива знаци, правилата също се опростяват.
l-правилаили правила с празна верига са всички граматични правила под формата A®l, AÎVN. Граматика G еграматика безl-правила, ако няма правила за формата (A®l), AнVN, A¹S, и има само едно правило (S®l)нP, ако lнL(G)препоръчително е граматиката да се сведе до форма без l-правила.
Цикълв граматика G е извод от формата AÞ*A, AÎVN. Очевидно подобно заключение е безполезно, така че се препоръчва да се избягва възможността за цикли в разпознаващите CF-езици.
Циклите са възможни, ако граматикатаверигаправилана формата A®B, A,BÎVN. Достатъчно е да елиминирате верижните правила от набора от граматични правила, за да елиминирате възможността за цикли.
За да конвертирате произволна CF-граматика в канонична форма, трябва да изпълните следните стъпки (и в точния ред, в който са изброени):
§ премахнете всички празни знаци;
§ премахнете всички недостижими знаци;
§ Премахнете верижните правила.
Всяко от тези действия има свой собствен алгоритъм. Нека разгледаме тези алгоритми в реда, в който се изисква да бъдат изпълнени.
1Изтриване на празни символи
Извършва се поетапно конструиране на множество Yi, коетоне съдържа стерилни символиот разглежданата граматика. На всяка стъпка нови нетерминални символи се добавят към вече изградения набор. В същото време той първоначално включва онези символи, от които могат да бъдат изведени крайни низове, а на следващите стъпки символи, от които могат да бъдат изведени низове, състоящи се както от терминални символи, така и от символи на вече конструиран набор. След като наборът Yi престане да се променя от определена стъпка, процесът на изграждане се счита за завършен. Крайният набор от нетерминални символи трябва да включва само символи от конструирания набор Yi.
3. Докато стане Yi=Yi–1, i:=i+1 се изпълнява и отново стъпка 2.
4. Нова граматика: набор от терминални символи VT¢съвпада със стария VT: VT¢=VT, VN¢=Yi, S¢=S и P¢ включва онези правила от P, които съдържат само символи от набора (YiÈVT).
2Премахване на недостижими символи
Този алгоритъм изгражданабор от достъпни символиViот оригиналната граматика. Първо, този набор включва само целевия символ S от граматиката G, след което се допълва въз основа на правилата на тази граматика. Комплектът се счита за изграден, ако към него не може да се добави нищо ново. Всички знаци, които не са включени в този набор, са недостижими, следователно трябва да бъдат изключени от речника и от граматическите правила.
3. Докато се изпълни Vi=Vi–1, i:=i+1 и отново стъпка 2.
4. Нова граматика: наборът от терминални символи VT¢=VTÇVi, наборът от нетерминални символи VN¢=VNÇVi, S¢=S и P¢ включва онези правила от P, които съдържат само символи от набора Vi.
И двата разгледани алгоритъма - премахването на стерилни и недостижими символи - принадлежат към първата група алгоритми, т.е. прилагането им води до опростяване на граматиката, намаляване на броя на правилата и намаляване на обема на азбуката.
Примерза работата на разглежданите алгоритми: