JavaScript로 S-표현식 파서 만들기

S-표현식은 Lisp 프로그래밍 언어 계열의 핵심 구성 요소입니다. 이 글에서는 간단한 S-표현식 파서를 단계별로 만드는 방법을 설명하며, 이는 Lisp 파서의 기초로 활용될 수 있습니다.

Lisp는 구현이 가장 간단한 언어 중 하나이며, 파서를 만드는 것이 첫 번째 단계입니다. 파서 생성기를 사용할 수도 있지만, 직접 작성하는 것이 더 간단합니다. 여기서는 JavaScript를 사용합니다.

S-표현식이란 무엇인가?

Lisp 언어에 익숙하지 않다면 S-표현식은 다음과 같이 보일 수 있습니다:

(+ (second (list "xxx" 10)) 20)

이는 괄호로 둘러싸인 원자(atom) 또는 리스트로 구성된 데이터 형식입니다. 리스트는 공백으로 구분됩니다.

S-표현식은 JSON과 유사하게 다양한 데이터 타입을 가질 수 있습니다:

  • 숫자
  • 문자열
  • 심볼(Symbol): 따옴표 없이 사용되며, 다른 언어의 변수명처럼 해석될 수 있습니다.

또한, 특별한 점(dot) 연산자를 사용하여 쌍(pair)을 만들 수도 있습니다.

(1 . b)

리스트는 점 쌍으로 표현될 수 있으며, 이는 연결 리스트 데이터 구조와 같습니다.

다음과 같은 리스트:

(1 2 3 4)

다음과 같이 표현할 수 있습니다:

(1 . (2 . (3 . (4 . nil))))

여기서 nil은 빈 리스트를 나타내는 특수한 심볼입니다. 이 형식을 사용하면 모든 이진 트리를 만들 수 있습니다. 하지만 단순화를 위해 파서에서는 이 점 표기법을 사용하지 않습니다.

S-표현식의 용도

Lisp 코드는 S-표현식으로 작성되지만, 데이터 교환 형식으로도 사용할 수 있습니다. 또한 WebAssembly의 텍스트 표현 형식의 일부이기도 합니다. 이는 파서의 단순성과 형식 정의의 필요성이 없기 때문일 수 있습니다. JSON 대신 서버와 브라우저 간의 통신에 사용할 수 있습니다.

JavaScript에서 S-표현식 파서 구현하기

토크나이저(Tokenizer)

토크나이저는 파서의 일부로, 텍스트를 파싱 가능한 토큰으로 분할합니다. 일반적으로 파서는 렉서(Lexer) 또는 토크나이저와 함께 토큰을 생성합니다. 이것이 파서 생성기(예: lex와 Yacc 또는 flex와 bison)의 작동 방식입니다.

가장 간단한 토큰화 방법은 다음과 같습니다:


'(foo bar (baz))'.split(/(\(|\)|\n|\s+|\S+)/);

이 정규식은 괄호, 줄 바꿈, 공백, 그리고 공백이 아닌 문자열을 구분합니다. 괄호는 정규식에서 특수 문자이므로 이스케이프 처리해야 합니다.

이 방법은 거의 작동하지만, 정규식 매치 사이에 빈 문자열이 생성되는 문제가 있습니다:


'(('.split(/(\(|\)|\n|\s+|\S+)/);
// 결과: [ '', '(', '', '(', '' ]

빈 문자열을 제거하기 위해 Array::filter를 사용할 수 있습니다:


'(('.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.length);
// 결과: ["(", "("]

공백도 제거할 수 있습니다:


'(   ('.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.trim().length);
// 결과: ["(", "("]

또 다른 문제는 마지막 토큰 baz))가 제대로 분리되지 않는 것입니다:


'(foo bar (baz))'.split(/(\(|\)|\n|\s+|\S+)/).filter(token => token.trim().length);
// 결과: ["(", "foo", "bar", "(", "baz))"]

\S+ 정규식이 탐욕적으로 동작하여 괄호를 포함하지 않는 모든 것을 매치하기 때문입니다. 이를 해결하기 위해 [^\s()]+를 사용할 수 있습니다. 이 정규식은 공백과 괄호를 제외한 모든 문자열을 매치합니다.


'(foo bar (baz))'.split(/(\(|\)|\n|\s+|[^\s()]+)/).filter(token => token.trim().length);
// 결과: ["(", "foo", "bar", "(", "baz", ")", ")"]

이제 출력이 올바릅니다. 이 토크나이저를 함수로 만들겠습니다:


const tokens_re = /(\(|\)|\n|\s+|[^\s()]+)/;
function tokenize(string) {
    string = string.trim();
    if (!string.length) {
        return [];
    }
    return string.split(tokens_re).filter(token => token.trim());
}

token.trim() 뒤에 length를 사용할 필요는 없습니다. 빈 문자열은 false로 평가되므로 필터링됩니다.

문자열 리터럴(따옴표로 둘러싸인 표현식)은 어떻게 처리할까요?


tokenize(`(define (square x)
            "Function calculate square of a number"
            (* x x))`);
/* 결과:
["(", "define", "(", "square", "x", ")", "\"Function", "calculate", "square",
 "of", "a", "number\"", "(", "*", "x", "x", ")", ")"]
*/

출력에서 볼 수 있듯이, 따옴표로 둘러싸인 문자열이 공백으로 분리되었습니다. 이를 수정해야 합니다.

문자열을 위한 정규식

문자열 리터럴을 토크나이저의 예외로 추가해야 합니다. 정규식의 OR 조건에서 첫 번째 항목으로 두는 것이 좋습니다.

문자열 리터럴을 처리하는 정규식은 다음과 같습니다:

/"[^"\\]*(?:\\[\S\s][^"\\]*)*"/

이 정규식은 문자열 내의 이스케이프된 따옴표도 처리합니다.

전체 정규식은 다음과 같습니다:


const tokens_re = /("[^"\\]*(?:\\[\S\s][^"\\]*)*"|\(|\)|\n|\s+|[^\s()]+)/;

Lisp 주석도 추가할 수 있지만, 이 글은 S-표현식 파서에 관한 것이므로 생략합니다. JSON도 주석을 지원하지 않습니다. Lisp 파서를 만들고 싶다면 주석 처리를 연습 삼아 추가해 보세요.

이제 토크나이저가 올바르게 작동합니다:


tokenize(`(define (square x)
            "Function calculate square of a number"
            (* x x))`);
/* 결과:
["(", "define", "(", "square", "x", ")",
 "\"Function calculate square of a number\"",
 "(", "*", "x", "x", ")", ")"]
*/

파서(Parser)

스택(LIFO - Last-In, First-Out) 데이터 구조를 사용하여 파서를 만듭니다. 파서의 작동 방식을 완전히 이해하려면 연결 리스트, 이진 트리, 스택과 같은 데이터 구조를 아는 것이 좋습니다.

파서의 첫 번째 버전입니다:


function parse(string) {
    const tokens = tokenize(string);
    const result = []; // 최종 결과 배열
    const stack = []; // 스택
    tokens.forEach(token => {
        if (token === '(') {
            stack.push([]); // 새 리스트를 스택에 푸시
        } else if (token === ')') {
            if (stack.length > 0) {
                const top = stack.pop(); // 현재 리스트를 스택에서 팝
                if (stack.length > 0) {
                    // 이전 리스트에 현재 리스트를 추가
                    stack[stack.length - 1].push(top);
                } else {
                    // 완전히 구성된 리스트를 결과에 추가
                    result.push(top);
                }
            } else {
                throw new Error('구문 오류 - 짝이 맞지 않는 우괄호');
            }
        } else {
            // 원자를 찾아 스택의 최상단 리스트에 추가
            if (stack.length > 0) {
                stack[stack.length - 1].push(token);
            } else {
                // 최상위 레벨의 원자 처리 (일반적이지 않음)
                 result.push(token);
            }
        }
    });
    if (stack.length > 0) {
        throw new Error('구문 오류 - 우괄호가 필요합니다');
    }
    return result;
}

이 함수는 배열 형식으로 표현된 구조를 반환합니다. 여러 S-표현식을 파싱해야 한다면 결과 배열에 더 많은 항목이 포함됩니다:


parse(`(1 2 3) (1 2 3)`)
// 결과: [["1", "2", "3"], ["1", "2", "3"]]

점 표기법은 처리하지 않지만, S-표현식은 다음과 같은 형태로 존재할 수 있습니다:

((foo . 10) (bar . 20))

파서가 제대로 작동하려면 리스트를 위한 특별한 구조가 필요하지 않습니다. 하지만 처음부터 해당 구조를 가지는 것이 좋습니다(Lisp 인터프리터의 기초로 활용할 수 있도록). 모든 이진 트리를 만들 수 있도록 Pair 클래스를 사용하겠습니다.


class Pair {
    constructor(head, tail) {
        this.head = head;
        this.tail = tail;
    }
}

class Nil {}
const nil = new Nil(); // 빈 리스트 또는 리스트의 끝을 나타내는 nil 객체

배열을 우리 구조로 변환하는 정적 메소드를 추가할 수 있습니다:


class Pair {
    constructor(head, tail) {
        this.head = head;
        this.tail = tail;
    }
    static fromArray(array) {
        if (array.length === 0) {
            return nil;
        }
        const [head, ...rest] = array;
        let processedHead = head;
        if (Array.isArray(head)) {
            processedHead = Pair.fromArray(head);
        }
        return new Pair(processedHead, Pair.fromArray(rest));
    }
}

이것을 파서에 추가하려면 마지막에 result.map(Pair.fromArray)를 추가하면 됩니다.

배열 전체를 변환하지 않는 이유는 이것이 S-표현식의 컨테이너이기 때문입니다. 배열의 각 요소는 리스트여야 하므로 Array::map을 사용합니다.

작동 방식을 살펴보겠습니다:


parse('(1 (1 2 3))')

출력은 다음과 같은 구조가 될 것입니다 (JSON.stringify로 출력했으며, nil 값은 포함되어 있습니다):

{
    "head": "1",
    "tail": {
        "head": {
            "head": "1",
            "tail": {
                "head": "2",
                "tail": {
                    "head": "3",
                    "tail": null // nil이 JSON으로 직렬화될 때 null이 됨
                }
            }
        },
        "tail": null
    }
}

마지막으로, 리스트를 문자열로 변환하기 위해 Pair 클래스에 toString 메소드를 추가합니다:


class Pair {
    constructor(head, tail) {
        this.head = head;
        this.tail = tail;
    }
    toString() {
        const arr = ['('];
        let current = this;
        while (current instanceof Pair) {
            let valueStr;
            if (typeof current.head === 'string') {
                 // 문자열은 따옴표로 감싸고 이스케이프 처리
                valueStr = JSON.stringify(current.head).replace(/\\n/g, '\n');
            } else if (current.head instanceof Nil) {
                valueStr = 'nil';
            } else if (current.head instanceof LSymbol) {
                 // LSymbol은 이름만 출력
                valueStr = current.head.toString();
            } else {
                 // 다른 객체 (예: 숫자, 중첩된 Pair)
                valueStr = current.head.toString();
            }
            arr.push(valueStr);

            if (!(current.tail instanceof Pair) && !(current.tail instanceof Nil)) {
                 // 점 표기법 처리 (선택 사항)
                arr.push(' . ');
                arr.push(current.tail.toString());
                break;
            }
            current = current.tail;
            if (!(current instanceof Nil)) {
                arr.push(' ');
            }
        }
        if (current instanceof Nil) {
             // 리스트의 끝
        } else {
             // 점 표기법이 아닌 경우, 마지막 요소를 추가하고 종료
             // 이 부분은 위 로직에서 처리되므로 사실상 불필로
        }
        arr.push(')');
        return arr.join('');
    }

    static fromArray(array) {
        if (array.length === 0) {
            return nil;
        }
        const [head, ...rest] = array;
        let processedHead = head;
        if (Array.isArray(head)) {
            processedHead = Pair.fromArray(head);
        } else if (typeof head === 'string' && head.startsWith('"') && head.endsWith('"')) {
             // 문자열 리터럴 처리 (파서에서 이미 처리되었지만, 안전하게)
            processedHead = JSON.parse(head.replace(/\\n/g, '\\\\n')); // 이스케이프된 줄바꿈 복원
        }
        return new Pair(processedHead, Pair.fromArray(rest));
    }
}

이제 작동 방식을 살펴봅니다:


parse("(1 (1 2 (3)))")[0].toString()
// 결과: "(1 (1 (1 2 (3)) nil) nil)" - Pair.fromArray 로직 개선 필요

Pair.fromArray와 toString 메소드의 구현을 개선해야 합니다.

원자(Atom) 파싱

다음 정규식을 사용하여 숫자를 파싱합니다:


const int_re = /^[-+]?[0-9]+([eE][-+]?[0-9]+)?$/;
const float_re = /^([-+]?((\.[0-9]+|[0-9]+\.[0-9]+)([eE][-+]?[0-9]+)?)|[0-9]+\.)$/;

function parseAtom(atom) {
    if (atom.match(int_re) || atom.match(float_re)) { // 숫자
        return parseFloat(atom);
    } else if (atom.match(/^".*"$/)) { // 문자열
       // JSON.parse는 이스케이프된 문자를 자동으로 처리합니다.
       // JavaScript에서 문자열 내의 줄바꿈은 \n으로 이스케이프되어야 합니다.
        return JSON.parse(atom);
    } else {
       // 숫자가 아니고 따옴표로 둘러싸이지 않았으면 심볼로 간주
       return new LSymbol(atom);
    }
}

LSymbol 클래스를 정의합니다:


class LSymbol {
    constructor(name) {
        this.name = name;
    }
    toString() {
        return this.name;
    }
}

이제 파서 함수를 업데이트합니다:


function parse(string) {
    const tokens = tokenize(string);
    const result = [];
    const stack = [];
    tokens.forEach(token => {
        if (token === '(') {
           stack.push([]);
        } else if (token === ')') {
           if (stack.length > 0) {
               const top = stack.pop();
               if (stack.length > 0) {
                  stack[stack.length - 1].push(top);
               } else {
                  result.push(top);
               }
           } else {
               throw new Error('구문 오류 - 짝이 맞지 않는 우괄호');
           }
        } else {
           if (stack.length > 0) {
               // 원자를 파싱하여 스택의 최상단 리스트에 추가
               stack[stack.length - 1].push(parseAtom(token));
           } else {
               // 최상위 레벨의 원자 처리
               result.push(parseAtom(token));
           }
        }
    });
    if (stack.length > 0) {
        throw new Error('구문 오류 - 우괄호가 필요합니다');
    }
    // 각 최상위 리스트를 Pair 구조로 변환
    return result.map(item => {
        if (Array.isArray(item)) {
            return Pair.fromArray(item);
        }
        return item; // 원자 자체인 경우 그대로 반환
    });
}

Pair.fromArray와 toString 메소드를 개선하여 숫자, 문자열, 심볼 및 중첩된 구조를 올바르게 처리하도록 합니다.


class Pair {
    constructor(head, tail) {
        this.head = head;
        this.tail = tail;
    }

    // Pair와 Nil을 포함한 모든 요소를 올바르게 문자열로 변환
    static stringifyValue(value) {
        if (value instanceof Pair) {
            return value.toString();
        } else if (value instanceof Nil) {
            return 'nil';
        } else if (typeof value === 'string') {
            // 문자열은 따옴표로 감싸고 내부의 줄바꿈은 \n으로 처리
            return JSON.stringify(value).replace(/\\n/g, '\n');
        } else {
            // 숫자, LSymbol 등
            return value.toString();
        }
    }

    toString() {
        const parts = [];
        let current = this;
        while (current instanceof Pair) {
            parts.push(Pair.stringifyValue(current.head));
            current = current.tail;
            if (!(current instanceof Pair) && !(current instanceof Nil)) {
                // 점 표기법 처리
                parts.push('.');
                parts.push(Pair.stringifyValue(current));
                break;
            }
            if (current instanceof Pair) {
                parts.push(' ');
            }
        }
        if (current instanceof Nil) {
            // 리스트 끝
        } else {
             // 점 표기법이 아닌 경우, nil이 아닐 때만 추가
             if (current !== this) parts.push(' '); // 이미 추가되지 않은 경우
        }
        return `(${parts.join(' ')})`;
    }

    static fromArray(array) {
        if (array.length === 0) {
            return nil;
        }
        const [head, ...rest] = array;
        let processedHead = head;
        if (Array.isArray(head)) {
            processedHead = Pair.fromArray(head);
        }
        // head가 이미 파싱된 원자(숫자, 문자열, LSymbol)일 경우 그대로 사용
        return new Pair(processedHead, Pair.fromArray(rest));
    }
}

// LSymbol 클래스는 그대로 유지
class LSymbol {
    constructor(name) {
        this.name = name;
    }
    toString() {
        return this.name;
    }
}

// Nil 클래스와 nil 객체는 그대로 유지
class Nil {}
const nil = new Nil();

// parseAtom 함수는 위에서 정의된 대로 사용
function parseAtom(atom) {
    const int_re = /^[-+]?[0-9]+([eE][-+]?[0-9]+)?$/;
    const float_re = /^([-+]?((\.[0-9]+|[0-9]+\.[0-9]+)([eE][-+]?[0-9]+)?)|[0-9]+\.)$/;

    if (atom.match(int_re) || atom.match(float_re)) {
        return parseFloat(atom);
    } else if (atom.match(/^".*"$/)) {
        // JSON.parse는 문자열 리터럴을 올바르게 처리
        return JSON.parse(atom);
    } else {
        return new LSymbol(atom);
    }
}

// tokenize 함수는 위에서 정의된 대로 사용
const tokens_re = /("[^"\\]*(?:\\[\S\s][^"\\]*)*"|\(|\)|\n|\s+|[^\s()]+)/;
function tokenize(string) {
    string = string.trim();
    if (!string.length) {
        return [];
    }
    return string.split(tokens_re).filter(token => token.trim());
}


// 최종 parse 함수
function parse(string) {
    const tokens = tokenize(string);
    const result = [];
    const stack = [];
    tokens.forEach(token => {
        if (token === '(') {
           stack.push([]);
        } else if (token === ')') {
           if (stack.length > 0) {
               const top = stack.pop();
               if (stack.length > 0) {
                  stack[stack.length - 1].push(top);
               } else {
                  result.push(top);
               }
           } else {
               throw new Error('구문 오류 - 짝이 맞지 않는 우괄호');
           }
        } else {
           if (stack.length > 0) {
               stack[stack.length - 1].push(parseAtom(token));
           } else {
               result.push(parseAtom(token));
           }
        }
    });
    if (stack.length > 0) {
        throw new Error('구문 오류 - 우괄호가 필요합니다');
    }
    return result.map(item => {
        if (Array.isArray(item)) {
            return Pair.fromArray(item);
        }
        return item;
    });
}

이제 완전한 파서가 완성되었습니다. true, false, null 등의 값을 처리하는 것은 독자에게 연습 문제로 남겨둡니다.

태그: JavaScript 파서 S-표현식 Lisp 컴파일러

7월 23일 20:09에 게시됨

인기 태그

©2026 괴물 클럽