식 구문 분석하기
구문 분석 트리를 만들어 보세요.
식 구문 분석하기은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
토큰에서 트리로
구문 분석은 평평한 토큰 스트림을 구조화된 추상 구문 트리(AST)로 바꿉니다. 트리는 원시 토큰이 암시하기만 하는 우선순위와 그룹화를 표현합니다.
3 + 4 * 2의 경우 AST는 곱셈을 덧셈 아래에 중첩하므로 결과는 14가 아니라 11입니다.
AST Node 형태
각 Node는 숫자 잎이거나 두 자식을 가진 이항 연산입니다. 태그가 있는 구조체와 공용체를 사용하면 메모리를 компакт하게 유지할 수 있습니다.
연산자 문자는 실행 중에 +, -, *, /를 구분합니다.
typedef struct Node {
enum { N_NUM, N_BINOP } kind;
union {
int value; /* N_NUM */
struct { /* N_BINOP */
char op;
struct Node *left, *right;
} bin;
};
} Node;Node 할당하기
두 개의 작은 생성자가 힙에 Node를 할당합니다. 트리를 아래에서 위로 만들면 잎을 먼저 만든 다음 연산자 Node로 감쌉니다.
실제 인터프리터라면 나중에 해제할 수 있도록 이러한 할당을 추적해야 합니다.
#include <stdlib.h>
static Node *num(int v) {
Node *n = malloc(sizeof *n);
n->kind = N_NUM; n->value = v;
return n;
}
static Node *binop(char op, Node *l, Node *r) {
Node *n = malloc(sizeof *n);
n->kind = N_BINOP;
n->bin.op = op; n->bin.left = l; n->bin.right = r;
return n;
}문법
고전적인 우선순위 문법을 사용합니다. expr는 +와 -를 처리하고, term은 *와 /를 처리하며, factor는 숫자와 괄호를 처리합니다.
우선순위가 높은 규칙이 더 깊은 곳에 배치되므로 곱셈이 덧셈보다 자동으로 더 강하게 결합됩니다.
/* Grammar (EBNF):
expr = term { ('+' | '-') term } ;
term = factor { ('*' | '/') factor } ;
factor = NUMBER | '(' expr ')' ; */토큰 일치시키기
expect 도우미는 필요한 종류의 토큰을 소비하거나 중단합니다. 이는 구문 분석기와 어휘 분석기 사이의 계약입니다.
토큰화 학습에서 사용한 cur와 bump 미리 보기 도우미를 재사용합니다.
#include <stdio.h>
#include <stdlib.h>
static void expect(TokKind k) {
if (cur().kind != k) {
fprintf(stderr, "parse error: unexpected token\n");
exit(1);
}
bump();
}인수 구문 분석하기
인수는 문법의 원자입니다. 즉, 리터럴 숫자이거나 괄호로 묶인 하위 표현식입니다. 괄호는 parse_expr로 다시 재귀 호출됩니다.
이 재귀 때문에 재귀 하강 구문 분석기라는 이름이 붙었습니다.
static Node *parse_expr(void);
static Node *parse_factor(void) {
if (cur().kind == TOK_NUM) {
int v = cur().value; bump();
return num(v);
}
expect(TOK_LPAREN);
Node *e = parse_expr();
expect(TOK_RPAREN);
return e;
}항 구문 분석하기
항은 인수 하나를 구문 분석한 다음, * 또는 /를 발견하는 동안 반복하면서 각각을 왼쪽 결합 이항 연산 노드로 묶습니다.
왼쪽 결합이란 8 / 4 / 2가 (8 / 4) / 2 = 1로 구문 분석된다는 뜻입니다.
static Node *parse_term(void) {
Node *left = parse_factor();
while (cur().kind == TOK_STAR || cur().kind == TOK_SLASH) {
char op = (cur().kind == TOK_STAR) ? '*' : '/';
bump();
left = binop(op, left, parse_factor());
}
return left;
}표현식 구문 분석하기
최상위 규칙은 parse_term을 본떠 만들었지만 +와 -를 처리합니다. 각 계층은 다음으로 높은 우선순위의 규칙을 호출하므로 트리가 올바르게 중첩됩니다.
이 세 함수 구조가 구문 분석기의 핵심입니다.
static Node *parse_expr(void) {
Node *left = parse_term();
while (cur().kind == TOK_PLUS || cur().kind == TOK_MINUS) {
char op = (cur().kind == TOK_PLUS) ? '+' : '-';
bump();
left = binop(op, left, parse_term());
}
return left;
}트리 살펴보기
이 프로그램은 표현식을 구문 분석한 뒤 완전히 괄호로 묶인 형태로 다시 출력하여 우선순위가 어떻게 결정되었는지 보여 줍니다.
예쁘게 출력하는 함수는 구문 분석기가 만든 것과 동일한 노드 구조를 재귀적으로 순회합니다.
#include <stdio.h>
typedef struct Node {
int is_num; int value;
char op; struct Node *l, *r;
} Node;
static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }
static void show(Node *n){
if (n->is_num){ printf("%d", n->value); return; }
printf("("); show(n->l); printf(" %c ", n->op); show(n->r); printf(")");
}
int main(void){
/* 3 + 4 * 2 -> (3 + (4 * 2)) */
Node *ast = B('+', N(3), B('*', N(4), N(2)));
show(ast); printf("\n");
return 0;
}왼쪽 재귀 피하기
expr = expr '+' term과 같은 단순한 문법은 parse_expr가 영원히 자기 자신을 호출하게 만듭니다. 재귀 하강 방식은 직접적인 왼쪽 재귀를 처리할 수 없습니다.
규칙을 { '+' term }에 대한 while 반복문으로 다시 작성하면 무한 재귀를 완전히 피할 수 있습니다.
AST가 필요한 이유
AST는 구문과 실행을 분리합니다. 같은 트리를 다시 구문 분석하지 않고도 평가하거나 최적화하거나 바이트코드로 컴파일할 수 있습니다.
다음으로 이 트리를 순회하며 값을 계산합니다.
빠른 확인
문법의 각 계층이 우선순위를 어떻게 강제하는지 생각해 보세요.
복습
재귀 하강 구문 분석기를 작성했습니다. 여기에는 AST 노드 구조체와 생성자, 그리고 우선순위와 왼쪽 결합을 인코딩하는 expr/term/factor 함수가 포함됩니다.
이제 결과 트리를 평가할 준비가 되었습니다.
자주 묻는 질문
“식 구문 분석하기” 강의는 무료인가요?
네 — “식 구문 분석하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“식 구문 분석하기”에서 뭘 배우나요?
구문 분석 트리를 만들어 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“식 구문 분석하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.