소개

본 기사의 대상 독자는, 구문 분석에 흥미는 있지만 처음의 한 걸음이 좀처럼 밟을 수 없는 분입니다.
목표는 다른 기사를 읽을 때 문턱을 낮추는 것입니다.

또, 구문 분석은 컴파일러 작성이나 계산기 작성에 사용할 수 있는 기술입니다.
꼭 여기에서 조금 이해해 다른 기사로 완전 이해를 목표로 해 주세요!

※이 기사의 설명에 사용하는 프로그램 : htps : // 기주 b. 코 m / shiban g g / ぇ ts
※ 참고로 한 기사 : htps //w w. Shigbu s.んふぉ / 코 mpi r 보오 k

구문 분석

구문 분석이란 형식 문법에 따라 구문 트리를 생성하는 행위입니다.

예를 들어 다음 그림이 나타내는 동작이 그에 해당합니다.


위에서는 수식과 같은 문법을 이용하여 구문 분석을 실시하고 있습니다.

또한 구문 분석은 주로 두 가지 처리로 이루어져 있습니다.
하나는 어휘 분석이고 다른 하나는 구문 분석입니다.

어휘 분석

어휘 분석은 문자열에서 의미있는 단위 (토큰 *)의 배열로 변환하는 행위입니다.

예를 들어 다음 그림이 나타내는 동작이 그에 해당합니다.


우선 이것의 목적은 구문 분석을 실시할 때에 원시의 캐릭터 라인을 취급하는 것을 피하는 것입니다.
이렇게 하면 다음 처리인 구문 분석에서 구문의 정확성에만 주목할 수 있습니다.

아래가 프로그램 예입니다.

Token *tokenize(char *string) {
    Token *root = calloc(sizeof(Token), 1);
    root->kind = T_ROOT;

    Token *head = root;

    for(;; string++) {
        char value = string[0];

        if (value == '\0') {
            Token token = {.kind = T_END};
            head = new_token(token, head);

            return root;
        }

        if (is_space(value)) continue;
        if (is_num(value)) {
            Token token = {.value = value, .kind = T_NUM, .next_token = NULL};
            head = new_token(token, head);
        }

        if (is_operator(value)) {
            Token token = {.value = value, .kind = T_OPE, .next_token = NULL};
            head = new_token(token, head);
        }
    }
}

이 프로그램은 원시 문자열(string)을 한 문자씩 보고 해당 토큰으로 변환합니다.
연산자이면 "OPERATOR"를 숫자이면 "NUMBER", 토큰 종류로 저장합니다. 공백이면 읽습니다.

따라서, 어휘 해석을 실시하는 것으로, 구문 분석시에 공백을 신경쓸 필요가 없어집니다.
또 토큰의 종류 나누기도 행해지기 때문에, 그 토큰이 무엇인가를 용이하게 알 수 있습니다.

※new_token(Token* token, Token* parent)은, parent의 다음의 토큰으로서 token을 연결하는 함수를 상정하고 있습니다.

구문 분석

구문 분석은 어휘 분석에서 얻은 토큰 열을 구문을 따라 구문 트리로 변환하는 행위입니다.　

예를 들어 다음 그림이 나타내는 동작이 그에 해당합니다.


아래가 프로그램 예입니다.

Node *parse(Token *token ,Node* node) {
    if (!is_root_token(token)) exit(1);

    Node *result = expression(token->next_token);

    return result;
}

Node* number(Token *token) {
    Node *node = new_node(NUMBER, token->value, NULL, NULL);

    return node;
}

Node* expression(Token *token) {
    Node *node = number(token);
    token = token->next_token;

    while (1) {
        if (is_num_token(token)) exit(1);

        if (is_end_token(token)) return node;

        if (is_operator_token(token)) {
            char symbol = token->value;
            token = token->next_token;

            Node *right_number = number(token);
            node = new_node(OPERATOR, symbol, node, right_number);

            token = token->next_token;
            continue;
        }

        exit(1);
    }
}

이 프로그램은 다음을 수행합니다.
1. 토큰 열이 구문을 따르는지 확인
2. 토큰 유형과 해당 노드를 만듭니다.
3. 만든 노드를 연결한다

이 짧은 설명으로, 얼마나 긴 문자열이 입력 되더라도 구문이 정확하면 나무로 만들 수 있습니다.

*new_node(Kind kind, char value, Node *left, Node *right)는 절의 종류, 값으로서 kind, value를 받고 왼쪽의 요소로서 left 오른쪽의 요소로서 right를 받아, 그 절을 돌려주는 함수를 상정해 있습니다.

마지막으로

본 기사에서는 등장하지 않았습니다만, BNF나 재귀 함수라고 하는 것의 생각이나 사용법은 습득해 두면 좋다.
이름으로부터 조금 어려운 것처럼 생각할지도 모릅니다만, 양쪽 모두 쓰는 방법에 관련되는 것이므로 가벼운 기분으로 도전해 보세요.

또한 이 두 가지를 아는 것만으로 읽기 쉬워지는 기사도 늘어날 것입니다.