파서
우리가 구축할 파서는 재귀 내림 파서라고 불립니다. 이는 문법을 따라 내려가면서 추상구문트리(АСТ)를 구성하는 수동적인 과정입니다.
파서는 간단하게 시작합니다. 소스 코드, 렉서, 그리고 렉서로부터 소비된 현재 토큰을 보유합니다.
pub struct Parser<'a> {
/// 소스 코드
source: &'a str,
lexer: Lexer<'a>,
/// 렉서로부터 소비된 현재 토큰
cur_token: Token,
/// 이전 토큰의 종료 범위
prev_token_end: usize,
}
impl<'a> Parser<'a> {
pub fn new(source: &'a str) -> Self {
Self {
source,
lexer: Lexer::new(source),
cur_token: Token::default(),
}
}
pub fn parse(&mut self) -> Program<'a> {
Ok(Program {
node: Node {
start: 0,
end: self.source.len(),
}
body: vec![]
})
}
}도우미 함수
현재 토큰 cur_token: Token은 렉서로부터 반환된 현재 토큰을 저장합니다. 이 토큰을 탐색하고 검사하기 위한 몇 가지 도우미 함수를 추가함으로써 파서 코드를 더욱 깔끔하게 만들 수 있습니다.
impl<'a> Parser<'a> {
fn start_node(&self) -> Node {
let token = self.cur_token();
Node::new(token.start, 0)
}
fn finish_node(&self, node: Node) -> Node {
Node::new(node.start, self.prev_token_end)
}
fn cur_token(&self) -> &Token {
&self.cur_token
}
fn cur_kind(&self) -> Kind {
self.cur_token.kind
}
/// 현재 인덱스에 지정된 `Kind` 토큰이 있는지 확인합니다
fn at(&self, kind: Kind) -> bool {
self.cur_kind() == kind
}
/// 현재 토큰이 `Kind`라면 진행합니다
fn bump(&mut self, kind: Kind) {
if self.at(kind) {
self.advance();
}
}
/// 어떤 토큰이든 진행합니다
fn bump_any(&mut self) {
self.advance();
}
/// 현재 토큰이 `Kind`라면 진행하고 `true`를 반환, 그렇지 않으면 `false`를 반환합니다
fn eat(&mut self, kind: Kind) -> bool {
if self.at(kind) {
self.advance();
return true;
}
false
}
/// 다음 토큰으로 이동합니다
fn advance(&mut self) {
let token = self.lexer.next_token();
self.prev_token_end = self.cur_token.end;
self.cur_token = token;
}
}파싱 함수
DebuggerStatement은 파싱하기 가장 간단한 문장이므로, 이를 시도해보고 유효한 프로그램을 반환해보겠습니다.
impl<'a> Parser<'a> {
pub fn parse(&mut self) -> Program {
let stmt = self.parse_debugger_statement();
let body = vec![stmt];
Program {
node: Node {
start: 0,
end: self.source.len(),
}
body,
}
}
fn parse_debugger_statement(&mut self) -> Statement {
let node = self.start_node();
// NOTE: 렉서에서 반환된 토큰은 `Kind::Debugger`입니다. 나중에 수정하겠습니다.
self.bump_any();
Statement::DebuggerStatement {
node: self.finish_node(node),
}
}
}다른 모든 파싱 함수는 이러한 기본적인 도우미 함수들을 기반으로 구축됩니다. 예를 들어, swc에서 while 문장을 파싱하는 방식은 다음과 같습니다:
// https://github.com/swc-project/swc/blob/554b459e26b24202f66c3c58a110b3f26bbd13cd/crates/swc_ecma_parser/src/parser/stmt.rs#L952-L970
fn parse_while_stmt(&mut self) -> PResult<Stmt> {
let start = cur_pos!(self);
assert_and_bump!(self, "while");
expect!(self, '(');
let test = self.include_in_expr(true).parse_expr()?;
expect!(self, ')');
let ctx = Context {
is_break_allowed: true,
is_continue_allowed: true,
..self.ctx()
};
let body = self.with_ctx(ctx).parse_stmt(false).map(Box::new)?;
let span = span!(self, start);
Ok(Stmt::While(WhileStmt { span, test, body }))
}표현식 파싱
표현식의 문법은 깊이 중첩되고 재귀적이며, 긴 표현식에서는 스택 오버플로우가 발생할 수 있습니다 (예: 이 타입스크립트 테스트).
재귀를 피하기 위해 '프래트 파싱(Pratt Parsing)'이라는 기술을 사용할 수 있습니다. 더 깊이 있는 안내는 여기에서 찾을 수 있으며, 이 글은 루스트-애널라이저의 작성자에 의해 작성되었습니다. 그리고 루스트 버전은 로미에서 확인할 수 있습니다.
목록
목록을 구분하는 구두점으로 나누어 파싱해야 하는 경우가 많습니다. 예를 들어 [a, b, c] 또는 {a, b, c}와 같은 형태 말입니다.
목록을 파싱하는 코드는 모두 비슷하며, 템플릿 메서드 패턴을 사용하여 특성(trait)을 통해 중복을 피할 수 있습니다.
// https://github.com/rome/tools/blob/85ddb4b2c622cac9638d5230dcefb6cf571677f8/crates/rome_js_parser/src/parser/parse_lists.rs#L131-L157
fn parse_list(&mut self, p: &mut Parser) -> CompletedMarker {
let elements = self.start_list(p);
let mut progress = ParserProgress::default();
let mut first = true;
while !p.at(JsSyntaxKind::EOF) && !self.is_at_list_end(p) {
if first {
first = false;
} else {
self.expect_separator(p);
if self.allow_trailing_separating_element() && self.is_at_list_end(p) {
break;
}
}
progress.assert_progressing(p);
let parsed_element = self.parse_element(p);
if parsed_element.is_absent() && p.at(self.separating_element_kind()) {
// 누락된 요소
continue;
} else if self.recover(p, parsed_element).is_err() {
break;
}
}
self.finish_list(p, elements)
}이 패턴은 무한 루프를 방지할 수도 있으며, 특히 progress.assert_progressing(p);에 의해서 가능합니다.
구현 세부 사항은 다양한 목록에 대해 제공될 수 있습니다. 예를 들어:
// https://github.com/rome/tools/blob/85ddb4b2c622cac9638d5230dcefb6cf571677f8/crates/rome_js_parser/src/syntax/expr.rs#L1543-L1580
struct ArrayElementsList;
impl ParseSeparatedList for ArrayElementsList {
fn parse_element(&mut self, p: &mut Parser) -> ParsedSyntax {
match p.cur() {
T![...] => parse_spread_element(p, ExpressionContext::default()),
T![,] => Present(p.start().complete(p, JS_ARRAY_HOLE)),
_ => parse_assignment_expression_or_higher(p, ExpressionContext::default()),
}
}
fn is_at_list_end(&self, p: &mut Parser) -> bool {
p.at(T![']'])
}
fn recover(&mut self, p: &mut Parser, parsed_element: ParsedSyntax) -> RecoveryResult {
parsed_element.or_recover(
p,
&ParseRecovery::new(
JS_UNKNOWN_EXPRESSION,
EXPR_RECOVERY_SET.union(token_set!(T![']'])),
),
js_parse_error::expected_array_element,
)
}
fn list_kind() -> JsSyntaxKind {
JS_ARRAY_ELEMENT_LIST
}
fn separating_element_kind(&mut self) -> JsSyntaxKind {
T![,]
}
fn allow_trailing_separating_element(&self) -> bool {
true
}
}커버 문법
커버 문법에서 자세히 설명되어 있듯이, 때때로 표현식(Експрессия)을 바인딩 식별자(Вязующий идентификатор)로 변환해야 할 때가 있습니다. 동적 언어인 자바스크립트는 단순히 노드 유형을 다시 작성할 수 있지만:
https://github.com/acornjs/acorn/blob/11735729c4ebe590e406f952059813f250a4cbd1/acorn/src/lval.js#L11-L26루스트에서는 구조체에서 구조체로의 변환을 수행해야 합니다. 이를 깔끔하게 수행하는 좋은 방법은 특성(트레이트)을 사용하는 것입니다.
pub trait CoverGrammar<'a, T>: Sized {
fn cover(value: T, p: &mut Parser<'a>) -> Result<Self>;
}이 특성은 입력 타입으로 T를 받으며, Self와 출력 타입을 받으므로 다음과 같이 정의할 수 있습니다:
impl<'a> CoverGrammar<'a, Expression<'a>> for BindingPattern<'a> {
fn cover(expr: Expression<'a>, p: &mut Parser<'a>) -> Result<Self> {
match expr {
Expression::Identifier(ident) => Self::cover(ident.unbox(), p),
Expression::ObjectExpression(expr) => Self::cover(expr.unbox(), p),
Expression::ArrayExpression(expr) => Self::cover(expr.unbox(), p),
_ => Err(()),
}
}
}
impl<'a> CoverGrammar<'a, ObjectExpression<'a>> for BindingPattern<'a> {
fn cover(obj_expr: ObjectExpression<'a>, p: &mut Parser<'a>) -> Result<Self> {
...
BindingIdentifier::ObjectPattern(ObjectPattern { .. })
}
}
impl<'a> CoverGrammar<'a, ArrayExpression<'a>> for BindingPattern<'a> {
fn cover(expr: ArrayExpression<'a>, p: &mut Parser<'a>) -> Result<Self> {
...
BindingIdentifier::ArrayPattern(ArrayPattern { .. })
}
}그러면 표현식을 바인딩 패턴으로 변환해야 하는 어느 곳이라도 BindingPattern::cover(expression)를 호출하면 됩니다.
타입스크립트
자바스크립트를 마무리하고 타입스크립트를 파싱하는 것을 도전하고자 하시나요?
악담은 규격이 없다는 것이지만, 다행히도 타입스크립트 파서는 하나의 파일 안에 존재합니다 🙃.
JSX vs TSX
다음 코드를 살펴보세요.
let foo = <string> bar;이 코드가 tsx라면 문법 오류입니다 (종료되지 않은 JSX), 하지만 VariableDeclaration과 TSTypeAssertion로 올바르게 해석됩니다.
앞선 보기
일부 위치에서는 파서가 여러 토큰을 미리 보아야 하며, 올바른 문법을 결정하기 위해 한 번 이상의 토큰을 조사해야 합니다.
타입스크립트 인덱스 서명
예를 들어 TSIndexSignature를 파싱할 때, 다음 두 경우를 고려해보세요:
type A = { readonly [a: number]: string }
^__________________________^ TSIndexSignature
type B = { [a]: string }
^_________^ TSPropertySignaturetype A에서 첫 번째 {에서, readonly, [, a, : 및 number까지 총 5개의 토큰을 미리 읽어봐야, 이것이 TSIndexSignature인지 아닌지를 확실히 판단할 수 있습니다.
이렇게 가능하고 효율적으로 하기 위해 렉서는 여러 토큰을 저장하기 위한 버퍼가 필요합니다.
화살표 표현식
커버 문법에서 논의된 바와 같이, SequenceExpression 뒤에 => 토큰을 발견하면 표현식(Експрессия)에서 바인딩 패턴(Вязующий паттерн)으로 변환해야 합니다.
그러나 이 접근법은 타입스크립트에는 적용되지 않습니다. 괄호 안의 각 항목은 타입스크립트 문법을 가질 수 있기 때문에 다루어야 할 경우가 너무 많습니다. 예를 들어:
(<x>a, b as c, d!);
(a?: b = {} as c!) => {};이 특정 경우에 대해 타입스크립트 소스 코드를 공부하는 것이 권장됩니다. 관련 코드는 다음과 같습니다:
function tryParseParenthesizedArrowFunctionExpression(
allowReturnTypeInArrowFunction: boolean,
): Expression | undefined {
const triState = isParenthesizedArrowFunctionExpression();
if (triState === Tristate.False) {
// 분명히 괄호화된 화살표 함수 표현식이 아님.
return undefined;
}
// 분명히 화살표 함수라면, 후속 `=>` 또는 `{` 토큰이 필요 없이 그냥 파싱할 수 있다. 그렇지 않다면, 화살표 함수일 가능성만 있을 뿐이다.
// 파싱해보지만 모호함을 허용하지 않으며, 만약 이것이 표현식일 수 있다면 `undefined`를 반환한다.
return triState === Tristate.True
? parseParenthesizedArrowFunctionExpression(
/*allowAmbiguity*/ true,
/*allowReturnTypeInArrowFunction*/ true,
)
: tryParse(() =>
parsePossibleParenthesizedArrowFunctionExpression(allowReturnTypeInArrowFunction),
);
}
// True -> 여기서 분명히 괄호화된 화살표 함수를 기대합니다.
// False -> 여기서 괄호화된 화살표 함수가 *절대* 존재할 수 없습니다.
// Unknown -> 여기서 괄호화된 화살표 함수가 *있을 수도* 있습니다.
// 확률적으로 앞선 보기로 확인하고, 아니라면 롤백합니다.
function isParenthesizedArrowFunctionExpression(): Tristate {
if (
token() === SyntaxKind.OpenParenToken ||
token() === SyntaxKind.LessThanToken ||
token() === SyntaxKind.AsyncKeyword
) {
return lookAhead(isParenthesizedArrowFunctionExpressionWorker);
}
if (token() === SyntaxKind.EqualsGreaterThanToken) {
// 오류 복구 튜닝:
// 독립된 `=>`를 보았다면, 사용자가 의도한 바가 아마도 화살표 함수 표현식일 것이라고 판단하여 파싱합니다.
return Tristate.True;
}
// 분명히 괄호화된 화살표 함수가 아님.
return Tristate.False;
}요약하면, 타입스크립트 파서는 앞선 보기(빠른 경로)와 백트래킹을 조합하여 화살표 함수를 파싱합니다.