Ekspresi reguler (RE) adalah bentuk penulisan yang sangat nyaman yang disebut bahasa reguler atau automata. Oleh karena itu, RT digunakan sebagai bahasa masukan di banyak sistem yang memproses rantai. Mari kita lihat contoh sistem tersebut:
- perintah grep sistem operasi Unix atau perintah serupa untuk mencari string yang ditemukan di browser Web atau sistem pemformatan teks. Dalam sistem seperti itu, RF digunakan untuk mendeskripsikan pola yang dicari pengguna dalam sebuah file. Berbagai mesin pencari mengubah mesin pencari menjadi mesin keadaan terbatas deterministik (DFA) atau mesin keadaan terbatas non-deterministik (NFA) dan menerapkan mesin ini pada file yang sedang dicari.
- Generator penganalisis leksikal. Penganalisis leksikal adalah komponen kompiler, mereka memecah program sumber menjadi unit logis (token), yang dapat terdiri dari satu atau lebih karakter dan memiliki arti tertentu. Generator penganalisis leksikal menerima deskripsi formal leksem, yang pada dasarnya adalah RV, dan membuat DFA yang mengenali leksem mana yang muncul dalam masukannya.
- RV dalam bahasa pemrograman.
Pada artikel ini, pertama-tama kita akan mengenal mesin keadaan terbatas dan tipenya (DFA dan NFA), lalu mempertimbangkan contoh pembuatan DFA minimal menggunakan ekspresi reguler.
Mesin keadaan terbatas
Mesin keadaan terbatas (FA) adalah konverter yang memungkinkan Anda mengasosiasikan masukan dengan keluaran yang sesuai, dan keluaran ini tidak hanya bergantung pada masukan saat ini, tetapi juga pada apa yang terjadi sebelumnya, pada sejarah pengoperasian mesin keadaan terbatas. mesin negara. Bahkan perilaku manusia, dan bukan hanya sistem buatan, dapat digambarkan dengan menggunakan pesawat ruang angkasa. Misalnya, reaksi Anda terhadap kenyataan bahwa tetangga Anda mendengarkan musik keras di malam hari akan terjadi setelah kejadian pertama dan sangat berbeda setelah beberapa kejadian serupa. Jumlah prasejarah seperti itu bisa jadi tak terbatas; pertanyaan yang muncul adalah: jenis memori apa yang harus dimiliki pesawat ruang angkasa agar dapat berperilaku berbeda pada setiap prasejarah? Jelas bahwa tidak mungkin menyimpan backstories dalam jumlah tak terbatas. Oleh karena itu, robot semacam ini memecah semua kemungkinan prasejarah ke dalam kelas-kelas kesetaraan. Dua sejarah dikatakan ekuivalen jika mempunyai pengaruh yang sama terhadap perilaku mesin di masa depan. Kelas ekuivalen yang sejarahnya saat ini telah ditetapkan oleh automaton disebut juga keadaan internal mesin.Mari kita perhatikan contoh pengoperasian pesawat ruang angkasa primitif:
Pesawat luar angkasa ini terdiri dari:
- pita yang diwakili oleh rantai masukan.
- perangkat membaca.
- blok kontrol yang berisi daftar aturan transisi.
Pembaca dapat bergerak ke satu arah, biasanya dari kiri ke kanan, sehingga membaca karakter string masukan. Untuk setiap gerakan tersebut, satu simbol dapat dihitung. Selanjutnya, karakter baca ditransmisikan ke unit kontrol. Unit kontrol mengubah keadaan mesin berdasarkan aturan transisi. Jika daftar aturan transisi tidak berisi aturan untuk simbol baca, maka mesin “mati”.
Sekarang mari kita lihat cara menentukan CA. Mereka dapat ditentukan dalam bentuk grafik atau dalam bentuk tabel kontrol. Dalam bentuk grafik, CA ditentukan dengan cara sebagai berikut:
- simpul-simpul grafik sesuai dengan keadaan pesawat ruang angkasa.
- tepi berarah sesuai dengan fungsi transisi (di samping setiap tepi tersebut, simbol di mana transisi dilakukan ditunjukkan).
- sebuah titik dengan sisi yang masuk ke dalamnya yang tidak meninggalkan lebih dari satu keadaan berhubungan dengan keadaan awal.
- keadaan akhir pesawat ruang angkasa ditandai dengan garis tebal.
Dalam bentuk tabel kontrol, seperti ini:
- keadaan pesawat ruang angkasa terletak di baris tabel.
- karakter bahasa yang dikenali ada di kolom.
- di persimpangan, ditunjukkan suatu negara bagian yang dapat dicapai dari suatu negara bagian tertentu dengan menggunakan simbol tertentu.
Contoh CA dalam bentuk grafik dan tabel kontrol akan disajikan di bawah ini.
DKA dan NKA
Perbedaan utama antara DKA dan NKA adalah DKA hanya dapat berada di satu negara bagian selama beroperasi, sedangkan NKA dapat berada di beberapa negara bagian pada waktu yang bersamaan. Sebagai contoh karya NCA, kita dapat mengutip gagasan fisikawan Amerika Hugh Everett bahwa setiap peristiwa membagi dunia menjadi beberapa dunia, yang masing-masing dunia berakhir dengan caranya sendiri. Misalnya, di satu dunia, Hitler memenangkan dunia kedua perang Dunia, di sisi lain - Newton terjun ke bisnis alih-alih fisika dan penemuan hukum mekanika klasik harus ditunda selama 50 tahun. Untuk menarik kesimpulan dari pengoperasian robot, seseorang harus mempelajari semua "dunia". Setelah seluruh rantai masukan dibaca, kami berasumsi bahwa NFA menerima rantai ini jika ia telah menyelesaikan operasinya di negara penerima di setidaknya satu dari banyak “dunia”. Oleh karena itu, automaton menolak rantai tersebut jika berakhir pada keadaan tidak dapat diterima di setiap “dunia”. DKA menerima rantai tersebut; hal ini terlihat jelas jika, setelah membaca seluruh rantai masukan, DKA berada dalam keadaan menerima.
Dalam kebanyakan kasus, membangun NKV jauh lebih mudah daripada DKA. Namun meskipun demikian, penggunaan NKA untuk pemodelan bukanlah yang terbaik ide bagus. Untungnya, untuk setiap NFA dimungkinkan untuk membuat DFA yang menerima bahasa masukan yang sama. Pada artikel ini kami tidak akan menyajikan algoritma untuk membangun DFA menggunakan NFA, tetapi kami akan mempertimbangkan algoritma ini berdasarkan contoh yang jelas di bawah.
Membangun DFA minimal menggunakan ekspresi reguler
Untuk memulainya, berikut adalah daftar operasi RT yang digunakan dalam artikel ini, berdasarkan prioritas:
- iterasi (penutupan Kleene), menggunakan simbol "*"
- penggabungan ditentukan menggunakan spasi atau string kosong (misalnya: ab)
- bergabung menggunakan simbol "|".
Mari kita lihat contoh dimana ekspresi reguler diberikan:
Xy* (x | kamu*) | ab (x | y*) | (x | a*) (x | y*)
Penting untuk membuat DFA minimal menggunakan ekspresi reguler dan mendemonstrasikan pengenalan rantai yang benar dan salah.
Untuk memulainya, mari kita sederhanakan RV ini, dengan menggunakan hukum distributif rangkaian kanan terhadap penyatuan, kita memperoleh RV berikut:
(xy* | ab | (x | a*)) (x | y*)
Sekarang kita membuat robot berdasarkan RV ini:
Menurut aturan untuk mengubah rangkaian (kami tidak akan memberikan aturan untuk mengubah PB menjadi KA, karena cukup jelas), kami memperoleh otomat berikut:
Menurut aturan transformasi serikat pekerja:
Menurut aturan transformasi penggabungan:
Dan pada akhirnya kita menerapkan aturan transformasi penutupan dan mendapatkan εNKA. Di sini perlu dibuat reservasi bahwa εNKA adalah NKA yang mengandung transisi ε. Pada gilirannya, transisi ε adalah transisi di mana mesin tidak memperhitungkan rantai input atau, dengan kata lain, transisi sepanjang simbol kosong.
Kita menghilangkan transisi ε (“tanda bintang” menunjukkan keadaan akhir):
Dalam NFA ini, keadaan s3 dan s5 adalah ekuivalen, karena δ(s3, x) = δ(s5, x) = s1 dan δ(s3, y) = δ(s5, y) = s5, s7. Ganti nama negara bagian s6 -> s5 dan s7 -> s6:
Kami membangun DKA menurut NKA:
Dalam DFA ini, keadaan p1 dan p5 adalah ekuivalen, karena
δ(p1, x) = δ(p5, x) = p4 dan δ(p1, y) = δ(p5, y) = p5. Ganti nama negara bagian p6 -> p5 dan p7 -> p6:
Mesin ini minimal DKA.
Misalkan δ adalah fungsi transisi, maka kita menyatakan fungsi transisi yang diperluas yang dibangun dari δ dengan δ’, dan ω adalah rantai masukan.
Misalkan inputnya adalah rantai ω = aaax, kita berharap mesin berada di salah satu status penerimaan.
δ'(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4
P4 adalah keadaan akhir yang valid, sehingga rantai aaax benar untuk mesin ini.
Sekarang mari kita asumsikan bahwa ω = xyyb:
δ'(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅
Di sini kita melihat bahwa jika kita memberikan simbol b pada input otomat ketika dalam keadaan p1, maka otomat ini akan mati, oleh karena itu rantai xyyb salah.
P. S. Artikel ini membahas algoritme untuk membuat DFA menggunakan RT, tetapi ada algoritme yang lebih mudah digunakan, khususnya untuk pemrograman, tetapi ini adalah topik untuk artikel lain...
DKA adalah kasus khusus dari NKA. Di dalam dia:
tidak ada keadaan dengan transisi ε;
untuk setiap keadaan S dan simbol masukan a, terdapat paling banyak satu busur yang berasal dari S dan diberi label a.
DFA hanya memiliki maksimal satu transisi untuk setiap simbol masukan dari setiap negara bagian. Jika tabel digunakan untuk mewakili fungsi transisi DFA, maka setiap record hanya akan berisi satu status. Dengan demikian, mudah untuk memeriksa apakah DFA tertentu mengizinkan garis tertentu, karena hanya ada satu jalur dari keadaan awal, yang ditandai dengan garis ini.
Gambar 3 menunjukkan grafik transisi DFA yang menerima bahasa yang sama (a|b) * a(a|b)(a|b) seperti NFA pada Gambar 1.
Gambar 3. DFA mengizinkan string (a|b) * a(a|b)(a|b).
Sebuah robot terbatas deterministik M yang menerima bahasa tertentu:
M = ((1, 2, 3, 4, 5, 6, 7, 8), (a, b), D, 1, (3, 5, 6, 8))
Fungsi transisi D didefinisikan sebagai berikut:
Membangun nka menggunakan ekspresi reguler
1. Untuk ε NKA mempunyai bentuk sebagai berikut (0 – keadaan awal, 1 – akhir):
2. Untuk yang termasuk dalam bahasa NKA tertentu:
3. Misalkan N(s) dan N(t) adalah NFA untuknya ekspresi reguler s dan t.
Untuk ekspresi reguler s|t, NFA komposit memiliki bentuk berikut:
B. Untuk ekspresi reguler st NKA:
Dengan. Untuk ekspresi s* NFA mempunyai bentuk:
D. Untuk ekspresi dalam tanda kurung (s), digunakan NFA N(s) seperti pada poin a.
Setiap negara bagian baru menerima nama individu. Pembangunan satelit N(r) memiliki properti berikut:
N(r) memiliki jumlah negara bagian yang tidak melebihi jumlah simbol lebih dari 2 kali.
N(r) mempunyai tepat satu keadaan awal dan satu keadaan akhir. Keadaan akhir tidak mempunyai transisi keluar.
Setiap keadaan N(r) mempunyai 1 transisi untuk simbol dari alfabet (), atau tidak lebih dari 2 transisi ε keluar.
Mengubah nka menjadi dka.
NFA pada Gambar 1 memiliki 2 transisi dari keadaan 0 untuk simbol a: keadaan 0 dan 1. Transisi tersebut bersifat ambigu, seperti transisi pada ε. Memodelkan satelit tersebut menggunakan program komputer jauh lebih sulit. Definisi kelayakan menyatakan bahwa harus ada beberapa jalur dari keadaan awal ke keadaan akhir, tetapi ketika ada beberapa jalur untuk string masukan yang sama, semuanya harus dipertimbangkan untuk menemukan jalur ke keadaan akhir atau mengetahui bahwa ada tidak ada jalan seperti itu.
Dalam tabel transisi NKA, setiap entri berhubungan dengan banyak negara bagian, namun dalam tabel transisi DKA, hanya ada satu. Inti dari transformasi ini adalah bahwa setiap status DFA berhubungan dengan sekumpulan status NFA. DFA menggunakan statusnya untuk melacak semua kemungkinan status di mana NFA berada setelah membaca simbol masukan berikutnya. Artinya, setelah membaca aliran masukan, DFA berada dalam keadaan yang mewakili serangkaian keadaan NFA tertentu, yang dapat dijangkau dari keadaan awal di sepanjang jalur yang sesuai dengan string masukan. Jumlah negara bagian DFA tersebut dapat secara signifikan melebihi jumlah negara bagian NFA (ketergantungan eksponensial), tetapi dalam praktiknya hal ini sangat jarang terjadi, dan terkadang jumlah negara bagian di DFA bahkan lebih sedikit daripada di NFA.
Mari kita pertimbangkan transformasi seperti itu menggunakan contoh spesifik. Gambar 4 menunjukkan NFA lain yang mengizinkan bahasa (a|b) * a(a|b)(a|b) (seperti pada Gambar 1 dan 3).
Gambar 4. NFA mengizinkan bahasa (a|b) * a(a|b)(a|b)
Transisi dari keadaan 13 ke keadaan 14 yang ditunjukkan pada gambar dapat direpresentasikan dengan cara yang sama dengan transisi dari keadaan ke-8 ke ke-13.
Mari buat DFA untuk bahasa ini. Keadaan awal dari DFA ekuivalen adalah keadaan A = (0, 1, 2, 4, 7), yaitu keadaan yang dapat dicapai dari 0 dengan ε.
Alfabet simbol masukannya adalah (a,b). Dari keadaan awal A, kita dapat menghitung keadaan yang dapat dicapai oleh a. Kita sebut keadaan ini B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14).
Di antara negara bagian di A, hanya negara bagian 4 yang mengalami transisi sepanjang b ke negara bagian 5, sehingga DKA memiliki transisi sepanjang b dari A ke negara bagian C = (1, 2, 4, 5, 6, 7).
Jika kita melanjutkan proses ini dengan negara bagian B dan C, semua rangkaian negara bagian NFA akan ditandai. Jadi kita akan memiliki kumpulan negara bagian:
SEBUAH = (0, 1, 2, 4, 7)
B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)
C = (1, 2, 4, 5, 6, 7)
D = (10, 12, 13, 14)
Keadaan A adalah keadaan awal, dan keadaan B, D, E adalah keadaan akhir.
Tabel transisi lengkap diberikan di bawah ini.
Di bawah pada Gambar 5 adalah DFA itu sendiri untuk bahasa ini.
Gambar 5. Bahasa penerima DFA (a|b) * a(a|b)(a|b)
Daftar literatur bekas:
Pentus A.E., Pentus M.R. – Teori bahasa formal
A. Aho, R. Sethi, D. Ullman - Penyusun: prinsip, teknologi, alat.
Lebih mudah untuk mendeskripsikan kosakata suatu bahasa dalam bentuk ekspresi reguler, dan mengenali bahasa tersebut menggunakan CA. Oleh karena itu, penting untuk dapat mengubah definisi bahasa yang berupa ekspresi reguler menjadi definisi dalam bentuk CA. Transformasi ini diusulkan oleh Kenneth Thompson.
Mesin keadaan terbatas adalah lima (S, S, d, S 0 , F)
S adalah himpunan keadaan yang terbatas.
S adalah sekumpulan sinyal masukan valid yang terbatas.
d - fungsi transisi. Ini mencerminkan himpunan Sx(SÈ(e)) ke dalam himpunan keadaan robot terbatas non-deterministik. Untuk otomat deterministik, fungsi transisi mencerminkan himpunan SxS ke dalam himpunan status otomat. Dengan kata lain, bergantung pada keadaan dan simbol masukan, d menentukan keadaan baru mesin.
S 0 - keadaan awal robot terbatas, S 0 О S.
F adalah himpunan keadaan akhir robot, F О S.
Pengoperasian mesin keadaan terbatas merupakan serangkaian langkah. Langkahnya ditentukan oleh keadaan mesin dan simbol masukan. Langkahnya sendiri terdiri dari mengubah keadaan mesin dan membaca simbol selanjutnya dari urutan masukan.
Ada aturan berikut mengubah ekspresi reguler menjadi mesin negara.
1 Ekspresi reguler “e” diubah menjadi otomat dua keadaan dan transisi elektronik di antara keduanya (Gambar 1).
Gambar 1. – Mesin otomatis untuk e-transisi
2 Ekspresi reguler dari satu karakter "a" diubah menjadi otomat terbatas dari dua keadaan dan transisi di antara keduanya berdasarkan sinyal input a (Gambar 2).
Gambar 2. – Mesin otomatis untuk bergerak dengan simbol a
3 Misalkan terdapat ekspresi reguler rs dan mesin keadaan terbatas untuk ekspresi r dan ekspresi s telah dibuat. Kemudian dua mesin dihubungkan secara seri. Gambar 3 menunjukkan automata asli untuk bahasa r dan s. Gambar tersebut menunjukkan robot untuk mengenali rangkaian bahasa-bahasa ini.
Mesin untuk r Mesin untuk s
Gambar 3. – Automata awal
Gambar 4. – Mesin penggabungan bahasa
4 Misalkan ada ekspresi reguler r | s dan mesin negara terbatas telah dibangun untuk ekspresi r dan ekspresi s (Gambar 3). Maka automaton yang dihasilkan harus mempunyai alternatif untuk mengeksekusi salah satu dari dua automata tersebut. Artinya, sebuah otomat untuk ekspresi r | s untuk automata untuk r dan s dari Gambar 3 memiliki bentuk seperti pada Gambar 5.
Gambar 5. – Mesin otomatis untuk menggabungkan bahasa
5 Misalkan terdapat ekspresi reguler r* untuk otomat terbatas yang dikonstruksikan r. Dalam hal ini, dua keadaan baru diperkenalkan untuk memungkinkan untuk melewati ekspresi otomat r, dan juga memperkenalkan transisi e antara keadaan akhir dan awal untuk memungkinkan pengulangan otomat r beberapa kali. Jika untuk ekspresi reguler r sebuah otomat yang mirip dengan Gambar 3 dibuat, maka ekspresi reguler r* sesuai dengan otomat terbatas yang disajikan pada Gambar 6.
Pada bagian ini, kami akan merumuskan isu-isu penting terkait bahasa reguler. Pertama, Anda perlu memahami apa artinya mengajukan pertanyaan tentang bahasa tertentu. Bahasa pada umumnya tidak terbatas, jadi tidak masuk akal untuk menyajikan string bahasa tersebut kepada seseorang dan mengajukan pertanyaan yang memerlukan pengujian string dalam jumlah tak terbatas. Jauh lebih masuk akal untuk menggunakan salah satu representasi bahasa yang terbatas, yaitu: DFA, NFA, ε-NFA atau ekspresi reguler.
Jelas sekali, bahasa yang direpresentasikan dengan cara ini akan menjadi bahasa biasa. Benar-benar tidak ada cara untuk merepresentasikan bahasa yang sepenuhnya arbitrer. Bab-bab berikut mengusulkan metode terbatas untuk mendeskripsikan kelas yang lebih luas daripada kelas bahasa biasa, dan dari sana dimungkinkan untuk mempertimbangkan pertanyaan tentang bahasa. Namun, algoritma untuk menyelesaikan banyak pertanyaan tentang bahasa hanya ada untuk kelas bahasa biasa. Pertanyaan-pertanyaan yang sama menjadi “tidak dapat diputuskan” (tidak ada algoritma untuk menjawab pertanyaan-pertanyaan ini) jika pertanyaan-pertanyaan tersebut diajukan menggunakan notasi yang lebih “ekspresif” (digunakan untuk mengekspresikan variasi bahasa yang lebih luas) dibandingkan representasi yang dikembangkan untuk bahasa biasa.
Mari kita mulai mempelajari algoritme untuk pertanyaan tentang bahasa biasa dengan melihat cara satu representasi bahasa diubah ke bahasa lain. Secara khusus, mari kita pertimbangkan kompleksitas waktu dari algoritma yang melakukan transformasi. Kemudian kita akan melihat tiga pertanyaan dasar tentang bahasa.
1. Apakah bahasa yang dideskripsikan merupakan himpunan kosong?
2. Apakah beberapa string w termasuk dalam bahasa yang diwakili?
3. Apakah memang ada dua? deskripsi yang berbeda mewakili bahasa yang sama? (Masalah ini sering disebut “kesetaraan” bahasa.)
2.1 Konversi antara representasi bahasa yang berbeda
Masing-masing dari empat representasi bahasa reguler dapat dikonversi ke salah satu dari tiga representasi lainnya. Pada Gambar. 3.1 menunjukkan transisi dari satu representasi ke representasi lainnya. Meskipun ada algoritma untuk setiap transformasi ini, terkadang kita tertarik tidak hanya pada kelayakan transformasi tertentu, tetapi juga pada waktu yang dibutuhkan untuk menyelesaikannya. Secara khusus, penting untuk membedakan algoritme yang memerlukan waktu eksponensial (waktu sebagai fungsi dari ukuran data masukan) dan oleh karena itu hanya dapat dieksekusi untuk data masukan berukuran relatif kecil, dari algoritme yang waktu eksekusinya linier, kuadratik. , atau derajat polinomial rendah sebagai fungsi dari ukuran data masukan. Algoritme yang terakhir ini “realistis” karena dapat dieksekusi untuk kelas contoh masalah yang lebih luas. Mari kita lihat kompleksitas waktu dari setiap transformasi yang dibahas.
Konversi NKA ke DKA
Waktu eksekusi untuk mengubah NFA atau ε-NFA menjadi DFA dapat berupa fungsi eksponensial dari jumlah status NFA. Untuk memulainya, menghitung penutupan ε dari n keadaan membutuhkan waktu O(n3). Kita perlu mencari semua busur dengan label ε yang mengarah dari masing-masing n keadaan. Jika terdapat n negara bagian, maka paling banyak terdapat n2 busur. Penggunaan yang wajar sumber daya sistem dan struktur data yang dirancang dengan baik memastikan bahwa waktu untuk menjelajahi setiap negara bagian tidak melebihi O(n2). Faktanya, untuk mengevaluasi seluruh penutupan ε satu kali, seseorang dapat menggunakan algoritma penutupan transitif seperti algoritma Warshall5.
Setelah menghitung ε-closure, kita dapat melanjutkan ke sintesis DFA menggunakan konstruksi himpunan bagian. Pengaruh utama pada konsumsi waktu diberikan oleh jumlah status DFA, yang bisa sama dengan 2n. Untuk setiap keadaan, transisi dapat dihitung dalam waktu O(n3) menggunakan ε-closure dan tabel transisi NFA untuk setiap simbol masukan. Misalkan kita perlu menghitung δ((q1, q2, …, qk), a) untuk DFA. Dari masing-masing keadaan qi seseorang dapat mencapai paling banyak n keadaan sepanjang jalur berlabel ε, dan masing-masing keadaan ini dapat mempunyai paling banyak n busur berlabel a. Dengan membuat array yang diindeks berdasarkan negara bagian, kita dapat menghitung gabungan paling banyak n himpunan dari paling banyak n negara bagian dalam waktu yang sebanding dengan n2.
Dengan cara ini, untuk setiap keadaan qi, seseorang dapat menghitung himpunan keadaan yang dapat dicapai dari qi sepanjang jalur berlabel a (mungkin termasuk busur berlabel ε). Karena k ≤ n, terdapat paling banyak n keadaan qi, dan untuk masing-masing keadaan tersebut, menghitung keadaan yang dapat dijangkau memerlukan waktu O(n2). Dengan demikian, waktu keseluruhan menghitung status yang dapat dijangkau adalah O(n3). Menggabungkan kumpulan status yang dapat dijangkau hanya memerlukan O(n2) waktu tambahan, sehingga menghitung satu transisi DFA memerlukan waktu O(n3).
Perhatikan bahwa jumlah simbol masukan dianggap konstan dan tidak bergantung pada n. Jadi, baik dalam perkiraan waktu berjalan ini maupun lainnya, jumlah simbol masukan tidak dipertimbangkan. Ukuran alfabet masukan hanya mempengaruhi faktor konstanta yang tersembunyi dalam notasi “O Besar”.
Jadi, waktu untuk mengubah NKA menjadi DKA, termasuk situasi ketika NKA mengandung transisi ε, adalah O(n32n). Tentu saja, dalam praktiknya, biasanya jumlah negara bagian yang dibangun jauh lebih sedikit dari 2n. Terkadang hanya ada n dari mereka. Oleh karena itu, kita dapat mengatur perkiraan waktu berjalan ke O(n3s), dengan s adalah jumlah status yang sebenarnya dimiliki DFA.
Konversi DKA ke NKA
Ini adalah transformasi sederhana yang memerlukan waktu O(n) untuk DFA dengan n status. Yang perlu dilakukan hanyalah mengubah tabel transisi untuk DFA dengan mengapit status dalam tanda kurung () dan juga menambahkan kolom untuk ε jika ingin mendapatkan ε-NFA. Karena jumlah simbol masukan (yaitu lebar tabel lompat) diasumsikan konstan, penyalinan dan pemrosesan tabel memerlukan waktu O(n).
Mengubah automaton menjadi ekspresi reguler
Di setiap n tahapan (di mana n adalah jumlah status DFA), ukuran ekspresi reguler yang dibuat dapat meningkat empat kali lipat, karena setiap ekspresi dibuat dari empat ekspresi dari siklus sebelumnya. Dengan demikian, entri sederhana n3 ekspresi dapat memakan waktu O(n34n). Desain yang ditingkatkan dari Bagian 3.2.2 mengurangi faktor konstanta namun tidak mempengaruhi eksponensial masalah ini (dalam kasus terburuk).
Konstruksi serupa memerlukan waktu berjalan yang sama jika NFA, atau bahkan ε-NFA, dikonversi, tetapi hal ini tidak dibuktikan di sini. Namun, penggunaan desain untuk satelit telah sangat penting. Jika Anda terlebih dahulu mengubah NFA menjadi DFA, lalu DFA menjadi ekspresi reguler, maka diperlukan waktu O(n34n32n), yaitu eksponensial ganda.
Mengubah ekspresi reguler menjadi robot
Mengonversi ekspresi reguler menjadi ε-NFA akan memerlukan waktu linier. Anda perlu mengurai ekspresi reguler secara efisien menggunakan metode yang membutuhkan waktu O(n) untuk ekspresi reguler dengan panjang n6. Hasilnya adalah sebuah pohon dengan satu simpul untuk setiap karakter ekspresi reguler (walaupun tanda kurung tidak muncul di pohon ini, karena tanda kurung hanya mengontrol penguraian ekspresi).
Pohon yang dihasilkan dari ekspresi reguler tertentu dapat diproses dengan membuat ε-NFA untuk setiap node. Aturan transformasi ekspresi reguler yang disajikan di Bagian 3.2.3 tidak pernah menambahkan lebih dari dua status dan empat busur ke setiap simpul pohon ekspresi. Akibatnya, jumlah negara bagian dan jumlah busur dari ε-NFA yang dihasilkan sama dengan O(n). Selain itu, pekerjaan pembuatan elemen-elemen ini pada setiap node pohon analisis adalah konstan, asalkan fungsi yang memproses setiap subpohon mengembalikan pointer ke status awal dan status penerimaan robot tersebut.
Kami sampai pada kesimpulan bahwa membangun ε-NFA menggunakan ekspresi reguler membutuhkan waktu, bergantung secara linear pada ukuran ekspresi. Transisi ε dapat dihilangkan dari ε-NFA dengan n status dengan mengubahnya menjadi NFA reguler dalam waktu O(n3) dan tanpa menambah jumlah status. Namun, konversi ke DKA memerlukan waktu yang sangat lama.
Diperlukan oleh mesin keadaan terbatas non-deterministik M = (Q, T, D, Q 0 , F) membangun robot terbatas deterministik M = (Q", T, D", Q" 0 , F"). Keadaan awal otomat yang sedang dibangun adalah penutupan ε dari keadaan awal otomat asli. ε-closure adalah sekumpulan keadaan yang dapat dicapai dari keadaan tertentu melalui transisi sepanjang ε. Lebih jauh lagi, meskipun terdapat keadaan-keadaan yang transisinya belum dibangun (transisi dibuat sepanjang simbol-simbol yang transisinya ada pada otomat aslinya), untuk setiap simbol, penutupan ε dari himpunan keadaan-keadaan yang dapat dijangkau dari keadaan yang dipertimbangkan melalui transisi sepanjang simbol yang dipertimbangkan dihitung. Jika keadaan yang sesuai dengan himpunan yang ditemukan sudah ada, maka transisi ditambahkan di sana. Jika tidak, maka status baru yang diterima akan ditambahkan.
Contoh
Inisialisasi
Keadaan yang berhubungan dengan penutupan ε dari keadaan awal ditandai. Negara-negara bagian ini akan sesuai dengan negara bagian A DKA masa depan.
Iterasi pertama
Dari penutupan ε terdapat transisi ke keadaan NKA 3 dan 10 (menurut A Dan C, masing-masing). Untuk keadaan 3, penutupan ε adalah himpunan keadaan (3, 4, 6), untuk keadaan 10 - (10). Mari kita nyatakan status DFA baru yang sesuai dengan himpunan ini sebagai B Dan C.
| kondisi DKA | Banyak negara bagian NKA | |||
|---|---|---|---|---|
| A | B | C | ||
| A | {1, 2, 9} | B | - | C |
| B | {3, 4, 6} | - | - | - |
| C | {10} | - | - | - |
Iterasi kedua
Dari kumpulan status NFA (3, 4, 6), sesuai dengan status DFA B ada dua transisi - ke keadaan 5 (oleh B) dan 7 (oleh C). Penutupan ε-nya berpotongan, tetapi himpunannya sendiri berbeda, sehingga dikaitkan dengan dua status DFA baru - D Dan E. Dari negara bagian NKA yang sesuai dengan negara bagian DKA C, tidak ada transisi.
| kondisi DKA | Banyak negara bagian NKA | Simbol yang digunakan untuk bernavigasi | ||
|---|---|---|---|---|
| A | B | C | ||
| A | {1, 2, 9} | B | - | C |
| B | {3, 4, 6} | - | D | E |
| C | {10} | - | - | - |
| D | {2, 5, 8, 9} | - | - | - |
| E | {2, 7, 8, 9} | - | - | - |
Iterasi ketiga
Dari kumpulan status NFA yang sesuai dengan status DFA D Dan E transisi dilakukan ke himpunan keadaan yang sesuai dengan keadaan yang ada (dari himpunan (2, 5, 8, 9) yang sesuai dengan keadaan tersebut D, Oleh A transisi ke keadaan 3, milik himpunan (3, 4, 6), sesuai dengan keadaan DFA B, Oleh C- transisi ke negara bagian 10, sesuai dengan negara bagian C; demikian pula untuk himpunan yang sesuai dengan status DFA E). Proses pembuatan tabel negara bagian dan transisi DKA telah selesai.
| kondisi DKA | Banyak negara bagian NKA | Simbol yang digunakan untuk bernavigasi | ||
|---|---|---|---|---|
| A | B | C | ||
| A | {1, 2, 9} | B | - | C |
| B | {3, 4, 6} | - | D | E |
| C | {10} | - | - | - |
| D | {2, 5, 8, 9} | B | - | C |
| E | {2, 7, 8, 9} | B | - | C |
Hasil:
Konstruksi tata bahasa linier kanan menggunakan finite automaton
Kami menetapkan nonterminal untuk setiap negara bagian. Jika terjadi peralihan dari negara X dalam sebuah keadaan Y Oleh A, tambahkan aturan X → ay. Tambahkan aturan untuk keadaan akhir X→ ε. Untuk transisi ε - X → Y.
Contoh 1 (mesin keadaan terbatas deterministik)
- SEBUAH → A B | C C
- B → B D | C E
- C → ε
- D → A B | C C
- E → A B | C C
Contoh 2 (mesin keadaan terbatas non-deterministik)
- 1 → 2 | 9
- 2 → A 3
- 3 → 4 | 6
- 4 → B 5
- 5 → 8
- 6 → C 7
- 7 → 8
- 8 → 2 | 9
- 9 → C 10
- 10→ε
Pembangunan DFA dari RT
Biarkan ada ekspresi reguler R. Dengan menggunakan ekspresi reguler ini, perlu untuk membangun robot terbatas deterministik D seperti yang L(D) = L(R).
Modifikasi Ekspresi Reguler
Mari kita tambahkan simbol yang menunjukkan akhir RT - “#”. Hasilnya, kami mendapatkan ekspresi reguler ( R)#.
Membangun pohon
Mari kita bayangkan ekspresi reguler sebagai pohon, yang daunnya merupakan simbol terminal, dan simpul internal adalah operasi penggabungan ".", gabungan "∪" dan iterasi "*". Kami akan menetapkan nomor unik untuk setiap daun pohon (kecuali daun ε) dan merujuknya, di satu sisi, sebagai posisi di pohon dan, di sisi lain, sebagai posisi simbol yang sesuai dengan daun.
Evaluasi fungsi nullable, firstpos, lastpos
Sekarang, melintasi pohon T dari bawah ke atas dari kiri ke kanan, kita menghitung tiga fungsi: dapat dibatalkan, pos pertama, Dan pos terakhir. Fungsi dapat dibatalkan, pos pertama Dan pos terakhir didefinisikan pada simpul pohon. Arti dari semua fungsi kecuali dapat dibatalkan, adalah sekumpulan posisi. Fungsi pos pertama(N) untuk setiap node n dari pohon sintaksis ekspresi reguler memberikan himpunan posisi yang sesuai dengan karakter pertama dalam substring yang dihasilkan oleh subekspresi dengan titik di N. Juga, pos terakhir(N) memberikan himpunan posisi yang sesuai dengan karakter terakhir dalam substring yang dihasilkan oleh subekspresi dengan titik puncak N. Untuk node N, yang subpohonnya (yaitu pohon yang simpulnya N adalah root) dapat menghasilkan kata kosong, kita definisikan dapat dibatalkan(N) = BENAR, dan untuk node yang tersisa PALSU. Tabel perhitungan dapat dibatalkan, pos pertama, pos terakhir:
| simpul N | dapat dibatalkan(N) | pos pertama(N) | pos terakhir(N) |
|---|---|---|---|
| ε | BENAR | ∅ | ∅ |
| Saya ≠ ε | PALSU | {Saya} | {Saya} |
| u∪v | dapat dibatalkan(kamu) atau dapat dibatalkan(ay) | pos pertama(kamu) ∪ pos pertama(ay) | pos terakhir(kamu) ∪ pos terakhir(ay) |
| kamu. ay | dapat dibatalkan(kamu) Dan dapat dibatalkan(ay) | jika dapat dibatalkan(kamu) Kemudian pos pertama(kamu) ∪ pos pertama(ay) kalau tidak pos pertama(kamu) | jika dapat dibatalkan(ay) Kemudian pos terakhir(kamu) ∪ pos terakhir(ay) kalau tidak pos terakhir(ay) |
| v* | BENAR | pos pertama(ay) | pos terakhir(ay) |
Membangun pos tindak lanjut
Fungsi pos tindak lanjut dihitung melalui dapat dibatalkan, pos pertama Dan pos terakhir. Fungsi pos tindak lanjut didefinisikan dalam banyak posisi. Arti pos tindak lanjut adalah sekumpulan posisi. Jika Saya- posisi, kalau begitu pos tindak lanjut(Saya) ada banyak posisi J sedemikian rupa sehingga ada string tertentu... CD..., termasuk dalam bahasa yang dijelaskan oleh RT, sedemikian rupa Saya cocok dengan kejadian ini C, A J- kejadian D. Fungsi pos tindak lanjut juga dapat dihitung dalam satu traversal pohon menggunakan dua aturan berikut
- Membiarkan N- simpul internal dengan operasi "." (rangkaian); A, B- keturunannya. Kemudian untuk setiap posisi Saya termasuk dalam pos terakhir(A pos tindak lanjut(Saya) sekelompok pos pertama(B).
- Membiarkan N- simpul internal dengan operasi “*” (iterasi), A- keturunannya. Kemudian untuk setiap posisi Saya termasuk dalam pos terakhir(A), ditambahkan ke kumpulan nilai pos tindak lanjut(Saya) sekelompok pos pertama(A).
Contoh
Hitung nilai fungsi pos tindak lanjut untuk ekspresi reguler ( A(B|C))*C.
| Posisi | Arti pos tindak lanjut |
|---|---|
| 1: (A (B|C))*C | {2, 3} |
| 2: (A(B |C))*C | {1, 4} |
| 3: (A(B|C ))*C | {1, 4} |
| 4: (A(B|C))*C | {5} |
Konstruksi DFA
DFA mewakili sekumpulan status dan serangkaian transisi di antara status tersebut. Negara bagian DKA mewakili banyak posisi. Pembangunan DFA terdiri dari penambahan negara-negara yang diperlukan secara bertahap dan membangun transisi untuk negara-negara tersebut. Awalnya ada satu negara bagian, pos pertama(akar) (akar- akar pohon) yang transisinya belum dibuat. Transisi dilakukan menggunakan karakter dari ekspresi reguler. Setiap karakter berhubungan dengan serangkaian posisi ( P Saya). Menyatukan semua orang pos tindak lanjut(x) adalah negara bagian yang perlu dipindahkan, di mana x adalah posisi yang ada di antara posisi negara bagian tersebut dan di antara posisi simbol dari RF yang dilalui transisi tersebut. Kalau tidak ada keadaan seperti itu, maka harus ditambah. Proses ini harus diulang sampai semua transisi untuk semua negara bagian telah selesai dibangun. Semua negara bagian yang memuat posisi simbol # yang ditambahkan di akhir PB dinyatakan final.
DKA diperoleh dari RV ( A(B|C))*C
Contoh
Buat DFA menggunakan ekspresi reguler ( A(B|C))*C.
| kondisi DKA | Simbol | ||
|---|---|---|---|
| sebuah (1) | b (2) | c (3, 4) | |
| SEBUAH (1, 4) | B (2, 3) | - | C (5) |
| B (2, 3) | - | SEBUAH (1, 4) | SEBUAH (1, 4) |
| C (5) | - | - | - |
Pembangunan DFA dengan jumlah negara bagian minimum
DFA dengan jumlah negara bagian minimum dibuat untuk DFA yang ditentukan di mana pun, yaitu. seperti yang . Untuk DFA apa pun, ada DFA yang setara di mana pun.
Konstruksi DFA yang ditentukan di mana-mana
Mari kita perkenalkan negara bagian baru dan tentukan kumpulan negara bagian baru 
.
Mari kita definisikan fungsi transisi baru seperti ini:
Konstruksi partisi (formal)
Mari kita buat partisi awal P kumpulan negara bagian menjadi dua kelompok: negara bagian akhir F dan sisanya S\F, yaitu. P = {F, Tanya Jawab}.
Terapkan ke setiap kelompok G ∈ P prosedur berikut. Menghancurkan G menjadi subkelompok sehingga menyatakan S Dan T dari G berada dalam grup yang sama jika dan hanya jika untuk setiap simbol masukan A negara S Dan T mengalami transisi A menjadi negara bagian dari kelompok yang sama menjadi P.
Kami menambahkan subgrup yang dihasilkan ke partisi baru P baru.
Kami menerima P = P baru dan ulangi konstruksi partisi hingga stabil, yaitu hingga partisi berhenti berubah.
Konstruksi partisi (algoritma)
Untuk membangun partisi, ada algoritma berikut. Kami membuat tabel transisi untuk automaton asli, kami membangun partisi awal.
Kami menetapkan pengidentifikasi untuk setiap grup dari partisi (untuk partisi awal, misalnya, 0 dan 1).
Untuk setiap negara bagian (setiap baris tabel) kami menetapkan string dalam bentuk "a.bcd...xyz", di mana adalah pengidentifikasi grup tempat negara bagian tersebut berasal [kolom pertama (dari mana kita pergi) , kolom kedua (di mana kita menggunakan karakter pertama), ..., kolom terakhir (di mana kita menggunakan karakter terakhir)].
Kami membangun grup baru berdasarkan kebetulan string, yaitu, sehingga negara bagian dengan string identik dimasukkan ke dalam satu grup.
Kemudian, iterasi baru. Kami menetapkan pengidentifikasi baru ke grup yang dihasilkan, misalnya (0, 1, ..., n). Dan kami ulangi pembangunan partisi hingga stabil.
Perhatikan bahwa ketika hanya ada satu negara bagian yang tersisa dalam grup, pada tahap selanjutnya dalam membangun partisi, tidak perlu menuliskan string pengidentifikasi untuk negara ini, karena string ini bagaimanapun juga akan menjadi unik karena karakter pertama dari talinya. Dengan kata lain, ketika dipecah, tidak akan terjadi apa-apa pada grup dari satu negara bagian - grup tersebut ditransfer ke pemisahan baru apa adanya.
Konstruksi robot tereduksi
Masing-masing grup yang dihasilkan menjadi status DFA baru. Jika suatu grup berisi keadaan awal (final) dari robot asli, maka grup ini menjadi keadaan awal (final) dari DFA baru. Transisi dibangun dengan cara yang jelas: transisi ke suatu keadaan dari suatu kelompok dianggap sebagai transisi ke suatu kelompok.
Kami membawa senapan mesin. Pertama-tama kita membuang yang tidak menghasilkan (steril, “mati”), Kemudian keadaan yang tidak dapat dijangkau (definisi diberikan untuk simbol, tetapi jelas ditransfer ke keadaan robot).
Secara umum, menghapus negara-negara mati mengubah DFA menjadi NFA, karena dalam DFA semua transisi harus didefinisikan. Namun, dalam Buku Naga, penyimpangan dari definisi formal masih dianggap dapat diterima.
Contoh
Untuk membuat DFA dengan nomor negara bagian minimum untuk DFA dengan bentuk berikut:
- Partisi awal: (C) ( keadaan akhir), (A, B, D, E) ( semua negara bagian lainnya).
- (C) ( tanpa perubahan), (A, D, E), (B), ( karena dari A, D, E kita masing-masing melewati a, c ke B dan C).
- Kita tidak bisa membuat perpecahan lagi.
Misalkan grup (C) berkorespondensi dengan negara bagian C, grup (A, D, E) berkorespondensi dengan negara bagian A, dan grup (B) berkorespondensi dengan negara bagian B. Kemudian kita memperoleh DFA dengan jumlah negara bagian minimum:
Contoh (algoritma untuk membangun partisi)
Tabel transisi untuk DFA yang ditentukan di mana pun (keadaan Z ditambahkan) yang sesuai dengan RT (ab|ε)a*|abb|b*a. Dari tugas ujian tahun 2012.
| A | B | saya 0 | saya 1 | |
|---|---|---|---|---|
| →SEBUAH* | B | C | 0.01 | 0.12 |
| B* | D | E | 0.00 | 1.01 |
| C | F | C | 1.01 | |
| D* | D | Z | 0.01 | 0.04 |
| E* | D | Z | 0.00 | 1.03 |
| F* | Z | Z | 0.11 | |
| Z | Z | Z | 1.11 |
Iterasi:
- Saya 0: ABCDEF(0), CZ(1).
- Saya 1: IKLAN(0), MENJADI(1), C(2), F(3), Z(4).
- Saya 2: A, B, C, D, E, F, Z.
Hasilnya: mesin sudah memiliki jumlah minimum status :-)
DKA memungkinkan penambahan lidah
Algoritme untuk membuat DFA yang menerima komplemen bahasa L(L̅) terdiri dari dua langkah:
- Konstruksi DFA lengkap
- Membangun robot yang diinginkan darinya
Faktanya, tidak ada DKA yang lengkap. Di bawah DKA penuh beberapa guru memahami robot yang tabel transisinya tidak memiliki sel kosong. Namun, sesuai dengan definisi DFA - δ: Q × Σ → Q - dalam hal apa pun tidak boleh ada sel kosong. Namun, robot “dengan sel kosong” memenuhi definisi NFA. Selama penyelesaian, kita sering kali hanya mendapatkan NFA yang tidak memiliki transisi ke DFA.
Untuk mengisinya kembali, cukup menambahkan negara bagian baru X, dan “alih-alih” transisi yang tidak ada menambahkan transisi ke keadaan baru ini. Pada saat yang sama, Anda harus ingat untuk menambahkan transisi dari X V X. Sangat mudah untuk melihat bahwa ketika mesin asli tidak menerima rantai tertentu karena kurangnya transisi, mesin baru akan masuk ke negara bagian X dan terjebak di dalamnya. Karena negara bagian baru tidak menerima (final), mesin baru juga tidak akan menerima rantai ini.
Sekarang, untuk membangun robot yang diperlukan, yang diperlukan hanyalah mengubah peran negara penerima dan non-penerima. Dengan kata lain, F" = Q\F.
Konstruksi penganalisis LL(k).
Konversi Tata Bahasa
Tidak semua tata bahasa dapat dianalisis LL(k). Tata bahasa bebas konteks termasuk dalam kelas LL(1) jika tidak mengandung konflik tipe FIRST-FIRST (rekursi kiri - kasus spesial konflik seperti itu) dan IKUTI PERTAMA.
Terkadang tata bahasa non-LL(1) dapat diubah sehingga menjadi LL(1). Beberapa transformasi (lebih tepatnya, yang dibahas dalam kursus) diberikan di bawah ini.
Menghapus rekursi kiri
Mari kita punya aturan bentuk (selanjutnya di bagian ini, huruf kapital - simbol non-terminal, huruf kecil - rantai karakter apa pun):
- SEBUAH → SEBUAH A| A B| ... | A k | M | N | … | z
Hal ini tidak memungkinkan analisis yang jelas, sehingga harus diubah.
Mudah untuk menunjukkan bahwa aturan ini ekuivalen dengan pasangan aturan berikut:
- SEBUAH → M B | N B | ... | z B
- B → A B | B B | ... | k B | ε
Faktorisasi kiri
Inti dari prosedur ini adalah menghilangkan ambiguitas dalam pemilihan aturan berdasarkan simbol kiri. Untuk melakukan ini, awalan kiri yang umum ditemukan dan apa yang mengikutinya dimasukkan ke dalam aturan baru (huruf kecil - rantai karakter apa pun)
Contoh
- SEBUAH → A C | A df | A dg | B
Mengonversi menjadi
- SEBUAH → A B | B
- B → C | D F | D G
Yang pada gilirannya akan berubah menjadi
- SEBUAH → A B | B
- B → C | D DENGAN
- C → F | G
Contoh Konversi Tata Bahasa
G= ((S, A, B), (a, b, c), P, S)
- S → SAbB | A
- SEBUAH → ab | aa | ε
- B → c | ε
Menghapus rekursi kiri untuk S:
- S → sebagai 1
- S 1 → AbBS 1 | ε
Faktorisasi kiri untuk A:
- SEBUAH → aA 1 | ε
- A 1 → b | A
Tata bahasa terakhir:
- S → sebagai 1
- S 1 → AbBS 1 | ε
- SEBUAH → aA 1 | ε
- A 1 → b | A
- B → c | ε
Konstruksi PERTAMA dan IKUTI
PERTAMA(α), dimana α ∈ (N ∪ T)* adalah himpunan terminal dimana α dapat dimulai. Jika α ⇒ ε, maka ε ∈ PERTAMA(α). Oleh karena itu, nilai FOLLOW( A) untuk nonterminal A- banyak terminal yang dapat muncul segera setelahnya A dalam bentuk kalimat apa pun. Jika A mungkin karakter paling kanan dalam beberapa bentuk kalimat, maka penanda akhir $ juga milik FOLLOW( A)
Perhitungan PERTAMA
Untuk terminal
- Untuk terminal mana pun X, X ∈ T,PERTAMA( X) = {X}
Untuk non-terminal
- Jika X adalah nonterminal, maka kita masukkan FIRST( X) = {∅}
- Jika ada aturan dalam tata bahasa X→ ε, lalu tambahkan ε ke PERTAMA( X)
- Untuk setiap non-terminal X dan untuk setiap aturan inferensi X → Y 1 …Y k akan ditambahkan ke FIRST( X) himpunan PERTAMA dari semua simbol di sisi kanan aturan sampai simbol pertama yang tidak menurunkan ε, termasuk simbol tersebut
Untuk rantai
- Untuk serangkaian karakter X 1 …X k FIRST adalah gabungan simbol-simbol FIRST yang termasuk dalam rantai sampai dengan simbol pertama yang ε ∉ FIRST.
Contoh
- S → sebagai 1
- S 1 → AbBS 1 | ε
- SEBUAH → aA 1 | ε
- A 1 → b | A
- B → c | ε
Non-terminal PERTAMA dalam urutan resolusi ketergantungan:
- PERTAMA(S) = (a)
- PERTAMA(A) = (a, ε)
- PERTAMA(A 1) = (b, a)
- PERTAMA(B) = (c, ε)
- PERTAMA(S 1) = (a, b, ε)
PERTAMA untuk aturan inferensi:
- PERTAMA(aS 1) = (a)
- PERTAMA(AbBS 1) = (a, b)
- PERTAMA(ε) = (ε)
- PERTAMA(aA 1) = (a)
- PERTAMA(a) = (a)
- PERTAMA(b) = (b)
- PERTAMA(c) = (c)
IKUTI perhitungan
Mengevaluasi fungsi FOLLOW untuk karakter X:
- Misalkan IKUTI(X) = (∅)
- Jika X adalah aksioma tata bahasa, tambahkan penanda $ ke FOLLOW
- Untuk semua aturan bentuk A → αXβ, tambahkan FIRST(β)\(ε) ke FOLLOW(X) (X dapat diikuti oleh karakter yang dimulai dengan β)
- Untuk semua aturan berbentuk A → αX dan A → αXβ, ε ∈ FIRST(β), tambahkan FOLLOW(A) ke FOLLOW(X) (yaitu, X dapat diikuti oleh semua simbol yang mengikuti A, jika dalam In aturan inferensi, simbol X mungkin yang paling kanan)
- Ulangi dua langkah sebelumnya hingga dimungkinkan untuk menambahkan karakter ke kumpulan
Contoh
- S → sebagai 1
- S 1 → AbBS 1 | ε
- SEBUAH → aA 1 | ε
- A 1 → b | A
- B → c | ε
Hasil:
- IKUTI(S) = ($)
- IKUTI(S 1) = ($) (S 1 adalah karakter paling kanan dalam aturan S → aS 1)
- IKUTI(A) = (b) (setelah A pada aturan S 1 → AbBS 1 muncul b)
- FOLLOW(A 1) = (b) (A 1 adalah karakter paling kanan dalam aturan A → aA 1, oleh karena itu, tambahkan FOLLOW(A) ke FOLLOW(A 1))
- IKUTI(B) = (a, b, $) (tambahkan FIRST(S 1)\(ε) (mengikuti aturan S 1 → AbBS 1), IKUTI(S 1) (karena ada S 1 → ε))
Menyusun tabel
Di meja M untuk pasangan non-terminal-terminal (dalam sel M[A, A]) menunjukkan aturan yang diperlukan untuk menggabungkan kata masukan. Tabel diisi sebagai berikut: untuk setiap aturan inferensi dari tata bahasa tertentu A → α (di mana α adalah rantai di sisi kanan aturan), tindakan berikut dilakukan:
- Untuk setiap terminal A∈ PERTAMA(α) tambahkan aturan A → α Ke M[A, A]
- Jika ε ∈ PERTAMA(α), maka untuk masing-masing B∈IKUTI( A) menambahkan A → α Ke M[A, B]
- ε ∈ PERTAMA(α) dan $ ∈ IKUTI( A), menambahkan A → α Ke M[A, $]
- Semua sel kosong - kesalahan pada kata masukan
Contoh
Buatlah tabel untuk tata bahasa
- S → sebagai 1
- S 1 → AbBS 1 | ε
- SEBUAH → aA 1 | ε
- A 1 → b | A
- B → c | ε
Hasil:
| A | B | C | $ | |
|---|---|---|---|---|
| S | S → sebagai 1 (Aturan pertama, kesimpulan S → aS 1 , a ∈ FIRST(aS 1)) | Kesalahan (Aturan keempat) | Kesalahan (Aturan keempat) | Kesalahan (Aturan keempat) |
| S 1 | S 1 → AbBS 1 (Aturan pertama, keluaran S 1 → AbBS 1 , a ∈ FIRST(AbBS 1)) | S 1 → AbBS 1 (Aturan pertama, keluaran S 1 → AbBS 1 , b ∈ FIRST(AbBS 1)) | Kesalahan (Aturan keempat) | S 1 → ε (Aturan ketiga, kesimpulan S 1 → ε, ε ∈ FIRST(ε), $ ∈ FOLLOW(S 1)) |
| A | SEBUAH → aA 1 (Aturan pertama, keluaran A → aA 1 , a ∈ FIRST(aA 1)) | SEBUAH → ε (Aturan kedua, keluaran A 1 → ε, b ∈ IKUTI(A 1)) | Kesalahan (Aturan keempat) | Kesalahan (Aturan keempat) |
| Sebuah 1 | SEBUAH 1 → sebuah (Aturan pertama, kesimpulan A 1 → a, a ∈ PERTAMA(a)) | SEBUAH 1 → b (Aturan pertama, keluaran A 1 → b, b ∈ PERTAMA(b)) | Kesalahan (Aturan keempat) | Kesalahan (Aturan keempat) |
| B | B → ε | B → ε (Aturan kedua, kesimpulan B → ε, a ∈ IKUTI(B)) | B → c (Aturan pertama, kesimpulan B → c, c ∈ PERTAMA(c)) | B → ε (Aturan ketiga, kesimpulan B → ε, $ ∈ IKUTI(B)) |
Mengurai string
Proses parsing string cukup sederhana. Esensinya adalah sebagai berikut: pada setiap langkah karakter teratas dibaca ay C rantai masukan.
- Jika ay- karakter terminal
- Jika ay bertepatan dengan Dengan, lalu keduanya musnah, terjadilah pergeseran
- Jika ay tidak cocok Dengan, maka kesalahan parse ditandai
- Jika ay- simbol non-terminal, C kembali ke awal baris sebagai gantinya ay dikembalikan ke tumpukan bagian kanan aturan yang diambil dari sel tabel M[ay, C]
Proses berakhir ketika garis dan tumpukan telah mencapai penanda akhir (#).
Contoh
Mari kita parsing string "aabbaabcb":
| tumpukan | garis | tindakan |
|---|---|---|
| S# | A abbabcb$ | S → sebagai 1 |
| A S 1# | A abbabcb$ | menggeser |
| S 1# | A bbaabcb$ | S 1 → AbBS 1 |
| A bBS 1# | A bbaabcb$ | SEBUAH → aA 1 |
| A A 1 bBS 1# | A bbaabcb$ | menggeser |
| Sebuah 1 bBS 1# | B baabcb$ | SEBUAH 1 → b |
| B bBS 1# | B baabcb$ | menggeser |
| B BS 1# | B aabcb$ | menggeser |
| B S 1# | A abcb$ | B → ε |
| S 1# | A abcb$ | S 1 → AbBS 1 |
| A bBS 1# | A abcb$ | SEBUAH → aA 1 |
| A bBS 1# | A abcb$ | SEBUAH → aA 1 |
| A A 1 bBS 1# | A abcb$ | menggeser |
| Sebuah 1 bBS 1# | A bcb$ | SEBUAH 1 → sebuah |
| A bBS 1# | A bcb$ | menggeser |
| B BS 1# | B cb$ | menggeser |
| B S 1# | C menjadi$ | B → c |
| C S 1# | C menjadi$ | menggeser |
| S 1# | B$ | S 1 → AbBS 1 |
| A bBS 1# | B$ | SEBUAH → ε |
| B BS 1# | B$ | menggeser |
| B S 1# | $ | B → ε |
| S 1# | $ | S 1 → ε |
| # | $ | siap |
Membangun penganalisis LR(k).
Perhitungan k dalam LR(k)
Tidak ada algoritme yang memungkinkan seseorang menghitung k dalam kasus umum untuk tata bahasa arbitrer. Biasanya ada baiknya mencoba membuat parser LR(1). Jika tidak lebih dari satu operasi untuk setiap set (Shift, Reduce atau Accept), maka tata bahasanya adalah LR(0). Jika konflik dan benturan muncul saat membuat penganalisis LR(1), maka tata bahasa ini bukan LR(1) dan patut dicoba untuk membuat LR(2). Jika tidak memungkinkan untuk membangunnya, maka LR(3) dan seterusnya.
Pengisian ulang tata bahasa
Mari tambahkan aturan baru S" → S, dan jadikan S" sebagai aksioma tata bahasa. Aturan tambahan ini diperlukan untuk menentukan kapan penganalisis dihentikan dan kapan string input diizinkan. Toleransi terjadi jika dan hanya jika dimungkinkan untuk melakukan konvolusi menurut aturan S → S."
Konstruksi sistem kanonik dari kumpulan situasi LR(1) yang dapat diterima
Pada awalnya ada himpunan I 0 dengan konfigurasi penganalisis S" → .S, $. Selanjutnya, operasi penutupan diterapkan pada konfigurasi ini hingga, sebagai hasil penerapannya, tidak ada lagi konfigurasi baru yang ditambahkan. Selanjutnya, transisi ke himpunan baru dibangun dengan menggeser titik sebanyak satu karakter ke kanan (transisi dilakukan sepanjang karakter yang berdiri setelah titik sebelum transisi dan sebelum setelah transisi), dan konfigurasi yang diperoleh dari yang sudah ada di ini cara ditambahkan ke himpunan ini. Bagi mereka, operasi penutupan juga diterapkan, dan seluruh proses diulang sampai tidak ada lagi himpunan baru yang muncul.
Contoh
Buatlah sistem kanonik dari kumpulan situasi LR(1) yang dapat diterima untuk tata bahasa tertentu:
- S" → S
- S → ABA
- SEBUAH → Aa | ε
- B → cBc | D
Larutan:
- Kami membuat penutupan untuk konfigurasi S" → .S, $:
- S → .ABA, $
- Untuk konfigurasi yang dihasilkan (S → .ABA, $) kami juga membuat penutupan:
- SEBUAH → .Aa, c
- A → .Aa, d
- SEBUAH → ., c
- SEBUAH → ., d
- Untuk konfigurasi yang dihasilkan (A → .Aa, c; A → .Aa, d) kami juga membuat penutupan:
- SEBUAH → .Aa, a
- SEBUAH → ., sEBUAH
- Tidak mungkin untuk membuat lebih banyak konfigurasi di status I 0 - penutupan telah dibuat
- Dari I 0 Anda dapat melakukan transisi sepanjang S dan A dan mendapatkan sekumpulan konfigurasi I 1 dan I 2, yang terdiri dari elemen-elemen berikut:
- Saya 1 = (S" → S., $)
- Saya 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
- I 1 tidak memerlukan penutupan
- Mari kita buat penutupan I 2:
- B → .cBc, a
- B → .cBc, $
- B→.d, a
- B → .d, $
- Semua set lainnya dibuat dengan cara yang sama.
Membangun tabel penganalisis
Tahap terakhir dalam membangun penganalisis LR(1) adalah membuat tabel Tindakan Dan Pergi ke. Meja Tindakan dibuat untuk karakter jalur masukan, yaitu untuk terminal dan penanda akhir jalur $, tabel Pergi ke dibangun untuk simbol tata bahasa, yaitu untuk terminal dan non-terminal.
Membangun Tabel Goto
Tabel Goto menunjukkan keadaan yang harus dituju ketika menemukan simbol tata bahasa berikutnya. Oleh karena itu, jika dalam sistem himpunan kanonik terjadi transisi dari saya saya V aku j dengan simbol A, lalu di Goto( SAYA Saya, A) kami menempatkan negara bagian SAYA J. Setelah mengisi tabel, kami berasumsi bahwa di semua sel kosong Goto( SAYA Saya, A) = Kesalahan
Membangun tabel Tindakan
- Jika terjadi peralihan melalui terminal a dari keadaan I i ke keadaan I j, maka Aksi(I i, a) = Shift(I j)
- Jika A ≠ S" dan terdapat konfigurasi A → α., a, maka Aksi(I i , a) = Kurangi(A → α)
- Untuk keadaan I i yang didalamnya terdapat konfigurasi S" → S., $, Action(I i, $) = Accept
- Untuk semua sel kosong Tindakan(I i , a) = Error
Contoh
Buat tabel Action dan Goto untuk tata bahasa
- S" → S
- S → ABA
- SEBUAH → Aa | ε
- B → cBc | D
Larutan:
| Tindakan | Pergi ke | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| A | C | D | $ | S | S" | A | B | A | C | D | |
| saya 0 | Kurangi (A → ε) | Kurangi (A → ε) | Kurangi (A → ε) | saya 1 | saya 2 | ||||||
| saya 1 | Menerima | ||||||||||
| saya 2 | Pergeseran(I 6) | Pergeseran(I 4) | Pergeseran(I 5) | saya 3 | saya 6 | saya 4 | saya 5 | ||||
| saya 3 | Kurangi (A → ε) | Kurangi (A → ε) | saya 13 | ||||||||
| saya 4 | Pergeseran(I 8) | Pergeseran(I 9) | saya 7 | saya 8 | saya 9 | ||||||
| saya 5 | Kurangi (B → d) | Kurangi (B → d) | |||||||||
| saya 6 | Kurangi (A → Aa) | Kurangi (A → Aa) | Kurangi (A → Aa) | ||||||||
| saya 7 | Pergeseran(I 10) | saya 10 | |||||||||
| saya 8 | Pergeseran(I 8) | Pergeseran(I 9) | saya 11 | saya 8 | saya 9 | ||||||
| saya 9 | Kurangi (B → d) | ||||||||||
| saya 10 | Kurangi (B → cBc) | Kurangi (B → cBc) | |||||||||
| saya 11 | Pergeseran(I 12) | saya 12 | |||||||||
| saya 12 | Kurangi (B → cBc) | ||||||||||
| saya 13 | Pergeseran(I 14) | Kurangi (S → ABA) | saya 14 | ||||||||
| saya 14 | Kurangi (A → Aa) | Kurangi (A → Aa) | |||||||||
Mengurai rantai
Pada setiap langkah, karakter teratas dibaca ay dari tumpukan penganalisis dan mengambil karakter terakhir C rantai masukan.
Jika dalam tabel tindakan di persimpangan ay Dan C terletak:
- Menggeser( Baik), kemudian dimasukkan ke dalam tumpukan Dengan kemudian Baik. Di mana C dihapus dari garis.
- mengurangi( A → kamu), lalu semua simbol terminal dan non-terminal yang membentuk rantai dibersihkan dari atas tumpukan kamu, setelah itu negara bagian melihat Aku, tetap di atas. Menurut tabel transisi di persimpangan Aku Dan A keadaan berikut ditemukan Adalah. Setelah itu A didorong ke tumpukan, dan kemudian Adalah. Garisnya tetap tidak berubah.
- Terima, maka analisis selesai
- kekosongan - kesalahan
Contoh
Mari kita parsing string aaaccdcc:
| Tumpukan | Garis | Tindakan |
| saya 0 | A aaccdcc$ | Kurangi (A → ε), lanjutkan ke I 2 |
| saya 0 A saya 2 | A aaccdcc$ | Pergeseran(I 6) |
| Saya 0 A Saya 2 a saya 6 | A accdcc$ | Kurangi (A → Aa), lanjutkan ke I 2 |
| saya 0 A saya 2 | A accdcc$ | Pergeseran(I 6) |
| Saya 0 A Saya 2 a saya 6 | A ccdcc$ | Kurangi (A → Aa), lanjutkan ke I 2 |
| saya 0 A saya 2 | A ccdcc$ | Pergeseran(I 6) |
| Saya 0 A Saya 2 a saya 6 | C cdcc$ | Kurangi (A → Aa), lanjutkan ke I 2 |
| saya 0 A saya 2 | C cdcc$ | Pergeseran(I 4) |
| saya 0 A saya 2c saya 4 | C dcc$ | Pergeseran(I 8) |
| Saya 0 A Saya 2 c Saya 4 c saya 8 | D cc$ | Pergeseran(I 9) |
| saya 0 A saya 2 c saya 4 c saya 8 d saya 9 | C c$ | Kurangi(B → d), pergi ke I 11 |
| Saya 0 A Saya 2 c Saya 4 c Saya 8 B saya 11 | C c$ | Pergeseran(I 12) |
| Saya 0 A Saya 2 detik Saya 4 detik Saya 8 B Saya 11 detik saya 12 | C$ | Kurangi (B → cBc), ke I 7 |
| Saya 0 A Saya 2 c Saya 4 B saya 7 | C$ | Pergeseran(I 10) |
| Saya 0 A Saya 2 detik dan 4 B Saya 7 detik saya 10 | $ | Kurangi (B → cBc), ke I 3 |
| Saya 0 A Saya 2 B saya 3 | $ | Kurangi (A → ε), lanjutkan ke I 13 |
| Saya 0 A Saya 2 B Saya 3 A saya 13 | $ | Kurangi (S → ABA), masuk ke I 1 |
| saya 0 S saya 1 | $ | Menerima |
Terjemahan ekspresi aritmatika (algoritma Set-Ullman)
Catatan. Kode tersebut dihasilkan oleh doggy style seperti Motorola
Op Arg1, Arg2
berdiri untuk
Arg2 = Arg1 Op Arg2
Membangun pohon
Pohon dibangun seperti biasa untuk ekspresi aritmatika: Di akar adalah operasi dengan prioritas terendah, diikuti oleh operasi dengan prioritas sedikit lebih tinggi, dan seterusnya. Tanda kurung memiliki prioritas tertinggi. Jika ada beberapa operasi dengan prioritas yang sama - a op b op c, maka pohon dibangun untuk ekspresi (a op b) op c.
Contoh
Buatlah pohon untuk ekspresi a + b / (d + a − b × c / d − e) + c × d
Larutan: Mari kita tuliskan ekspresi dalam bentuk
((a) + ((b) / ((((d) + (a)) − ((b) × (c)) / (d)) − (e)))) + ((c) × ( D))
Kemudian akan ada operasi pada akar setiap subpohon, dan ekspresi dalam tanda kurung di kiri dan kanannya akan menjadi subpohonnya. Misalnya, untuk subekspresi ((b) × (c)) / (d), akar dari subpohon yang bersangkutan akan memiliki operasi “/”, dan subpohonnya akan menjadi subekspresi ((b) × (c)) dan (d).
Tata letak pohon (menghitung jumlah register)
- Jika simpulnya adalah daun kiri (yaitu variabel), maka kita tandai dengan nol.
- Jika titik puncaknya adalah daun sebelah kanan, maka kita tandai dengan satu
- Jika kita sudah menandai kedua subpohonnya untuk sebuah simpul, maka kita menandainya sebagai berikut:
- Jika subpohon kiri dan kanan diberi label nomor yang berbeda, lalu pilih yang terbesar
- Jika subpohon kiri dan kanan diberi label angka yang sama, lalu ke subpohon ini kita mengasosiasikan angka yang satu lebih besar dari angka yang menandai subpohon tersebut
| Penandaan daun | Menandai pohon dengan subpohon yang identik | Subpohon kiri ditandai dengan angka besar | Subpohon sebelah kanan ditandai dengan angka besar |
|---|---|---|---|
 |  |  |  |
Kode dihasilkan dengan menelusuri pohon dari bawah ke atas sebagai berikut:
1. Untuk simpul dengan label 0, kode tidak dihasilkan
2. Jika simpulnya adalah lembar X dengan label 1 dan register R Saya, lalu kode tersebut dicocokkan dengannya
PINDAHKAN X, Ri
3. Jika simpulnya internal dengan register R Saya dan anak kirinya adalah sheet X dengan label 0, maka kodenya sesuai
<Код правого поддерева>Op X, Ri
4. Jika subpohon dari simpul dengan register R Saya- tidak daun dan label simpul kanan lebih besar atau sama dengan label simpul kiri (yang mempunyai register Rj, j = i + 1), maka kode tersebut sesuai dengan simpul tersebut
<Код Kanan subpohon><Код kiri subpohon>Op Rj, Ri
5. Jika subpohon dari simpul dengan register R Saya- tidak daun dan label simpul sebelah kanan (yang register Rj, j = i + 1) lebih kecil dari label simpul kiri, maka kode tersebut sesuai dengan simpul tersebut
Distribusi register ditunjukkan pada grafik di sebelah kanan. Kode yang dihasilkan:
PINDAHKAN d, R0 ;R0 = d PINDAH c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d PINDAHKAN a, R1 ;R1 = a TAMBAHKAN d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) PINDAHKAN e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + d) − ((b × c) / d)) − e PINDAHKAN R1, R0;R0 = ((a + d) − ((b × c) / d)) − e DIV b, R0 ;R0 = b / (((a + d) − ((b × c) / d)) − e) TAMBAHKAN a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d )) − e)) PINDAHKAN d, R1 ;R1 = d MUL c, R1 ;R1 = c × d TAMBAHKAN R0, R1 ;R1 = (a + (b / (((a + d) − ((b × c ) / d)) − e))) + (c × d) PINDAHKAN R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d)) − e) )) + (c×d)
Terjemahan ekspresi logis
Bagian ini menunjukkan cara membuat kode untuk mengevaluasi ekspresi Boolean dengan malas. Hasil dari algoritma ini adalah sepotong kode yang, menggunakan operasi TST, BNE, BEQ, menghitung ekspresi logika dengan masuk ke salah satu label: TRUELAB atau FALSELAB.
Membangun pohon
Pohon ekspresi logis mencerminkan urutan evaluasinya sesuai dengan prioritas operasi, yaitu untuk mengevaluasi nilai dari node pohon tertentu (yang merupakan operasi pada dua operan yang merupakan subpohon dari node), kita harus pertama-tama evaluasi nilai subpohonnya.
Prioritas operasi: Operasi NOT mempunyai prioritas tertinggi, diikuti oleh AND, dan kemudian OR. Jika ekspresi menggunakan yang lain operasi logis maka ketiganya harus diekspresikan melalui ketiganya dengan cara tertentu (biasanya, tidak ada operasi lain dan tidak diperlukan transformasi ekspresi). Asosiatif untuk operasi dengan prioritas yang sama adalah dari kiri ke kanan, yaitu A dan B dan C dianggap sebagai (A dan B) dan C
Contoh
Buatlah pohon untuk ekspresi logika bukan A atau B dan C dan (B atau bukan C).
Larutan: lihat diagram di sebelah kanan.
Untuk setiap simpul pohon, 4 atribut dihitung:
- Nomor simpul
- Beri label ke mana harus pergi jika ekspresi dalam node salah (label salah, fl)
- Beri label ke mana harus pergi jika ekspresi di node benar (label benar, tl)
- Tanda tangan (lihat di bawah untuk lebih jelasnya)
Node diberi nomor dalam urutan apa pun; satu-satunya syarat adalah nomor nodenya unik.
Pohon itu ditandai sebagai berikut:
- fl menunjukkan nomor simpul tempat transisi dilakukan, atau falselab jika simpul ini salah
- tl menunjukkan nomor simpul tempat transisi dilakukan atau truelab jika simpul ini benar
Tanda menunjukkan kapan harus berhenti menghitung subpohon saat ini.
Untuk akar pohon fl=falselab, tl=truelab, tanda=false.
Dengan demikian:
Contoh
Beri label pohon yang dibuat untuk ekspresi logika bukan A atau B dan C dan (B atau bukan C).
Pembuatan kode
Perintah mesin yang digunakan dalam kode yang dihasilkan:
- TST
- BNE - transisi berdasarkan label jika flag tidak disetel, yaitu kondisi diperiksa menggunakan TST BENAR
- BEQ - transisi berdasarkan label jika flag disetel, yaitu kondisi yang diperiksa menggunakan TST PALSU
Kode ini dibuat sebagai berikut:
- pohon dilintasi dari akar, untuk AND dan OR subpohon kiri dilintasi terlebih dahulu, kemudian subpohon kanan
- Untuk setiap simpul yang dilewati, nomornya (label) dicetak
- untuk lembar A(nomor, tl, fl, tanda) TST A dicetak
- jika tanda == benar, BNE tl dicetak
- jika tanda == salah, BEQ fl dicetak
Contoh
Untuk ekspresi yang dibahas di atas, kode berikut akan dihasilkan:
1:2:4 : TST A BEQ TRUELAB 3:5:7 : TST B BEQ FALSELAB 8 : TST C BEQ FALSELAB 6:9 : TST B BNE TRUELAB 10:11 : TST C BNE FALSELAB BENAR : FALSELAB :
Metode pencocokan pola
Ide dari metode ini adalah bahwa kode dapat dihasilkan untuk bagian program yang sama cara yang berbeda, dan sebagai hasilnya, pengoptimalan dapat dicapai berdasarkan satu atau beberapa parameter lainnya.
Rumusan masalah
Ada banyak sampel, yang masing-masing merupakan bagian dari representasi perantara yang dapat diterapkan, bobot, dan kode yang dihasilkan ditentukan. Ada pohon representasi perantara, yang merupakan bagian dari program yang kodenya perlu dibuat. Tujuannya adalah untuk membuat penutup pohon representasi perantara dengan sampel sedemikian rupa sehingga bobot total sampel menjadi minimal.
Sampel adalah instruksi perakitan dan penguraian pohon yang sesuai dengannya. Untuk setiap sampel, waktu eksekusi (dalam siklus jam) diketahui. Dengan bantuan mereka, kami akan menghasilkan kode yang optimal (dalam hal waktu eksekusi).
Contoh sampel
Membangun representasi perantara
Pertama, kita membuat pohon parse untuk keseluruhan ekspresi.
Konstruksi cakupan
Sekarang untuk setiap simpul (kita mengurutkannya dari daun hingga akar) kita akan menghasilkan kode optimal untuk subpohonnya. Untuk melakukan ini, kita cukup memeriksa semua sampel yang berlaku di titik ini. Waktu eksekusi saat menggunakan sampel tertentu akan menjadi jumlah waktu penghitungan argumennya (dan kita sudah mengetahui kode optimal untuk menghitungnya berkat urutan traversal pohon) dan waktu eksekusi sampel itu sendiri. Dari semua opsi yang diterima, kami memilih yang terbaik - ini akan menjadi kode optimal untuk subpohon node ini. Di akar pohon kita mendapatkan kode optimal untuk keseluruhan ekspresi.
Pembuatan kode
Tidak perlu menuliskan kode untuk semua simpul - cukup menuliskan kode minimumnya waktu yang dibutuhkan dan sampel untuk digunakan. Segala sesuatu yang lain dari ini dapat dengan mudah dipulihkan.
Dalam tugas ini kami memiliki jumlah register yang tidak terbatas, sehingga Anda dapat menggunakan register baru setiap saat.
Pembangunan RT menggunakan DKA
Konstruksi NFA menggunakan tata bahasa linier kanan
Membawa tata bahasa
Untuk mengonversi tata bahasa KS arbitrer ke bentuk tertentu, Anda harus melakukan langkah-langkah berikut:
- hapus semua karakter yang tidak membuahkan hasil;
- hapus semua karakter yang tidak dapat dijangkau;
Menghapus karakter yang tidak berguna
Pintu masuk: Tata bahasa KS G = (T, N, P, S).
KELUAR: Tata bahasa KS G’ = (T, N’, P’, S), tidak mengandung simbol steril, sehingga L(G) = L(G’).
Metode:
Kami secara rekursif membangun himpunan N 0, N 1, ...
- N 0 = ∅, saya = 1.
- N i = (A | (A → α) ∈ P dan α ∈ (N i - 1 ∪ T)*) ∪ N i-1 .
- Jika N i ≠ N i - 1, maka i = i + 1 dan lanjutkan ke langkah 2, jika tidak, N’ = N i; P' terdiri dari aturan-aturan himpunan P yang hanya berisi simbol-simbol dari N' ∪ T; G' = (T, N', P', S).
Definisi: suatu simbol x ∈ (T ∪ N) dikatakan tidak terjangkau dalam tata bahasa G = (T, N, P, S) jika tidak muncul dalam bentuk kalimat apa pun dari tata bahasa tersebut.
Contoh
Hapus karakter yang tidak berguna dari tata bahasa G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)
- S → AcDe | CaDbCe | SaCa | aCb | dFg
- A → SeAd | cSA
- B → CaBd | aDBc | BSCf | bfg
- C → Ebd | Seb | aAc | lih
- D → fCE | ac | dEdAS | ε
- E → ESacD | aec | eFf
Larutan
- N 0 = ∅
- N 1 = (B (B → bfg) , D (D → ac) , E (E → aec) )
- N 2 = (B, D, E, C (C → Ebd) )
- N 3 = (B, D, E, C, S (S → aCb) )
- N 4 = (B, D, E, C, S) = N 3
G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)
- S → CaDbCe | SaCa | aCb
- B → CaBd | aDBc | BSCf | bfg
- C → Ebd | Seb
- D → fCE | ac | ε
- E → ESacD | aec
Menghapus karakter yang tidak dapat dijangkau
Pintu masuk: Tata bahasa KS G = (T, N, P, S)
KELUAR: Tata bahasa KS G’ = (T’, N’, P’, S), tidak mengandung simbol-simbol yang tidak dapat dijangkau, sehingga L(G) = L(G’).
Metode:
- V 0 = (S); saya = 1.
- V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P dan A ∈ V i - 1 ) ∪ V i-1 .
- Jika V i ≠ V i - 1, maka i = i + 1 dan lanjutkan ke langkah 2, jika tidak, N’ = V i ∩ N; T’ = V i ∩ T; P' terdiri dari aturan-aturan himpunan P yang hanya berisi simbol-simbol dari V i ; G' = (T', N', P', S).
Definisi: Suatu KS-tata bahasa G dikatakan tereduksi apabila tidak mengandung simbol-simbol yang tidak terjangkau dan steril.
Contoh
Hapus karakter yang tidak dapat dijangkau dari tata bahasa G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)
- S → CaDbCe | SaCa | aCb
- B → CaBd | aDBc | BSCf | bfg
- C → Ebd | Seb
- D → fCE | ac | ε
- E → ESacD | aec
Larutan
- V 0 = (S)
- V 1 = (S, C (S → CaDbCe), D (S → CaDbCe), a (S → CaDbCe), b (S → CaDbCe), e (S → CaDbCe) )
- V 2 = (S, C, D, a, b, e, E (C → Ebd), d (C → Ebd), f (D → fCE) )
- V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD) )
- V 4 = (S, C, D, E, a, b, d, e, f, c) = V 3
G""((C, D, E, S), (a, b, c, d, e, f), P"", S)
- S → CaDbCe | SaCa | aCb
- C → Ebd | Seb
- D → fCE | ac | ε
- E → ESacD | aec