KAL
Menu

Parser Generator

Posisi yacc, bison, dan ANTLR dibandingkan terhadap parser tulis tangan.

Daftar isi

Parser generator adalah perkakas yang menerima grammar tata bahasa sebagai masukan dan menghasilkan kode parser secara otomatis. Topik ini membahas perbandingan parser generator seperti yacc, bison, dan ANTLR dengan parser tulis tangan, lalu menunjukkan dua contoh konkret dengan Python ast.parse dan pustaka lark. Pembaca memperoleh berkas parser_gen_demo.py yang memperlihatkan keluaran AST dari dua pendekatan, beserta pemahaman kapan generator dipilih dan kapan parser tulis tangan lebih sesuai.

Apa itu parser generator#

Parser generator menerima grammar tata bahasa sebagai masukan dan menghasilkan kode parser, baik dalam bahasa yang sama (lark di Python) maupun dalam bahasa target berbeda (yacc menghasilkan C). Generator mengabstraksikan detail transisi token, tabel lookahead, dan konstruksi AST, sehingga penulis bahasa cukup mendeskripsikan sintaksis dan menentukan aksi per aturan. Pola ini disebut “berikan grammar, dapatkan parser”, dan sebagian besar generator modern juga menyertakan pembangkit AST otomatis.

Generator tertua yang masih dipakai adalah yacc (Yet Another Compiler Compiler) dari 1970-an, yang menghasilkan parser LALR(1) dalam C. Penggantinya, bison, memperluas yacc dengan dukungan tata bahasa yang lebih besar dan pesan error yang lebih baik. ANTLR adalah generator modern yang mendukung LL(*) dan menghasilkan parser dalam Java, C#, Python, dan lainnya. Lark adalah generator Python yang berjalan pada saat runtime, sehingga cocok untuk prototyping dan pengajaran.

Parser generator versus tulis tangan#

Pemilihan antara generator dan tulis tangan bergantung pada empat pertimbangan. Pertama, kecepatan pengembangan. Generator mempersingkat penulisan parser, sebab grammar menjadi sumber kebenaran dan kode parser dibangkitkan. Tulis tangan memerlukan setiap metode per aturan, tetapi memberi kendali penuh atas pesan error dan struktur AST. Kedua, kualitas pesan error. Parser tulis tangan menghasilkan pesan yang lebih kontekstual karena penulis tahu titik keputusan, sedangkan generator sering menghasilkan pesan generik seperti “syntax error” kecuali diberi anotasi tambahan.

Ketiga, kompleksitas tata bahasa. Tata bahasa sederhana seperti bahasa mini v1 cukup ditulis tangan, sedangkan tata bahasa besar seperti C++ sering memerlukan generator atau rekayasa khusus pada parser tulis tangan (GCC dan Clang memakai recursive descent tulis tangan untuk C++, tetapi memerlukan penanganan kasus khusus yang rumit). Keempat, ketergantungan perkakas. Generator menambah ketergantungan pada perkakas eksternal, sedangkan parser tulis tangan hanya memerlukan kompiler bahasa target. Pada proyek dengan kendala ketergantungan, tulis tangan menjadi pilihan.

Pada jalur ini, parser tulis tangan dipilih untuk bahasa mini v1 sebab pembaca perlu memahami mekanisme parsing, bukan mengandalkan generator sebagai kotak hitam. Topik ini menunjukkan konsep generator dengan dua contoh, tanpa meminta pembaca membangun parser berbasis generator untuk proyek jalur.

Python ast.parse sebagai contoh generator bawaan#

Python sendiri mempunyai parser bawaan yang dapat diakses lewat modul ast. Parser ini dikembangkan dari grammar EBNF (berkas Grammar/python.gram di CPython) yang diolah oleh pgenerator menjadi kode C. Meskipun pengguna Python tidak menulis grammar sendiri, parser ini tetap merupakan hasil generator, dan ast.dump memperlihatkan AST yang dihasilkan.

Demo pertama pada berkas parser_gen_demo.py memanggil ast.parse("1 + 2 * 3", mode="eval") dan menampilkan AST dengan ast.dump(tree, indent=2). Mode "eval" membatasi masukan ke ekspresi tunggal, sehingga AST yang dihasilkan adalah ast.Expression yang membungkus ast.BinOp. Struktur node BinOp(left, op, right) pada Python AST mirip dengan Binary(left, op, right) pada AST bahasa mini v1, sehingga pemetaan konseptual menjadi sederhana.

Lark sebagai parser generator runtime#

Lark adalah parser generator Python yang menerima grammar EBNF dan membangun parser pada saat runtime. Lark mendukung dua algoritma, yaitu earley (umum, menangani tata bahasa ambigu) dan lalr (lebih cepat, menuntut tata bahasa LALR(1)). Demo kedua pada berkas parser_gen_demo.py memakai parser="lalr" dengan fragmen grammar bahasa mini v1, lalu memparsing let x = 1 + 2 * 3 dan menampilkan pohon derivasi dengan tree.pretty().

Perbedaan mencolok antara lark dan parser tulis tangan adalah jumlah kode. Grammar lark untuk fragmen ini hanya sekitar 15 baris, sedangkan parser tulis tangan pada topik recursive-descent memerlukan ratusan baris untuk mencakup semua lapisan. Namun, keluaran lark berupa pohon derivasi generik (objek Tree), sehingga pembaca perlu mengonversinya ke AST bahasa mini v1 yang spesifik. Konversi ini biasanya dilakukan dengan kelas Transformer lark, yang menambah beberapa baris lagi. Setelah konversi, total kode tidak jauh lebih ringkas daripada tulis tangan, tetapi grammar menjadi sumber kebenaran yang lebih mudah dibaca.

Berkas parser_gen_demo.py#

Berkas berikut memperlihatkan kedua demo. Demo pertama memakai ast.parse bawaan Python, sedangkan demo kedua memakai lark untuk membangun parser dari grammar EBNF pada saat runtime. Keduanya mengilustrasikan pola generator, yaitu masukan grammar dan keluaran AST, tanpa kode parsing tulis tangan.

python parser_gen_demo.py 
"""Demo parser generator: Python ast.parse dan lark.

Topik parser-generator memakai demo ini untuk memperlihatkan
konsep parser generator tanpa menulis grammar sendiri:

  1. `ast.parse` adalah parser bawaan Python yang menghasilkan AST
     modul standar. Parser ini dikembangkan dari grammar EBNF
     (berkas Grammar/python.gram di CPython) yang diolah oleh
     pgenerator menjadi kode C. Demo memanggilnya pada mode
     "eval" (ekspresi tunggal) dan menampilkan AST yang
     dihasilkan dengan `ast.dump`.
  2. `lark` adalah parser generator Python yang menerima grammar
     EBNF dan membangun parser pada saat runtime. Demo memakainya
     pada fragmen bahasa mini v1 sebagai pembanding, dengan
     keluaran pohon derivasi yang menyerupai keluaran bnf_demo.py.

Keduanya mengilustrasikan pola yang sama, yaitu "berikan grammar,
dapatkan AST", tanpa kode parsing tulis tangan.
"""
import ast

from lark import Lark


# ----- 1. Parser bawaan Python (ast.parse) -----
def demo_python_ast() -> None:
    print("=== Parser bawaan Python (ast.parse) ===")
    source = "1 + 2 * 3"
    print(f"Sumber: {source}")
    # mode="eval": ekspresi tunggal, menghasilkan ast.Expression.
    tree = ast.parse(source, mode="eval")
    print(ast.dump(tree, indent=2))
    print()


# ----- 2. Parser generator lark untuk fragmen bahasa mini v1 -----
def demo_lark() -> None:
    print("=== Parser generator lark ===")
    grammar = r"""
    program: stmt+
    stmt: let_stmt
    let_stmt: LET IDENT EQ expr
    expr: term ((PLUS | MINUS) term)*
    term: factor ((STAR | SLASH) factor)*
    factor: NUMBER | IDENT | LPAREN expr RPAREN

    LET: "let"
    EQ: "="
    PLUS: "+"
    MINUS: "-"
    STAR: "*"
    SLASH: "/"
    LPAREN: "("
    RPAREN: ")"
    IDENT: /[A-Za-z_][A-Za-z0-9_]*/
    NUMBER: /[0-9]+(\.[0-9]+)?/

    %import common.WS
    %ignore WS
    """
    parser = Lark(grammar, start="program", parser="lalr")
    source = "let x = 1 + 2 * 3"
    print(f"Sumber: {source}")
    tree = parser.parse(source)
    print(tree.pretty())


def main() -> None:
    demo_python_ast()
    demo_lark()


if __name__ == "__main__":
    main()

Keluaran berikut diperoleh dengan menjalankan python3 parser_gen_demo.py. Bagian pertama memperlihatkan AST Python bawaan untuk 1 + 2 * 3, dengan BinOp berisi op=Add(), left=Constant(value=1), dan right=BinOp yang membungkus Constant(value=2), op=Mult(), dan Constant(value=3). Struktur ini menyerupai Binary('+', Literal(1), Binary('*', Literal(2), Literal(3))) pada AST bahasa mini v1, sehingga konsepnya dapat dipetakan langsung. Bagian kedua memperlihatkan pohon derivasi lark untuk let x = 1 + 2 * 3, dengan expr sebagai akar, term pertama sebagai factor 1, dan term kedua sebagai factor * factor (2 * 3), persis seperti pohon pada topik tata-bahasa.

text Keluaran 
=== Parser bawaan Python (ast.parse) ===
Sumber: 1 + 2 * 3
Expression(
  body=BinOp(
    left=Constant(value=1),
    op=Add(),
    right=BinOp(
      left=Constant(value=2),
      op=Mult(),
      right=Constant(value=3))))

=== Parser generator lark ===
Sumber: let x = 1 + 2 * 3
program
  stmt
    let_stmt
      let
      x
      =
      expr
        term
          factor	1
        +
        term
          factor	2
          *
          factor	3

Ringkasan#

  • Parser generator menerima grammar tata bahasa sebagai masukan dan menghasilkan kode parser, sehingga penulis bahasa cukup mendeskripsikan sintaksis dan menentukan aksi per aturan.
  • yacc, bison, ANTLR, dan lark adalah generator yang lazim, dengan lark berjalan pada saat runtime di Python.
  • Pemilihan antara generator dan tulis tangan bergantung pada kecepatan pengembangan, kualitas pesan error, kompleksitas tata bahasa, dan ketergantungan perkakas.
  • Python ast.parse adalah contoh parser hasil generator yang sudah bawaan, sedangkan lark membangun parser dari grammar EBNF pada saat runtime dan menghasilkan pohon derivasi yang dapat dikonversi ke AST spesifik.

Referensi#