어휘 분석
- 프로그램 분석: 문자 → (어휘 분석) → 어휘 → (구문 분석) → 구문
- 어휘 분석
- 어휘 분석의 목적: 프로그램에 사용되는 단어를 구별해 냄
- 토큰: 어휘 분석을 통해 얻어지는 결과
- 토큰과 렉심
- 렉심(lexeme): 프로그램에 사용되는 단어
- 토큰: 렉심의 집합
- 예약어나 연산자 등 토큰과 렉심이 같은 경우가 많으므로 통상 렉심을 토큰이라고 부르기도 함
- 식별자: 변수명, 함수명 등 이름을 나타내는 토큰
- 예약어
- 프로그래밍 언어 자체에 정의되어 포함된 토큰
- 식별자와 구문 구조는 같지만 식별자로 쓸 수 없음(사용자 재정의 불가)
파스 트리
- 유도(derivation)
- 구문 규칙을 이용하여 주어진 프로그램을 만들어 내는 과정
- 유도가 가능하면 문법적 오류가 없는 유효한 프로그램임
- 파스 트리(parse tree)
- 유도를 트리 형태로 나타낸 것
- 구문 트리: 혹은 유도 트리라고 부르기도 함
- 루트 노드: 시작 비단말 기호
- 단말 노드: 왼쪽부터 오른쪽으로 차례로 나열하면 주어진 프로그램이 됨
- 주어진 표현에 대한 파스 트리가 존재하면 구문에 부합하는 표현임
- 주어진 표현에 대한 파스 트리가 존재하지 않으면 오류 있는 표현임
모호성
- 파스 트리의 모호성
- 주어진 표현에 대한 파스 트리가 존재하면 구문에 부합하는 표현임
- 만약 주어진 표현에 대한 파스 트리가 여러 개 존재한다면
- 구문론 관점: 파스 트리가 존재하므로 구문에는 부합
- 의미론 관점: 주어진 표현이 서로 다른 의미로 해석될 수 있음
- 모호한 문법
- 동일한 표현에 대해 서로 다른 파스 트리가 만들어지는 문법
- 모호한 문법의 문제점
- 하나의 프로그램이 서로 다른 결과를 도출
- 프로그래머의 의도와는 다르게 해석되어 잘못된 결과를 도출
- 모호성 제거
- 문법의 명확화
- 의도하지 않은 의미로 해석되지 않도록 모호한 문법을 명확하게 변경
- 모호성 제거를 위해 새로운 비단말 기호와 새로운 구문 규칙을 추가
- 대표적인 예: 연산자 우선순위, 좌결합 연산자, 중첩된 if문의 else
연산자 우선순위
- 덧셈과 뺄샘 < 곱셈과 나눗셈 < 괄호
- 구문 규칙을 3개로 구분하고, 우선순위가 낮는 덧셈과 뺄셈 연산자부터 <exp>의 구문 규칙에 표현
// 모호한 문법
<exp> ::= <exp>+<exp> | <exp>-<exp>
| <exp>*<exp> | <exp>/<exp>
| (<exp>) | <digit>
<digit> ::= 0 | 1 | 2 | ... | 8 | 9
// 모호성이 제거된 문법
<exp> ::= <exp>+<exp> | <exp>-<exp> | <term>
<term> ::= <term>*<term> | <term>/<term> | <factor>
<factor> ::= (<exp>) | <digit>
<digit> ::= 0 | 1 | 2 | ... | 8 | 9
좌결합 연산자
- 우선순위가 동일한 연산자 사이의 계산 순서는 왼쪽이 우선
- 오른쪽 피연산자를 다음 높은 우선순위의 구문 규칙에서 정의하는 비단말 기호로 변경
// 모호한 문법
<exp> ::= <exp>+<exp> | <exp>-<exp> | <term>
<term> ::= <term>*<term> | <term>/<term> | <factor>
// 모호성이 제거된 문법
<exp> ::= <exp>+<exp> | <exp>-<exp> | <term>
<term> ::= <term>*<factor> | <term>/<factor> | <factor>
중첩된 if문의 else
- 중첩된 if문에서 else문의 개수가 if문의 개수보다 적은 경우 각 else문을 어느 조건이 거짓일 때 수행해야 하는지 모호
- 다른 else문과 짝이 되지 않은 가장 가까운 if문과 짝이 되도록 정함
- 구문 규칙에서 else문 앞의 <문장>에는 if문과 else문이 짝인 경우만 가능하도록 변경
// 모호한 문법
<if문> ::= if <논리식> then <문장> else <문장>
| if <논리식> then <문장>
<문장> ::= <if문> | ...
// 모호성이 제거된 문법
<if문> ::= if <논리식> then <문장2> else <문장>
| if <논리식> then <문장>
<if문2> ::= if <논리식> then <문장2> else <문장2>
<문장> ::= <if문> | ...
<문장2> ::= <if문2> | ...