일진법 수식 덧셈 계산기

일진법(The unary numeral system)은 자연수를 나타내는 가장 단순한 수 체계이다. 자연수 N을 나타내기 위해 숫자 기호 1을 N번 반복하며, 위치에 따른 자릿값의 차이는 존재하지 않는다.

일진법에서는 수 0(영)은 빈 문자열, 즉 아무 기호도 없는 상태로 나타내어진다. 수 1, 2, 3, 4, 5, 6, ...은 일진법으로 각각
1₍₁₎,
11₍₁₎,
111₍₁₎,
1111₍₁₎,
11111₍₁₎,
111111₍₁₎,
...
으로 나타낼 수 있다.

일진법에서의 덧셈은 두 피연산자를 단순히 이어붙이는 것과 동치이다. 예를 들어 1₍₁₎ + 11₍₁₎ = 111₍₁₎ 이다. 따라서 계산 자체만을 고려한다면 문자열 결합만으로도 충분히 구현할 수 있다.

하지만 해당 프로그램에서는 이러한 단순한 연산을 직접 문자열로 처리하지 않는다. 입력된 표현식을 먼저 어휘 분석(Lexical Analysis)하여 토큰(Token)으로 분해하고, 이후 구문 분석(Parsing)을 통해 표현식의 구조를 분석하여 추상 구문 트리(Abstract Syntax Tree, AST)를 생성한다.

생성된 AST는 평가 단계(Evaluation)를 통해 순회하며, 각 노드에 정의된 연산 규칙에 따라 최종적인 일진법 값을 계산한다. 즉, 111 + 11 + 1과 같은 입력은 단순한 문자열 연결이 아니라, 하나의 표현식으로서 Lexing -> Parsing + AST Construction -> Evaluation의 과정을 거쳐 처리된다.

이는 일진법 덧셈이라는 문제를 해결하기 위해 명백히 과도한 구조일 수 있다. 그러나 단순한 연산을 대상으로 하더라도 일반적인 언어 처리 과정의 구조를 적용함으로써, 입력의 문법을 정의하고 표현식의 계층 구조를 명시적으로 표현하며, 이후 새로운 연산자나 문법을 확장할 수 있는 기반을 마련하였다.

아래는 일진법 덧셈 연산을 위한 EBNF이다.

whitespace_char
    = " " | "\n" | "\t" | "\r" | "\f" | "\b" ;

S
    = { whitespace_char } ;

W
    = whitespace_char , { whitespace_char } ;

digit
    = "1" ;

unary_num
    = digit , { digit } ;

addition_operator
    = "+" ;

left_parenthesis
    = "(" ;

right_parenthesis
    = ")" ;

primary_expr
    = unary_num
    | left_parenthesis
    , S
    , expr
    , S
    , right_parenthesis
    ;

addition_expr
    = primary_expr
    , S
    , addition_operator
    , S
    , expr
    ;

expr
    = addition_expr
    | primary_expr
    ;

program
    = S
    , expr
    , S
    ;