2장: 파싱

새 파일

• src/lexer.rs
• src/pratt.rs
• src/ast.rs
• src/eval.rs
• build.rs
• src/diagnostic.rs
• src/lib.rs
• src/main.rs

변경된 파일

없음.

동기

우리는 1 + 2 * 3을 읽고 곱셈이 먼저라는 것을 압니다. 컴퓨터가 받는 것은 문자열입니다. 컴퓨터가 무엇이든 계산하려면 먼저 그 문자들이 어떻게 맞물리는지 가르쳐야 합니다. 그것이 파서의 일입니다.

우리는 소스 텍스트에서 답에 이르기까지 전 과정을 따라갈 수 있을 만큼 작은 계산기부터 시작하겠습니다. 이 계산기의 파서는 두 번 만들 것입니다. LALRPOP을 쓰면 문법을 적기만 해도 파싱 장치를 대신 생성해 줍니다. Pratt 파서는 연산자를 처리하는 로직을 짧은 Rust 함수 하나에 담습니다. 둘을 모두 살펴보면 파서 생성기가 우리 대신 무엇을 하고 있는지 알아내는 데 도움이 됩니다.

현재의 언어

프로그램은 식 하나입니다. 이 언어에는 십진 정수 리터럴, 이름, +, -, *, /, 단항 마이너스, 괄호, 그리고 비재귀 let이 있습니다.

let x = 7 in (let y = x + 1 in y * y) - x

바인딩은 본문에서 보이며, 우변에서는 보이지 않습니다. 중첩된 바인딩은 바깥쪽 이름을 가립니다. 곱셈과 나눗셈은 덧셈과 뺄셈보다 강하게 결합합니다. 네 연산자는 모두 왼쪽으로 결합합니다. 단항 마이너스는 이들보다 더 강하게 결합합니다. 이 미니 언어에서 / 연산자는 정수 나눗셈 결과를 0 쪽으로 버림합니다. 완전한 Fun에서는 /를 분수 산술용으로 남겨 두고, 이 연산은 quot로 표기할 것입니다.

이론

1 + 2 * 3에 대해서는 그럴듯한 트리가 두 가지 있습니다. 하나는 덧셈을 먼저 하여 9를 반환합니다. 다른 하나는 곱셈을 먼저 하여 7을 반환합니다. 우리가 원하는 것은 두 번째이므로, 문법이 그 선택을 표현할 수 있어야 합니다. 우리는 합, 곱, 아톰을 서로 다른 규칙으로 분리하겠습니다. 합은 곱 전체를 하나의 피연산자로 포함할 수 있습니다. 괄호를 쓰면 다른 묶음을 원할 때 전체 식 문법에서 다시 시작할 수 있습니다.

파싱 전략 고르기

모든 면에서 앞서는 단 하나의 파싱 기법은 없습니다. 어떤 접근법은 문법 전체를 살펴보기 쉽게 해 줍니다. 또 어떤 접근법은 호스트 언어로 작은 파서를 직접 작성하기 쉽게 해 줍니다. 고르기 전에, 흔히 한데 묶어 생각하는 세 가지를 구분해 두면 도움이 됩니다. 문법은 어떤 구문을 받아들일지 정하고, 알고리즘은 그것을 인식하며, API는 우리가 파서를 어떻게 작성할지를 결정합니다.

LR(1)은 왼쪽에서 오른쪽으로 읽어 나가며 최우단 유도(rightmost derivation)를 역순으로 구성합니다. LR(1)의 상태는 이미 읽은 접두부를 요약합니다. 미리 보기(lookahead) 토큰 하나가 다음 토큰을 시프트할지, 완성된 생성 규칙을 리듀스할지를 결정하는 데 도움을 줍니다. “1”이라는 숫자가 식을 토큰 하나로 제한한다는 뜻은 아닙니다. 파서의 스택은 임의로 깊은 구문 문맥을 유지합니다. 더 작은 합을 포함하는 합과 같은 좌재귀는 이러한 상향식 과정에 자연스럽게 들어맞습니다.

LALR(1)은 기반이 되는 LR(0) 항목이 같은 LR(1) 상태들을 병합하고, 그 미리 보기 집합들을 합칩니다. 이렇게 하면 테이블 크기가 줄어들지만, 병합하지 않은 문법에는 없던 충돌이 생길 수 있습니다. 이름과 달리 우리가 사용하는 생성기는 기본적으로 LR(1)을 사용합니다. LALR(1)은 선택 사항입니다. LALRPOP 문서를 참고하십시오. 충돌은 유용한 피드백입니다. 생성된 파서를 신뢰하려면 먼저 문법을 손봐야 합니다.

Pratt 파싱은 연산자에 관한 결정을 국소적으로 내립니다. 1 + 2를 읽은 뒤 파서는 뒤따르는 *를 +의 결합력(binding power)과 비교합니다. 곱셈은 오른쪽 피연산자 안에 속하므로 1 + 2 * 3은 1 + (2 * 3)이 됩니다. 8 - 3 - 1의 경우 오른쪽 피연산자의 문턱값이 같은 세기의 뺄셈을 배제하므로 (8 - 3) - 1이 됩니다. -의 전위 용법과 중위 용법에는 서로 다른 처리기를 둘 수 있습니다. 이 방식은 식에는 아주 잘 맞지만, 그 자체로는 클래스 선언이나 레이아웃 블록의 구조를 규정하지 않습니다.

Packrat 파싱은 각 위치에서 규칙의 성공 또는 실패를 기억해 두어 백트래킹 중의 중복 작업을 피합니다. 이 기법은 흔히 파싱 식 문법(PEG)과 함께 거론되며, 이 문법의 대안들은 순서 있는 선택(ordered choice)을 사용합니다. 처음으로 성공한 대안이 채택됩니다. 따라서 대안의 순서를 바꾸면 언어가 달라질 수 있습니다. 메모이제이션된 항목마다 작업량이 제한된 고정 문법이라면, 이 방식은 선형 인식 시간을 보장하며 메모 저장 공간도 대체로 선형입니다. 일반적인 좌재귀 규칙은 다시 작성하거나 특수한 확장을 사용해야 합니다. 이러한 선택들은 Ford의 packrat과 PEG 개요에서 자세히 다룹니다.

파서 콤비네이터는 파서를 작성하는 방법이지, 하나의 인식 알고리즘이 아닙니다. 순차 콤비네이터는 한 파서를 실행한 뒤 다른 파서를 실행합니다. 선택 콤비네이터는 해당 라이브러리의 규칙에 따라 대안들을 시도합니다. 콤비네이터 라이브러리는 커밋하거나, 백트래킹하거나, 메모이제이션할 수 있습니다. 겉보기에 편리하다고 해서 선형 시간, 좋은 오류 복구, 좌재귀 지원이 저절로 주어지지는 않습니다. 이것들은 여전히 설계상의 선택으로 남습니다.

왜 LALRPOP와 비교용 Pratt 파서를 함께 쓸까요?

LALRPOP는 언어 전체에 대해 들여다볼 수 있는 하나의 문법, AST를 구성하기 위한 타입이 있는 Rust 액션, 그리고 명시적인 복구 생성 규칙을 제공합니다. Pratt는 계산기의 우선순위 규칙을 간결하게 설명하는 두 번째 방식을 제공합니다. 여기서 둘 다 구현하면 묶음(grouping) 결정이 구체적으로 드러나고, 독립적인 비교 대상도 얻을 수 있습니다. 이후의 컴파일러는 LALRPOP를 유지합니다. 두 파서를 모두 실행하지는 않습니다.

Haskell 스타일 구문에는 문법 바깥에서 해야 할 작업도 있습니다. 8장에서 logos는 토큰을 인식하고, marginalia는 포매팅을 위해 주석과 공백을 보존하며, offsides는 들여쓰기를 블록 구분자로 변환합니다. 뒤의 두 라이브러리는 이 프런트엔드에 필요한 트리비아(trivia)와 Haskell 스타일 레이아웃 지원을 제공합니다. 그런 다음 LALRPOP가 이렇게 준비된 토큰 스트림을 소비합니다. 레이아웃은 파서 액션 곳곳에 흩어지는 대신, 별도로 테스트할 수 있는 독립된 변환으로 드러나 있습니다. 이 계산기에는 아직 레이아웃도 주석 보존도 없습니다.

사용자가 선언하는 결합성(fixity)은 별개의 문제를 일으킵니다. 생성된 파서는 소스 파일마다 다른 우선순위 표를 가질 수 없습니다. 8장에서는 평평한 연산자 연쇄를 파싱한 뒤 그 묶음을 나중에 해석합니다. Pratt 루프든 파서 생성기든, 그러한 선언이 언제 알려지는지를 결정해야 할 필요성을 없애 주지는 않습니다.

구문과 타입

이 작은 언어는 이미 타입 판단으로 기술할 수 있습니다. 두 피연산자의 타입이 Int이면, 그 합의 타입도 Int입니다:

$$\frac{\Gamma ⊢e_1:\mathsf{Int}\Gamma ⊢e_2:\mathsf{Int}}{\Gamma ⊢e_1+e_2:\mathsf{Int}}\text{(Add)}$$

값이 정수뿐이므로 아직은 타입 추론기가 필요하지 않습니다. 다만 평가하기 전에 렉시컬 스코프는 검사합니다. Pierce는 구문, 타입, 평가 사이의 구분을 자세히 전개합니다 (Pierce 2002). Haskell Report도 비교 자료로 유용하지만, Fun의 이후 결합성 규칙은 여기서 의도적으로 빠져 있습니다 (Simon Marlow 2010).

구현

lexer.rs는 logos를 사용해 토큰을 인식하고 바이트 범위(span)를 보존합니다. 길이가 같으면 키워드가 식별자보다 우선합니다. 잘못된 문자나 범위를 벗어난 리터럴은 E0001을 발생시킵니다. ast.rs는 각 식에 범위를 저장하므로, 소스 정보를 잃지 않고 두 파서를 비교할 수 있습니다.

#![allow(unused)]
fn main() {
/// Byte offsets into the single source file, including parentheses when present.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Expr {
    pub kind: Kind,
    pub span: Range<usize>,
}

/// An error node exists only during recovery; the driver never evaluates it.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Kind {
    Int(i64),
    Var(String),
    Neg(Box<Expr>),
    Binary(Op, Box<Expr>, Box<Expr>),
    Let(String, Box<Expr>, Box<Expr>),
    Error,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Op {
    Add,
    Sub,
    Mul,
    Div,
}
}

생성된 파서는 비단말 기호로 우선순위를 구현합니다. 전체 문법은 바인딩, 괄호, 단항 마이너스, 그리고 복구 생성 규칙도 처리합니다.

Sum: Expr = {
    <a:Sum> "+" <b:Product> => Expr::binary(Op::Add, a, b),
    <a:Sum> "-" <b:Product> => Expr::binary(Op::Sub, a, b),
    Product,
};
Product: Expr = {
    <a:Product> "*" <b:Unary> => Expr::binary(Op::Mul, a, b),
    <a:Product> "/" <b:Unary> => Expr::binary(Op::Div, a, b),
    Unary,
};

! 생성 규칙은 오류 노드를 삽입하고 복구 진단을 저장합니다. 드라이버는 복구로 트리가 만들어지더라도 오류를 반환합니다. 평가기는 복구 노드를 절대 받지 않습니다. diagnostic.rs는 안정적인 오류 코드 줄과 위치를 출력한 다음, ariadne가 바이트 인덱싱으로 소스 발췌를 렌더링하게 합니다.

#![allow(unused)]
fn main() {
/// Parse and recover enough to report several syntax errors, then stop the pass.
pub fn parse(source: &str) -> Result<Expr, Vec<Diagnostic>> {
    let tokens = lexer::lex(source)?;
    let mut recovered = Vec::new();
    let parsed = parser::ExprParser::new()
        .parse(&mut recovered, tokens.into_iter().map(Ok));
    let mut errors: Vec<_> = recovered
        .into_iter()
        .map(|r| parse_error(r.error))
        .collect();
    match parsed {
        Ok(expr) if errors.is_empty() => Ok(expr),
        Ok(_) => Err(errors),
        Err(error) => {
            errors.push(parse_error(error));
            Err(errors)
        }
    }
}
}

Pratt 파서의 루프는 결합력이 충분히 높은 연산자를 소비합니다. 오른쪽 피연산자를 power + 1에서 파싱하면 연산자가 왼쪽 결합이 됩니다. 전위 파싱은 이름, 리터럴, 괄호, 부정을 처리합니다. let은 별도의 진입점이 처리합니다.

#![allow(unused)]
fn main() {
fn infix(&mut self, min_power: u8) -> Result<Expr, Diagnostic> {
    let mut left = self.prefix()?;
    loop {
        let (op, power) = match self.peek() {
            Some(Token::Plus) => (Op::Add, 1),
            Some(Token::Minus) => (Op::Sub, 1),
            Some(Token::Star) => (Op::Mul, 3),
            Some(Token::Slash) => (Op::Div, 3),
            _ => break,
        };
        if power < min_power {
            break;
        }
        self.at += 1;
        let right = self.infix(power + 1)?;
        left = Expr::binary(op, left, right);
    }
    Ok(left)
}
}

eval.rs는 끝에서부터 탐색하는 바인딩 스택을 사용해 렉시컬 스코프를 모델링합니다. 이항 연산자의 왼쪽 피연산자를 오른쪽 피연산자보다 먼저 평가하고, 바인딩 본문이 실패하더라도 환경을 복원합니다. 산술은 처음부터 랩어라운드되는 63비트 값을 사용하므로 Rust의 디버그 오버플로 검사에 의존하지 않습니다. 정규화 함수는 Rust 항목으로 포함됩니다:

#![allow(unused)]
fn main() {
use crate::{
    ast::{Expr, Kind, Op},
    diagnostic::Diagnostic,
};
/// Check every variable occurrence without executing arithmetic.
pub fn check(expr: &Expr) -> Result<(), Vec<Diagnostic>> {
    fn visit(
        expr: &Expr,
        names: &mut Vec<String>,
        errors: &mut Vec<Diagnostic>,
    ) {
        match &expr.kind {
            Kind::Var(name) if !names.contains(name) => {
                errors.push(Diagnostic::new(
                    "E0101",
                    format!("unbound variable `{name}`"),
                    expr.span.clone(),
                ))
            }
            Kind::Neg(a) => visit(a, names, errors),
            Kind::Binary(_, a, b) => {
                visit(a, names, errors);
                visit(b, names, errors);
            }
            Kind::Let(name, a, b) => {
                visit(a, names, errors);
                names.push(name.clone());
                visit(b, names, errors);
                names.pop();
            }
            _ => {}
        }
    }
    let mut errors = Vec::new();
    visit(expr, &mut Vec::new(), &mut errors);
    if errors.is_empty() {
        Ok(())
    } else {
        Err(errors)
    }
}
/// The environment is a stack: the most recent binding shadows earlier names.
pub fn evaluate(
    expr: &Expr,
    env: &mut Vec<(String, i64)>,
) -> Result<i64, String> {
    match &expr.kind {
        Kind::Int(n) => Ok(normalize(*n)),
        Kind::Var(name) => env
            .iter()
            .rev()
            .find(|(key, _)| key == name)
            .map(|(_, value)| *value)
            .ok_or_else(|| format!("unbound variable `{name}`")),
        Kind::Neg(value) => {
            Ok(normalize(evaluate(value, env)?.wrapping_neg()))
        }
        Kind::Binary(op, left, right) => {
            let a = evaluate(left, env)?;
            let b = evaluate(right, env)?;
            Ok(normalize(match op {
                Op::Add => a.wrapping_add(b),
                Op::Sub => a.wrapping_sub(b),
                Op::Mul => a.wrapping_mul(b),
                Op::Div if b == 0 => return Err("divide by zero".into()),
                Op::Div => a / b,
            }))
        }
        Kind::Let(name, value, body) => {
            let value = evaluate(value, env)?;
            env.push((name.clone(), value));
            let result = evaluate(body, env);
            env.pop();
            result
        }
        Kind::Error => {
            Err("internal error: attempted to evaluate a recovery node"
                .into())
        }
    }
}
pub fn normalize(n: i64) -> i64 {
    (n << 1) >> 1
}
}

#![allow(unused)]
fn main() {
/// The environment is a stack: the most recent binding shadows earlier names.
pub fn evaluate(
    expr: &Expr,
    env: &mut Vec<(String, i64)>,
) -> Result<i64, String> {
    match &expr.kind {
        Kind::Int(n) => Ok(normalize(*n)),
        Kind::Var(name) => env
            .iter()
            .rev()
            .find(|(key, _)| key == name)
            .map(|(_, value)| *value)
            .ok_or_else(|| format!("unbound variable `{name}`")),
        Kind::Neg(value) => {
            Ok(normalize(evaluate(value, env)?.wrapping_neg()))
        }
        Kind::Binary(op, left, right) => {
            let a = evaluate(left, env)?;
            let b = evaluate(right, env)?;
            Ok(normalize(match op {
                Op::Add => a.wrapping_add(b),
                Op::Sub => a.wrapping_sub(b),
                Op::Mul => a.wrapping_mul(b),
                Op::Div if b == 0 => return Err("divide by zero".into()),
                Op::Div => a / b,
            }))
        }
        Kind::Let(name, value, body) => {
            let value = evaluate(value, env)?;
            env.push((name.clone(), value));
            let result = evaluate(body, env);
            env.pop();
            result
        }
        Kind::Error => {
            Err("internal error: attempted to evaluate a recovery node"
                .into())
        }
    }
}
}

main.rs는 이 조각들을 명령과 REPL에 연결합니다. 같은 식에 두 파서를 모두 적용해 보고 각각의 트리를 살펴보십시오. 테스트도 이 작업을 하며, 서로 다른 묶음을 가진 생성된 식들도 포함합니다. 트리를 비교하면 우연히 맞아떨어진 수치 결과가 가릴 수 있는 실수를 잡아낼 수 있습니다.

실행해 보기

$ cd crates/ch02_calc
$ cargo run -q -- run tests/programs/precedence.fun
7
$ cargo run -q -- dump --pass=parse tests/programs/precedence.fun
(+ 1 (* 2 3))
$ cargo run -q -- run tests/programs/precedence.fun --parser=pratt
7
$ cargo run -q -- repl
Calc: :quit to exit, :parse EXPR to inspect the AST.
calc> let x = 6 in x * 7
42
calc> :quit

check는 산술을 실행하지 않고 구문과 이름을 검증합니다. 따라서 1 / 0은 check를 통과하지만, run은 fun: divide by zero를 보고하고 상태 1로 종료합니다. 렉서 스팬을 살펴보려면 dump --pass=tokens를 사용하십시오.

연습 문제

1. 쉬움. 20 - 3 * 4 - 1의 값과 파스 덤프를 모두 예측한 다음 실행해 보십시오.
2. 쉬움. 1과 (1)의 스팬을 비교하십시오. 두 값이 같은 이유를 설명하십시오.
3. 보통. Pratt 파서의 오른쪽 결합력을 power로 바꾸십시오. 결합성 변화를 드러내는 가장 작은 뺄셈 식을 찾으십시오.
4. 보통. 서로 독립적인 구문 오류 두 개를 보고하는 잘못된 식을 작성하십시오. 복구가 어디에서 재개될 수 있는지 설명하십시오.
5. 어려움. 생성기를 확장해 불필요한 괄호를 삽입하게 하고, 평가 결과가 바뀌지 않음을 검증하십시오.

더 읽을거리

Pierce는 구문과 의미를 신중하게 구분합니다 (Pierce 2002). Haskell Report는 훨씬 더 큰 구체 구문과 결합성 해석 절차를 규정합니다(Simon Marlow 2010).