프로그램 분석
문자가 모여 어휘를 분석하고, 어휘들이 구문에 맞추어 프로그램을 구성한다. 프로그램의 분석은 크게 "어휘 분석"과 "구문 분석"으로 구분된다.
어휘 분석
어휘 분석의 목적은 "프로그램에서 사용된 단어를 구별해 내는 것"이다. 어휘 분석을 통하여 얻어지는 결과를 "토큰(Token)"이라고 한다. 토큰은 문법적으로 더 이상 나누어질 수 없는 요소이며, 토큰에는 연산자, 구분자, 식별자, 예약어 등이 포함된다.
- 연산자(Operator): 연산을 수행하기 위해 사용되는 토큰으로, +, -, =, * 등이 있다.
- 구분자(Separator): 프로그래밍 요소를 구분하는 토큰으로, 세미콜론(;), 콤마(,) 등이 있다. 연산자를 제외한 대부분의 기호가 구분자이다.
- 식별자(Identifier): 프로그램에서 변수나 함수 등의 이름을 나타내는 토큰이다. 사용자가 만들어낼 수 있으며, 이때 식별자는 문자(대문자/소문자 알파벳)와 숫자(0~9)로 구성되며 첫 글자는 문자여야 한다.
- 예약어(Reserved Word): 프로그래밍 언어 자체에 정의되어 포함된 토큰이다. 사용자 재정의가 불가능하다. 대표적인 예약어의 예시로는 조건문 "if", 반복문 "for", 정수형 "int" 등이 있다.
구문 분석
어휘 분석 이후 진행되는 구문 분석을 위해서는 "구문 규칙"과 프로그램 사이의 "연결고리"가 필요하다. "유도(Derivation)"는 구문 규칙을 이용하여 주어진 프로그램을 만들어 내는 과정이다. 유도가 가능하면 주어진 프로그램은 오류가 없는 유효한 프로그램이다.
한 가지의 예시를 가지고 "유도" 과정을 진행해보도록 하겠다.
<exp> ::= <exp>+<exp> | <exp>-<exp> | <exp>*<exp> | <exp>/<exp> | (<exp>) | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
위의 수식 구문 규칙이 주어질 경우, 이를 통해 $1+5 \times 2$를 유도하는 과정은 다음과 같다.
<exp>
-> <exp>+<exp>
-> <exp>+<exp>*<exp>
-> <exp>+<exp>*<digit>
-> <exp>+<exp>*2
-> <exp>+<digit>*2
-> <exp>+5*2
-> <digit>+5*2
-> 1+5*2
파스 트리 (Parse Tree)
유도 과정은 트리 형태로도 나타낼 수 있다, 이를 파스 트리(Parse Tree)라고 하며, 유도 트리, 구문 트리라고도 불린다. 파스 트리의 루트 노드(Root Node)는 시작 비단말 기호가 되고, 단말 노드(Leaf Node)는 단말 기호가 되어, 왼쪽부터 오른쪽으로 차례로 나열하면 주어진 프로그램이 된다.
표현에 대한 파스 트리가 존재할 경우, 유도가 가능하기에 주어진 표현은 구문에 부합하는 표현이 된다. 반면, 주어진 표현에 대한 파스 트리가 존재하지 않는다면 유도가 불가능하며 이는 오류가 있는 구문임을 알 수 있다.
모호성
동일한 표현에 대해 서로 다른 파스 트리가 만들어지는 경우가 있다. 이를 "모호한 문법"이라고 한다. 모호한 문법의 문제점은 "한 개의 프로그램이 서로 다른 결과를 도출할 수 있다는 것"이다. 이러한 모호성을 제거하기 위하여 문법의 명확화가 필요하며 프로그램이 의도하지 않은 경우로 동작하지 않도록 모호한 문법을 명확하게 변경해야 한다. 새로운 비단말 기호와 새로운 구문 규칙을 통해 모호한 문법을 명확하게 변경할 수 있다.
- 연산자 우선순위: 실제 수식에 연산자 우선순위가 존재하듯, 프로그램에서도 연산자 우선순위를 고려하여 프로그램을 동작하도록 한다.
- 좌결합 연산자: 우선순위가 동일한 연산자 사이에서도 계산 순서를 부여한다. 동일한 우선순위를 가지는 연산자가 여럿 있다면 왼쪽부터 계산하도록 한다. (좌결합)
- 중첩된 if문의 else: else문 앞에 나온 if문들 중 다른 else문과 짝이 되지 않은 가장 가까운 if문과 짝이 되도록 정한다.
