KAL
Menu

Presedensi dan Asosiativitas

Rekursi kiri dan kanan, serta teknik precedence climbing untuk ekspresi berlapis.

Daftar isi

Presedensi menetapkan urutan pengikatan operator pada kalimat dengan beberapa operator, sedangkan asosiativitas menetapkan sisi pengikatan untuk operator yang sama berurutan. Topik ini membahas dua teknik untuk menangani keduanya pada parser tulis tangan, yaitu pemecahan lapisan berbasis rekursi (kiri dan kanan) dan teknik precedence climbing dengan tabel presedensi. Pembaca memperoleh berkas precedence_demo.py yang membandingkan kedua teknik pada kalimat 1 + 2 * 3 dan 1 - 2 - 3, serta menunjukkan kesalahan rekursi kiri yang ditulis tanpa penanganan.

Presedensi dan asosiativitas#

Presedensi (precedence) menetapkan operator mana yang mengikat lebih dulu pada kalimat dengan beberapa operator berbeda. Pada 1 + 2 * 3, operator * mengikat 2 dan 3 lebih dulu karena presedensi * lebih tinggi dari +, sehingga hasilnya 1 + (2 * 3), bukan (1 + 2) * 3. Presedensi ditetapkan oleh bahasa, dan tata bahasa mencerminkannya lewat lapisan nonterminal yang berurutan dari yang paling longgar hingga yang paling ketat.

Asosiativitas (associativity) menetapkan sisi pengikatan untuk operator yang sama berurutan. Sebagian besar operator biner asosiatif kiri, sehingga 1 - 2 - 3 diurai sebagai (1 - 2) - 3. Beberapa operator asosiatif kanan, misalnya penugasan x = y = 5 diurai sebagai x = (y = 5). Pemilihan asosiativitas ditetapkan oleh bahasa, dan tata bahasa mencerminkannya lewat bentuk produksi yang rekursif kiri atau rekursif kanan.

Rekursi kiri dan jebakannya#

Rekursi kiri adalah bentuk produksi expr := expr "+" term | term, di mana nonterminal expr muncul sebagai simbol pertama pada produksi dirinya sendiri. Bentuk ini menghasilkan asosiativitas kiri karena rekursi mengenai operand kiri lebih dulu. Namun, parser recursive descent yang meniru produksi ini secara harfiah akan memanggil expr() lagi sebelum mengonsumsi token apa pun, sehingga rekursi tidak pernah maju dan parser jatuh ke rekursi tak terhingga.

Bug ini muncul karena recursive descent memerlukan kemajuan konsumsi token pada setiap panggilan rekursif. Tanpa konsumsi sebelum rekursi, posisi token tidak pernah maju, dan rekursi berputar di tempat. Solusinya adalah menulis ulang produksi rekursi kiri menjadi bentuk iteratif, yaitu expr := term (("+" | "-") term)*. Bentuk ini ekuivalen secara bahasa, tetapi memakai loop alih-alih rekursi, sehingga parser mengonsumsi token pada setiap iterasi.

Alternatif lain adalah mengganti rekursi kiri dengan rekursi kanan, yaitu expr := term (("+" | "-") expr)?. Bentuk ini tidak menyebabkan rekursi tak terhingga karena operand kiri (term) dikonsumsi lebih dulu, sebelum rekursi pada operand kanan. Namun, rekursi kanan menghasilkan asosiativitas kanan, yang salah untuk operator yang seharusnya asosiatif kiri seperti -. Demo pada berkas precedence_demo.py memperlihatkan kesalahan ini pada kalimat 1 - 2 - 3.

Precedence climbing#

Precedence climbing adalah teknik alternatif yang memakai satu fungsi utama dengan tabel presedensi, alih-alih memecah lapisan menjadi banyak metode. Setiap operator memiliki dua nilai, yaitu left_bp (binding power kiri) dan right_bp (binding power kanan). Fungsi parse_expr(min_bp) mengurai operand kiri, lalu berulang memeriksa operator berikut, dan hanya mengonsumsinya jika left_bp >= min_bp. Setelah konsumsi, fungsi memanggil parse_expr(right_bp) untuk operand kanan.

Untuk operator asosiatif kiri, right_bp = left_bp + 1, sehingga operand kanan hanya mengikat operator berpresedensi lebih tinggi. Operator berikutnya pada presedensi yang sama ditangani oleh loop luar, sehingga pohon yang dihasilkan miring kiri, yaitu asosiatif kiri. Untuk operator asosiatif kanan, right_bp = left_bp, sehingga operand kanan juga mengikat operator pada presedensi yang sama, dan pohon miring kanan.

Pada kalimat 1 + 2 * 3, kedua teknik (lapisan berlapis dan precedence climbing) menghasilkan pohon yang sama, yaitu + sebagai akar dan 2 * 3 sebagai anak kanan. Pada 1 - 2 - 3, precedence climbing menghasilkan pohon (1 - 2) - 3, sedangkan rekursi kanan menghasilkan 1 - (2 - 3). Perbedaan ini menunjukkan bahwa pemilihan asosiativitas mempengaruhi hasil numerik, bukan hanya struktur pohon.

Berkas precedence_demo.py#

Berkas berikut membandingkan tiga pendekatan. Fungsi left_recursion_bug meniru grammar rekursi-kiri secara harfiah dan membatasi kedalaman agar error tertangkap. Fungsi right_recursive memakai rekursi kanan yang berjalan tetapi salah asosiativitas. Fungsi precedence_climbing memakai tabel presedensi yang menghasilkan asosiativitas kiri yang benar.

python precedence_demo.py 
"""Membandingkan teknik parsing ekspresi: rekursi dan precedence climbing.

Tiga parser diuji pada dua kalimat, yaitu "1 + 2 * 3" (uji presedensi)
dan "1 - 2 - 3" (uji asosiativitas kiri):

  1. left_recursion_bug: meniru grammar rekursi-kiri `expr := expr
     '+' term | term` secara harfiah. Tanpa konsumsi token sebelum
     memanggil diri sendiri, parser jatuh ke rekursi tak terhingga.
     Demo membatasi kedalaman agar error tertangkap.
  2. right_recursive: grammar rekursi kanan `expr := term ('+' expr
     | '-' expr)?` berjalan, tetapi menghasilkan asosiativitas kanan
     yang salah untuk operator `-` (yang seharusnya asosiatif kiri).
  3. precedence_climbing: satu fungsi utama dengan tabel presedensi
     (left_bp, right_bp). Untuk operator asosiatif kiri, right_bp =
     left_bp + 1, sehingga operand kanan hanya mengikat operator
     berpresedensi lebih tinggi, dan operator setelahnya diambil
     oleh loop luar untuk membangun asosiativitas kiri.
"""
import sys


class Node:
    """Node pohon ekspresi: (op, left, right) atau daun bilangan."""

    __slots__ = ("op", "left", "right")

    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

    def __repr__(self) -> str:
        return f"Node({self.op!r}, {self.left!r}, {self.right!r})"


def tokenize(s: str) -> list:
    """Tokenizer sederhana: NUM, OP, EOF."""
    out = []
    i = 0
    while i < len(s):
        if s[i].isspace():
            i += 1
            continue
        if s[i].isdigit():
            j = i
            while j < len(s) and s[j].isdigit():
                j += 1
            out.append(("NUM", int(s[i:j])))
            i = j
        else:
            out.append(("OP", s[i]))
            i += 1
    out.append(("EOF", None))
    return out


# ----- 1. Left recursion bug -----
def left_recursion_bug(tokens: list, depth: int = 0):
    """Meniru `expr := expr '+' term | term` secara harfiah.

    Produksi pertama memanggil expr() lagi sebelum mengonsumsi token
    apa pun, sehingga rekursi tidak pernah maju. Tanpa batas
    kedalaman, fungsi ini memicu stack overflow.
    """
    if depth > 20:
        raise RecursionError("rekursi tak terhingga pada grammar rekursi-kiri")
    return left_recursion_bug(tokens, depth + 1)


# ----- 2. Right-recursive (asosiativitas kanan, salah untuk -) -----
def right_recursive(tokens: list):
    """expr := term (('+' | '-') expr)? ; term := NUM ( '*' | '/' term )?

    Rekursi pada `expr` di sisi kanan operator menghasilkan pohon
    miring kanan, sehingga `1 - 2 - 3` diurai sebagai `1 - (2 - 3)`.
    """
    pos = [0]

    def expr():
        left = term()
        if pos[0] < len(tokens) and tokens[pos[0]][0] == "OP" \
                and tokens[pos[0]][1] in "+-":
            op = tokens[pos[0]][1]
            pos[0] += 1
            right = expr()           # rekursi kanan
            return Node(op, left, right)
        return left

    def term():
        left = factor()
        if pos[0] < len(tokens) and tokens[pos[0]][0] == "OP" \
                and tokens[pos[0]][1] in "*/":
            op = tokens[pos[0]][1]
            pos[0] += 1
            right = factor()
            return Node(op, left, right)
        return left

    def factor():
        tok = tokens[pos[0]]
        pos[0] += 1
        return tok[1]

    return expr()


# ----- 3. Precedence climbing -----
# Tabel: operator -> (left_bp, right_bp)
# Asosiatif kiri: right_bp = left_bp + 1 (operand kanan hanya
# mengikat operator berpresedensi lebih tinggi).
# Asosiatif kanan: right_bp = left_bp (operand kanan mengikat
# operator pada presedensi yang sama).
PREC = {
    "+": (1, 2),
    "-": (1, 2),
    "*": (2, 3),
    "/": (2, 3),
}


def precedence_climbing(tokens: list):
    """Precedence climbing dengan tabel presedensi (left_bp, right_bp)."""
    pos = [0]

    def parse_expr(min_bp: int):
        left = parse_primary()
        while pos[0] < len(tokens):
            tok = tokens[pos[0]]
            if tok[0] != "OP" or tok[1] not in PREC:
                break
            left_bp, right_bp = PREC[tok[1]]
            if left_bp < min_bp:
                break
            pos[0] += 1
            right = parse_expr(right_bp)
            left = Node(tok[1], left, right)
        return left

    def parse_primary():
        tok = tokens[pos[0]]
        pos[0] += 1
        return tok[1]

    return parse_expr(0)


def show(node, indent: int = 0) -> None:
    pad = "  " * indent
    if isinstance(node, Node):
        print(f"{pad}Node('{node.op}')")
        show(node.left, indent + 1)
        show(node.right, indent + 1)
    else:
        print(f"{pad}{node}")


def main() -> None:
    sys.setrecursionlimit(200)
    for src in ["1 + 2 * 3", "1 - 2 - 3"]:
        print(f"=== Sumber: {src} ===")
        print("--- Right recursive (asosiativitas kanan, salah untuk -) ---")
        show(right_recursive(tokenize(src)))
        print("--- Precedence climbing (asosiativitas kiri, benar) ---")
        show(precedence_climbing(tokenize(src)))
        print()
    print("=== Left recursion bug ===")
    try:
        left_recursion_bug(tokenize("1 + 2"))
    except RecursionError as e:
        print(f"RecursionError: {e}")


if __name__ == "__main__":
    main()

Keluaran berikut diperoleh dengan menjalankan python3 precedence_demo.py. Pada 1 + 2 * 3, kedua teknik menghasilkan pohon yang sama, dengan + sebagai akar dan 2 * 3 sebagai anak kanan. Pada 1 - 2 - 3, rekursi kanan menghasilkan Node('-', 1, Node('-', 2, 3)) yang bermakna 1 - (2 - 3) = 2, sedangkan precedence climbing menghasilkan Node('-', Node('-', 1, 2), 3) yang bermakna (1 - 2) - 3 = -4. Bagian akhir menunjukkan bahwa grammar rekursi-kiri yang ditulis secara harfiah memicu RecursionError.

text Keluaran 
=== Sumber: 1 + 2 * 3 ===
--- Right recursive (asosiativitas kanan, salah untuk -) ---
Node('+')
  1
  Node('*')
    2
    3
--- Precedence climbing (asosiativitas kiri, benar) ---
Node('+')
  1
  Node('*')
    2
    3

=== Sumber: 1 - 2 - 3 ===
--- Right recursive (asosiativitas kanan, salah untuk -) ---
Node('-')
  1
  Node('-')
    2
    3
--- Precedence climbing (asosiativitas kiri, benar) ---
Node('-')
  Node('-')
    1
    2
  3

=== Left recursion bug ===
RecursionError: rekursi tak terhingga pada grammar rekursi-kiri

Kesalahan umum#

Beberapa kesalahan sering muncul saat presedensi dan asosiativitas ditangani. Pertama, menulis produksi rekursi kiri expr := expr "+" term secara harfiah pada recursive descent, sehingga parser jatuh ke rekursi tak terhingga. Kedua, mengganti rekursi kiri dengan rekursi kanan tanpa menyadari bahwa asosiativitas berubah, sehingga operator asosiatif kiri seperti - menjadi asosiatif kanan. Ketiga, pada precedence climbing, lupa memberi right_bp = left_bp + 1 untuk operator asosiatif kiri, sehingga operator berikutnya pada presedensi yang sama ikut diambil oleh panggilan rekursif dan pohon miring kanan.

Ringkasan#

  • Presedensi menetapkan urutan pengikatan operator berbeda, sedangkan asosiativitas menetapkan sisi pengikatan untuk operator sama berurutan.
  • Rekursi kiri pada recursive descent menyebabkan rekursi tak terhingga, sehingga produksi harus ditulis ulang sebagai iterasi term (("+" | "-") term)*.
  • Rekursi kanan menggantikan rekursi kiri tanpa infinite loop, tetapi mengubah asosiativitas menjadi kanan, yang salah untuk operator asosiatif kiri seperti -.
  • Precedence climbing memakai satu fungsi dengan tabel (left_bp, right_bp), di mana right_bp = left_bp + 1 untuk asosiatif kiri dan right_bp = left_bp untuk asosiatif kanan.

Referensi#