KAL
Menu

Tata Bahasa

BNF, derivasi, dan ambiguitas sebagai alat mendeskripsikan sintaksis bahasa.

Daftar isi

Tata bahasa formal mendeskripsikan sintaksis bahasa pemrograman sebagai himpunan aturan produksi, sehingga parser dapat memutuskan apakah deret token membentuk kalimat yang sah. Topik ini membahas BNF sebagai notasi standar tata bahasa, derivasi kalimat sebagai jejak penerapan aturan, ambiguitas sebagai sumber kegagalan semantik, dan contoh konkret memakai pustaka lark untuk menghasilkan pohon derivasi dari fragmen bahasa mini v1. Pembaca memperoleh BNF lengkap untuk bahasa mini v1 dan pemahaman mengapa tata bahasa yang ditulis tangan harus bebas ambiguitas.

Tata bahasa formal dan BNF#

Tata bahasa formal (formal grammar) adalah himpunan aturan yang menetapkan himpunan kalimat sah pada sebuah bahasa. Notasi yang paling banyak dipakai adalah BNF (Backus-Naur Form), diperkenalkan oleh John Backus dan Peter Naur pada akhir 1950-an untuk mendeskripsikan bahasa ALGOL. BNF memakai produksi berbentuk nonterminal := terminal terminal ... | alternatif, di mana := berarti “didefinisikan sebagai” dan | memisahkan alternatif.

Setiap tata bahasa memiliki empat komponen. Komponen pertama adalah himpunan simbol terminal, yaitu token yang dihasilkan lexer. Komponen kedua adalah himpunan simbol nonterminal, yaitu nama aturan yang masih harus diturunkan. Komponen ketiga adalah himpunan produksi, yaitu aturan yang menggantikan nonterminal dengan deret simbol. Komponen keempat adalah simbol awal, yaitu nonterminal yang menjadi titik mula derivasi. Pada bahasa mini v1, simbol awalnya adalah program.

BNF dapat diperluas menjadi EBNF (Extended BNF) dengan operator * (nol atau lebih), + (satu atau lebih), dan ? (nol atau satu). EBNF tidak menambah kekuatan ekspresif, tetapi mempersingkat aturan repetitif. Sebagai contoh, statement* EOF lebih ringkas daripada menulis statement statement statement ... dengan kemungkinan berhenti pada titik mana pun. Bahasa mini v1 memakai EBNF pada spesifikasi modul 0, dan demo pada topik ini juga memakai EBNF lark.

BNF untuk bahasa mini v1#

Spesifikasi pada modul 0 menetapkan BNF lengkap untuk bahasa mini v1. BNF berikut menetapkan program, pernyataan, dan ekspresi dengan lapisan presedensi. Notasi * berarti nol atau lebih, ? berarti nol atau satu, dan | berarti pilihan. Karakter dalam tanda kutip adalah terminal literal.

text BNF bahasa mini v1 
program     := statement* EOF

statement   := let_stmt
             | print_stmt
             | if_stmt
             | while_stmt
             | block_stmt
             | expr_stmt

let_stmt    := "let" IDENT "=" expression
print_stmt  := "print" expression
if_stmt     := "if" expression block ("else" block)?
while_stmt  := "while" expression block
block_stmt  := "{" statement* "}"
expr_stmt   := expression

expression  := logic_or
logic_or    := logic_and ("or" logic_and)*
logic_and   := equality ("and" equality)*
equality    := comparison (("==" | "!=") comparison)*
comparison  := term (("<" | "<=" | ">" | ">=") term)*
term        := factor (("+" | "-") factor)*
factor      := unary (("*" | "/") unary)*
unary       := ("-" | "!") unary | primary
primary     := NUMBER | STRING | "true" | "false" | "nil"
             | IDENT | "(" expression ")"

Tata bahasa ini memenuhi dua sifat yang dipakai parser tulis tangan. Sifat pertama, tidak ada produksi rekursi kiri pada lapisan ekspresi, karena lapisan ditulis sebagai iterasi factor (("+" | "-") factor)* alih-alih expr := expr "+" factor. Sifat kedua, setiap titik keputusan dapat diambil berdasarkan satu token lookahead, sehingga parser dapat memutuskan cabang dengan pemeriksaan sederhana pada token saat ini. Tata bahasa yang memenuhi dua sifat ini disebut LL(1).

Derivasi kalimat#

Derivasi adalah jejak penerapan aturan produksi dari simbol awal hingga kalimat terminal. Sebagai contoh, kalimat let x = 1 + 2 * 3 diturunkan melalui langkah berikut. program diturunkan menjadi statement* EOF, kemudian statement diturunkan menjadi let_stmt, lalu let_stmt diturunkan menjadi "let" IDENT "=" expression. IDENT diturunkan menjadi x, dan expression diturunkan melewati logic_or, logic_and, equality, comparison, hingga term.

Pada lapisan term, produksi factor (("+" | "-") factor)* mengikat 1 sebagai factor pertama, kemudian + dan factor kedua. Factor kedua ini adalah 2 * 3, yang diturunkan lebih lanjut melalui term dan factor (("*" | "/") factor)*. Hasil akhirnya adalah pohon derivasi dengan + sebagai akar, 1 sebagai anak kiri, dan 2 * 3 sebagai anak kanan. Derivasi dapat dilakukan dengan strategi leftmost (nonterminal paling kiri diturunkan lebih dulu) atau rightmost, tetapi keduanya menghasilkan pohon yang sama jika tata bahasa tidak ambigu.

Ambiguitas tata bahasa#

Tata bahasa disebut ambigu apabila ada satu kalimat yang memiliki dua pohon derivasi berbeda. Ambiguitas berbahaya karena parser tidak dapat memutuskan struktur mana yang dimaksud pengguna, sehingga semantik program menjadi tidak pasti. Contoh klasik adalah tata bahasa expr := expr "+" expr | expr "*" expr | NUMBER. Kalimat 1 + 2 * 3 memiliki dua pohon, yaitu pohon pertama dengan + sebagai akar (salah, karena * lebih tinggi) dan pohon kedua dengan * sebagai akar (benar). Tanpa aturan presedensi eksplisit, parser dapat memilih salah satu secara sembarangan.

Solusi yang dipakai bahasa mini v1 adalah memecah lapisan ekspresi menjadi beberapa nonterminal yang mencerminkan presedensi, yaitu equality, comparison, term, factor, dan unary. Setiap lapisan hanya mengikat operator pada presedensinya, dan lapisan di bawahnya dipanggil sebagai operand. Strategi ini menghilangkan ambiguitas tanpa menambah kekuatan ekspresif tata bahasa. Pemecahan lapisan juga mempermudah penulisan parser recursive descent.

Demo BNF dengan lark#

Pustaka lark adalah parser generator Python yang menerima grammar EBNF dan membangun parser pada saat runtime. Demo berikut memakai lark untuk memparsing dua pernyataan let dengan ekspresi aritmetika, lalu mencetak pohon derivasi yang dihasilkan. Grammar pada demo hanya mencakup fragmen bahasa mini v1 (pernyataan let dengan penjumlahan dan perkalian) agar pohon keluaran tetap dapat dibaca.

python bnf_demo.py 
"""Demo BNF untuk fragmen bahasa mini v1 memakai pustaka lark.

Topik tata-bahasa memakai demo ini untuk memperlihatkan bagaimana
aturan BNF berubah menjadi pohon derivasi konkret. Fragmen yang
dipakai mencakup pernyataan `let` dengan ekspresi aritmetika
lengkap, sehingga pohon yang dihasilkan menunjukkan beberapa level
presedensi (penjumlahan dan perkalian) tanpa membengkak.

Notasi EBNF lark:
  * berarti nol atau lebih
  + berarti satu atau lebih
  ? berarti nol atau satu
  | berarti pilihan
Token bernama (huruf kapital, misalnya PLUS) dipertahankan dalam
pohon, sedangkan literal string anonim (misalnya "+") dibuang
secara default. Demo ini memakai token bernama agar operator
muncul pada pohon keluaran.
"""
from lark import Lark


# Fragmen BNF bahasa mini v1 (lihat spesifikasi pada modul 0).
# Hanya mencakup pernyataan `let` dengan ekspresi aritmetika
# penjumlahan dan perkalian, agar pohon tetap ringkas.
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
"""


def main() -> None:
    parser = Lark(GRAMMAR, start="program", parser="lalr")
    source = "let x = 1 + 2 * 3\nlet y = (1 + 2) * 3"
    print("=== Sumber ===")
    print(source)
    print()
    print("=== Pohon derivasi (lark) ===")
    tree = parser.parse(source)
    print(tree.pretty())


if __name__ == "__main__":
    main()

Keluaran berikut diperoleh dengan menjalankan python3 bnf_demo.py. Pohon pertama menunjukkan bahwa 1 + 2 * 3 diurai dengan + sebagai akar dan 2 * 3 sebagai sub-term, sesuai presedensi * yang lebih tinggi dari +. Pohon kedua menunjukkan bahwa tanda kurung () memaksa 1 + 2 menjadi sub-expr dalam factor, sehingga * mengikat sub-expr tersebut dengan 3 sebagai akar. Kedua pohon tidak ambigu karena grammar memecah ekspresi menjadi lapisan expr dan term.

text Keluaran 
=== Sumber ===
let x = 1 + 2 * 3
let y = (1 + 2) * 3

=== Pohon derivasi (lark) ===
program
  stmt
    let_stmt
      let
      x
      =
      expr
        term
          factor	1
        +
        term
          factor	2
          *
          factor	3
  stmt
    let_stmt
      let
      y
      =
      expr
        term
          factor
            (
            expr
              term
                factor	1
              +
              term
                factor	2
            )
          *
          factor	3

Kesalahan umum#

Beberapa kesalahan sering muncul saat tata bahasa ditulis. Pertama, menulis expr := expr "+" term secara rekursif kiri, sehingga parser tulis tangan jatuh ke rekursi tak terhingga. Kedua, mencampur presedensi dalam satu nonterminal, misalnya expr := expr "+" expr | expr "*" expr, yang menghasilkan tata bahasa ambigu. Ketiga, lupa menambahkan EOF pada simbol awal, sehingga parser menerima sisa masukan yang tidak diharapkan tanpa melaporkan error.

Ringkasan#

  • BNF mendeskripsikan sintaksis sebagai himpunan produksi nonterminal := ... | alternatif, dengan empat komponen, yaitu terminal, nonterminal, produksi, dan simbol awal.
  • Bahasa mini v1 memakai BNF berlapis untuk ekspresi, dengan presedensi ditetapkan oleh urutan nonterminal logic_or, logic_and, equality, comparison, term, factor, dan unary.
  • Ambiguitas dihindari dengan memecah lapisan ekspresi menjadi beberapa nonterminal, sehingga setiap kalimat memiliki pohon derivasi tunggal.
  • Pustaka lark menghasilkan pohon derivasi konkret dari BNF, yang menjadi referensi visual saat memverifikasi parser tulis tangan.

Referensi#