프로그래밍 언어론 구문분석

어휘분석

int a1;
a1 = 3*6;
if a1>5 then...

위의 프로그램을 구성하는 문자는 i, n, t, a,1,=,*임을 알 수 있다. 그리고 어휘 분석을 통해 int, a1, =, *,if 등은 토큰으로 사용되었음을 알 수 있다.  구문 분석을 통해 첫 줄은 <선언문> : := <자료형> <변수>; 로 구성되고 두 번째 줄은 <대입문> : := <변수> = <수식> 구문으로 구성됨을 알 수 있다.

이때에 어휘 분석을 통해 얻어지는 결과를 토큰이라고 부른다 토큰에는 연산자(+,-,=), 구분자(, (콤마),;. [,])), 식별자, 예약어 등이 포함되며 위 프로그램에 사용된 토큰은 예약어 int, 식별자 a1, 구분자 ; , 연산자 *,= 등이 있다. 어휘 분석으로 나타나는 식별자는 변수나 함수 등 이름을 나타내는 토큰이다. 변수명 a1이나 함수명 printf 등도 모두 식별자다, 이러한 식별자는 사용자가 직접 만들어내는 것이라 연산자나 구분자처럼 직접정의 할 수 없는 것들도 있다.

• 연산자 +, - , *, /, =등
• 구분자 ,, ; , []등
• 식별자 : 변수나 함수등의 이름을 나타내는것이고 보통 문자나 숫자로 구성되고 첫글자는 문자로 시작한다. a1, printf등
• 예약어 : 프로그래밍 언어 자체에 정의되어있는 토큰 - for, if, int 등 사용자 재정의 불가

전통적인 식별자의 정의를 BNF로 표현하면 아래와 같다.

<identifier> : := <letter> | <identifier><letter> | <identifier><digit>
<letter> : := A|B|C|a|b....|z
<digit> : := 0|1|2|3|4|5|6|7|8|9

즉 identifier 식별자는 문자와 숫자로 구성되어 있으며 첫 글자는 문자여야 한다.

그리고 토큰의 한 종류인 예약어인 if, for, int 등은 실제로는 사용자 재정의가 불가능하다고 약속되어 있어 식별자로 사용할 수 없다.

파스트리

유도 : 구문규칙을 이용하여 주어진 프로그램을 만들어 내는 과정이며 유도가 가능하면 문법적 오류가 없는 유효한 프로그램이다. 예) 수식 1+2*3

 

수식의 구문규칙이 아래와 같을 때
<exp> : := <exp><exp>+<exp> | <exp>-<exp> | <exp>*<exp> | <exp>/<exp>| (<exp>) | <digit>
<digit> : := 1|2|3|4|5|6|7|8|9|0

1+2*3 수식을 유도하는 과정은 다음과 같다.

<exp>
→<exp>+<exp> →<exp>+<exp>*<exp>
→<exp>+<exp>*<digit> →<exp>+<exp>*3
→<exp>+<digit>*3  → <exp>+<digit>*3 → <exp>+2*3 
→<exp>+2*3  → <digit>+2*3 → 1+2*3 

수식을 의미하는 <exp> 단말기호들의 조합을 만들기 위해 연속적으로 구문규칙을 적용한 것이다. 먼저 +와*가 사용되니 <exp>+<exp>*<exp>까지 유도하고 <exp>는 <digit>이라는 규칙과 <digit>는 2라는 규칙을 이용하여 유도한다.

이러한 유도는 트리형태로 나타낼 수도 있다. 이를 파스 트리라고 한다.

※자식노드가 있으면 비단말 노드라고하고 자식이 없는 가장 밑에있는거는 단말기호이고 시작하는 비단말기호를 루드노드라고 한다. 완성된 단말노드를 왼쪽부터 나열하면 프로그램이됨

위의 파스트리를 생성하기 위해 유도에서 적용한 구문규칙을 부모 자식노드로 표현하면 된다.

루트노드인 <exp>에는 <exp>+<exp>라는 규칙을 적용해 세 자식 노드로 나누고 가장왼쪽에 있는 비단말 노드는 <digit> 노드는 자식노드로 1을 생성하는 것처럼 하면 된다.

• 루드 노드 : 시작 비단말 기호
• 단말 노드 왼쪽부터 오른쪽으로 차례로 나열하면 주어진 프로그램이 됨
• 이러한 파스트리가 존재하면 구문에 부합하는 표현이고 파스트리가 존재하지 않는(만들어지지 않는다면) 오류가 있는 것이다.

모호성

위의 파스트리를 생각해 보자  이러한 파스트리가 여러 개 존재한다면? 1+2*3을 이어서 생각해 보자 만약에 파스 트리만 완성하면 문제가 없을까? 

1+2*3에서 첫 번째 왼쪽부터 했다면 1+(2*3) 뒤에가 다시 세 갈래로 나뉘는 형식이다 이렇게 되면 2*3을 먼저 하고 1을 더하게 된다. 하지만 1+2*3에서 (1+2)*3 처음에 나뉘는 방식이 이렇게 해도 파스트리는 완성이 된다. 처음에 나뉠 때 <exp>+<exp>이 아니라 <exp>*<exp>로 나뉜다면 앞에 <exp>가 세 자식 노드를 만들 것이다. 그럼 값은 9가 된다.

위와 같은 경우를 위해 모호한 문법을 명확하게 변경해야 하고 일반적으로 새로운 비단말 기호와 새로운 규문규칙을 추가하여 명확하게 변경한다.

 

연산자 우선순위

<exp> : := <exp>+<exp> | <exp>-<exp> | <exp>*<exp> | <exp>/<exp>| (<exp>) | <digit>
<digit> : := 1|2|3|4|5|6|7|8|9|0
앞서 예시는 우선순위가 없었다. 모두 동등했었다 그렇기에 연산자 우선순위를 넣어준다면
<exp> : := <exp>+<exp> | <exp>-<exp>  | <term>
<term> : :=<exp>*<exp> | <exp>/<exp> | <factor>
<factor> : : = (<exp>) | <digit> 
를 하게되면연산자가 우선순위되어 표현될 수 있다.

실제 계산을 할때는 아래단계부터 계산이 되고 이렇게 우선순위를 둔다면 +,-가 가장 윗단계에있어 가장 늦게 계산이된다.

 

좌결합연산자

그리고 우선순위가 같은 연산자 사이에도 계산 순서는 필요하다. 이경우  <exp>+<exp>가 아니라 오른쪽에 있는 피연산자를 다음 높은 우선순위의 구문 규칙에서 정의하는 비단말기호로 변경한다.

<exp> : := <exp>+<term> | <exp>-<term>  | <term>
<term> : := <term>*<factor> | <term>/<factor> | <factor>
<factor> : : = (<exp>) | <digit> 

그럼 자식노드의 깊이가 길수록 먼저 한다는 뜻이 되는 건가...
5-3+2를 할 경우 5는 시작부터 보면
<exp>-<exp>-<exp>-<term>-<factor>-<digit>-5가 되고
<exp>-<exp>-<term>-<factor>-<digit>-3
<exp>-<term>-<factor>-<digit>-2가 된다 깊이가 깊을수록 빨리 한다는 건가?? 이건 헷갈리는군요 아!

아!  먼저그 이해해야할것은 좌결합을 해야하는이유를 보면 5-3+2 는 좌결합우선순위라면 4가 나와야하지만 3+2부터하면 값은 0이나오기때문에 모호한거군.
그래서 오른쪽을 그다음단계의 비단말 기호로 넣어주면 <exp> +<term>이 되어 오른쪽은 더이상 +나 -를 만들어 낼수없다. 그러므로 왼쪽로는 하나의 더 +나 -를 만들어줄수있어 실제로 계산할때는 가장 깊은트리 아래쪽부터?계산하니까 왼쪽부터 계산할수가 있다 5-3+2일경우에는 처음에 3+2부터만들어지고 3자리에서 5-2가 다시 트리가된다.

중첩된 if문의 else

if문은 여러 번 중첩할 수 있다. 이러한 중첩된 if문에서 else문의 개수가 if문의 개수보다 적은 경우 각 else문을 어느 조건에 수행해야 하는지 모호하다.

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

이경우 처음 if문과 그다음 if문에 대한 else가 가리키는 것은 애매모호하다. 

모호한 문법
<if문> : := if <논리식> then <문장> else <문장> | if 논리식 then <문장>
<문장> : : <if문> |...

모호성이 제거된 문법
<if문> : := if <논리식> then <문장 2> else <문장>| if <논리식> them <문장>
<if문 2> : := if<논리식> then <문장2> else <문장2>
<문장> : : <if문> |...
<문장2> : : <if문2> |...

위와 같이 문장 2를 중첩으로 if문을 사용할 때에 문장 2에 대한 정의에 넣어주게 되면 문장 else의 사용하는 if문이 어디인지 명확하게 나타낼 수가 있다.