Token dan Lexeme

Token adalah unit terkecil yang diproses parser, dan lexeme adalah teks pada kode sumber yang dipetakan lexer menjadi sebuah token. Topik ini membahas kelas token yang dikenali lexer bahasa mini v1, struktur data yang dipakai untuk merepresentasikan token, dan pelacakan baris serta kolom yang memungkinkan pesan diagnostik menyebut posisi sumber dengan tepat. Pembaca memperoleh kontrak data token yang akan dipakai ulang oleh parser dan tahap analisis semantik.

Lexeme dan token#

Lexeme adalah deret karakter pada kode sumber yang membentuk satu kesatuan leksikal. Saat lexer membaca teks let hasil = 0, lexer mengenali empat lexeme, yaitu let, hasil, =, dan 0. Token adalah pasangan (kelas, lexeme) yang dilengkapi posisi sumber, sehingga tahap berikutnya tidak perlu memeriksa karakter per karakter.

Pemetaan dari lexeme ke token bersifat banyak-satu. Lexeme let, print, dan while semuanya dipetakan ke kelas KEYWORD, sedangkan hasil, i, dan nama dipetakan ke kelas IDENTIFIER. Pembedaan antara lexeme (teks mentah) dan token (kelas plus teks plus posisi) menjaga agar konsep leksikal dan sintaksis tidak tercampur aduk ketika pesan error ditulis. Sebuah token sudah membawa kelasnya, sehingga parser tidak perlu menelusuri ulang karakter untuk memutuskan cabang produksi yang sesuai.

Lexeme yang identik dapat dipetakan ke kelas berbeda bergantung pada konteks leksikal. Misalnya, lexeme true adalah KEYWORD karena termasuk kata kunci, sedangkan lexeme benar adalah IDENTIFIER karena bukan kata kunci. Pemetaan ini sepenuhnya ditentukan pada tahap leksikal, tanpa melibatkan tabel simbol atau cakupan (scope) yang merupakan urusan semantik.

Kelas token bahasa mini v1#

Bahasa mini v1 mengenal tujuh kelas token. Tiap kelas memiliki pola leksikal yang khas, dan keanggotaan sebuah lexeme dalam satu kelas menentukan cabang parser yang akan memproses lexeme tersebut. Tabel berikut menyajikan kelas, contoh lexeme, dan peran singkat.

Daftar kata kunci yang termasuk kelas KEYWORD ditetapkan oleh spesifikasi bahasa mini v1, yaitu let, print, if, else, while, true, false, nil, and, dan or. Lexer memeriksa keanggotaan sebuah lexeme dalam himpunan kata kunci setelah memutuskan bahwa lexeme tersebut berbentuk identifier, sehingga pembedaan dilakukan pada tahap pasca-pemindaian, bukan pada level transisi karakter.

Kelas NUMBER tidak membedakan bilangan bulat dan desimal di tingkat token, karena pembedaan tersebut adalah urusan semantik dan dapat diturunkan dari lexeme. Lexeme yang memuat tanda titik menandakan bilangan desimal, sedangkan lexeme tanpa titik menandakan bilangan bulat. Pemisahan kelas pada level token akan membebani parser tanpa keuntungan, sebab parser hanya perlu tahu bahwa sebuah token adalah bilangan, dan konversi ke tipe int atau float dilakukan kemudian oleh tahap analisis semantik.

Pelacakan posisi sumber#

Setiap token membawa nomor baris dan kolom pada kode sumber. Nomor baris dimulai dari 1, dan nomor kolom dimulai dari 1 pada setiap baris. Bila lexer melaporkan karakter ilegal pada baris 3 kolom 14, pembaca dapat membuka berkas sumber dan melihat langsung posisi tersebut tanpa menghitung ulang.

Pelacakan posisi diperlukan karena pesan error tanpa lokasi hampir tidak berguna. Bandingkan pesan “error: identifier tak terdefinisi” dengan pesan “error: identifier nmaa tak terdefinisi pada baris 7 kolom 5”. Pesan kedua menyatakan dengan tepat posisi sumber yang perlu diperbaiki, sedangkan pesan pertama hanya menyatakan bahwa ada sesuatu yang salah di suatu tempat. Tanpa pelacakan, sebuah compiler bahkan tidak dapat menyebutkan token mana yang menyebabkan masalah.

Lexer memelihara dua buah penghitung, yaitu line dan column. Keduanya diperbarui setiap kali sebuah karakter dikonsumsi. Karakter baris baru menambah line dan mereset column ke 1, sedangkan karakter biasa menambah column. Saat sebuah lexeme selesai dipindai, token yang dibangun mencatat line dan column pada awal lexeme tersebut, bukan pada akhirnya, sehingga pesan error menunjuk ke awal token yang bermasalah, bukan ke akhir.

Token sebagai data immutable#

Token direpresentasikan sebagai namedtuple Python dengan empat field, yaitu type, lexeme, line, dan column. namedtuple dipilih karena tiga alasan. Pertama, objek token tidak perlu diubah setelah dibuat, dan namedtuple pada dasarnya adalah tuple biasa dengan nama field, sehingga token bersifat tidak terubah secara default. Kedua, akses field dengan nama seperti token.type membuat kode parser lebih jelas dibanding akses indeks seperti token[0]. Ketiga, namedtuple ringan dan dapat di-hash, sehingga daftar token dapat disimpan, dibandingkan, dan diperiksa keanggotaannya dengan biaya rendah.

Kontrak data ini dipakai ulang oleh parser dan tahap analisis semantik. Parser menerima list[Token] dari lexer, mengonsumsi token satu per satu, dan membangun pohon sintaksis. Karena struktur Token bersifat publik dan tidak berubah sepanjang pipeline, tahap-tahap berikutnya pada pipeline dapat mengandalkan field yang sama, yaitu type, lexeme, line, dan column, tanpa perlu tahu bagaimana lexer membangunnya.

Membangun token secara manual#

Struktur Token dapat ditunjukkan dengan membangun beberapa token secara manual. Berkas token_demo.py berikut membangun dua belas token yang mewakili potongan program let hasil = 0 dan while i <= 10 { ... }, kemudian mencetaknya dengan format yang menampilkan posisi, kelas, dan lexeme.

"""Contoh pembangunan Token secara manual untuk topik token-dan-lexeme.

Token direpresentasikan sebagai namedtuple dengan empat field:
  - type: kelas token, salah satu dari TOKEN_KINDS
  - lexeme: teks sumber yang cocok dengan token
  - line: nomor baris (mulai dari 1)
  - column: nomor kolom (mulai dari 1)
"""
from collections import namedtuple

# Kelas token yang dikenal lexer bahasa mini v1.
TOKEN_KINDS = (
    "KEYWORD",      # kata kunci: let, print, if, else, while, true, false, nil, and, or
    "IDENTIFIER",   # nama buatan pengguna, misalnya hasil, i, nama
    "NUMBER",       # bilangan bulat maupun desimal, misalnya 42, 3.14
    "STRING",       # teks dalam tanda kutip ganda, misalnya "halo"
    "OPERATOR",     # operator: + - * / < <= > >= == != ! =
    "PUNCT",        # tanda baca: ( ) { }
    "EOF",          # penanda akhir masukan
)

# Tabel kata kunci bahasa mini v1, sesuai spesifikasi pada modul 0.
KEYWORDS = frozenset({
    "let", "print", "if", "else", "while",
    "true", "false", "nil", "and", "or",
})

# Struktur data Token. namedtuple dipakai agar objek token ringan dan
# tidak dapat diubah setelah dibuat, sehingga aman dibagikan antar tahap
# pipeline compiler.
Token = namedtuple("Token", ["type", "lexeme", "line", "column"])


def main() -> None:
    # Beberapa token dibangun manual untuk menunjukkan struktur Token.
    # Setiap token membawa posisinya pada kode sumber, sehingga pesan
    # error dapat menyebutkan baris dan kolom dengan tepat.
    tokens = [
        Token("KEYWORD",    "let",     1,  1),
        Token("IDENTIFIER", "hasil",   1,  5),
        Token("OPERATOR",   "=",       1, 11),
        Token("NUMBER",     "0",       1, 13),
        Token("KEYWORD",    "while",   2,  1),
        Token("IDENTIFIER", "i",       2,  7),
        Token("OPERATOR",   "<=",      2,  9),
        Token("NUMBER",     "10",      2, 12),
        Token("PUNCT",      "{",       3,  1),
        Token("STRING",     '"halo"',  4,  5),
        Token("PUNCT",      "}",       5,  1),
        Token("EOF",        "",        5,  2),
    ]
    for t in tokens:
        print(f"{t.line:>2}:{t.column:<3} {t.type:<10} {t.lexeme!r}")


if __name__ == "__main__":
    main()

Keluaran berikut diperoleh dengan menjalankan python3 token_demo.py pada sandbox. Setiap baris keluaran menampilkan posisi, kelas, dan lexeme sebuah token, sehingga struktur Token terlihat langsung dari baris-baris yang dicetak.

 1:1   KEYWORD    'let'
 1:5   IDENTIFIER 'hasil'
 1:11  OPERATOR   '='
 1:13  NUMBER     '0'
 2:1   KEYWORD    'while'
 2:7   IDENTIFIER 'i'
 2:9   OPERATOR   '<='
 2:12  NUMBER     '10'
 3:1   PUNCT      '{'
 4:5   STRING     '"halo"'
 5:1   PUNCT      '}'
 5:2   EOF        ''

Token EOF pada akhir daftar memiliki lexeme kosong dan posisi tepat setelah token terakhir. Konvensi ini dipakai parser untuk mendeteksi akhir masukan tanpa harus memeriksa panjang daftar token pada setiap langkah.

Ringkasan#

• Lexeme adalah teks sumber, sedangkan token adalah kelas, lexeme, dan posisi yang dibungkus menjadi satu unit. Lexer memetakan banyak lexeme ke kelas token yang lebih sedikit.
• Bahasa mini v1 mengenal tujuh kelas token, yaitu KEYWORD, IDENTIFIER, NUMBER, STRING, OPERATOR, PUNCT, dan EOF. Daftar kata kunci ditetapkan oleh spesifikasi, dan pembedaan identifier versus kata kunci dilakukan setelah pemindaian.
• Setiap token membawa line dan column pada awal lexeme, sehingga pesan error dapat menyebut posisi sumber dengan tepat.
• Token dipakai sebagai namedtuple dengan field type, lexeme, line, dan column, dan kontrak ini dipakai ulang oleh parser serta tahap analisis semantik.

Referensi#

• Crafting Interpreters — Bob Nystrom — Bab “Scanning” memperkenalkan konsep token dan lexeme pada bahasa Lox yang menjadi inspirasi bentuk bahasa mini.
• Lexical analysis — Wikipedia — Ringkasan konsep leksikal, kelas token, dan peran scanner dalam pipeline compiler.
• collections.namedtuple — docs.python.org — Dokumentasi resmi struktur namedtuple yang dipakai sebagai representasi Token.