Analisis Leksikal dan Sintaksis

Analisis leksikal dan sintaksis membentuk bagian depan kompiler, memecah teks sumber menjadi token dan mengenali struktur gramatikalnya sebagai pohon parse atau sintaksis.

Definition

Analisis leksikal adalah fase yang mengelompokkan karakter masukan menjadi token, dan analisis sintaksis (parsing) adalah fase yang menentukan apakah dan bagaimana token-token tersebut membentuk program yang valid sesuai dengan tata bahasa, menghasilkan pohon sintaksis.

Scope

Topik ini mencakup analisis leksikal, yang mengubah aliran karakter menjadi token menggunakan bahasa reguler dan automata hingga, serta analisis sintaksis (parsing), yang mengenali struktur frasa suatu program terhadap tata bahasa bebas konteks. Ini mencakup parsing top-down (LL) dan bottom-up (LR), generator parser, ambiguitas dan pemulihan kesalahan, serta konstruksi pohon sintaksis abstrak.

Core questions

• Bagaimana bahasa reguler dan bebas konteks digunakan untuk menggambarkan struktur program?
• Apa saja pertukaran antara parsing LL dan LR?
• Bagaimana ambiguitas dan kesalahan parse dideteksi dan ditangani?
• Bagaimana pohon sintaksis abstrak dibangun dari aliran token?

Key theories

Parsing LR

Knuth memperkenalkan parsing LR, teknik bottom-up yang secara deterministik mengurai kelas tata bahasa LR yang luas dalam waktu linier, membentuk dasar dari banyak generator parser.

Parsing bebas konteks umum

Algoritma Earley mengurai tata bahasa bebas konteks arbitrer, termasuk yang ambigu, menyediakan metode umum ketika parser deterministik yang terbatas tidak mencukupi.

Dasar-dasar reguler dan bebas konteks dari bagian depan

The Dragon Book mensistematisasi penggunaan ekspresi reguler dan automata hingga untuk pemindaian dan tata bahasa bebas konteks untuk parsing, termasuk algoritma konstruksi LL dan LR standar.

Clinical relevance

Lexing dan parsing adalah dasar tidak hanya untuk kompiler tetapi juga untuk interpreter, linter, formatter, IDE, dan prosesor format data. Parsing yang kuat dengan pemulihan kesalahan yang baik sangat penting untuk pengalaman pengembang dari setiap perkakas bahasa.

History

Hierarki bahasa formal Chomsky pada akhir 1950-an menyediakan teori bahasa reguler dan bebas konteks. Knuth memformalkan parsing LR pada tahun 1965, dan Earley memberikan algoritma bebas konteks umum pada tahun 1970. Generator parser seperti yacc membuat parsing LR praktis, sementara pekerjaan selanjutnya mengeksplorasi tata bahasa ekspresi parsing dan parser berbasis kombinator.

Debates

Parser yang dihasilkan versus yang ditulis tangan

Praktisi memperdebatkan penggunaan generator parser dari tata bahasa formal, yang ringkas dan dapat diverifikasi, dibandingkan dengan parser recursive-descent yang ditulis tangan, yang seringkali memberikan pesan kesalahan dan kontrol yang lebih baik dengan biaya kode yang lebih banyak.

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

Apa perbedaan antara lexer dan parser?

Lexer mengelompokkan karakter mentah menjadi token seperti pengidentifikasi dan operator, sementara parser mengatur token-token tersebut menjadi pohon sintaksis hierarkis sesuai dengan tata bahasa bahasa tersebut.

Apa perbedaan antara parsing LL dan LR?

Parser LL bekerja secara top-down, memprediksi produksi dari prefiks masukan, sementara parser LR bekerja secara bottom-up, mengurangi substring yang dikenali; LR menangani kelas tata bahasa yang secara ketat lebih besar tetapi lebih kompleks untuk dibangun.