기본 콘텐츠로 건너뛰기

방송대 방통대 프로그래밍언어론 5강 - 어휘 분석, 파스 트리와 모호성 - 요약 노트 시험족보 예상문제 - 올에이클래스

0-썸네일-요약노트-프로그래밍언어론-5강

프로그래밍언어론 5강 - 어휘 분석, 파스 트리와 모호성

프로그램의 문자들이 토큰으로 묶이고, 토큰의 나열이 문법에 맞는 구조인지 판정되는 과정을 학습한다. 유도와 파스 트리를 바탕으로 문법의 모호성을 이해하고, 연산자 우선순위·결합 방향·짝 잃은 else 문제를 통해 모호성을 제거하는 방법을 살펴본다.

제1장 프로그램 분석과 어휘 분석

1. 문자에서 어휘와 구문으로

프로그램은 겉으로 보면 문자들의 연속이다. 예를 들어 int x12;, x12 = 1 + 5 * 2;에는 영문자, 숫자, 세미콜론, 등호, 덧셈 기호와 곱셈 기호가 등장한다. 분석기는 이 문자들을 곧바로 문장 구조로 해석하지 않는다. 먼저 서로 관련된 문자를 하나의 단어 단위로 묶는 어휘 분석을 수행한 뒤, 그 단위들이 문법에 맞게 배치되었는지 확인하는 구문 분석을 수행한다.

단계입력과 결과핵심 질문
어휘 분석문자의 연속을 토큰의 연속으로 변환어떤 문자들이 한 단어를 이루는가?
구문 분석토큰의 연속을 문법 규칙에 맞는 구조로 분석토큰들이 올바른 문장을 이루는가?

예컨대 문자 i, n, t, x, 1, 2, ;는 어휘 분석을 거치면 int, x12, ;라는 단위로 구별된다. 이어 구문 분석기는 이를 <선언문> ::= <자료형> <변수> ‘;’ 같은 규칙과 대조한다. 즉, 어휘 분석은 단어를 찾고 구문 분석은 그 단어들이 이루는 구조를 찾는다.

2. 렉심과 토큰

렉심(lexeme)은 실제 프로그램에 나타난 단어이고, 토큰(token)은 같은 문법적 역할을 하는 렉심들의 집합이다. count, x12, total은 서로 다른 렉심이지만 모두 식별자 토큰으로 분류될 수 있다. 어휘 분석의 결과로 얻는 대표 토큰에는 연산자, 구분자, 식별자, 예약어, 리터럴 등이 있다.

시험 핵심: 렉심은 소스 코드에 실제로 쓰인 개별 단어이고, 토큰은 렉심을 문법적 종류에 따라 분류한 범주이다.

3. 식별자와 예약어

식별자는 변수나 함수 등의 이름을 나타내는 토큰이다. 강의에서 다루는 전통적인 식별자는 문자와 숫자로 구성되며 첫 글자는 문자이다. 따라서 x12는 식별자가 될 수 있지만 12x는 이 규칙에 맞지 않는다. 다음 규칙은 식별자가 문자 하나에서 시작해 뒤에 문자 또는 숫자가 반복해서 붙을 수 있음을 나타낸다.

<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

재귀적으로 등장하는 <identifier>가 이미 만들어진 식별자 뒤에 문자나 숫자를 더 붙이는 역할을 한다.

예약어if, for, int처럼 프로그래밍 언어 자체에 정의되어 포함된 토큰이다. 형태만 보면 식별자와 같은 문자 나열이지만, 정해진 언어 기능을 표시하므로 사용자가 변수나 함수 이름으로 재정의할 수 없다. C 언어의 어휘 분석기는 식별자처럼 보이는 렉심을 만났을 때 예약어인지 먼저 검사하고, 예약어이면 해당 예약어 토큰을 반환한다.

구분식별자예약어
역할변수·함수 등 사용자가 이름 붙인 대상을 나타냄언어가 미리 정한 문법적 기능을 나타냄
x12, totalif, for, int
재정의명명 규칙 안에서 사용자가 정함사용자가 재정의할 수 없음

제2장 유도와 파스 트리

1. 유도의 의미

유도(derivation)는 구문 규칙을 차례로 적용하여 시작 비단말 기호에서 주어진 프로그램을 만들어 내는 과정이다. 어떤 문자열을 문법으로 유도할 수 있다면 그 문자열은 문법에 부합하는 유효한 표현이다. 반대로 끝까지 유도할 수 없다면 구문 오류가 있는 표현이다.

강의의 수식 문법은 <exp>를 덧셈, 뺄셈, 곱셈, 나눗셈, 괄호로 묶인 수식 또는 숫자로 바꿀 수 있게 한다. 수식 1+5*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

중간 단계에는 아직 다른 기호로 바뀔 수 있는 비단말 기호가 남아 있지만, 마지막에는 실제 프로그램을 구성하는 단말 기호만 남는다. 이처럼 유도는 문법 규칙이 실제 문자열을 만들어 내는 과정을 순서대로 보여 준다.

2. 파스 트리의 구조와 판정

파스 트리(parse tree)는 유도를 트리 형태로 나타낸 것이다. 루트 노드는 유도의 출발점인 시작 비단말 기호이고, 내부 노드는 적용된 문법 구조를 보여 주며, 단말 노드는 더 이상 문법 규칙으로 바꾸지 않는 단말 기호이다. 단말 노드를 왼쪽에서 오른쪽으로 나열하면 분석 대상 프로그램이 된다.

구성 요소의미
루트 노드문법의 시작 비단말 기호
내부 노드와 가지어떤 구문 규칙이 적용되어 하위 구조가 만들어졌는지 표현
단말 노드실제 프로그램을 이루는 단말 기호

1+5*2에는 모든 단말 기호를 빠짐없이 포함하는 파스 트리가 존재하므로 주어진 문법에 부합한다. 그러나 1+5*는 마지막 곱셈 기호 뒤에 피연산자가 없다. 유도 중 남은 <exp>를 없애면서 동시에 입력과 일치하게 만들 수 없으므로 완전한 파스 트리를 구성할 수 없고, 구문 오류로 판정된다.

판정 기준: 대상 표현 전체를 단말 노드의 왼쪽부터 오른쪽 순서로 얻는 파스 트리가 존재하면 문법에 부합한다. 파스 트리가 존재하지 않으면 오류가 있는 표현이다.

제3장 모호한 문법과 그 위험

1. 파스 트리가 여러 개일 때

모호한 문법은 동일한 표현에 대해 서로 다른 파스 트리가 만들어지는 문법이다. 파스 트리가 하나 이상 존재하므로 구문론 관점에서는 문법에 부합한다. 하지만 여러 트리가 서로 다른 연산 구조를 나타내면 의미론 관점에서는 하나의 표현이 여러 의미로 해석될 수 있다.

예를 들어 모든 이항 연산자를 같은 수준에서 정의한 문법으로 1+5*2를 분석하면 1+(5*2) 구조와 (1+5)*2 구조를 모두 만들 수 있다. 전자는 11, 후자는 12이므로 파스 트리 선택에 따라 결과가 달라진다. 이는 프로그래머의 의도와 다른 실행 결과를 만들 위험을 내포한다.

구문에 맞는다는 사실만으로 의미가 하나로 결정되는 것은 아니다. 파스 트리의 존재 여부는 구문 적합성을 말해 주지만, 유일한 의미를 보장하려면 파스 트리도 의도한 구조로 하나만 결정되어야 한다.

2. 모호성 제거의 기본 원리

모호성을 제거하려면 의도하지 않은 구조가 생성되지 않도록 문법을 명확하게 바꾸어야 한다. 대표적으로 새로운 비단말 기호와 구문 규칙을 추가하여 연산자 우선순위를 계층화하고, 같은 우선순위 연산자에는 결합 방향을 강제하며, 중첩 조건문에서는 else가 결합될 if를 명확히 한다.

모호성 상황제거 방법의도한 해석
서로 다른 우선순위의 연산자exp·term·factor로 계층화괄호, 곱셈·나눗셈, 덧셈·뺄셈 순으로 결합
같은 우선순위 연산자의 연속문법으로 결합 방향 강제좌결합 연산자는 왼쪽 연산부터 결합
if보다 else가 적은 중첩문짝이 맞은 문장과 아닌 문장을 구분else를 가장 가까운 짝 없는 if와 결합

제4장 연산자 문법의 모호성 제거

1. 우선순위 계층화

강의에서 연산자 우선순위는 +-가 가장 낮고, */가 그보다 높으며, 괄호가 가장 높다. 이 차이를 문법에 반영하려면 수식을 한 비단말 기호로만 정의하지 않고 <exp>, <term>, <factor>의 계층으로 나눈다.

<exp> ::= <exp> + <exp> | <exp> - <exp> | <term>

<term> ::= <term> * <term> | <term> / <term> | <factor>

<factor> ::= ( <exp> ) | <digit>

<factor>는 괄호나 숫자처럼 가장 단단히 묶이는 요소를 나타내고, <term>은 factor들을 곱셈과 나눗셈으로 묶으며, <exp>는 term들을 덧셈과 뺄셈으로 묶는다. 따라서 1+5*2에서 5*2가 하나의 term으로 먼저 구성되고 그 뒤에 1과 더해진다. 우선순위가 다른 연산자 때문에 생기는 두 해석 중 1+(5*2)만 남는다.

2. 결합 방향 강제

우선순위만 계층화해도 같은 수준의 연산자가 연속되면 모호성이 남을 수 있다. 5-3+2(5-3)+2로 계산하면 4지만, 5-(3+2)로 계산하면 0이다. 좌결합 연산자는 우선순위가 같은 연산자가 피연산자 사이에 연속될 때 왼쪽 연산자를 먼저 고려한다.

<exp> ::= <exp> + <term> | <exp> - <term> | <term>

<term> ::= <term> * <factor> | <term> / <factor> | <factor>

<factor> ::= ( <exp> ) | <digit>

왼쪽 재귀 형태의 <exp>는 이미 만들어진 왼쪽 수식에 새로운 term을 붙인다. 그 결과 5-3+2(5-3)+2로 묶이며 값은 4가 된다. 우선순위 계층화가 서로 다른 수준의 연산자를 구분한다면, 결합 방향 강제는 같은 수준 연산자의 묶이는 순서를 결정한다.

구분: 우선순위는 종류가 다른 연산자 중 무엇을 먼저 묶을지 정하고, 결합 방향은 우선순위가 같은 연산자가 이어질 때 어느 쪽부터 묶을지 정한다.

제5장 짝 잃은 else 문제

1. 중첩 if에서 생기는 모호성

짝 잃은 else 문제(dangling else problem)는 중첩된 if문에서 else문의 수가 if문의 수보다 적을 때 각 else가 어느 if의 조건이 거짓일 경우에 수행되는지 모호해지는 문제이다. 다음 문장에는 if가 둘이고 else가 하나뿐이다.

if x>1 then if x<5 then y=1 else y=2

이 문장은 else를 안쪽의 if x<5와 결합하는 파스 트리와 바깥쪽의 if x>1과 결합하는 파스 트리를 모두 가질 수 있다. 두 구조는 조건이 거짓일 때 y=2를 실행하는 상황이 다르므로 의미도 달라진다.

2. 가장 가까운 짝 없는 if와 결합

강의의 해결 원칙은 각 else를 그 앞에 나온 if들 가운데 아직 다른 else와 짝이 되지 않은 가장 가까운 if와 결합하는 것이다. 이를 문법으로 강제하기 위해 else까지 갖춘 완전한 if문과 else가 없을 수도 있는 if문을 서로 다른 비단말 기호로 구분한다.

<if문> ::= if <논리식> then <문장2> else <문장> | if <논리식> then <문장>

<if문2> ::= if <논리식> then <문장2> else <문장2>

<문장> ::= <if문> | <문장2> | ...

<문장2> ::= <if문2> | <대입문> | ...

여기서 <if문2>는 then과 else가 모두 갖추어진 문장을 나타낸다. 이 구분 때문에 바깥 if가 else를 차지하려면 그 then 부분이 이미 짝이 완성된 문장이어야 한다. 앞의 예에서는 안쪽 if가 아직 짝을 기다리고 있으므로 else는 안쪽 if와 결합하는 구조만 허용된다.

시험 핵심: 짝 잃은 else는 앞에 있는 if 중 다른 else와 아직 짝이 되지 않은 가장 가까운 if와 결합한다.

핵심 개념 정리

프로그램 분석은 크게 어휘 분석과 구문 분석으로 나뉜다. 어휘 분석은 문자의 연속에서 연산자, 구분자, 식별자, 예약어, 리터럴 등의 토큰을 구별한다. 렉심은 프로그램에 실제로 쓰인 단어이고 토큰은 같은 문법적 역할을 하는 렉심의 집합이다. 식별자는 변수나 함수의 이름이며, 예약어는 언어가 미리 정해 사용자 재정의가 허용되지 않는 토큰이다.

유도는 구문 규칙으로 주어진 표현을 만들어 내는 과정이고, 파스 트리는 유도를 트리로 표현한 것이다. 루트는 시작 비단말 기호이고 단말 노드를 왼쪽부터 오른쪽으로 읽으면 대상 프로그램이 된다. 완전한 파스 트리가 없으면 구문 오류이며, 하나의 표현에 서로 다른 파스 트리가 여러 개 존재하면 그 문법은 모호하다.

모호성은 같은 프로그램이 서로 다른 의미나 결과를 갖게 할 위험이 있다. 연산자 우선순위는 exp·term·factor 같은 비단말 기호로 계층화하고, 같은 우선순위 연산자의 결합 방향은 재귀 구조로 강제한다. 중첩 if의 else는 가장 가까운 짝 없는 if와 결합하도록 완전한 if문과 불완전할 수 있는 if문을 구분한다.

최종 정리: 어휘 분석은 “어떤 단어인가”를, 구문 분석은 “어떤 구조인가”를 밝힌다. 파스 트리는 구문 적합성과 해석 구조를 드러내며, 문법 설계자는 우선순위·결합 방향·else의 결합 대상을 문법에 명시해 하나의 표현이 의도한 하나의 구조로 분석되도록 해야 한다.

예상문제 20선

1. 어휘 분석의 주된 목적은 무엇인가?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
어휘 분석은 문자들의 연속에서 렉심을 찾고 이를 토큰으로 분류하는 단계이다.

2. 렉심과 토큰의 관계를 옳게 설명한 것은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
x12는 실제 렉심이며, 식별자는 이와 같은 렉심들을 묶는 토큰 범주이다.

3. 강의의 전통적인 식별자 규칙에 맞는 것은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
전통적인 식별자는 문자로 시작하고 그 뒤에 문자 또는 숫자가 올 수 있다.

4. 예약어에 대한 설명으로 옳은 것은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
if, for, int 등은 언어가 미리 정의한 예약어이므로 사용자가 식별자로 재정의할 수 없다.

5. 유도(derivation)의 의미로 가장 적절한 것은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
유도는 시작 비단말 기호에 구문 규칙을 적용해 대상 문자열을 생성하는 과정이다.

6. 파스 트리의 단말 노드를 왼쪽부터 오른쪽으로 나열하면 무엇을 얻는가?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
파스 트리의 단말 노드는 실제 표현을 구성하며, 왼쪽부터 읽으면 원래 프로그램이 된다.

7. 주어진 표현에 대한 완전한 파스 트리가 존재하지 않을 때의 판정은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
표현 전체를 생성하는 파스 트리가 없다는 것은 해당 문법으로 그 표현을 유도할 수 없다는 뜻이다.

8. 수식 1+5*가 강의의 수식 문법에 맞지 않는 직접적인 이유는?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
곱셈 연산의 오른쪽 수식이 비어 있어 남은 비단말 기호를 입력과 일치하는 단말 기호로 바꿀 수 없다.

9. 모호한 문법의 정의는 무엇인가?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
하나의 표현을 두 가지 이상의 구조로 분석할 수 있으면 문법은 모호하다.

10. 모호한 문법으로 1+5*2를 분석할 때 가능한 두 결과는?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
1+(5*2)는 11이고 (1+5)*2는 12이므로 파스 트리에 따라 결과가 달라진다.

11. 모호한 문법이 내포하는 가장 중요한 위험은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
서로 다른 파스 트리는 서로 다른 의미를 나타낼 수 있어 프로그래머의 의도와 다른 결과를 만들 수 있다.

12. 우선순위 계층화 문법에서 <factor>가 나타내는 것은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
factor는 괄호 수식 또는 숫자를 나타내며, term과 exp의 기초가 되는 가장 강하게 결합된 요소이다.

13. 강의에서 제시한 연산자 우선순위가 낮은 것부터 높은 것까지 올바른 순서는?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
강의에서는 +·-가 가장 낮고 *·/가 중간이며 괄호가 가장 높은 우선순위를 갖는다.

14. 우선순위 계층화가 직접 해결하는 모호성은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
exp, term, factor를 나누면 곱셈·나눗셈이 덧셈·뺄셈보다 먼저 묶이도록 구조가 제한된다.

15. 좌결합 연산자의 설명으로 옳은 것은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
좌결합은 동일한 우선순위의 연산자가 이어질 때 왼쪽의 연산부터 묶도록 한다.

16. 좌결합 규칙에 따라 5-3+2를 묶고 계산한 결과는?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
좌결합이면 (5-3)+2로 묶이므로 결과는 4이다.

17. 우선순위와 결합 방향을 비교한 설명으로 옳은 것은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
우선순위 계층화와 결합 방향 강제는 해결하는 모호성의 종류가 서로 다르다.

18. 짝 잃은 else 문제가 발생하는 상황은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
하나의 else가 안쪽 if와 바깥쪽 if 중 어디에 속하는지 두 구조가 가능할 때 모호성이 생긴다.

19. 강의에서 제시한 else 결합 원칙은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
else는 다른 else와 짝이 되지 않은 가장 가까운 if와 짝을 이루도록 정한다.

20. 짝 잃은 else의 모호성을 문법으로 제거하는 핵심 방법은?

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
짝이 완성된 문장과 미완성일 수 있는 문장을 구분하면 else가 의도한 가장 가까운 if와만 결합하도록 문법 구조를 제한할 수 있다.

댓글