Recursive descent adalah teknik parsing tulis tangan yang menetapkan satu metode per aturan tata bahasa, dengan setiap metode memanggil metode lain sesuai produksi. Topik ini menyusun parser recursive descent lengkap untuk bahasa mini v1, memakai token dari modul 1 dan menghasilkan AST sesuai kontrak pada topik desain-ast. Pembaca memperoleh berkas parser.py yang berdiri sendiri, beserta pemahaman struktur lapisan ekspresi yang menghasilkan presedensi dan asosiativitas kiri tanpa grammar rekursi-kiri.
Apa itu recursive descent#
Recursive descent adalah teknik parsing di mana setiap nonterminal pada tata bahasa dipetakan menjadi satu metode pada parser. Metode let_statement() mengonsumsi token let, lalu memanggil metode lain untuk identifier, operator =, dan ekspresi pengikat. Pemanggilan metode membentuk rekursi yang menuruni aturan produksi, sehingga pohon panggilan metode mencerminkan pohon derivasi yang dihasilkan.
Teknik ini disebut descent karena parsing bergerak dari simbol awal ke bawah, menuju terminal. Teknik ini disebut recursive karena metode memanggil diri sendiri atau metode lain yang akhirnya kembali ke diri sendiri (misalnya expression() memanggil assignment() yang memanggil logic_or() dan seterusnya hingga primary() yang dapat memanggil expression() kembali lewat tanda kurung). Recursive descent berbeda dari parser generator seperti yacc yang memakai tabel transisi, tetapi keduanya menghasilkan AST yang setara untuk tata bahasa yang sama.
Keunggulan utama recursive descent adalah keterbacaan kode. Setiap aturan tata bahasa tampak sebagai satu metode, sehingga inspeksi pesan error, penambahan fitur, dan pelacakan bug menjadi sederhana. Sebagian besar compiler produksi, termasuk GCC dan Rust, memakai recursive descent untuk front end-nya.
Anatomi parser#
Parser memelihara dua variabel keadaan, yaitu tokens (daftar token dari lexer) dan pos (indeks token saat ini). Dua operasi dasar menggerakkan parsing, yaitu _peek() yang mengembalikan token pada posisi saat ini tanpa memajukan indeks, dan _advance() yang mengembalikan token saat ini lalu memajukan indeks. Pemisahan peek dan advance membuat lookahead menjadi murah, sehingga titik keputusan cabang dapat diambil dengan pemeriksaan sederhana pada token saat ini.
Tiga metode bantu membungkus operasi dasar. _check(type, lexeme) mengembalikan nilai kebenaran apakah token saat ini cocok dengan tipe dan lexeme yang diberikan. _match(type, lexeme) memeriksa, lalu mengonsumsi bila cocok, mirip dengan peek-then-advance. _consume(type, lexeme, message) mengonsumsi token yang diharapkan, atau memunculkan ParseError dengan pesan yang menyebut posisi sumber. Ketiga bantuan ini membuat kode aturan menjadi ringkas, sebab setiap cabang cukup menyebut “konsumsi token ini atau laporkan pesan itu”.
Lapisan presedensi#
Ekspresi dipecah menjadi lapisan yang mencerminkan presedensi operator, dari yang paling longgar hingga yang paling lekat. Urutannya adalah assignment, logic_or, logic_and, equality, comparison, term, factor, unary, dan primary. Setiap lapisan memanggil lapisan di bawahnya sebagai operand, sehingga operator berpresedensi lebih tinggi mengikat lebih dulu. Lapisan term misalnya, memanggil factor sebagai operand, sehingga 1 + 2 * 3 diurai dengan * mengikat 2 dan 3 lebih dulu, lalu + mengikat 1 dan hasil perkalian.
Asosiativitas kiri untuk operator biner diperoleh lewat loop while dengan akumulasi node. Pada lapisan term, metode memanggil factor() untuk operand kiri, lalu berulang mengonsumsi + atau - dan memanggil factor() lagi untuk operand kanan. Setiap iterasi membungkus node sebelumnya sebagai anak kiri node baru, sehingga 1 - 2 - 3 menjadi Binary(Binary(1, -, 2), -, 3), yaitu asosiatif kiri. Pola loop ini menggantikan rekursi kiri yang dilarang pada parser tulis tangan.
Asosiativitas kanan untuk assignment diperoleh lewat rekursi. Pada assignment(), metode memanggil logic_or() untuk operand kiri, lalu bila menemui =, memanggil assignment() lagi untuk nilai kanan. Rekursi ini membuat x = y = 5 diurai sebagai Assign("x", Assign("y", 5)), yaitu asosiatif kanan, sesuai konvensi penugasan pada sebagian besar bahasa.
Pernyataan#
Pernyataan dipetakan ke satu metode per jenis, dengan dispatch berdasarkan token pertama. statement() memeriksa token saat ini, lalu memanggil let_statement(), print_statement(), if_statement(), while_statement(), atau block(). Bila tidak ada yang cocok, pernyataan dianggap sebagai ekspresi yang dibungkus Expression. Dispatch satu token lookahead cukup karena tata bahasa v1 memenuhi sifat LL(1) untuk pernyataan.
Blok { ... } memerlukan penanganan khusus karena berulang memanggil statement() hingga mencapai }. Metode block() mengonsumsi {, lalu berulang memanggil statement() selama token saat ini bukan } dan bukan akhir masukan. Setelah perulangan, block() mengonsumsi }. Pola ini memungkinkan blok bersarang, sebab setiap statement() dapat kembali memanggil block() jika menemui {.
Berkas parser.py#
Berkas berikut adalah parser recursive descent lengkap untuk bahasa mini v1. Definisi token dan lexer ringkas disertakan ulang dari modul 1, dan AST disertakan ulang dari topik desain-ast, agar berkas berdiri sendiri dan dapat dijalankan tanpa modul lain. Demo main() memparsing program yang menjumlahkan n sampai 0, lalu mencetak AST sebagai pohon terindentasi.
"""Parser recursive descent untuk bahasa mini v1.
Antarmuka publik:
Parser(tokens).parse() -> Program
Masukan adalah list[Token] dari lexer modul 1, dengan Token sebagai
namedtuple (type, lexeme, line, column) dan kelas token KEYWORD,
IDENTIFIER, NUMBER, STRING, OPERATOR, PUNCT, EOF.
Keluaran adalah AST sesuai ast_nodes.py pada topik desain-ast. Agar
berkas ini berdiri sendiri, definisi AST dan token disertakan ulang
sebagai salinan ringkas dari kontrak pada topik desain-ast dan
modul 1.
Struktur parser:
- satu metode per aturan tata bahasa
- lapisan ekspresi mengikuti presedensi: assignment -> logic_or ->
logic_and -> equality -> comparison -> term -> factor -> unary
-> primary
- asosiativitas kiri untuk operator biner diperoleh lewat loop
while dengan akumulasi node
- asosiativitas kanan untuk assignment diperoleh lewat rekursi
"""
from collections import namedtuple
from dataclasses import dataclass, field
from typing import Any
# ----- Token (salinan ringkas dari modul 1) -----
Token = namedtuple("Token", ["type", "lexeme", "line", "column"])
KEYWORDS = frozenset({
"let", "print", "if", "else", "while",
"true", "false", "nil", "and", "or",
})
# ----- Lexer ringkas (salinan dari modul 1) -----
DUA_KARAKTER = {"<=", ">=", "==", "!="}
SATU_KARAKTER = set("+-*/<>!=")
PUNCT = set("(){}")
class Lexer:
"""Scanner tulis tangan untuk bahasa mini v1."""
def __init__(self, source: str):
self.src = source
self.pos = 0
self.line = 1
self.column = 1
def _peek(self, offset: int = 0) -> str:
idx = self.pos + offset
if idx >= len(self.src):
return ""
return self.src[idx]
def _advance(self) -> str:
ch = self.src[self.pos]
self.pos += 1
if ch == "\n":
self.line += 1
self.column = 1
else:
self.column += 1
return ch
def _at_end(self) -> bool:
return self.pos >= len(self.src)
def tokens(self) -> list[Token]:
out: list[Token] = []
while not self._at_end():
ch = self._peek()
if ch in " \t\r\n":
self._advance()
continue
if ch == "/" and self._peek(1) == "/":
while not self._at_end() and self._peek() != "\n":
self._advance()
continue
if ch.isalpha() or ch == "_":
out.append(self._identifier())
continue
if ch.isdigit():
out.append(self._angka())
continue
if ch == '"':
out.append(self._string())
continue
if ch in PUNCT:
line, col = self.line, self.column
self._advance()
out.append(Token("PUNCT", ch, line, col))
continue
if ch in SATU_KARAKTER:
out.append(self._operator())
continue
self._advance() # karakter tak dikenal dilewati
out.append(Token("EOF", "", self.line, self.column))
return out
def _identifier(self) -> Token:
line, col = self.line, self.column
start = self.pos
while not self._at_end() and (self._peek().isalnum() or self._peek() == "_"):
self._advance()
lex = self.src[start:self.pos]
kelas = "KEYWORD" if lex in KEYWORDS else "IDENTIFIER"
return Token(kelas, lex, line, col)
def _angka(self) -> Token:
line, col = self.line, self.column
start = self.pos
while not self._at_end() and self._peek().isdigit():
self._advance()
if self._peek() == "." and self._peek(1).isdigit():
self._advance()
while not self._at_end() and self._peek().isdigit():
self._advance()
return Token("NUMBER", self.src[start:self.pos], line, col)
def _string(self) -> Token:
line, col = self.line, self.column
self._advance()
start = self.pos
while not self._at_end() and self._peek() != '"':
self._advance()
lex = '"' + self.src[start:self.pos] + '"'
if not self._at_end():
self._advance()
return Token("STRING", lex, line, col)
def _operator(self) -> Token:
line, col = self.line, self.column
dua = self._peek() + self._peek(1)
if dua in DUA_KARAKTER:
self._advance()
self._advance()
return Token("OPERATOR", dua, line, col)
ch = self._advance()
return Token("OPERATOR", ch, line, col)
# ----- AST (salinan ringkas dari topik desain-ast) -----
@dataclass
class Expr:
pass
@dataclass
class Binary(Expr):
left: Expr
op: str
right: Expr
@dataclass
class Unary(Expr):
op: str
operand: Expr
@dataclass
class Literal(Expr):
value: Any
@dataclass
class Variable(Expr):
name: str
@dataclass
class Assign(Expr):
name: str
value: Expr
@dataclass
class Logical(Expr):
left: Expr
op: str
right: Expr
@dataclass
class Grouping(Expr):
expression: Expr
@dataclass
class Stmt:
pass
@dataclass
class Let(Stmt):
name: str
initializer: Expr
@dataclass
class Print(Stmt):
expression: Expr
@dataclass
class If(Stmt):
condition: Expr
then_branch: Stmt
else_branch: Stmt | None = None
@dataclass
class While(Stmt):
condition: Expr
body: Stmt
@dataclass
class Block(Stmt):
statements: list[Stmt] = field(default_factory=list)
@dataclass
class Expression(Stmt):
expression: Expr
@dataclass
class Program:
statements: list[Stmt] = field(default_factory=list)
# ----- Parser -----
class ParseError(Exception):
"""Error sintaksis dengan posisi sumber."""
class Parser:
"""Parser recursive descent untuk bahasa mini v1."""
def __init__(self, tokens: list[Token]):
self.tokens = tokens
self.pos = 0
# ----- antarmuka publik -----
def parse(self) -> Program:
statements: list[Stmt] = []
while not self._is_at_end():
statements.append(self.statement())
return Program(statements)
# ----- utilitas token -----
def _peek(self) -> Token:
return self.tokens[self.pos]
def _previous(self) -> Token:
return self.tokens[self.pos - 1]
def _is_at_end(self) -> bool:
return self._peek().type == "EOF"
def _advance(self) -> Token:
if not self._is_at_end():
self.pos += 1
return self._previous()
def _check(self, type_: str, lexeme: str | None = None) -> bool:
tok = self._peek()
if tok.type != type_:
return False
return lexeme is None or tok.lexeme == lexeme
def _match(self, type_: str, lexeme: str | None = None) -> bool:
if self._check(type_, lexeme):
self._advance()
return True
return False
def _match_any(self, type_: str, lexemes: set[str]) -> bool:
tok = self._peek()
if tok.type == type_ and tok.lexeme in lexemes:
self._advance()
return True
return False
def _consume(self, type_: str, lexeme: str | None, message: str) -> Token:
if self._check(type_, lexeme):
return self._advance()
raise self._error(self._peek(), message)
def _error(self, tok: Token, message: str) -> ParseError:
return ParseError(f"pada {tok.line}:{tok.column}: {message}")
# ----- pernyataan -----
def statement(self) -> Stmt:
if self._check("KEYWORD", "let"):
return self.let_statement()
if self._check("KEYWORD", "print"):
return self.print_statement()
if self._check("KEYWORD", "if"):
return self.if_statement()
if self._check("KEYWORD", "while"):
return self.while_statement()
if self._check("PUNCT", "{"):
return self.block()
return self.expression_statement()
def let_statement(self) -> Let:
self._advance() # 'let'
name_tok = self._consume("IDENTIFIER", None,
"identifier diperlukan setelah 'let'")
self._consume("OPERATOR", "=",
"'=' diperlukan setelah identifier pada pernyataan let")
value = self.expression()
return Let(name_tok.lexeme, value)
def print_statement(self) -> Print:
self._advance() # 'print'
value = self.expression()
return Print(value)
def if_statement(self) -> If:
self._advance() # 'if'
cond = self.expression()
then_branch = self.block()
else_branch = None
if self._match("KEYWORD", "else"):
else_branch = self.block()
return If(cond, then_branch, else_branch)
def while_statement(self) -> While:
self._advance() # 'while'
cond = self.expression()
body = self.block()
return While(cond, body)
def block(self) -> Block:
self._consume("PUNCT", "{", "'{' diperlukan untuk memulai blok")
statements: list[Stmt] = []
while not self._check("PUNCT", "}") and not self._is_at_end():
statements.append(self.statement())
self._consume("PUNCT", "}", "'}' diperlukan untuk menutup blok")
return Block(statements)
def expression_statement(self) -> Expression:
expr = self.expression()
return Expression(expr)
# ----- ekspresi (lapisan presedensi) -----
def expression(self) -> Expr:
return self.assignment()
def assignment(self) -> Expr:
expr = self.logic_or()
if self._match("OPERATOR", "="):
value = self.assignment()
if isinstance(expr, Variable):
return Assign(expr.name, value)
raise self._error(self._previous(),
"target penetapan tidak valid")
return expr
def logic_or(self) -> Expr:
expr = self.logic_and()
while self._match("KEYWORD", "or"):
right = self.logic_and()
expr = Logical(expr, "or", right)
return expr
def logic_and(self) -> Expr:
expr = self.equality()
while self._match("KEYWORD", "and"):
right = self.equality()
expr = Logical(expr, "and", right)
return expr
def equality(self) -> Expr:
expr = self.comparison()
while self._match_any("OPERATOR", {"==", "!="}):
op = self._previous().lexeme
right = self.comparison()
expr = Binary(expr, op, right)
return expr
def comparison(self) -> Expr:
expr = self.term()
while self._match_any("OPERATOR", {"<", "<=", ">", ">="}):
op = self._previous().lexeme
right = self.term()
expr = Binary(expr, op, right)
return expr
def term(self) -> Expr:
expr = self.factor()
while self._match_any("OPERATOR", {"+", "-"}):
op = self._previous().lexeme
right = self.factor()
expr = Binary(expr, op, right)
return expr
def factor(self) -> Expr:
expr = self.unary()
while self._match_any("OPERATOR", {"*", "/"}):
op = self._previous().lexeme
right = self.unary()
expr = Binary(expr, op, right)
return expr
def unary(self) -> Expr:
if self._match_any("OPERATOR", {"-", "!"}):
op = self._previous().lexeme
operand = self.unary()
return Unary(op, operand)
return self.primary()
def primary(self) -> Expr:
if self._match("KEYWORD", "true"):
return Literal(True)
if self._match("KEYWORD", "false"):
return Literal(False)
if self._match("KEYWORD", "nil"):
return Literal(None)
if self._match("NUMBER", None):
tok = self._previous()
if "." in tok.lexeme:
return Literal(float(tok.lexeme))
return Literal(int(tok.lexeme))
if self._match("STRING", None):
tok = self._previous()
return Literal(tok.lexeme[1:-1])
if self._match("IDENTIFIER", None):
return Variable(self._previous().lexeme)
if self._match("PUNCT", "("):
inner = self.expression()
self._consume("PUNCT", ")", "')' diperlukan setelah ekspresi")
return Grouping(inner)
raise self._error(self._peek(), "ekspresi diperlukan")
def pretty(node: Any, indent: int = 0) -> str:
"""Format AST sebagai pohon terindentasi (versi ringkas)."""
lines: list[str] = []
_emit(node, " " * indent, lines)
return "\n".join(lines) + "\n"
def _emit(node: Any, pad: str, lines: list[str]) -> None:
if isinstance(node, Program):
lines.append(f"{pad}Program")
for s in node.statements:
_emit(s, pad + " ", lines)
elif isinstance(node, Block):
lines.append(f"{pad}Block")
for s in node.statements:
_emit(s, pad + " ", lines)
elif isinstance(node, Let):
lines.append(f"{pad}Let {node.name!r}")
_emit(node.initializer, pad + " ", lines)
elif isinstance(node, Print):
lines.append(f"{pad}Print")
_emit(node.expression, pad + " ", lines)
elif isinstance(node, If):
lines.append(f"{pad}If")
lines.append(f"{pad} kondisi:")
_emit(node.condition, pad + " ", lines)
lines.append(f"{pad} maka:")
_emit(node.then_branch, pad + " ", lines)
if node.else_branch is not None:
lines.append(f"{pad} jika_tidak:")
_emit(node.else_branch, pad + " ", lines)
elif isinstance(node, While):
lines.append(f"{pad}While")
lines.append(f"{pad} kondisi:")
_emit(node.condition, pad + " ", lines)
lines.append(f"{pad} badan:")
_emit(node.body, pad + " ", lines)
elif isinstance(node, Expression):
lines.append(f"{pad}ExprStmt")
_emit(node.expression, pad + " ", lines)
elif isinstance(node, Binary):
lines.append(f"{pad}Binary {node.op!r}")
_emit(node.left, pad + " ", lines)
_emit(node.right, pad + " ", lines)
elif isinstance(node, Logical):
lines.append(f"{pad}Logical {node.op!r}")
_emit(node.left, pad + " ", lines)
_emit(node.right, pad + " ", lines)
elif isinstance(node, Unary):
lines.append(f"{pad}Unary {node.op!r}")
_emit(node.operand, pad + " ", lines)
elif isinstance(node, Grouping):
lines.append(f"{pad}Grouping")
_emit(node.expression, pad + " ", lines)
elif isinstance(node, Assign):
lines.append(f"{pad}Assign {node.name!r}")
_emit(node.value, pad + " ", lines)
elif isinstance(node, Literal):
lines.append(f"{pad}Literal {node.value!r}")
elif isinstance(node, Variable):
lines.append(f"{pad}Variable {node.name!r}")
else:
lines.append(f"{pad}{node!r}")
def main() -> None:
source = (
'let n = 10\n'
'let hasil = 0\n'
'while n > 0 {\n'
' hasil = hasil + n\n'
' n = n - 1\n'
'}\n'
'print hasil\n'
)
tokens = Lexer(source).tokens()
program = Parser(tokens).parse()
print("=== Sumber ===")
print(source, end="")
print()
print("=== AST (pohon terindentasi) ===")
print(pretty(program), end="")
if __name__ == "__main__":
main()Keluaran berikut diperoleh dengan menjalankan python3 parser.py. Program sumber menjumlahkan n dari 10 sampai 0. AST menunjukkan dua pernyataan Let di awal, satu pernyataan While dengan kondisi n > 0 dan blok badan yang memuat dua penetapan, lalu satu pernyataan Print di akhir. Penetapan hasil = hasil + n muncul sebagai ExprStmt yang membungkus Assign, sesuai aturan expr_stmt pada BNF.
=== Sumber ===
let n = 10
let hasil = 0
while n > 0 {
hasil = hasil + n
n = n - 1
}
print hasil
=== AST (pohon terindentasi) ===
Program
Let 'n'
Literal 10
Let 'hasil'
Literal 0
While
kondisi:
Binary '>'
Variable 'n'
Literal 0
badan:
Block
ExprStmt
Assign 'hasil'
Binary '+'
Variable 'hasil'
Variable 'n'
ExprStmt
Assign 'n'
Binary '-'
Variable 'n'
Literal 1
Print
Variable 'hasil'Kesalahan umum#
Beberapa kesalahan sering muncul saat parser recursive descent ditulis. Pertama, menulis lapisan ekspresi sebagai rekursi kiri (misalnya term := term "+" factor), sehingga parser jatuh ke rekursi tak terhingga. Kedua, lupa menambahkan cabang primary() yang memanggil expression() kembali lewat tanda kurung, sehingga ekspresi dalam kurung tidak terurai. Ketiga, memeriksa token dengan _check() tetapi tidak mengonsumsinya dengan _advance(), sehingga parser terjebak pada token yang sama.
Ringkasan#
- Recursive descent memetakan satu nonterminal tata bahasa menjadi satu metode parser, dengan rekursi yang mencerminkan pohon derivasi.
- Dua operasi dasar
_peek()dan_advance()menggerakkan parsing, dan tiga bantuan_check(),_match(), dan_consume()membungkus titik keputusan cabang. - Lapisan ekspresi mengikuti presedensi dari
assignmenthinggaprimary, dengan asosiativitas kiri diperoleh lewat loopwhiledan asosiativitas kanan diperoleh lewat rekursi. - Berkas
parser.pyberdiri sendiri dengan token, lexer ringkas, dan AST salinan dari kontrak pada modul 1 dan topik desain-ast.
Referensi#
- Crafting Interpreters — Bob Nystrom — Bab “Parsing Expressions” menampilkan parser recursive descent untuk bahasa Lox dengan lapisan presedensi dan pola loop untuk asosiativitas kiri.
- Recursive descent parser — Wikipedia — Ringkasan teknik recursive descent, termasuk hubungannya dengan tata bahasa LL(1).
- Compilers: Principles, Techniques, and Tools — Wikipedia — Bab “Syntax-Directed Translation” membahas pemetaan aturan tata bahasa ke metode parser.