პროგნოზირებადი ანალიზის გამოყენების მთავარი სირთულე არის შეყვანის ენის გრამატიკის პოვნა, რომელიც შეიძლება გამოყენებულ იქნას ანალიზის ცხრილის ასაგებად ცალსახად განსაზღვრული შენატანებით. ზოგჯერ, მარტივი გარდაქმნებით, გრამატიკა, რომელიც არ არის LL (1) შეიძლება შემცირდეს ექვივალენტურ LL (1) გრამატიკამდე. ამ გარდაქმნებს შორის ყველაზე ეფექტურია მარცხენა ფაქტორიზაცია და მოცილება მარცხენა რეკურსია... აქ ორი პუნქტია გასათვალისწინებელი. ჯერ ერთი, ამ გარდაქმნების შემდეგ ყველა გრამატიკა არ ხდება LL (1) და, მეორეც, ასეთი გარდაქმნების შემდეგ, შედეგად მიღებული გრამატიკა შეიძლება ნაკლებად გასაგები გახდეს.
დაუყოვნებელი მარცხენა რეკურსია, ანუ ხედვის რეკურსია, შეიძლება წაიშალოს შემდეგი გზით. პირველ რიგში ვაჯგუფებთ A-წესებს:
სადაც არცერთი სტრიქონი არ იწყება A-ით. შემდეგ შეცვალეთ ეს წესი კომპლექტით
სადაც A "არის ახალი არატერმინალი. იგივე ჯაჭვები შეიძლება გამოვიდეს არატერმინალიდან A, როგორც ადრე, მაგრამ ახლა ისინი არ არიან მარცხენა რეკურსია... ეს პროცედურა შლის ყველა პირდაპირს მარცხენა რეკურსიამაგრამ მარცხენა რეკურსია, რომელიც მოიცავს ორ ან მეტ საფეხურს, არ არის ამოღებული. ქვემოთ მოცემულია ალგორითმი 4.8საშუალებას გაძლევთ წაშალოთ ყველა მარცხენა რეკურსიაგრამატიკიდან.
ალგორითმი 4.8... წაშლა მარცხენა რეკურსია.
შესასვლელი... KS-გრამატიკა G ელ-წესების გარეშე (როგორც A -> e).
გასვლა... კს-გრამატიკა გ“ გარეშე მარცხენა რეკურსიაექვივალენტური გ.
მეთოდი... მიჰყევით ნაბიჯებს 1 და 2.
(1) დაალაგეთ G გრამატიკის არატერმინალები ნებისმიერი თანმიმდევრობით.
(2) შეასრულეთ შემდეგი პროცედურა:
გარე მარყუჟის (i-1) მე-2 საფეხურზე გამეორების შემდეგ, ფორმის ნებისმიერი წესისთვის 
სადაც კ< i, выполняется s >კ. შედეგად, მომდევნო გამეორებისას (i-ით) შიდა ციკლი (j-ით) თანმიმდევრულად ზრდის m ქვედა ზღვარს ნებისმიერ წესში. 
სანამ m> = i. შემდეგ, პირდაპირი წაშლის შემდეგ მარცხენა რეკურსია A i-ს წესებისთვის m ხდება i-ზე მეტი.
ალგორითმი 4.8გამოიყენება, თუ გრამატიკას არ აქვს e- წესები (ა -> ე ფორმის წესები). ხელმისაწვდომია გრამატიკაში - წესები შეიძლება წაიშალოს წინასწარ. შედეგად მიღებული გრამატიკა გარეშე მარცხენა რეკურსიაშეიძლება ჰქონდეს ელექტრონული წესები.
მარცხენა ფაქტორიზაცია
მარცხენა ფაქტორიზაციის მთავარი იდეა არის ის, რომ იმ შემთხვევაში, როდესაც გაურკვეველია, რომელი ორი ალტერნატივის გამოყენება უნდა მოხდეს არატერმინალის A-ს გასახსნელად, თქვენ უნდა შეცვალოთ A-წესები ისე, რომ გადაწყვეტილების მიღება გადადოთ, სანამ საკმარისი ინფორმაცია იქნება. სწორი გადაწყვეტილების მისაღებად.
თუ 
- ორი A- წესი და შეყვანის სტრიქონი იწყება არა ცარიელი სტრიქონიდან, რომელიც გამოდის არ ვიცით გავაფართოვოთ პირველი წესის მიხედვით თუ მეორე. თქვენ შეგიძლიათ გადადოთ გადაწყვეტილება განლაგებით. შემდეგ, იმის გაანალიზების შემდეგ, თუ რა არის გამოტანილი, შეგიძლიათ გააფართოვოთ ან გააფართოვოთ. მარცხენა ფაქტორიზებული წესები იღებენ ფორმას
ალგორითმი 4.9... გრამატიკის მარცხენა ფაქტორიზაცია.
შესასვლელი... CS გრამატიკა გ.
გასვლა... მარცხნივ ფაქტორიზებული CS გრამატიკა G”, რომელიც ექვივალენტურია G.
მეთოდი... თითოეული არატერმინალური A-სთვის იპოვეთ ყველაზე გრძელი პრეფიქსი, რომელიც საერთოა მისი ორი ან მეტი ალტერნატივისთვის. თუ, ანუ, არსებობს არატრივიალური საერთო პრეფიქსი, შეცვალეთ ყველა A-წესები
სადაც z აღნიშნავს ყველა ალტერნატივას, რომელიც არ იწყება
სადაც A "ახალი არატერმინალია. გამოიყენეთ ეს ტრანსფორმაცია მანამ, სანამ ორ ალტერნატივას არ ექნება საერთო პრეფიქსი.
მაგალითი 4.9... კიდევ ერთხელ განვიხილოთ პირობითი განცხადებების გრამატიკა მაგალითი 4.6:
S -> თუ E მაშინ S | თუ E მაშინ S სხვა S | a E -> ბ
მარცხენა ფაქტორიზაციის შემდეგ გრამატიკა იღებს ფორმას
S -> თუ E, მაშინ SS "| a S" -> სხვა S | e E -> ბ
სამწუხაროდ, გრამატიკა რჩება ორაზროვანი და, შესაბამისად, არა LL (1) გრამატიკა.
(დრო: 1 წმ. მეხსიერება: 16 MB სირთულე: 20%)ფორმალური გრამატიკისა და ავტომატების თეორიაში (TFGiA) მნიშვნელოვან როლს თამაშობს ე.წ. კონტექსტის გარეშე გრამატიკა(კს-გრამატიკები). CS-გრამატიკა არის ოთხმაგი, რომელიც შედგება N არატერმინალური სიმბოლოების ნაკრებისგან, T ტერმინალის სიმბოლოების ნაკრებისგან, P წესების სიმრავლისგან (წარმოებები) და საწყისი სიმბოლო S, რომელიც ეკუთვნის N სიმრავლეს.
P-ის თითოეულ წარმოქმნას აქვს A -> ფორმა ა, სადაც A არის არატერმინალური სიმბოლო (A-დან N-დან) და a არის სტრიქონი, რომელიც შედგება ტერმინალური და არატერმინალური სიმბოლოებისგან. სიტყვის გამომუშავების პროცესი იწყება სტრიქონით, რომელიც შეიცავს მხოლოდ საწყის სიმბოლოს S. ამის შემდეგ, ყოველ საფეხურზე, მიმდინარე სტრიქონში შემავალი ერთ-ერთი არატერმინალური სიმბოლო იცვლება ერთ-ერთი წარმოების მარჯვენა მხარეს, რომელშიც ის მარცხენაა. მხარეს. თუ ასეთი ოპერაციის შემდეგ მიიღება სტრიქონი, რომელიც შეიცავს მხოლოდ ტერმინალურ სიმბოლოებს, მაშინ გამომავალი პროცესი მთავრდება.
ბევრ თეორიულ პრობლემაში მოსახერხებელია ე.წ ნორმალური ფორმებიგრამატიკა. გრამატიკის ნორმალიზების პროცესი ხშირად იწყება მარცხენა რეკურსიის აღმოფხვრით. ამ პრობლემაში განვიხილავთ მხოლოდ მის განსაკუთრებულ შემთხვევას, რომელსაც უწოდებენ პირდაპირ მარცხენა რეკურსიას. დასკვნის წესი A -> R შეიცავს დაუყოვნებლივ მარცხენა რეკურსიას, თუ R სტრიქონის პირველი სიმბოლო არის A.
CS-გრამატიკა დაყენებულია. საჭიროა მოიძიოთ წესების რაოდენობა, რომლებიც შეიცავს დაუყოვნებლივ მარცხენა რეკურსიას.
Შესაყვანი მონაცემები
შეყვანის ფაილის INPUT.TXT პირველი სტრიქონი შეიცავს გრამატიკის წესების რიცხვს n (1 ≤ n ≤ 1000). ყოველი შემდეგი n ხაზი შეიცავს ერთ წესს. არატერმინალური სიმბოლოები მითითებულია ინგლისური ანბანის დიდი ასოებით, ბოლოები - მცირე ასოებით. პროდუქციის მარცხენა მხარე გამოყოფილია მარჯვენა მხრიდან სიმბოლოებით ->. ნაწარმოების მარჯვენა მხარე 1-დან 30 სიმბოლომდეა.
ჩომსკის ფორმალური გრამატიკების კლასიფიკაცია
· გრამატიკა ტიპი 0 (ზოგადი). წესები არის α → β ფორმის
ტიპი 1 გრამატიკა (კონტექსტზე მგრძნობიარე, CV)
წესები არის αAβ → αγβ ფორმის. γ ეკუთვნის V +-ს, ანუ გრამატიკა არადამოკლებულია
α, β ეწოდება მარცხენა და მარჯვენა კონტექსტი
ტიპი 2 გრამატიკა (კონტექსტის გარეშე, KS)
წესები A → α ფორმისაა. α ეკუთვნის V *-ს, ანუ გრამატიკა შეიძლება შემცირდეს => KS ენები არ შეიცავს KZ-ს
BNF-თან ყველაზე ახლოს
ტიპი 3 გრამატიკა (ავტომატური, რეგულარული)
წესები A → aB, A → a, A → ε ფორმისაა
Automata ენები შეიცავს KS ენებს
მაგალითი. გრამატიკა, რომელიც ქმნის სწორი ფრჩხილების გამონათქვამების ენას.
S → (S) | SS | ე
ქვირითობა (გამომავალი)
აღნიშვნები
=> + (1 ან მეტი)
=> * (0 ან მეტი)
გრამატიკის წინადადების ფორმაარის სტრიქონი, რომელიც შეიძლება გამოიტანოს საწყისი სიმბოლოდან.
გრამატიკის წინადადება (მაქსიმა).მხოლოდ წინადადებების ფორმაა.
ენა L (G) გრამატიკა- ეს არის მისი ყველა წინადადების ნაკრები.
ლეგენდა:
მარცხენა, მარჯვენა გამომავალი (ქვირითი).
მარცხენა და მარჯვენა გამოსავალი პუნქტისთვის i + i * i
წინადადების ხაზის გამომავალი ხე (სინტაქსის ხე, ანალიზის ხე). ქვირითისგან განსხვავებით, ინფორმაცია გამომავალი შეკვეთის შესახებ გამორიცხულია მისგან.
Parse ხე გვირგვინი - ფოთლის ეტიკეტების ჯაჭვი მარცხნიდან მარჯვნივ
გრამატიკა, რომელიც იძლევა ერთზე მეტ განხილულ ხეს ზოგიერთი წინადადებისთვის, ეწოდება ორაზროვანი.
ორაზროვანი გრამატიკის მაგალითი. არითმეტიკული გამონათქვამების გრამატიკა.
E → E + E | E * E | მე
ორი გარჩეული ხე ჯაჭვისთვის i + i * i
ორაზროვანი გრამატიკის მაგალითი. პირობითი განცხადების გრამატიკა
S → თუ b მაშინ S
| თუ b მაშინ S სხვა S
ორი გარჩეული ხე ჯაჭვისთვის, თუ b მაშინ თუ b მაშინ a
კონვერტაცია ეკვივალენტურ ცალსახა გრამატიკაზე:
S → თუ b მაშინ S
| თუ b მაშინ S2 სხვა S
S2 → თუ b მაშინ S2 სხვა S2
44 ფორმალური ენები და გრამატიკა: არა ცარიელი, სასრული და უსასრულო ენები
45 ავტომატების ეკვივალენტობა და მინიმიზაცია
სასრული მდგომარეობის მანქანების ეკვივალენტობა
მოდით S იყოს ანბანი (სიმბოლოების სასრული ნაკრები) და S * ყველა სიტყვის სიმრავლე S ანბანში. ასო e აღნიშნავს ცარიელ სიტყვას, ე.ი. ის საერთოდ არ შეიცავს ასოებს (სიმბოლოებს S-დან), მაგრამ ნიშანი × არის სიტყვების მიკუთვნების (შეერთების) ოპერაცია.
ასე რომ, aav × wa = aavva. დავალების ოპერაციის × ნიშანი ხშირად გამოტოვებულია.
S ანბანის სიტყვები აღინიშნა მცირე ბერძნული ასოებით a, b, g, .... ცხადია, e არის ერთეული დავალების მოქმედებისთვის:
ასევე აშკარაა, რომ დავალების ოპერაცია ასოციაციურია, ე.ი. (აბ) გ = ა (ბგ).
ამგვარად, S * ანბანის ყველა სიტყვის სიმრავლე დავალების მოქმედების მიმართ არის ნახევარჯგუფი ერთეულით, ე.ი. მონოიდური;
S * ეწოდება თავისუფალ მონოიდს ანბანზე S.
სახელმწიფო მანქანების მინიმიზაცია
სხვადასხვა სახელმწიფო მანქანებს შეუძლიათ იგივე ფუნქციონირება, მაშინაც კი, თუ მათ აქვთ სხვადასხვა რაოდენობის მდგომარეობა. მნიშვნელოვანი ამოცანაა იპოვოთ მინიმალური სასრული ავტომატი, რომელიც ახორციელებს მოცემულ ავტომატურ რუკებს.
ბუნებრივია ავტომატის ეკვივალენტის ორ მდგომარეობას ვუწოდოთ, რომელთა გარჩევა შეუძლებელია შეყვანის სიტყვებით.
განმარტება 1: მდგომარეობის მანქანის ორი მდგომარეობა p და q
A = (S, X, Y, s0, d, l) ეწოდება ეკვივალენტს (აღნიშნავს p ~ q) თუ ("aÎ X *) l * (p, a) = l * (q, a)
46 ერთლენტიანი და მრავალწებოვანი ტურინგის მანქანების ეკვივალენტობა
ცხადია, k-tape MT-ის კონცეფცია უფრო ფართოა, ვიდრე "ჩვეულებრივი" ერთფირიანი აპარატის კონცეფცია. განმარტება 6. (k + 1) - tape MT M ′ პროგრამით w სიმულაციას უკეთებს k-ლენტის მანქანას M თუ შეყვანილი სიტყვების რომელიმე ნაკრებისთვის (x1, x2, ..., xk) სამუშაოს შედეგი M ემთხვევა მუშაობის შედეგი M იმავე შეყვანის მონაცემებზე. ვარაუდობენ, რომ ჯერ სიტყვა w იწერება (k + 1)-ე ფირზე M ′. შედეგი გაგებულია, როგორც MT-ის პირველი k ფირის მდგომარეობა გაჩერების მომენტში და თუ M არ ჩერდება მოცემულ შეყვანაზე, მაშინ მისი სიმულატორი არც ამ შეყვანაზე უნდა გაჩერდეს.
განმარტება 7. (k + 1) - ლენტი MT M * ეწოდება უნივერსალურ ტურინგის მანქანას k - ლენტის მანქანებისთვის, თუ რომელიმე k-ლენტის მანქანა M არის პროგრამა w, რომელზეც M * ახდენს M-ის სიმულაციას. 12 შენიშვნა: განმარტებაში. უნივერსალური MT იგივე მანქანა M 'უნდა მოახდინოს სხვადასხვა k-Draw ჩარჩოების სიმულაცია (სხვადასხვა პროგრამაზე w). განვიხილოთ შემდეგი თეორემა. თეორემა 3. ნებისმიერი k≥1-ისთვის არსებობს უნივერსალური (k + 1) - ტურინგის ფირის მანქანა. მტკიცებულება. მოდით დავამტკიცოთ თეორემა კონსტრუქციულად, ანუ მოდით ვაჩვენოთ, თუ როგორ შეიძლება შეიქმნას საჭირო უნივერსალური მანქანა M *. განვიხილოთ მხოლოდ ზოგადი სამშენებლო სქემა რთული დეტალების გამოტოვებით. მთავარი იდეა არის სიმულირებული ტურინგის მანქანის აღწერილობის განთავსება დამატებით (k + 1) -ე ფირზე და ამ აღწერილობის გამოყენება სიმულაციის პროცესში.
განმარტება 8. ჩვენ ვამბობთ, რომ ტურინგის მანქანა M ითვლის f ნაწილობრივ ფუნქციას: A * → A * თუ რომელიმე x∈A * ჩაწერილია მანქანის პირველ ფირზე M: თუ f (x) არის განსაზღვრული, მაშინ M ჩერდება, და იმ მომენტში, გაჩერება აპარატის ბოლო ფირზე შეიცავს სიტყვას f (x); თუ f (x) არ არის განსაზღვრული, მაშინ მანქანა M არ ჩერდება.
განმარტება 9. ჩვენ ვამბობთ, რომ მანქანები M და M ეკვივალენტურია, თუ ისინი გამოთვლიან ერთსა და იმავე ფუნქციას. ეკვივალენტობის ცნება „უფრო სუსტია“ ვიდრე სიმულაცია: თუ მანქანა M 'ამსგავსებს მანქანას M-ს, მაშინ მანქანა M არის M-ის ეკვივალენტური; საპირისპირო ზოგადად არ შეესაბამება სიმართლეს. მეორეს მხრივ, სიმულაცია მოითხოვს, რომ M ′-ს ჰქონდეს მინიმუმ იგივე რაოდენობის ლენტები, როგორც M, ხოლო ეკვივალენტობისთვის ეს არ არის აუცილებელი 15. სწორედ ეს თვისება გვაძლევს საშუალებას ჩამოვაყალიბოთ და დავამტკიცოთ შემდეგი თეორემა.
თეორემა 4. ნებისმიერი k-ლენტური მანქანისთვის M დროის სირთულით T (n), არსებობს ექვივალენტური ერთლენტიანი მანქანა M ′ დროის სირთულით T′ (n) = O (T 2 (n)).
48 CF გრამატიკის ეკვივალენტური ტრანსფორმაციები: ჯაჭვის წესების გამორიცხვა, გრამატიკის თვითნებური წესის ამოღება
განმარტება.ფორმის გრამატიკული წესი , სად , V A ეწოდება ჯაჭვი.
განცხადება.ჯაჭვის წესების შემცველი KS-გრამატიკისთვის Г შესაძლებელია ექვივალენტური გრამატიკის Г აწყობა, რომელიც არ შეიცავს ჯაჭვის წესებს.
მტკიცებულების იდეა შემდეგია. თუ გრამატიკული სქემა არის
R = (..., ,...,
მაშინ ასეთი გრამატიკა ექვივალენტურია გრამატიკის სქემით
R" = (..., ა
ვინაიდან გამომავალი გრამატიკაში ჯაჭვის R წრედთან ა
შეგიძლიათ მიიღოთ გრამატიკაში სქემით R "წესის გამოყენებით ა
ზოგად შემთხვევაში, ბოლო განცხადების დადასტურება შეიძლება შემდეგნაირად. ჩვენ ვყოფთ R-ს ორ ქვეჯგუფად R 1 და R 2, მათ შორის R 1-ში ფორმის ყველა წესი
თითოეული წესისთვის R 1-დან ვპოულობთ წესების S ( ), რომლებიც აგებულია ასე:
თუ *და R 2-ში არის წესი α, სადაც α არის ლექსიკონის ჯაჭვი (V т V A) *, შემდეგ S-ში ( ) ჩართეთ წესი
ჩვენ ვაშენებთ ახალ სქემას R "R 2 წესების და ყველა აგებული S კომპლექტების გაერთიანებით ( ). ვიღებთ გრამატიკა Г "= (V т, V A, I, R"), რომელიც მოცემულის ტოლფასია და არ შეიცავს ფორმის წესებს. .
მაგალითად, შევასრულოთ ჯაჭვის წესების ამოღება გრამატიკიდან Г 1.9 სქემით:
R = (
პირველ რიგში, ჩვენ დავყავით გრამატიკული წესები ორ ქვეჯგუფად:
R 1 = (
R 2 = (
თითოეული წესისთვის R 1-დან შექმენით შესაბამისი ქვესიმრავლე.
S (
S (
შედეგად, ჩვენ ვიღებთ სასურველ გრამატიკულ სქემას ჯაჭვის წესების გარეშე სახით:
R 2 U S (
განხილული ტრანსფორმაციების ბოლო ტიპი ასოცირდება გრამატიკიდან ცარიელი მარჯვენა მხარის წესების ამოღებასთან.
განმარტება.წესის ნახვა $ ჰქვია გაუქმების წესი.
49. კს-გრამატიკების ეკვივალენტური გარდაქმნები: უსარგებლო სიმბოლოების ამოღება.
მიეცით თვითნებური CS-გრამატიკა გ ... არატერმინალური ა ამ გრამატიკას ჰქვია პროდუქტიული თუ არსებობს ტერმინალური ჯაჭვი (მათ შორის ცარიელი) ისეთი, რომ ა Þ * ა არაპროდუქტიული.
თეორემა. თითოეული KS გრამატიკა უდრის KS გრამატიკას არაპროდუქტიული არატერმინალების გარეშე.
არატერმინალური ა გრამატიკა გ დაურეკა მიღწევადი თუ არსებობს ასეთი ჯაჭვი ა , რა ს Þ * ა ... წინააღმდეგ შემთხვევაში, არატერმინალი ეწოდება მიუღწეველი.
თეორემა. თითოეული CF გრამატიკა უდრის CF გრამატიკას მიუწვდომელი არატერმინალის გარეშე.
KS-გრამატიკაში არატერმინალური სიმბოლო ეწოდება უსარგებლო (ან არასაჭირო) თუ ის ან მიუღწეველია ან არაპროდუქტიული.
თეორემა. ყოველი CF გრამატიკა ექვივალენტურია CF გრამატიკისა, რომელსაც არ აქვს უსარგებლო არატერმინალები.
მაგალითი.ამოიღეთ უსარგებლო სიმბოლოები გრამატიკაში
ს® aC | ა; ა ® ტაქსი; ბ ® ბ; C ® ა.
Ნაბიჯი 1... კომპლექტის აგება მიღწევადიპერსონაჟები: {ს} ® { S, C, A}® { S, C, A, B}. ყველა არატერმინალი ხელმისაწვდომია. მიუწვდომელია გრამატიკული ცვლილებების გარეშე.
ნაბიჯი 2... კომპლექტის აგება პროდუქტიულიპერსონაჟები: {C, B}® { S, C, B}. ჩვენ ამას მივიღებთ ა - არა პროდუქტიული. ჩვენ მას და მასთან ერთად ყველა წესს ვყრით გრამატიკიდან. ვიღებთ
ს® aC; ბ ® ბ; C ® ა.
ნაბიჯი 3... კომპლექტის აგება მიღწევადიახალი გრამატიკის სიმბოლოები: {ს} ® { S, C}. ჩვენ ამას მივიღებთ ბ მიუღწეველი. ჩვენ მას და მასთან ერთად ყველა წესს ვყრით გრამატიკიდან. ვიღებთ
ს® aC; C ® ა.
ეს არის საბოლოო შედეგი.
50. კს-გრამატიკების ეკვივალენტური გარდაქმნები: მარცხენა რეკურსიის აღმოფხვრა, მარცხენა ფაქტორიზაცია.
მარცხენა რეკურსიის წაშლა
პროგნოზირებადი ანალიზის გამოყენების მთავარი სირთულე არის შეყვანის ენის გრამატიკის პოვნა, რომელიც შეიძლება გამოყენებულ იქნას ანალიზის ცხრილის ასაგებად ცალსახად განსაზღვრული შენატანებით. ზოგჯერ, მარტივი გარდაქმნებით, გრამატიკა, რომელიც არ არის LL (1) შეიძლება შემცირდეს ექვივალენტურ LL (1) გრამატიკამდე. ამ გარდაქმნებს შორის ყველაზე ეფექტურია მარცხენა ფაქტორიზაცია და მოცილება მარცხენა რეკურსია... აქ ორი პუნქტია გასათვალისწინებელი. ჯერ ერთი, ამ გარდაქმნების შემდეგ ყველა გრამატიკა არ ხდება LL (1) და, მეორეც, ასეთი გარდაქმნების შემდეგ, შედეგად მიღებული გრამატიკა შეიძლება ნაკლებად გასაგები გახდეს.
დაუყოვნებელი მარცხენა რეკურსია, ანუ ხედვის რეკურსია, შეიძლება წაიშალოს შემდეგი გზით. პირველ რიგში ვაჯგუფებთ A-წესებს:
სადაც არცერთი სტრიქონი არ იწყება A-ით. შემდეგ შეცვალეთ ეს წესი კომპლექტით
სადაც A "არის ახალი არატერმინალი. იგივე ჯაჭვები შეიძლება გამოვიდეს არატერმინალიდან A, როგორც ადრე, მაგრამ ახლა ისინი არ არიან მარცხენა რეკურსია... ეს პროცედურა შლის ყველა პირდაპირს მარცხენა რეკურსიამაგრამ მარცხენა რეკურსია, რომელიც მოიცავს ორ ან მეტ საფეხურს, არ არის ამოღებული. ქვემოთ მოცემულია ალგორითმი 4.8საშუალებას გაძლევთ წაშალოთ ყველა მარცხენა რეკურსიაგრამატიკიდან.
მარცხენა ფაქტორიზაცია
მარცხენა ფაქტორიზაციის მთავარი იდეა არის ის, რომ იმ შემთხვევაში, როდესაც გაურკვეველია, რომელი ორი ალტერნატივის გამოყენება უნდა მოხდეს არატერმინალის A-ს გასახსნელად, თქვენ უნდა შეცვალოთ A-წესები ისე, რომ გადაწყვეტილების მიღება გადადოთ, სანამ საკმარისი ინფორმაცია იქნება. სწორი გადაწყვეტილების მისაღებად.
თუ 
- ორი A- წესი და შეყვანის სტრიქონი იწყება არა ცარიელი სტრიქონიდან, რომელიც გამოდის არ ვიცით გავაფართოვოთ პირველი წესის მიხედვით თუ მეორე. თქვენ შეგიძლიათ გადადოთ გადაწყვეტილება განლაგებით. შემდეგ, იმის გაანალიზების შემდეგ, თუ რა არის გამოტანილი, შეგიძლიათ გააფართოვოთ ან გააფართოვოთ. მარცხენა ფაქტორიზებული წესები იღებენ ფორმას
51. ტურინგის მანქანის ენა.
ტურინგის მანქანა მოიცავს შეუზღუდავ ორივე მიმართულებით ლენტი(შესაძლებელია ტურინგის მანქანები, რომლებსაც აქვთ რამდენიმე უსასრულო ლენტი), დაყოფილია უჯრედებად და საკონტროლო მოწყობილობა(ასევე ე.წ წაკითხვა-წერის თავი (GZCH)), შეუძლია ერთ-ერთში ყოფნა სახელმწიფოთა ნაკრები... საკონტროლო მოწყობილობის შესაძლო მდგომარეობების რაოდენობა სასრულია და ზუსტად არის მითითებული.
საკონტროლო მოწყობილობას შეუძლია გადაადგილდეს მარცხნივ და მარჯვნივ ფირზე, წაიკითხოს და ჩაწეროს ზოგიერთი სასრული ანბანის სიმბოლოები უჯრედებში. გამოირჩევა განსაკუთრებული ცარიელისიმბოლო, რომელიც ავსებს ფირის ყველა უჯრედს, გარდა მათგან (სასრული რიცხვი), რომელზედაც იწერება შეყვანის მონაცემები.
საკონტროლო მოწყობილობა მუშაობს შესაბამისად გადასვლის წესებირომელიც წარმოადგენს ალგორითმს, რეალიზებადიეს ტურინგის მანქანა. ყოველი გადასვლის წესი ავალებს მანქანას, მიმდინარე მდგომარეობიდან და მიმდინარე უჯრედში დაფიქსირებული სიმბოლოდან გამომდინარე, დაწეროს ახალი სიმბოლო ამ უჯრედში, გადართოს ახალ მდგომარეობაში და გადაიტანოს ერთი უჯრედი მარცხნივ ან მარჯვნივ. ტურინგის მანქანის ზოგიერთ მდგომარეობას შეიძლება ეწოდოს ტერმინალი, ხოლო რომელიმე მათგანზე გადასვლა ნიშნავს სამუშაოს დასრულებას, ალგორითმის გაჩერებას.
ტურინგის მანქანა ე.წ განმსაზღვრელითუ მაქსიმუმ ერთი წესი ემთხვევა ცხრილის მდგომარეობისა და ზოლის სიმბოლოების თითოეულ კომბინაციას. თუ არსებობს წყვილი "ზოლიანი სიმბოლო - მდგომარეობა", რომლისთვისაც არის 2 ან მეტი ინსტრუქცია, ასეთ ტურინგ მანქანას ე.წ. არადეტერმინისტული.
LL (k) -საკუთრება დიდ შეზღუდვებს აწესებს გრამატიკაზე. ზოგჯერ შესაძლებელია გრამატიკის ისე გარდაქმნა, რომ მიღებული გრამატიკა ჰქონდეს ქონება LL (1) ... ასეთი ტრანსფორმაცია შორს არის ყოველთვის წარმატებულისგან, მაგრამ თუ შესაძლებელი იყო LL (1) -გრამატიკის მოპოვება, მაშინ ანალიზატორის ასაგებად შეიძლება გამოყენებულ იქნას რეკურსიული დაღმართის მეთოდი უკან დახევის გარეშე.
დავუშვათ, რომ გსურთ შექმნათ პარსერი ენისთვის, რომელიც გენერირებულია შემდეგი გრამატიკით:
ე → ე + თ | ე – თ | თ
T → T * F | T/F | ფ
ფ → რიცხ | (ე)
ტერმინალების კომპლექტი FIRST (T)ასევე მიეკუთვნება კომპლექტს FIRST (E + T)მაშასადამე, შეუძლებელია ცალსახად განისაზღვროს პროცედურების ზარების თანმიმდევრობა, რომელიც უნდა შესრულდეს შეყვანის ჯაჭვის ანალიზისას. პრობლემა ის არის, რომ არატერმინალი ეხდება წესის მარჯვენა მხარის პირველ პოზიციაზე, რომლის მარცხენა მხარეც არის ე... ასეთ სიტუაციაში არატერმინალი ეპირდაპირ მარცხენა რეკურსიული ეწოდება.
არატერმინალური აკს გრამატიკა გდაურეკა მარცხენა რეკურსიული თუ გრამატიკაში არის გამომავალი ა =>* აუ.
გრამატიკა მინიმუმ ერთი მარცხენა რეკურსიული წესით არ შეიძლება იყოს LL (1)-გრამატიკა.
მეორეს მხრივ, ცნობილია, რომ ყოველი CF ენა განისაზღვრება მინიმუმ ერთი არალევოკურსიული გრამატიკით.
მარცხენა რეკურსიულობის აღმოფხვრის ალგორითმი
დაე G = (N, T, P, S)- კს გრამატიკა და წესი A → აუ 1 | აუ 2 | … | აუ ნ | ვ 1 | ვ 2 | … | ვ მწარმოადგენს ყველა წესს პშემცველი ამარცხნივ და არცერთი ჯაჭვი ვ მეარ იწყება არატერმინალით ა.
კომპლექტში დამატება ნსხვა არატერმინალი A "და შეცვალეთ წესები, რომლებიც შეიცავს ამარცხნივ, შემდეგში:
A → v 1 | ვ 2 | … | ვ მ | ვ 1 A' | ვ 2 A '| … | ვ მ A "
A '→ w 1 | ვ 2 | … | ვ ნ | ვ 1 A '| ვ 2 A '| ...| ვ ნ A "
თქვენ შეგიძლიათ დაამტკიცოთ, რომ მიღებული გრამატიკა ორიგინალის ტოლფასია.
ამ ტრანსფორმაციის გამოყენების შედეგად არითმეტიკული გამონათქვამების აღწერილ ზემოხსენებულ გრამატიკაში მივიღებთ შემდეგ გრამატიკას:
ე → თ | TE"
ე" → + თ | + TE"
თ → ფ | FT"
თ"→ * ფ | * FT"
ფ → (ე) | რიცხ
ადვილია იმის ჩვენება, რომ მიღებულ გრამატიკას აქვს თვისება LL (1).
კიდევ ერთი მსგავსი პრობლემა უკავშირდება იმ ფაქტს, რომ ერთი და იგივე არატერმინალის ორი წესი იწყება ერთი და იგივე სიმბოლოებით.
Მაგალითად,
S → თუ E, მაშინ S სხვა S
ს → თუ ე მაშინ ს
ამ შემთხვევაში დავამატოთ კიდევ ერთი არატერმინალი, რომელიც შეესაბამება ამ წესების სხვადასხვა დაბოლოებებს. ჩვენ ვიღებთ შემდეგ წესებს:
ს → თუ ე მაშინ ს ს’
ს" →
ს"→ სხვა ს
შედეგად მიღებული გრამატიკისთვის შეიძლება განხორციელდეს რეკურსიული წარმოშობის მეთოდი.
9.1.4. რეკურსიული დაღმართი დაბრუნებით.
იმისათვის, რომ შეძლოთ რეკურსიული დაღმართის მეთოდის გამოყენება, საჭიროა 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 გრამატიკა გარდაქმნის ფორმას, რომელშიც კომპლექტები ᲞᲘᲠᲕᲔᲚᲘარ იკვეთება, რაც რთული პროცესია, ამიტომ, პრაქტიკაში, ტექნიკა ე.წ რეკურსიული დაღმართი უკუღმა .
ამისთვის ლექსიკური ანალიზატორი წარმოდგენილია როგორც ობიექტი, რომელიც, გარდა ტრადიციული მეთოდებისა სკანირება, შემდეგიდა ასე შემდეგ, ასევე არის ასლის კონსტრუქტორი. შემდეგ, ყველა სიტუაციაში, როდესაც შეიძლება გაურკვევლობა წარმოიშვას, სანამ დაიწყებთ ანალიზს, უნდა გახსოვდეთ ლექსიკური ანალიზატორის ამჟამინდელი მდგომარეობა (ანუ გააკეთეთ ლექსიკური ანალიზატორის ასლი) და განაგრძეთ ტექსტის ანალიზები, იმის გათვალისწინებით, რომ საქმე გვაქვს პირველთან. აშენება შესაძლებელია ამ სიტუაციაში. თუ ანალიზების ეს ვარიანტი ვერ მოხერხდა, მაშინ უნდა აღადგინოთ ლექსიკური ანალიზატორის მდგომარეობა და სცადოთ იგივე ფრაგმენტის გაანალიზება შემდეგი გრამატიკული ოფციის გამოყენებით და ა.შ.
ანალიზების ეს მეთოდი პოტენციურად უფრო ნელია ვიდრე რეკურსიული დაღმართი უკან დახევის გარეშე, მაგრამ ამ შემთხვევაში ის ახერხებს გრამატიკა თავდაპირველ ფორმაში შეინახოს და პროგრამისტის ძალისხმევა დაზოგოს.
მარცხენა რეკურსიის შემცველი გრამატიკა არ არის LL (1) გრამატიკა. გაითვალისწინეთ წესები
ა→ Აა(მარცხენა რეკურსია A-ში)
ა→ ა
Აქ აწინამორბედი სიმბოლო ორივე არატერმინალური ვარიანტისთვის ა... ანალოგიურად, გრამატიკა, რომელიც შეიცავს მარცხენა რეკურსიულ ციკლს, არ შეიძლება იყოს LL (1) გრამატიკა, მაგალითად.
ა→ ძვ.წ
ბ→ CD
C→ AE
მარცხენა რეკურსიული მარყუჟის შემცველი გრამატიკა შეიძლება გარდაიქმნას გრამატიკად, რომელიც შეიცავს მხოლოდ წინა მარცხენა რეკურსიას, და შემდგომ, დამატებითი არატერმინალის შემოღებით, მარცხენა რეკურსი შეიძლება მთლიანად აღმოიფხვრას (ფაქტობრივად, ის ჩანაცვლებულია მარჯვენა რეკურსიით, რომელიც არ წარმოადგენს პრობლემა LL (1) -თვისებების მიმართ).
მაგალითად, განიხილეთ გრამატიკა გენერაციული წესებით
ს→ Აა
ა→ ბბ
ბ→ Cc
C→ დდ
C→ ე
დ→ აზ
რომელსაც აქვს მარცხენა რეკურსიული ციკლი, რომელიც მოიცავს Ა Ბ Გ Დ... ამ მარყუჟის წინ მარცხენა რეკურსიით ჩასანაცვლებლად, ჩვენ ვაწესრიგებთ არატერმინალებს შემდეგნაირად: S, A, B, C, D.
განიხილეთ ფორმის გენერირების ყველა წესი
Xi→ Xj γ,
სადაც Xiდა Xj- არატერმინალები და γ - ტერმინალური და არატერმინალური სიმბოლოების სტრიქონი. წესებთან დაკავშირებით, რისთვისაც j ≥ i, არანაირი ქმედება არ არის მიღებული. თუმცა, ეს უთანასწორობა ვერ იქნება ყველა წესისთვის, თუ არის მარცხენა რეკურსიული მარყუჟი. ჩვენ მიერ არჩეული თანმიმდევრობით საქმე გვაქვს ერთ წესთან:
დ→ აზ
რადგან აწინ უძღოდა დამ შეკვეთაში. ახლა დავიწყოთ ჩანაცვლება აყველა იმ წესის გამოყენებით, რაც აქვს ამარცხნივ. შედეგად, ჩვენ ვიღებთ
დ→ ბბზ
Იმდენად, რამდენადაც ბწინ უძღოდა დიმისათვის, რომ პროცესი მეორდება, რომელიც იძლევა წესს:
დ→ Ccbz
შემდეგ ის კიდევ ერთხელ იმეორებს და იძლევა ორ წესს:
დ→ ეკბზ
დ→ Ddcbz
გარდაქმნილი გრამატიკა ახლა ასე გამოიყურება:
ს→ Აა
ა→ ბბ
ბ→ Cc
C→ დდ
C→ ე
დ→ Ddcbz
დ→ ეკბზ
ყველა ამ გენერირების წესს აქვს საჭირო ფორმა და მარცხენა რეკურსიული ციკლი ჩანაცვლებულია წინ მარცხენა რეკურსიით. წინა მარცხენა რეკურსიის აღმოსაფხვრელად, ჩვენ შემოგთავაზებთ ახალ არატერმინალურ სიმბოლოს ზდა შეცვალე წესები
დ→ ეკბზ
დ→ Ddcbz
დ→ ეკბზ
დ→ ecbzZ
ზ→ dcbz
ზ→ dcbzZ
გაითვალისწინეთ, რომ ტრანსფორმაციამდე და მის შემდეგ დქმნის რეგულარულ გამოხატულებას
(ecbz) (dcbz) *
შეჯამებით შეიძლება ნაჩვენები იყოს, რომ თუ არატერმინალურია აგამოჩნდება მარცხნივ რ+ სგენერაციული წესები, რრომელთაგან იყენებენ წინ მარცხენა რეკურსიას და ს- არა, ე.ი.
ა→ აα 1, ა→ აα 2,..., ა→ აαრ
ა→ β 1, ა→ β 2,..., ა→ β ს
მაშინ ეს წესები შეიძლება შეიცვალოს შემდეგით:
არაფორმალური დასტურია ის, რომ ტრანსფორმაციამდე და მის შემდეგ აქმნის რეგულარულ გამოხატულებას ( β 1 | β 2 |... | β ს) ( α 1 | α 2 |... | α ს) *
უნდა აღინიშნოს, რომ მარცხენა რეკურსიის (ან მარცხენა რეკურსიული მარყუჟის) აღმოფხვრით ჩვენ მაინც არ ვიღებთ LL (1) გრამატიკას, ვინაიდან ზოგიერთი არატერმინალისთვის, მიღებული გრამატიკის წესების მარცხენა მხარეს, არის ალტერნატიული მარჯვენა მხარეები, რომლებიც იწყება იგივე სიმბოლოებით. ამიტომ, მარცხენა რეკურსიის აღმოფხვრის შემდეგ, უნდა გაგრძელდეს გრამატიკის ტრანსფორმაცია LL (1) ფორმაში.
17. გრამატიკების LL (1) ფორმად გადაქცევა. ფაქტორიზაცია.
ფაქტორიზაცია
ბევრ სიტუაციაში, გრამატიკები, რომლებსაც არ გააჩნიათ LL (1) ატრიბუტი, შეიძლება გარდაიქმნას LL (1) გრამატიკებში ფაქტორიზაციის პროცესის გამოყენებით. განვიხილოთ ასეთი სიტუაციის მაგალითი.
პ→ დაიწყება დ; თანდასასრული
დ→ დ, დ
დ→ დ
თან→ ს; თან
თან→ ს
ფაქტორიზაციის პროცესში ჩვენ ვცვლით რამდენიმე წესს ერთი არატერმინალის მარცხენა მხარეს, რომლის მარჯვენა მხარე იწყება იგივე სიმბოლოთი (სიმბოლოების სტრიქონი) ერთი წესით, სადაც მარჯვენა მხარეს საერთო დასაწყისს მოჰყვება დამატებით შემოღებული არატერმინალური. ასევე, გრამატიკას ავსებს დამატებითი არატერმინალის წესები, რომლის მიხედვითაც მისგან არის მიღებული წესის ორიგინალური მარჯვენა მხარის სხვადასხვა „ნარჩენები“. ზემოაღნიშნული გრამატიკისთვის, ეს მისცემს შემდეგ LL (1) გრამატიკას:
პ→ დაიწყება დ; თანდასასრული
დ→ d X X)
X→ , დ(1-ლი წესის მიხედვით დორიგინალური გრამატიკა ამისთვის დშემდეგნაირად, დ)
X→ ε (მე-2 წესის მიხედვით დორიგინალური გრამატიკა ამისთვის დარაფერი (ცარიელი სტრიქონი))
თან→ s Y(ჩვენ შემოგთავაზებთ დამატებით არატერმინალს ი)
ი→ ; თან(1-ლი წესის მიხედვით Cორიგინალური გრამატიკა ამისთვის სმიჰყვება; C)
ი→ ε (მე-2 წესის მიხედვით Cორიგინალური გრამატიკა ამისთვის სარაფერი (ცარიელი სტრიქონი))
ანალოგიურად, გენერაციული წესები
ს→ aSb
ს→ ასც
ს→ ε
შეიძლება გარდაიქმნას ფაქტორიზაციით წესებად
ს→ aSX
ს→ ε
X→ ბ
X→ გ
და შედეგად მიღებული გრამატიკა არის LL (1). თუმცა, ფაქტორიზაციის პროცესის ავტომატიზაცია შეუძლებელია ზოგად საქმეზე გაფართოებით. შემდეგი მაგალითი გვიჩვენებს, რა შეიძლება მოხდეს. გაითვალისწინეთ წესები
1. პ→ Qx
2. პ→ რაი
3. ქ→ კვმ
4. ქ→ ქ
5. რ→ sRn
6. რ→ რ
სახელმძღვანელო სიმბოლოების ორივე ნაკრები ორი ვარიანტისთვის პშეიცავს სდა ცდილობს „გაუძლოს სფრჩხილების გარეთ“, ჩვენ ვცვლით ქდა რ 1 და 2 წესების მარჯვენა მხარეს:
პ→ sQmx
პ→ sRny
პ→ qx
პ→ რი
ეს წესები შეიძლება შეიცვალოს შემდეგი წესებით:
პ→ qx
პ→ რი
პ→ სპ 1
პ 1 → Qmx
პ 1 → რნი
წესები P1მსგავსია ორიგინალური წესებისთვის პდა აქვს სახელმძღვანელო სიმბოლოების გადახურვის ნაკრები. ჩვენ შეგვიძლია გადავცვალოთ ეს წესები ისევე, როგორც წესები პ:
პ 1 → sQmmx
პ 1 → qmx
პ 1 → sRnny
პ 1 → rny
ფაქტორინგი, მივიღებთ
