기술

nom으로 rslogo 파서 만들기

2024년 3월 18일 월요일 / , , , ,
简体中文한국어
요약 ·
Rust 파서 컴비네이터 라이브러리 nom으로 COMP6991 과제 rslogo의 파서를 만들었다. Logo의 표현식과 명령, 중첩된 코드 블록을 파싱한다.

이번 학기에 UNSW의 COMP6991을 듣고 있다. 과제 중 하나가 rslogo인데, Rust로 Logo 언어의 인터프리터를 만드는 과제다. Logo는 거북이를 앞으로 움직이고, 돌리고, 펜을 들거나 내려 그림을 그리는 교육용 언어다. rslogo가 할 일은 .lg 파일을 읽고 그 안의 명령을 실행한 뒤, 거북이가 그린 결과를 SVG로 저장하는 것이다.

코드를 실행하려면 먼저 파싱해야 한다. 전부 정규식으로 처리할 수도 있지만, Logo에는 중첩된 [ ]와 표현식이 있다. 이런 걸 정규식으로 쓰려면 머리도 아프고 실수하기도 쉽다. 기본적인 문자열 연산만 써서 공백으로 나눈 다음 하나씩 판별하는 방법도 있다. 구현은 되겠지만, 수많은 if와 인덱스로 뒤덮일 것이다. 깔끔하지도 않고 Rust답지도 않다.

다행히 이 과제에서는 외부 라이브러리를 써도 됐다. 좀 더 Rust다운 방법이 없을까 찾아보다가 nom과 pest를 발견했다. pest는 문법을 설명하는 별도의 .pest 파일을 작성해야 하고, 전용 문법도 새로 배워야 한다. 반면 nom으로 작성하는 건 평범한 Rust 함수다. 그래서 자연스럽게 nom을 골랐다.

rslogo의 문법

rslogo가 지원해야 할 코드는 이런 모습이다.

TEXT
TO Box "Arg
   FORWARD :Arg
   LEFT :Arg
END

MAKE "BOXLINE "2

WHILE LT :BOXLINE "60 [
      SETPENCOLOR + COLOR "2
      Box :BOXLINE
      IF LT "8 COLOR [
         SETPENCOLOR "2
      ]
      ADDASSIGN "BOXLINE "2
]

"로 시작하면 리터럴, :로 시작하면 변수다. COLOR 같은 것은 거북이의 현재 상태를 조회한다. 연산자는 전위 표기법을 써서, + COLOR "2가 COLOR + 2라는 뜻이다. IF와 WHILE 뒤에는 조건과 코드 블록이 오고, TO ... END는 프로시저를 정의한다. 표현식과 코드 블록은 얼마든지 중첩될 수 있다. 정규식이 특히 어려워하는 부분이다.

nom의 동작 방식

nom은 파서 컴비네이터 라이브러리다. 작은 파서를 여러 개 작성한 뒤, 블록을 쌓듯 조합해 큰 파서를 만드는 방식이다.

nom에서 파서는 그냥 함수다. 입력을 받아 파싱에 성공하면, 아직 처리하지 않은 나머지 입력과 파싱 결과를 반환한다.

Rust
use nom::{bytes::complete::tag, IResult};

fn penup(input: &str) -> IResult<&str, &str> {
    tag("PENUP")(input)
}

assert_eq!(penup("PENUP FORWARD"), Ok((" FORWARD", "PENUP")));

tag("PENUP") 자체가 파서를 반환하기 때문에 괄호 두 쌍이 이어지는 형태가 된다. PENUP을 소비하고 나면 나머지 " FORWARD"가 그대로 반환된다. 다음 파서는 여기서부터 계속 처리하면 된다. 반환하는 문자열도 모두 원래 입력의 슬라이스이므로, 이 과정에서 복사할 필요가 없다.

nom의 편리한 점은 쓸 만한 컴비네이터가 이미 많이 준비돼 있다는 것이다. alt는 여러 파서를 순서대로 시도해 처음 성공한 결과를 쓴다. preceded, delimited, tuple은 여러 파서를 순서대로 적용하고 필요한 결과를 골라낸다. many0는 반복해서 매칭하고, map은 결과를 원하는 타입으로 바꾼다. 예를 들어 "60은 따옴표 뒤에 숫자가 오는 형태이므로 nom으로는 이렇게 쓸 수 있다.

Rust
map(preceded(tag("\""), double), |n| Atom::Number(n as f32))

거의 문법 규칙 자체를 읽는 것 같다. 파서 하나하나가 작아 따로 테스트할 수 있고, 조합할 때는 타입 시스템이 각 단계가 맞물리는지도 확인해 준다.

구문 트리

파서를 작성하기 전에, 파싱 결과가 어떤 모양일지 enum으로 먼저 정의했다.

Rust
pub enum Atom {
    Number(f32),
    Boolean(bool),
    String(String),
    Variable(String),
    Query(Query),
}

pub enum Expr {
    Void,
    Constant(Atom),
    Call(String, Vec<Expr>),
    Calculation(Operator, Box<Expr>, Box<Expr>),
    If(Box<Expr>, Vec<Expr>),
    While(Box<Expr>, Vec<Expr>),
    Function(String, Vec<Atom>, Vec<Expr>),
}

파서가 할 일은 문자열을 Vec<Expr>로 바꾸는 것이다.

rslogo 파서

공백

Logo에는 공백이 여기저기 있다. 파서마다 매번 처리하면 번거로우니 ws를 만들었다. 파서를 받아 앞뒤 공백까지 소비하는 새 파서를 반환한다.

Rust
fn ws<'a, F: 'a, O>(inner: F) -> impl FnMut(&'a str) -> IResult<O>
where
    F: FnMut(&'a str) -> IResult<O>,
{
    delimited(multispace0, inner, multispace0)
}

이것도 직접 만든 컴비네이터라, 쓰는 방법은 nom에 기본으로 들어 있는 것과 다르지 않다.

값

각 값은 접두사 뒤에 내용이 오는 구조라 작성 방식도 비슷하다. 마지막에 alt로 묶는다.

Rust
fn parse_atom(input: &str) -> IResult<Atom> {
    alt((
        parse_number,
        parse_boolean,
        parse_string,
        parse_variable,
        parse_query,
    ))(input)
}

다만 여기서는 순서가 중요하다. alt는 처음 성공한 결과를 쓴다. "TRUE는 불리언으로 볼 수도 있고, TRUE라는 이름으로 볼 수도 있으므로 parse_boolean을 parse_string보다 앞에 둬야 한다.

전위 표현식

내가 nom에서 가장 깔끔하다고 느낀 부분이다. 계산은 연산자 뒤에 값을 가진 무언가가 두 개 오는 형태다. 그 둘도 다시 계산식일 수 있다.

Rust
fn parse_calculation(input: &str) -> IResult<Expr> {
    let parser = ws(tuple((
        alt((
            tag("EQ"), tag("NE"), tag("GT"), tag("LT"),
            tag("AND"), tag("OR"),
            tag("+"), tag("-"), tag("*"), tag("/"),
        )),
        parse_unvoid,
        parse_unvoid,
    )));
    map(parser, |(operator, left, right)| {
        // "EQ", "+" 같은 문자열을 Operator의 각 variant에 매핑하는 코드는 생략
        Expr::Calculation(to_operator(operator), Box::new(left), Box::new(right))
    })(input)
}

fn parse_unvoid(input: &str) -> IResult<Expr> {
    alt((parse_calculation, parse_constant))(input)
}

parse_calculation과 parse_unvoid는 서로 재귀 호출한다. 그래서 AND GT XCOR "0 GT YCOR "0처럼 여러 겹으로 중첩된 표현식도 한 번에 파싱할 수 있다. 전위 표현식은 연산자 우선순위를 따질 필요도, 괄호를 쓸 필요도 없어서 표현식 파서 전체가 이 몇 줄로 끝난다.

명령과 키워드

명령 호출은 이름 뒤에 여러 인수가 붙는 형태다.

Rust
fn parse_call(input: &str) -> IResult<Expr> {
    let parser_args = ws(many0(parse_unvoid));
    let parser_command = ws(verify(alphanumeric_underline1, |s: &str| {
        not_reserved_word(s)
    }));
    let parser = ws(pair(parser_command, parser_args));
    map(parser, |(command, args)| Expr::Call(command.to_string(), args))(input)
}

명령 이름과 키워드는 둘 다 글자가 나열된 형태라 구분하지 않으면 END까지 명령으로 소비해 버린다. 그러면 TO ... END의 끝을 찾을 수 없다. 그래서 이름에 매칭된 뒤 verify로 한 번 더 확인하고, 예약어면 실패로 처리했다. 이렇게 하면 프로시저 정의 안의 many0(parse_expr)가 END를 만났을 때 자연스럽게 멈추고, 바깥의 delimited가 이를 처리할 수 있다.

Rust
fn parse_function(input: &str) -> IResult<Expr> {
    let parser_name = ws(alphanumeric_underline1);
    let parser_args = ws(many0(parse_atom));
    let parser_body = ws(many0(parse_expr));
    let parser_inner = ws(tuple((parser_name, parser_args, parser_body)));
    let parser = ws(delimited(ws(tag("TO")), parser_inner, ws(tag("END"))));
    map(parser, |(name, args, body)| {
        Expr::Function(name.to_string(), args, body)
    })(input)
}

IF와 WHILE도 비슷하게 작성한다. 조건 뒤의 코드 블록은 delimited(tag("["), many0(parse_expr), tag("]"))로 파싱한다. 블록 안에서도 다시 parse_expr를 쓰니 중첩도 자연스럽게 지원된다.

진입점

마지막으로 모든 구문을 조합한다.

Rust
fn parse_expr(input: &str) -> IResult<Expr> {
    alt((
        parse_function,
        parse_while,
        parse_if,
        parse_constant,
        parse_call,
    ))(input)
}

pub fn parse(input: &str) -> Result<Vec<Expr>, ErrorTree<&str>> {
    final_parser(many0(ws(parse_expr)))(input)
}

ErrorTree와 final_parser는 nom-supreme에서 가져왔다. ErrorTree는 도중에 시도한 분기들을 기록해 주기 때문에, 오류가 나면 어디가 문제인지 알아보기 쉽다. final_parser는 입력을 전부 소비해야 한다는 조건을 건다. 일반적인 nom 파서는 입력의 일부만 파싱해도 성공을 반환할 수 있어서, 그대로 쓰면 남은 내용을 놓칠 수 있다.

파서 전체를 합쳐도 약 200줄이다. 각 함수는 거의 하나의 문법 규칙에 대응한다.

평가기

파서를 완성하고 나니 실행 부분은 훨씬 수월했다. 평가기는 거북이의 상태와 그림을 그릴 캔버스를 저장하는 구조체다. 캔버스는 수업에서 제공한 unsvg를 썼다.

Rust
pub struct Evaluater {
    pub image: Image,
    pen_down: bool,
    x: f32,
    y: f32,
    heading: i32,
    color: i32,
}

핵심은 Expr를 match하는 재귀 함수 eval_expr다. 구문 트리가 이미 enum으로 정의돼 있어서 각 구문을 어떻게 실행할지가 그대로 분기에 대응한다. 변수와 사용자 정의 프로시저는 HashMap<String, Expr>에 저장하며, 나는 여기에 context라는 이름을 붙였다.

Rust
fn eval_expr(
    &mut self,
    expr: Expr,
    context: &mut HashMap<String, Expr>,
) -> Result<Expr, String> {
    match expr {
        Expr::Constant(ref atom) => match atom {
            // 변수는 context에서 가져오고 쿼리는 거북이의 현재 상태를 반환
            Atom::Variable(v) => /* ... */,
            Atom::Query(q) => /* ... */,
            _ => Ok(expr),
        },
        Expr::Call(name, args) => match name.as_str() {
            "PENDOWN" => { /* ... */ }
            "FORWARD" => { /* ... */ }
            "MAKE" => { /* ... */ }
            // 내장 명령이 아니면 context에서 사용자 정의 프로시저를 찾는다
            _ => { /* ... */ }
        },
        Expr::Calculation(op, left, right) => { /* ... */ }
        Expr::If(condition, body) => { /* ... */ }
        Expr::While(condition, body) => { /* ... */ }
        Expr::Function(name, parameters, body) => { /* ... */ }
        Expr::Void => Ok(expr),
    }
}

eval_expr의 반환값도 Expr다. 표현식을 평가하면 Expr::Constant가 되고, 명령을 실행한 뒤 남는 값이 없으면 Expr::Void를 반환한다. 따라서 계산할 때는 먼저 양쪽을 재귀적으로 평가한 뒤, 둘 다 숫자인지 아니면 불리언인지 확인하면 된다.

Rust
Expr::Calculation(op, left, right) => {
    let left = self.eval_expr(*left, context)?;
    let right = self.eval_expr(*right, context)?;
    let res = match (left, right) {
        (Expr::Constant(Atom::Number(l)), Expr::Constant(Atom::Number(r))) => match op {
            Operator::Add => Atom::Number(l + r),
            Operator::LessThan => Atom::Boolean(l < r),
            // ...
        },
        (Expr::Constant(Atom::Boolean(l)), Expr::Constant(Atom::Boolean(r))) => match op {
            Operator::And => Atom::Boolean(l && r),
            Operator::Or => Atom::Boolean(l || r),
            // ...
        },
        _ => return Err("Invalid calculation".to_string()),
    };
    Ok(Expr::Constant(res))
}

match로 양쪽을 동시에 검사하므로 타입이 맞지 않는 조합은 마지막 분기에서 오류가 난다. 예를 들어 + "1 "TRUE는 이 검사를 통과하지 못한다.

IF와 WHILE은 먼저 조건을 평가한다. TRUE면 코드 블록을 실행하고, 불리언이 아니면 오류를 반환한다. WHILE은 매 반복마다 조건을 다시 평가하므로, 반복문 안에서 조건에 쓰는 변수를 바꾸면 다음 반복에서 새 값을 보게 된다.

프로시저 정의인 TO ... END를 실행할 때는 본문을 실행하지 않는다. 그대로 context에 저장하기만 한다. 이후 내장 명령이 아닌 이름을 호출하면 context에서 같은 이름의 프로시저를 찾는다. 찾았다면 현재 context를 복제해 새 스코프를 만들고, 인수의 값을 넣은 뒤 그 스코프에서 본문을 실행한다. 이렇게 하면 프로시저 안에서 변수를 바꿔도 바깥에는 영향을 주지 않는다.

Rust
_ => match context.get(&name).cloned() {
    Some(Expr::Function(_, parameters, body)) => {
        let mut scope = context.clone();
        for (parameter, arg) in parameters.into_iter().zip(args.into_iter()) {
            match parameter {
                Atom::String(s) => {
                    let expr = self.eval_expr(arg, context)?;
                    scope.insert(s.clone(), expr);
                }
                _ => return Err("Invalid parameter".to_string()),
            }
        }
        for expr in body {
            self.eval_expr(expr.clone(), &mut scope)?;
        }
    }
    _ => return Err(format!("Function {name} not found")),
},

선을 그리는 부분은 더 단순하다. FORWARD, BACK 같은 명령으로 끝점의 좌표를 계산하고, 펜이 내려가 있으면 unsvg로 두 점 사이에 선을 그린 뒤 거북이의 위치를 갱신한다. 모든 오류는 Result로 호출자에게 차례로 전달하고, 마지막에 main에서 color-eyre로 출력한다.

저장소: xxxbrian/unsw-comp6991-rslogo.

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...