Bagaimana Pendekatan Menulis Penerjemah Dari Awal
Diterbitkan: 2022-03-11Beberapa orang mengatakan bahwa "semuanya bermuara pada satu dan nol"—tetapi apakah kita benar-benar memahami bagaimana program kita diterjemahkan ke dalam bit-bit itu?
Compiler dan interpreter mengambil string mentah yang mewakili sebuah program, menguraikannya, dan memahaminya. Meskipun juru bahasa lebih sederhana dari keduanya, menulis bahkan juru bahasa yang sangat sederhana (yang hanya melakukan penjumlahan dan perkalian) akan menjadi pelajaran. Kami akan fokus pada kesamaan apa yang dimiliki oleh compiler dan interpreter: lexing dan parsing input.
Anjuran dan Larangan dalam Menulis Penerjemah Anda Sendiri
Pembaca mungkin bertanya-tanya Apa yang salah dengan regex? Ekspresi reguler sangat kuat, tetapi tata bahasa kode sumber tidak cukup sederhana untuk diuraikan olehnya. Tidak juga bahasa khusus domain (DSL), dan klien mungkin memerlukan DSL khusus untuk ekspresi otorisasi, misalnya. Tetapi bahkan tanpa menerapkan keterampilan ini secara langsung, menulis juru bahasa membuatnya lebih mudah untuk menghargai upaya di balik banyak bahasa pemrograman, format file, dan DSL.
Menulis parser dengan benar dengan tangan dapat menjadi tantangan dengan semua kasus tepi yang terlibat. Itulah mengapa ada alat populer, seperti ANTLR, yang dapat menghasilkan parser untuk banyak bahasa pemrograman populer. Ada juga library yang disebut parser combinator , yang memungkinkan pengembang untuk menulis parser secara langsung dalam bahasa pemrograman pilihan mereka. Contohnya termasuk FastParse untuk Scala dan Parsec untuk Python.
Kami merekomendasikan bahwa, dalam konteks profesional, pembaca menggunakan alat dan pustaka semacam itu untuk menghindari penemuan kembali roda. Namun, memahami tantangan dan kemungkinan menulis juru bahasa dari awal akan membantu pengembang memanfaatkan solusi tersebut secara lebih efektif.
Ikhtisar Komponen Interpreter
Seorang juru bahasa adalah program yang kompleks, jadi ada beberapa tahapan untuk itu:
- Lexer adalah bagian dari interpreter yang mengubah urutan karakter (teks biasa) menjadi urutan token.
- Sebuah parser , pada gilirannya, mengambil urutan token dan menghasilkan pohon sintaksis abstrak (AST) dari suatu bahasa. Aturan dimana parser beroperasi biasanya ditentukan oleh tata bahasa formal.
- Interpreter adalah program yang menginterpretasikan AST dari sumber program dengan cepat (tanpa mengkompilasinya terlebih dahulu).
Kami tidak akan membuat juru bahasa yang spesifik dan terintegrasi di sini. Sebagai gantinya, kita akan menjelajahi masing-masing bagian ini dan masalah umum mereka dengan contoh terpisah. Pada akhirnya, kode pengguna akan terlihat seperti ini:
val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res") Mengikuti tiga tahap, kita akan mengharapkan kode ini untuk menghitung nilai akhir dan mencetak Result is: 19 . Tutorial ini kebetulan menggunakan Scala karena:
- Sangat ringkas, memuat banyak kode dalam satu layar.
- Berorientasi ekspresi, tanpa perlu variabel yang tidak diinisialisasi/null.
- Ketik aman, dengan perpustakaan koleksi yang kuat, enum, dan kelas kasus.
Secara khusus, kode di sini ditulis dalam sintaks kurung kurawal opsional Scala3 (sintaks berbasis lekukan seperti Python). Tetapi tidak ada pendekatan yang spesifik untuk Scala , dan Scala mirip dengan banyak bahasa lain: Pembaca akan merasa mudah untuk mengubah contoh kode ini ke bahasa lain. Kecuali itu, contoh dapat dijalankan secara online menggunakan Scastie.
Terakhir, bagian Lexer, Parser, dan Interpreter memiliki contoh tata bahasa yang berbeda . Seperti yang ditunjukkan oleh repo GitHub yang sesuai, dependensi dalam contoh selanjutnya sedikit berubah untuk mengimplementasikan tata bahasa ini, tetapi konsep keseluruhannya tetap sama.
Komponen Penerjemah 1: Menulis Lexer
Katakanlah kita ingin melex string ini: "123 + 45 true * false1" . Ini berisi berbagai jenis token:
- Literal bilangan bulat
- A
+operator - A
*operator - Sebuah literal yang
true - Pengidentifikasi,
false1
Spasi di antara token akan dilewati dalam contoh ini.
Pada tahap ini, ekspresi tidak harus masuk akal; lexer hanya mengubah string input menjadi daftar token. (Pekerjaan "memahami token" diserahkan kepada parser.)
Kami akan menggunakan kode ini untuk mewakili token:
case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOFSetiap token memiliki tipe, representasi tekstual, dan posisi dalam input asli. Posisi dapat membantu pengguna akhir lexer dengan debugging.
Token EOF adalah token khusus yang menandai akhir input. Itu tidak ada dalam teks sumber; kami hanya menggunakannya untuk menyederhanakan tahap parser.
Ini akan menjadi output dari lexer kami:
Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )Mari kita periksa implementasinya:
class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toListKami mulai dengan daftar token yang kosong, lalu kami menelusuri string dan menambahkan token saat mereka datang.
Kami menggunakan karakter lookahead untuk menentukan jenis token berikutnya . Perhatikan bahwa karakter lookahead tidak selalu merupakan karakter terjauh di depan yang diperiksa. Berdasarkan lookahead, kita tahu seperti apa token itu dan menggunakan currentPos untuk memindai semua karakter yang diharapkan dalam token saat ini, lalu menambahkan token ke daftar:
Jika lookahead adalah spasi putih, kita lewati. Token satu huruf itu sepele; kami menambahkannya dan menaikkan indeks. Untuk bilangan bulat, kita hanya perlu menjaga indeks.
Sekarang kita sampai pada sesuatu yang agak rumit: pengidentifikasi versus literal. Aturannya adalah kita mengambil kecocokan terpanjang yang mungkin dan memeriksa apakah itu literal; jika tidak, itu adalah pengidentifikasi.
Berhati-hatilah saat menangani operator seperti < dan <= . Di sana Anda harus melihat ke depan satu karakter lagi dan melihat apakah itu = sebelum menyimpulkan bahwa itu adalah operator <= . Jika tidak, itu hanya < .
Dengan itu, lexer kami telah menghasilkan daftar token.
Komponen Penerjemah 2: Menulis Parser
Kita harus memberikan beberapa struktur pada token kita—kita tidak bisa berbuat banyak dengan daftar saja. Misalnya, kita perlu tahu:
Ekspresi mana yang bersarang? Operator mana yang diterapkan dalam urutan apa? Aturan pelingkupan mana yang berlaku, jika ada?
Struktur pohon mendukung bersarang dan memesan. Tapi pertama-tama, kita harus mendefinisikan beberapa aturan untuk membangun pohon. Kami ingin parser kami tidak ambigu—untuk selalu mengembalikan struktur yang sama untuk input yang diberikan.
Perhatikan bahwa parser berikut tidak menggunakan contoh lexer sebelumnya . Yang ini untuk menambahkan angka, jadi tata bahasanya hanya memiliki dua token, '+' dan NUM :
expr -> expr '+' expr expr -> NUM Setara, menggunakan karakter pipa ( | ) sebagai simbol "atau" seperti dalam ekspresi reguler, adalah:
expr -> expr '+' expr | NUM Either way, kami memiliki dua aturan: satu yang mengatakan bahwa kami dapat menjumlahkan dua expr s dan lainnya yang mengatakan bahwa expr dapat menjadi token NUM , yang di sini berarti bilangan bulat non-negatif.
Aturan biasanya ditentukan dengan tata bahasa formal . Tata bahasa formal terdiri dari: Aturan itu sendiri, seperti yang ditunjukkan di atas Aturan awal (aturan pertama ditentukan, per konvensi) Dua jenis simbol untuk mendefinisikan aturan dengan: Terminal: "huruf" (dan karakter lain) dari bahasa kita— simbol yang tidak dapat direduksi yang membentuk token Nonterminal: konstruksi perantara yang digunakan untuk penguraian (yaitu, simbol yang dapat diganti)
Hanya nonterminal yang bisa berada di sisi kiri aturan; sisi kanan dapat memiliki terminal dan nonterminal. Dalam contoh di atas, terminalnya adalah '+' dan NUM , dan satu-satunya nonterminal adalah expr . Untuk contoh yang lebih luas, dalam bahasa Java, kami memiliki terminal seperti 'true' , '+' , Identifier , dan '[' , dan nonterminal seperti BlockStatements , ClassBody , dan MethodOrFieldDecl .
Ada banyak cara kita bisa mengimplementasikan parser ini. Di sini, kita akan menggunakan teknik penguraian "rekursif keturunan". Ini adalah tipe yang paling umum karena paling sederhana untuk dipahami dan diterapkan.
Sebuah parser keturunan rekursif menggunakan satu fungsi untuk setiap nonterminal dalam tata bahasa. Itu dimulai dari aturan awal dan turun dari sana (karenanya "turun"), mencari tahu aturan mana yang akan diterapkan di setiap fungsi. Bagian "rekursif" sangat penting karena kita dapat membuat sarang nonterminal secara rekursif! Regex tidak dapat melakukan itu: Mereka bahkan tidak dapat menangani tanda kurung seimbang. Jadi kita membutuhkan alat yang lebih kuat.
Pengurai untuk aturan pertama akan terlihat seperti ini (kode lengkap):
def expr() = expr() eat('+') expr() Fungsi eat() memeriksa apakah lookahead cocok dengan token yang diharapkan dan kemudian memindahkan indeks lookahead. Sayangnya, ini belum berhasil karena kami perlu memperbaiki beberapa masalah dengan tata bahasa kami.
Ambiguitas Tata Bahasa
Masalah pertama adalah ambiguitas tata bahasa kami, yang mungkin tidak terlihat pada pandangan pertama:
expr -> expr '+' expr | NUM Mengingat input 1 + 2 + 3 , parser kami dapat memilih untuk menghitung baik expr expr terlebih dahulu dalam AST yang dihasilkan:

Itu sebabnya kita perlu memperkenalkan beberapa asimetri :
expr -> expr '+' NUM | NUMKumpulan ekspresi yang dapat kita wakili dengan tata bahasa ini tidak berubah sejak versi pertamanya. Hanya sekarang tidak ambigu : Pengurai selalu ke kiri. Hanya apa yang kami butuhkan!
Ini membuat operasi + kita dibiarkan asosiatif , tetapi ini akan menjadi jelas ketika kita sampai ke bagian Interpreter.
Aturan rekursif kiri
Sayangnya, perbaikan di atas tidak menyelesaikan masalah kami yang lain, rekursi kiri:
def expr() = expr() eat('+') eat(NUM)Kami memiliki rekursi tak terbatas di sini. Jika kami masuk ke fungsi ini, kami akhirnya akan mendapatkan kesalahan stack-overflow. Tetapi teori penguraian dapat membantu!
Misalkan kita memiliki tata bahasa seperti ini, di mana alpha dapat berupa urutan terminal dan nonterminal apa pun:
A -> A alpha | BKita dapat menulis ulang tata bahasa ini sebagai:
A -> BA' A' -> alpha A' | epsilon Di sana, epsilon adalah string kosong—tidak ada, tidak ada token.
Mari kita lihat revisi tata bahasa kita saat ini:
expr -> expr '+' NUM | NUM Mengikuti metode penulisan ulang aturan penguraian yang dirinci di atas, dengan alpha menjadi token '+' NUM kami, tata bahasa kami menjadi:
expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilonSekarang tata bahasanya OK, dan kita bisa menguraikannya dengan pengurai keturunan rekursif. Mari kita lihat bagaimana pengurai seperti itu akan mencari iterasi terbaru dari tata bahasa kita:
class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head Di sini kami menggunakan token EOF untuk menyederhanakan parser kami. Kami selalu yakin bahwa setidaknya ada satu token dalam daftar kami, jadi kami tidak perlu menangani kasus khusus dari daftar kosong.
Juga, jika kita beralih ke lexer streaming, kita tidak akan memiliki daftar dalam memori tetapi sebuah iterator, jadi kita memerlukan penanda untuk mengetahui kapan kita sampai pada akhir input. Ketika kita sampai pada akhir, token EOF harus menjadi token terakhir yang tersisa.
Berjalan melalui kode, kita dapat melihat bahwa ekspresi dapat berupa angka saja. Jika tidak ada yang tersisa, token berikutnya tidak akan menjadi Plus , jadi kami akan berhenti menguraikan. Token terakhir adalah EOF , dan kita akan selesai.
Jika string input memiliki lebih banyak token, maka ini harus terlihat seperti + 123 . Di situlah rekursi pada exprOpt() dimulai!
Menghasilkan AST
Sekarang setelah kami berhasil menguraikan ekspresi kami, sulit untuk melakukan apa pun dengannya apa adanya. Kami dapat melakukan beberapa panggilan balik di parser kami, tetapi itu akan sangat merepotkan dan tidak dapat dibaca. Sebagai gantinya, kami akan mengembalikan AST, pohon yang mewakili ekspresi input:
case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case EpsilonIni menyerupai aturan kami, menggunakan kelas data sederhana.
Pengurai kami sekarang mengembalikan struktur data yang berguna:
class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon Untuk eat() , error() , dan detail implementasi lainnya, silakan lihat repo GitHub terlampir.
Menyederhanakan Aturan
ExprOpt kami masih dapat ditingkatkan:
'+' NUM exprOpt | epsilonSulit untuk mengenali pola yang diwakilinya dalam tata bahasa kita hanya dengan melihatnya. Ternyata kita bisa mengganti rekursi ini dengan konstruksi yang lebih sederhana:
('+' NUM)* Konstruksi ini berarti '+' NUM terjadi nol kali atau lebih.
Sekarang tata bahasa lengkap kami terlihat seperti ini:
expr -> NUM exprOpt* exprOpt -> '+' NUMDan AST kami terlihat lebih bagus:
case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int) Parser yang dihasilkan memiliki panjang yang sama tetapi lebih sederhana untuk dipahami dan digunakan. Kami telah menghilangkan Epsilon , yang sekarang tersirat dengan memulai dengan struktur kosong.
Kami bahkan tidak membutuhkan kelas ExprOpt di sini. Kita bisa saja menempatkan case class Expr(num: Int, exprOpts: Seq[Int]) , atau dalam format tata bahasa, NUM ('+' NUM)* . Jadi mengapa kita tidak?
Pertimbangkan bahwa jika kita memiliki beberapa kemungkinan operator, seperti - atau * , maka kita akan memiliki tata bahasa seperti ini:
expr -> NUM exprOpt* exprOpt -> [+-*] NUM Dalam hal ini, AST kemudian membutuhkan ExprOpt untuk mengakomodasi jenis operator:
case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int) Perhatikan bahwa sintaks [+-*] dalam tata bahasa memiliki arti yang sama seperti dalam ekspresi reguler: "salah satu dari tiga karakter itu." Kita akan segera melihat ini beraksi.
Interpreter Komponen 3: Menulis Interpreter
Interpreter kami akan menggunakan lexer dan parser kami untuk mendapatkan AST dari ekspresi input kami dan kemudian mengevaluasi AST itu dengan cara apa pun yang kami inginkan. Dalam hal ini, kita berurusan dengan angka, dan kita ingin mengevaluasi jumlah mereka.
Dalam implementasi contoh interpreter kami, kami akan menggunakan tata bahasa sederhana ini:
expr -> NUM exprOpt* exprOpt -> [+-] NUMDan AST ini:
case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)(Kami telah membahas cara menerapkan lexer dan parser untuk tata bahasa yang serupa, tetapi setiap pembaca yang terjebak dapat membaca dengan teliti implementasi lexer dan parser untuk tata bahasa yang tepat ini dalam repo.)
Sekarang kita akan melihat bagaimana menulis juru bahasa untuk tata bahasa di atas:
class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp Jika kami menguraikan masukan kami menjadi AST tanpa mengalami kesalahan, kami yakin bahwa kami akan selalu memiliki setidaknya satu NUM . Kemudian kami mengambil nomor opsional dan menambahkannya ke (atau menguranginya dari) hasil kami.
Catatan dari awal tentang asosiasi kiri + sekarang jelas: Kita mulai dari angka paling kiri dan menambahkan yang lain, dari kiri ke kanan. Ini mungkin tampak tidak penting untuk penambahan, tetapi pertimbangkan pengurangan: Ekspresi 5 - 2 - 1 dievaluasi sebagai (5 - 2) - 1 = 3 - 1 = 2 dan bukan sebagai 5 - (2 - 1) = 5 - 1 = 4 !
Tetapi jika kita ingin melampaui interpretasi operator plus dan minus, ada aturan lain yang harus didefinisikan.
Hak lebih tinggi
Kami tahu cara mengurai ekspresi sederhana seperti 1 + 2 + 3 , tetapi jika menyangkut 2 + 3 * 4 + 5 , kami memiliki sedikit masalah.
Kebanyakan orang setuju pada konvensi bahwa perkalian memiliki prioritas lebih tinggi daripada penambahan. Tapi parser tidak tahu itu. Kita tidak bisa hanya mengevaluasinya sebagai ((2 + 3) * 4) + 5 . Sebaliknya kita ingin (2 + (3 * 4)) + 5 .
Ini berarti bahwa kita perlu mengevaluasi perkalian terlebih dahulu . Perkalian perlu lebih jauh dari akar AST untuk memaksanya dievaluasi sebelum penambahan. Untuk ini, kita perlu memperkenalkan lapisan tipuan lainnya.
Memperbaiki Tata Bahasa yang Naif Dari Awal hingga Selesai
Ini adalah tata bahasa rekursif kiri asli kami, yang tidak memiliki aturan prioritas:
expr -> expr '+' expr | expr '*' expr | NUMPertama, kami memberikan aturan prioritas dan menghilangkan ambiguitasnya :
expr -> expr '+' term | term term -> term '*' NUM | NUMKemudian mendapat aturan non-kiri-rekursif :
expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUMHasilnya adalah AST ekspresif yang indah:
case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)Ini memberi kita implementasi penerjemah singkat:
class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmpSeperti sebelumnya, ide-ide dalam lexer dan tata bahasa yang diperlukan telah dibahas sebelumnya, tetapi pembaca dapat menemukannya di repo jika diperlukan.
Langkah Selanjutnya dalam Menulis Penerjemah
Kami tidak membahas ini, tetapi penanganan dan pelaporan kesalahan adalah fitur penting dari pengurai mana pun. Sebagai pengembang, kami tahu betapa frustasinya ketika kompiler menghasilkan kesalahan yang membingungkan atau menyesatkan. Ini adalah area yang memiliki banyak masalah menarik untuk dipecahkan, seperti memberikan pesan kesalahan yang benar dan tepat, tidak menghalangi pengguna dengan lebih banyak pesan daripada yang diperlukan, dan memulihkan dengan baik dari kesalahan. Terserah pengembang yang menulis juru bahasa atau kompiler untuk memastikan pengguna masa depan mereka memiliki pengalaman yang lebih baik.
Dalam menelusuri contoh lexer, parser, dan interpreter kami, kami hanya menggores permukaan teori di balik compiler dan interpreter, yang mencakup topik-topik seperti:
- Lingkup dan tabel simbol
- Tipe statis
- Pengoptimalan waktu kompilasi
- Penganalisis dan linter program statis
- Pemformatan kode dan pencetakan cantik
- Bahasa khusus domain
Untuk bacaan lebih lanjut, saya merekomendasikan sumber daya ini:
- Pola Implementasi Bahasa oleh Terence Parr
- Buku online gratis, Crafting Interpreters , oleh Bob Nystrom
- Pengantar Tata Bahasa dan Parsing oleh Paul Klint
- Menulis Pesan Kesalahan Kompilator yang Baik oleh Caleb Meredith
- Catatan dari kursus East Carolina University “Penerjemahan dan Penyusunan Program”
