Pemulihan error parsing adalah strategi parser melanjutkan parsing setelah menemui satu error sintaksis, alih-alih menghentikan seluruh proses. Topik ini membahas panic mode sebagai strategi yang sederhana dan titik sinkronisasi sebagai tempat parser kembali melanjutkan parsing dengan aman. Pembaca memperoleh berkas parser_errors.py yang memperluas parser pada topik recursive-descent dengan panic mode, beserta pemahaman cara memilih titik sinkronisasi yang meminimalkan error tambahan akibat pemulihan.
Mengapa pemulihan diperlukan#
Tanpa pemulihan, parser berhenti pada error pertama dan tidak melaporkan kesalahan di baris berikutnya. Pengguna harus memperbaiki satu error, menjalankan compiler lagi, lalu memperbaiki error berikutnya. Pendekatan ini membuat satu siklus penyuntingan hanya menangkap satu masalah, sehingga waktu perbaikan program yang memuat banyak error menjadi panjang. Pemulihan error memungkinkan satu siklus penyuntingan menangkap beberapa masalah sekaligus, sebab parser tetap melanjutkan parsing setelah error pertama.
Tujuan pemulihan ada dua, yaitu melaporkan error sebanyak mungkin dan menghasilkan AST yang konsisten dengan token yang valid. Tujuan kedua penting karena tahap analisis semantik, IR, dan codegen mengonsumsi AST. AST yang dipulihkan dengan benar memungkinkan pipeline berlanjut untuk pernyataan yang valid, sementara pernyataan yang gagal dapat dilewati atau diganti dengan placeholder.
Panic mode#
Panic mode adalah strategi pemulihan yang melompati token sampai mencapai titik sinkronisasi yang dipilih. Strategi ini disebut panic karena parser keluar dari pernyataan saat ini tanpa berusaha memperbaikinya, lalu memulai pernyataan baru pada titik sinkronisasi. Strategi ini sederhana, dapat diprediksi, dan jarang menghasilkan error tambahan akibat upaya perbaikan yang salah.
Implementasi panic mode pada parser memerlukan tiga langkah. Langkah pertama, ketika error ditemui, parser mencatat pesan error beserta posisi sumber ke dalam daftar internal. Langkah kedua, parser melompati token dengan _synchronize() sampai mencapai titik sinkronisasi. Langkah ketiga, parser kembali ke loop utama parse() dan memproses pernyataan baru dari titik sinkronisasi tersebut. Tiga langkah ini diulang sampai akhir masukan, sehingga setiap pernyataan yang valid tetap dihasilkan.
Pemakaian exception internal _Panic memisahkan alur normal parsing dari alur pemulihan. Metode _consume() yang gagal memanggil _raise() yang mencatat error dan memunculkan _Panic. Loop parse() menangkap _Panic dan memanggil _synchronize(). Pola ini membuat kode pernyataan tetap ringkas, sebab cabang produksi tidak perlu menangani error secara eksplisit.
Titik sinkronisasi#
Titik sinkronisasi adalah token yang dipilih sebagai tempat aman untuk memulai pernyataan baru. Pemilihan titik sinkronisasi menyeimbangkan dua tujuan, yaitu meminimalkan token yang dibuang dan memaksimalkan peluang pernyataan berikutnya valid. Pada bahasa mini v1, titik sinkronisasi yang dipilih adalah keyword awal pernyataan (let, print, if, while) dan tanda kurung kurawal tutup }. EOF selalu menghentikan sinkronisasi.
Keyword awal pernyataan dipilih karena setiap pernyataan baru dimulai dengan salah satu keyword itu. Dengan berhenti sebelum keyword, parser dapat memproses pernyataan berikutnya tanpa membuang token penting. Tanda } dipilih karena menandai akhir blok, sehingga parser dapat kembali ke loop block() yang memproses pernyataan. Token titik sinkronisasi tidak dikonsumsi, sehingga loop utama atau block() dapat memprosesnya pada iterasi berikutnya.
Pilihan lain yang lazim adalah menambahkan tanda titik koma ; sebagai titik sinkronisasi pada bahasa yang memakai tanda itu untuk menutup pernyataan. Bahasa mini v1 tidak memakai tanda titik koma, sehingga pilihan itu tidak relevan. Pemilihan titik sinkronisasi yang terlalu longgar (misalnya hanya }) membuat parser melompati terlalu banyak token dan membuang banyak pernyataan valid, sedangkan pemilihan yang terlalu ketat (misalnya hanya let) membuat parser melaporkan error tambahan pada pernyataan print atau if yang valid.
Berkas parser_errors.py#
Berkas berikut memperluas parser.py pada topik recursive-descent dengan panic mode dan titik sinkronisasi. Perbedaan terhadap parser sebelumnya adalah penambahan daftar _errors, exception internal _Panic, dan metode _synchronize(). Antarmuka publik Parser(tokens).parse() tetap mengembalikan Program, dan Parser(tokens).errors() mengembalikan daftar ParseError.
"""Parser recursive descent dengan pemulihan error parsing (panic mode).
Antarmuka publik:
Parser(tokens).parse() -> Program
Parser(tokens).errors() -> list[ParseError]
Perbedaan terhadap parser.py pada topik recursive-descent adalah
penambahan panic mode dan titik sinkronisasi. Saat error sintaksis
ditemui, parser mencatat pesan error beserta posisi, lalu melompati
token sampai mencapai titik sinkronisasi (keyword awal pernyataan
atau `}` penutup blok). Strategi ini memungkinkan satu error tidak
menyembunyikan error berikutnya, sehingga pengguna dapat memperbaiki
beberapa masalah dalam satu putaran penyuntingan.
Agar berkas berdiri sendiri, definisi token, lexer ringkas, dan AST
disertakan ulang sebagai salinan dari kontrak pada modul 1 dan
topik desain-ast.
"""
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",
})
# Titik sinkronisasi panic mode: keyword awal pernyataan dan
# tanda kurung kurawal tutup. EOF selalu menghentikan sinkronisasi.
SYNC_KEYWORDS = frozenset({"let", "print", "if", "while"})
# ----- 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 dengan pemulihan -----
class ParseError:
"""Catatan error sintaksis dengan pesan dan posisi sumber."""
def __init__(self, message: str, line: int, column: int):
self.message = message
self.line = line
self.column = column
def __repr__(self) -> str:
return f"ParseError({self.message!r}, {self.line}, {self.column})"
class Parser:
"""Parser recursive descent dengan panic mode."""
def __init__(self, tokens: list[Token]):
self.tokens = tokens
self.pos = 0
self._errors: list[ParseError] = []
# ----- antarmuka publik -----
def parse(self) -> Program:
statements: list[Stmt] = []
while not self._is_at_end():
try:
statements.append(self.statement())
except _Panic:
self._synchronize()
return Program(statements)
def errors(self) -> list[ParseError]:
return list(self._errors)
# ----- 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()
self._raise(self._peek(), message)
def _raise(self, tok: Token, message: str) -> None:
"""Catat error dan hentikan parsing pernyataan saat ini."""
self._errors.append(ParseError(message, tok.line, tok.column))
raise _Panic()
# ----- pemulihan panic mode -----
def _synchronize(self) -> None:
"""Lompati token hingga titik sinkronisasi tercapai.
Titik sinkronisasi adalah:
- keyword awal pernyataan (let, print, if, while)
- tanda kurung kurawal tutup `}`
- akhir masukan (EOF)
Token titik sinkronisasi tidak dikonsumsi, sehingga loop
utama parse() dapat memprosesnya pada iterasi berikutnya.
"""
while not self._is_at_end():
tok = self._peek()
if tok.type == "PUNCT" and tok.lexeme == "}":
return
if tok.type == "KEYWORD" and tok.lexeme in SYNC_KEYWORDS:
return
self._advance()
# ----- 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():
try:
statements.append(self.statement())
except _Panic:
self._synchronize()
if not self._is_at_end():
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)
self._raise(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)
self._raise(self._peek(), "ekspresi diperlukan")
class _Panic(Exception):
"""Sinyal internal agar parse() keluar dari pernyataan saat ini."""
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:
# Sumber memuat dua error sintaksis: `let = 10` (tanpa identifier)
# dan `let 7 = 20` (identifier diganti bilangan). Parser harus
# melaporkan keduanya sekaligus dan tetap menghasilkan AST
# pernyataan yang valid (let x = 5 dan print x).
source = (
'let x = 5\n'
'let = 10\n'
'let 7 = 20\n'
'print x\n'
)
tokens = Lexer(source).tokens()
parser = Parser(tokens)
program = parser.parse()
print("=== Sumber ===")
print(source, end="")
print()
print("=== Error parsing ===")
for e in parser.errors():
print(f"error parsing pada {e.line}:{e.column}: {e.message}")
print()
print("=== AST yang dipulihkan ===")
print(pretty(program), end="")
if __name__ == "__main__":
main()Keluaran berikut diperoleh dengan menjalankan python3 parser_errors.py. Sumber memuat dua pernyataan let yang salah, yaitu let = 10 tanpa identifier dan let 7 = 20 dengan identifier diganti bilangan. Parser melaporkan kedua error sekaligus pada posisi token penyebabnya, kemudian melanjutkan parsing dan menghasilkan AST yang hanya memuat pernyataan valid, yaitu let x = 5 dan print x. Pernyataan yang gagal tidak masuk AST, sehingga tahap analisis semantik dapat beroperasi pada AST yang konsisten.
=== Sumber ===
let x = 5
let = 10
let 7 = 20
print x
=== Error parsing ===
error parsing pada 2:5: identifier diperlukan setelah 'let'
error parsing pada 3:5: identifier diperlukan setelah 'let'
=== AST yang dipulihkan ===
Program
Let 'x'
Literal 5
Print
Variable 'x'Kesalahan umum#
Beberapa kesalahan sering muncul saat pemulihan error parsing ditulis. Pertama, menghentikan parser pada error pertama tanpa panic mode, sehingga error di baris berikutnya tidak dilaporkan. Kedua, mengonsumsi token titik sinkronisasi saat _synchronize(), sehingga pernyataan berikutnya tidak dapat diproses karena keyword awalnya hilang. Ketiga, memilih titik sinkronisasi yang terlalu ketat, sehingga parser tetap melaporkan error tambahan pada pernyataan valid. Keempat, lupa menangani _Panic di dalam block(), sehingga satu error dalam blok menyebabkan seluruh blok gagal.
Ringkasan#
- Pemulihan error parsing memungkinkan parser melanjutkan parsing setelah satu error, sehingga satu siklus penyuntingan menangkap beberapa masalah.
- Panic mode melompati token sampai titik sinkronisasi tercapai, lalu memulai pernyataan baru dari titik itu.
- Titik sinkronisasi pada bahasa mini v1 adalah keyword awal pernyataan (
let,print,if,while) dan tanda}, dengan token titik sinkronisasi tidak dikonsumsi. - Exception internal
_Panicmemisahkan alur normal dari alur pemulihan, sehingga kode pernyataan tetap ringkas tanpa penanganan error eksplisit.
Referensi#
- Crafting Interpreters — Bob Nystrom — Bab “Parsing Expressions” menampilkan error recovery dengan panic mode dan pemilihan titik sinkronisasi.
- Compilers: Principles, Techniques, and Tools — Wikipedia — Bab “Error Recovery” membahas panic mode, phrase-level recovery, dan error productions.
- Panic mode — Wikipedia — Ringkasan strategi pemulihan pada parser, termasuk panic mode dan sinkronisasi.