Menulis Lexer

Scanner tulis tangan: tabel kata kunci, prinsip maximal munch, dan loop utama.

Daftar isi

Scanner tulis tangan mengubah kode sumber menjadi deret token dengan kode eksplisit yang memutuskan transisi satu karakter pada satu waktu. Topik ini menyusun scanner untuk bahasa mini v1, lengkap dengan tabel kata kunci, prinsip maximal munch pada operator dua karakter, dan loop utama yang memakai peek dan advance. Pembaca memperoleh berkas lexer.py dengan antarmuka Lexer(source).tokens() yang menjadi masukan bagi modul parsing.

Anatomi scanner tulis tangan#

Scanner memelihara empat variabel keadaan, yaitu src (kode sumber), pos (indeks karakter saat ini), line (nomor baris sumber saat ini), dan column (nomor kolom sumber saat ini). Dua operasi dasar menggerakkan pemindaian, yaitu _peek() yang membaca karakter pada posisi saat ini tanpa memajukan indeks, dan _advance() yang mengembalikan karakter pada posisi saat ini lalu memajukan indeks sekaligus memperbarui line dan column. Keempat variabel ini menjadi satu-satunya memori scanner sepanjang satu kali pemindaian, sehingga setiap pemindai kelas token mengakses dan memutakhirkan keadaan lewat dua operasi dasar tersebut.

Pemisahan antara peek dan advance membuat lookahead menjadi murah. Pemindai komentar // membutuhkan peek dua karakter untuk memutuskan apakah tanda / adalah awal komentar atau operator pembagian. Pemindai operator dua karakter seperti <= membutuhkan peek satu karakter ke depan sebelum memutuskan apakah lexeme adalah satu atau dua karakter. Tanpa peek, setiap pemindai akan memajukan indeks secara permanen dan kesulitan membedakan kasus-kasus ini.

Posisi sumber dijaga tetap konsisten dengan karakter yang dikonsumsi. Karakter baris baru menambah line dan mereset column ke 1, sedangkan karakter biasa menambah column sebesar satu. Token mencatat line dan column pada awal lexeme, sehingga pesan error yang menyebut sebuah token menunjuk ke awal lexeme, bukan ke akhir.

Tabel kata kunci#

Tabel KEYWORDS adalah frozenset yang berisi sepuluh kata kunci bahasa mini v1, yaitu let, print, if, else, while, true, false, nil, and, dan or. Pemindai identifier membangun lexeme terlebih dahulu, lalu memeriksa apakah lexeme itu anggota KEYWORDS. Bila ya, kelas token adalah KEYWORD, dan bila tidak, kelasnya adalah IDENTIFIER.

Strategi ini disebut pembedaan pasca-pemindaian (reserved-word lookup). Alternatifnya adalah memeriksa tabel kata kunci pada setiap transisi karakter, tetapi pendekatan itu rumit dan tidak menguntungkan karena kata kunci dalam bahasa mini v1 berbentuk identifier yang polanya identik dengan identifier biasa. Pembedaan pasca-pemindaian memisahkan dua tanggung jawab, yaitu pengenalan pola (identifier) dan keputusan kelas (kata kunci atau identifier), sehingga kode pemindai identifier tetap sederhana.

Pemakaian frozenset memberikan keanggotaan $O(1)$ rata-rata dan sifat tidak-terubah yang sesuai dengan tabel tetap. Tabel kata kunci tidak berubah selama pemindaian, sehingga tidak ada risiko satu token membaca tabel yang dimodifikasi oleh token lain. Sifat tidak-terubah ini juga memungkinkan tabel KEYWORDS didefinisikan sekali pada level modul dan dipakai oleh semua instansi Lexer tanpa risiko diubah oleh salah satu pemanggilan.

Prinsip maximal munch#

Prinsip maximal munch menyatakan bahwa pada posisi pemindaian tertentu, scanner memilih lexeme terpanjang yang valid. Prinsip ini penting untuk operator dua karakter seperti <=, >=, ==, dan !=, yang berbagi karakter pertama dengan operator satu karakter <, >, =, dan !. Bila scanner hanya melihat satu karakter pada satu waktu, string <= akan dipetakan menjadi dua token terpisah, yaitu < dan =, sehingga makna “kurang dari atau sama dengan” hilang.

Penerapan maximal munch pada pemindai operator cukup sederhana. Pemindai menggabungkan karakter saat ini dan karakter berikutnya menjadi string dua karakter, lalu memeriksa apakah string itu anggota DUA_KARAKTER. Bila ya, kedua karakter dikonsumsi sebagai satu token. Bila tidak, hanya karakter saat ini yang dikonsumsi sebagai operator satu karakter.

Tabel DUA_KARAKTER berisi {"<=", ">=", "==", "!="} dan tabel SATU_KARAKTER berisi {"+", "-", "*", "/", "<", ">", "=", "!"}. Urutan pemeriksaan dua-karakter-lebih-dahulu menjamin maximal munch, sebab pemeriksaan satu karakter hanya dilakukan bila pemeriksaan dua karakter tidak menghasilkan kecocokan. Tanpa urutan ini, <= akan terambil sebagai < lalu =, sehingga operator dua karakter terurai sebagai dua operator satu karakter terpisah.

Loop utama lexer#

Loop utama memeriksa karakter saat ini, lalu memanggil pemindai yang sesuai untuk kelas token. Spasi putih dan baris baru dilewati, komentar // dikonsumsi sampai akhir baris, dan pemindai per kelas dijalankan untuk huruf, digit, tanda kutip, tanda baca, dan operator. Diagram berikut menggambarkan alur keputusan loop utama.

Loop utama lexer: peek karakter, klasifikasi jenis, panggil pemindai per kelas, lalu kembali ke peek

Bentuk kode loop utama terlihat pada metodetokens()di berkaslexer.py. Setiap cabang mengembalikan token ke daftarout, dan loop berlanjut sampai seluruh karakter habis. TokenEOFditambahkan pada akhir daftar sebagai penanda akhir masukan.

pythonlexer.py

"""Scanner tulis tangan untuk bahasa mini v1.Antarmuka publik:Lexer(source).tokens() -> list[Token]Token adalah namedtuple dengan field (type, lexeme, line, column).Kelas token yang dikenal: KEYWORD, IDENTIFIER, NUMBER, STRING, OPERATOR,PUNCT, EOF.Karakteristik scanner:- tabel kata kunci KEYWORDS untuk membedakan IDENTIFIER dan KEYWORD- prinsip maximal munch pada operator dua karakter (<=, >=, ==, !=)- loop utama dengan peek dan advance- komentar // dilewati sampai akhir baris- spasi putih (spasi, tab, baris baru) dilewati"""fromcollectionsimportnamedtupleToken=namedtuple("Token",["type","lexeme","line","column"])# Tabel kata kunci bahasa mini v1 (lihat spesifikasi pada modul 0).KEYWORDS=frozenset({"let","print","if","else","while","true","false","nil","and","or",})# Operator dua karakter yang harus dicocokkan lebih dulu (maximal munch).DUA_KARAKTER={"<=",">=","==","!="}# Operator satu karakter.SATU_KARAKTER=set("+-*/<>!=")# Tanda baca (pemisah) satu karakter.PUNCT=set("(){}")classLexer:"""Scanner tulis tangan untuk bahasa mini v1."""def__init__(self,source:str):self.src=sourceself.pos=0self.line=1self.column=1# ----- utilitas karakter -----def_peek(self,offset:int=0)->str:idx=self.pos+offsetifidx>=len(self.src):return""returnself.src[idx]def_advance(self)->str:ch=self.src[self.pos]self.pos+=1ifch=="\n":self.line+=1self.column=1else:self.column+=1returnchdef_at_end(self)->bool:returnself.pos>=len(self.src)# ----- pemindai utama -----deftokens(self)->list[Token]:out:list[Token]=[]whilenotself._at_end():ch=self._peek()ifchin"\t\r\n":self._advance()continueifch=="/"andself._peek(1)=="/":self._komentar()continueifch.isalpha()orch=="_":out.append(self._identifier())continueifch.isdigit():out.append(self._angka())continueifch=='"':out.append(self._string())continueifchinPUNCT:line,col=self.line,self.columnself._advance()out.append(Token("PUNCT",ch,line,col))continueifchinSATU_KARAKTER:out.append(self._operator())continue# Karakter tak dikenal: dilewati tanpa pesan pada versi ini.# Penanganan error leksikal dibahas terpisah pada scanner# yang memperluas antarmuka publik lexer ini.self._advance()out.append(Token("EOF","",self.line,self.column))returnout# ----- pemindai per kelas -----def_komentar(self)->None:# Konsumsi kedua tanda garis miring, lalu sisa baris.self._advance()# '/'self._advance()# '/'whilenotself._at_end()andself._peek()!="\n":self._advance()def_identifier(self)->Token:line,col=self.line,self.columnstart=self.poswhilenotself._at_end()and(self._peek().isalnum()orself._peek()=="_"):self._advance()lex=self.src[start:self.pos]kelas="KEYWORD"iflexinKEYWORDSelse"IDENTIFIER"returnToken(kelas,lex,line,col)def_angka(self)->Token:line,col=self.line,self.columnstart=self.poswhilenotself._at_end()andself._peek().isdigit():self._advance()# Bagian desimal opsional: titik diikuti deret digit.ifself._peek()=="."andself._peek(1).isdigit():self._advance()# '.'whilenotself._at_end()andself._peek().isdigit():self._advance()returnToken("NUMBER",self.src[start:self.pos],line,col)def_string(self)->Token:line,col=self.line,self.columnself._advance()# tanda kutip pembukastart=self.poswhilenotself._at_end()andself._peek()!='"':self._advance()# Asumsi pada v1: string ditutup dengan benar (modul 0 menunda escape).lex='"'+self.src[start:self.pos]+'"'ifnotself._at_end():self._advance()# tanda kutip penutupreturnToken("STRING",lex,line,col)def_operator(self)->Token:line,col=self.line,self.columndua=self._peek()+self._peek(1)ifduainDUA_KARAKTER:self._advance()self._advance()returnToken("OPERATOR",dua,line,col)ch=self._advance()returnToken("OPERATOR",ch,line,col)defmain()->None:source=('// contoh lexer\n''let n = 10\n''let hasil = 0\n''while n > 0 {\n'' hasil = hasil + n\n'' n = n - 1\n''}\n''print hasil\n')lexer=Lexer(source)fortinlexer.tokens():print(f"{t.line:>2}:{t.column:<3}{t.type:<10}{t.lexeme!r}")if__name__=="__main__":main()

Keluaran scanner#

Keluaran berikut diperoleh dengan menjalankanpython3 lexer.py. Setiap baris keluaran menampilkan satu token dengan formatbaris:kolom kelas lexeme. Komentar// contoh lexerpada baris 1 tidak menghasilkan token apa pun, sehingga token pertama muncul pada baris 2. Operator=dikenali sebagaiOPERATORsatu karakter, dan>juga dikenali sebagaiOPERATORsatu karakter karena tidak diikuti=.

textKeluaran

2:1 KEYWORD 'let'2:5 IDENTIFIER 'n'2:7 OPERATOR '='2:9 NUMBER '10'3:1 KEYWORD 'let'3:5 IDENTIFIER 'hasil'3:11 OPERATOR '='3:13 NUMBER '0'4:1 KEYWORD 'while'4:7 IDENTIFIER 'n'4:9 OPERATOR '>'4:11 NUMBER '0'4:13 PUNCT '{'5:5 IDENTIFIER 'hasil'5:11 OPERATOR '='5:13 IDENTIFIER 'hasil'5:19 OPERATOR '+'5:21 IDENTIFIER 'n'6:5 IDENTIFIER 'n'6:7 OPERATOR '='6:9 IDENTIFIER 'n'6:11 OPERATOR '-'6:13 NUMBER '1'7:1 PUNCT '}'8:1 KEYWORD 'print'8:7 IDENTIFIER 'hasil'9:1 EOF ''

TokenEOFpada baris 9 kolom 1 menandai akhir masukan. Posisi yang dicatat pada tokenEOFadalah posisi setelah token terakhir, sehingga parser dapat menyebut posisi akhir jika melaporkan error “akhir masukan tak terduga”. Konsistensi antara token biasa danEOFdalam hal pencatatan posisi membuat kode parser tidak perlu memperlakukan akhir masukan sebagai kasus khusus.

Kesalahan umum#

Beberapa kesalahan sering muncul saat scanner ditulis pertama kali. Pertama, lupa memeriksa dua karakter lebih dahulu pada pemindai operator, sehingga<=terambil sebagai<lalu=. Kedua, mencatatlinedancolumnpada akhir lexeme alih-alih awal, sehingga pesan error menunjuk ke akhir token. Ketiga, mengabaikan baris baru saat memperbaruicolumn, sehinggacolumnterus bertambah melintasi baris dan pesan error menyebut kolom yang melebihi lebar baris.

Ringkasan#

Scanner tulis tangan memakai dua operasi dasar, yaitu_peek()untuk membaca karakter tanpa memajukan indeks dan_advance()untuk mengonsumsi karakter sekaligus memperbarui posisi sumber.
TabelKEYWORDSberisi sepuluh kata kunci bahasa mini v1, dan pembedaanKEYWORDversusIDENTIFIERdilakukan setelah pemindai identifier selesai, bukan pada level transisi karakter.
Prinsip maximal munch diterapkan dengan memeriksa operator dua karakter lebih dahulu sebelum operator satu karakter, sehingga<=,>=,==, dan!=terambil sebagai satu token.
Antarmuka publikLexer(source).tokens()mengembalikanlist[Token]yang berakhir denganEOF, dan kontrak ini dipakai parser.

Referensi#

Crafting Interpreters — Bob Nystrom— Bab “Scanning” menampilkan scanner tulis tangan untuk bahasa Lox dengan peek, advance, dan tabel kata kunci.
Flex (lexical analyser generator) — Wikipedia— Penjelasan generator lexer yang memperjelas maximal munch dan aturan pencocokan terpanjang pada scanner otomatis.
Lexical analysis — Wikipedia— Ringkasan teknik scanner, termasuk prinsip longest match dan reserved-word lookup.