Membuat Bahasa Pemrograman Sederhana dengan Rust dan LLVM - Bagian 2 Parser
Tahap berikutnya setelah melakukan lexical analysis adalah Parsing.
Untuk kode yang sudah lengkap bisa dilihat di github: https://github.com/aldidana/hitung
Proses parsing akan memvalidasi token yang sudah ada menjadi sebuah AST (Abstract Syntax Tree), AST yaitu sebuah pohon yang berisikan Expression dari token yang ada seperti pada gambar diatas.
Untuk parser kita akan menggunakan teknik Pratt Parser yang berdasarkan Recursive Descent. Pratt Parser dan Recursive Descent mengambil paradigma dari Top Down Precedence Parsing menerapkan leftmost derivation yaitu akan memproses dari root atau akarnya kemudian dari kiri ke kanan.
Disini kita akan menggunakan nilai left binding power dari sebuah token seperti yang ada di kode token.rs
....
pub fn lbp(&self) -> usize {
match *self {
Token::Add => 10,
Token::Sub => 10,
Token::Mul => 20,
Token::Div => 20,
Token::LParen => 99,
Token::ASSIGN => 100,
Token::RParen => 0,
_ => 0,
}
}Struktur
hitung
│ Cargo.toml
│
└───src
| main.rs
| lexer.rs
| token.rs
| expression.rs // file baru
| parser.rs // file baruExpression
Pertama kita akan membuat sebuah file expression.rs yaitu representasi dari AST.
Tambahkan kode berikut ini:
use crate::token::Token;
#[derive(Debug, PartialEq)]
pub enum Expression {
Num(f64),
Unary(Token, Box<Expression>),
Binary(Box<Expression>, Token, Box<Expression>),
Paren(Box<Expression>),
Variable(String),
Conditional(Box<Expression>, Box<Expression>, Box<Expression>),
}
impl From<isize> for Expression {
fn from(n: isize) -> Self {
Expression::Num(n as f64)
}
}Untuk enum Expression terutama dibagian yang menggunakan Box dimana berisikan enum Expression itu sendiri (Recursive structure) kita membutuhkan Box<T>. Untuk Recursive structure dibutuhkan sebanyak apa alokasi ukuran/size yang dibutuhkan di memory, contoh dibawah ini tidak akan bisa dicompile:
pub enum Expression {
...
Unary(Token, Expression),
// disini compiler tidak tahu seberapa banyak alokasi yang dibutuhkan
// dengan menggunakan Box yang dimana sudah ditentukan ukurannya
// maka untuk `Unary` kita akan tahu berapa ukuran yang dibutuhkan
}Box adalah smart pointer yang mengalokasikan data ke dalam heap dengan nilai bertipe data T, Box termasuk smart pointer dikarenakan ketika Box sudah tidak digunakan lagi maka otomatis destructor untuk Box tersebut akan dipanggil dan object yang ada didalamnya akan dihapus serta memory di heap akan dihapus/freed.
Parser
Untuk selanjutnya buat file parser.rs dan tambahkan kode berikut:
use std::iter::Iterator;
use std::iter::Peekable;
use std::vec::IntoIter;
use crate::expression::Expression;
use crate::token::Token;
pub struct Parser {
tokens: Peekable<IntoIter<Token>>,
}
impl Parser {
pub fn new(tokens: Vec<Token>) -> Self {
Parser {
tokens: tokens.into_iter().peekable(),
}
}
pub fn handle_next(&mut self) -> Result<Token, String> {
self.tokens.next().ok_or("Error get next token".to_string())
}
}Struct Parser berisikan tokens yang akan diproses untuk menjadi sebuah Expression. Disini kita membuat Iterator dari tokens tersebut sama seperti input di bagian 1 Lexer.
Tambahkan kode berikut ini setelah fungsi handle_next()
//Null Denotation
pub fn nud(&mut self, token: Token) -> Result<Expression, String> {
match token {
Token::ILLEGAL => Err("Input not supported".to_string()),
Token::IDENTIFIER(i) => Ok(Expression::Variable(i)),
Token::Num(n) => Ok(Expression::Num(n)),
Token::Sub | Token::Add => {
let tok = self.tokens.next().expect("eee");
match tok {
Token::Num(n) => {
Ok(Expression::Unary(
token.clone(),
Box::new(Expression::Num(n)),
))
}
_ => Err("Input not supported".to_string()),
}
}
Token::LParen => {
let mut parenthesis = Vec::new();
let mut counter: usize = 1;
while let Some(token) = self.tokens.next() {
match &token {
Token::LParen => counter += 1,
Token::RParen => {
match counter {
1 => {
return Parser::new(parenthesis)
.expr(0)
.map(|t| Expression::Paren(Box::new(t)));
}
0 => return Err("Unmatched closing paren".to_string()),
_ => {}
};
counter -= 1;
}
_ => {}
};
parenthesis.push(token);
}
Err("Unmatched closing paren".to_string())
}
Token::RParen => Err("Unmatched closing paren".to_string()),
Token::If => {
let lhs = self.handle_next()?;
let cmp = self.handle_next()?;
let rhs = self.handle_next()?;
let lhs = self.nud(lhs)?;
let rhs = self.nud(rhs)?;
let left = Box::new(
Expression::Binary(
Box::new(lhs),
cmp,
Box::new(rhs),
)
);
let then = self.handle_next()?;
let then = self.handle_next()?;
let then_expression = self.nud(then)?;
let else_if = self.handle_next()?;
let else_if = self.handle_next()?;
let else_expression = self.nud(else_if)?;
Ok(Expression::Conditional(
left,
Box::new(then_expression),
Box::new(else_expression),
))
}
_ => Err(format!("Token {:?} error", token.clone())),
}
}Nud atau null denotation adalah fungsi yang akan memproses sebuah token prefix disinilah yang hanya memproses sebuah literal dalam contoh ini sebuah number dan variable sedangkan Led atau Left Denotation yang akan memproses sebuah token infix dalam contoh ini adalah operator Binary.
Fungsi nud akan menentukan setiap token akan menjadi Expression yang sudah ditentukan, untuk hal branching atau if saat ini kita akan membatasi hanya 1 level jadi kita tidak akan bisa melakukan if didalam if.
selanjutnya untuk fungsi led tambahkan kode berikut setelah fungsi nud diatas:
...
//Left Denotation
pub fn led(&mut self, bp: usize, left: Expression, token: Token) -> Result<Expression, String> {
match token {
Token::Add | Token::Sub | Token::Mul | Token::Div | Token::ASSIGN => {
let rhs = self.expr(bp)?;
Ok(Expression::Binary(
Box::new(left),
token,
Box::new(rhs),
))
}
_ => Err(format!("Token {:?} error", token)),
}
}Selanjutnya tambahkan fungsi expr setelah fungsi led, fungsi expr inilah yang akan mengevaluasi setiap token dan memanggil fungsi sebelumnya yaitu fungsi nud dan led. Berikut kodenya:
pub fn expr(&mut self, rbp: usize) -> Result<Expression, String> {
let first_token = self.handle_next()?;
let mut left = self.nud(first_token)?;
while let Some(peeked) = self.tokens.peek() {
if *peeked == Token::ILLEGAL {
return Err("Input not supported".to_string());
}
if rbp >= peeked.lbp() {
break;
}
let op = self.handle_next()?;
left = self.led(op.lbp(), left, op)?;
}
Ok(left)
}Test Parser
Jangan lupa untuk meambahkan test untuk parser.rs, tambahkan kode berikut dibagian paling bawah:
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_nud() {
let tokens = vec![
Token::Sub,
Token::from(3),
Token::Mul,
Token::from(2),
Token::EOF,
];
let expression = Parser::new(tokens).expr(0).unwrap();
let expected = Expression::Binary(
Box::new(Expression::Unary(
Token::Sub,
Box::new(Expression::from(3))
)),
Token::Mul,
Box::new(Expression::from(2)),
);
assert_eq!(expected, expression);
}
#[test]
fn test_error() {
let tokens = vec![Token::Mul, Token::from(2), Token::EOF];
let expression = Parser::new(tokens).expr(0).map_err(|e| e);
let expected = Err(String::from("Token Mul error"));
assert_eq!(expected, expression);
}
#[test]
fn test_binary() {
let tokens = vec![Token::from(3), Token::Div, Token::from(2), Token::EOF];
let expression = Parser::new(tokens).expr(0).unwrap();
let expected = Expression::Binary(
Box::new(Expression::from(3)),
Token::Div,
Box::new(Expression::from(2)),
);
assert_eq!(expected, expression);
}
#[test]
fn test_unary() {
let tokens = vec![Token::Sub, Token::from(2), Token::EOF];
let expression = Parser::new(tokens).expr(0).unwrap();
let expected = Expression::Unary(Token::Sub, Box::new(Expression::from(2)));
assert_eq!(expected, expression);
}
#[test]
fn test_precedence_add_and_mul() {
let tokens = vec![
Token::from(3),
Token::Add,
Token::from(2),
Token::Mul,
Token::from(2),
Token::EOF,
];
let expression = Parser::new(tokens).expr(0).unwrap();
let expected = Expression::Binary(
Box::new(Expression::from(3)),
Token::Add,
Box::new(Expression::Binary(
Box::new(Expression::from(2)),
Token::Mul,
Box::new(Expression::from(2)),
)),
);
assert_eq!(expected, expression);
}
#[test]
fn test_precedence_add_and_sub() {
let tokens = vec![
Token::from(3),
Token::Add,
Token::from(2),
Token::Sub,
Token::from(2),
Token::EOF,
];
let expression = Parser::new(tokens).expr(0).unwrap();
let expected = Expression::Binary(
Box::new(Expression::Binary(
Box::new(Expression::from(3)),
Token::Add,
Box::new(Expression::from(2)),
)),
Token::Sub,
Box::new(Expression::from(2)),
);
assert_eq!(expected, expression);
}
#[test]
fn test_assignment() {
let tokens = vec![
Token::IDENTIFIER("a".to_string()),
Token::ASSIGN,
Token::from(2),
];
let expression = Parser::new(tokens).expr(0).unwrap();
let expected = Expression::Binary(
Box::new(Expression::Variable("a".to_string())),
Token::ASSIGN,
Box::new(Expression::from(2)),
);
assert_eq!(expected, expression);
}
#[test]
fn test_if_then_else() {
let tokens = vec![
Token::If,
Token::from(1),
Token::LT,
Token::from(9),
Token::Then,
Token::from(1),
Token::Else,
Token::from(0),
];
let expression = Parser::new(tokens).expr(0).unwrap();
let expected = Expression::Conditional(
Box::new(Expression::Binary(
Box::new(Expression::from(1)),
Token::LT,
Box::new(Expression::from(9)),
)),
Box::new(Expression::from(1)),
Box::new(Expression::from(0)),
);
assert_eq!(expected, expression);
}
}Main
Setelah menambahkan beberapa kode diatas, saatnya untuk mencoba menjalankan program dengan menggunakan parser yang telah kita buat.
Tambahkan kode berikut ini di file main.rs
use std::io;
use std::io::Write;
mod lexer;
mod token;
mod expression;
mod parser;
use lexer::Lexer;
use parser::Parser;
fn main() {
loop {
println!();
print!("> ");
io::stdout()
.flush()
.expect("Error when flush stdout.");
let mut input = String::new();
io::stdin()
.read_line(&mut input)
.expect("Could not read from standard input.");
let lexer = Lexer::new(input.as_str());
let result = lexer.lex();
let mut parser = Parser::new(result);
match parser.expr(0) {
Ok(expression) => println!("Result {:?}", expression),
Err(err) => eprintln!("Error {:?}", err),
}
}
}
Disini kita menambahkan 2 file yaitu expression.rs dan parser.rs
Untuk melihat hasilnya jalankan program dengan perintah sebagai berikut:
cargo runInput kode berikut ini
a = 1 * 2 + 3 * 4Maka kode diatas akan menghasilkan AST berupa expression sebagai berikut
Binary(Binary(Binary(Variable("a"), ASSIGN, Num(1.0)), Mul, Num(2.0)), Add, Binary(Num(3.0), Mul, Num(4.0)))contoh lainnya:
if 1 > 2 then 1 else 0hasilnya sebagai berikut:
Conditional(Binary(Num(1.0), GT, Num(2.0)), Num(1.0), Num(0.0))