조건부 구조 표현식과 상태 전이 다이어그램 FSM

지금까지 C나 java를 통해 간단하게 조건문을 사용했었다.

그렇다면 컴파일러는 조건부 구조를 어떻게 기계어로 변환하는지 알아보자.

 

 

 

 

블록 구조의 IF 문

high level language에서 조건문은 아래와 같이 표현한다.

if( op1 == op2 )
 X = 1;
 else
 X = 2;

 

 

이런 간단한 논리적 구조를 어셈블리언어로 변환하면 다음과 같다.

mov eax,op1
cmp eax,op2
jne L1
mov X,1
jmp L2
 L1:mov X,2
 L2:

사실상 JE 명령어로 == 연산자를 구현한 셈이다. 물론 이 방법만 있는 것은 아니며  여러가지 방법이 있다.

 

 

학교 ppt에는 바로 다음으로 넘어가긴 했지만 책에 나온 if 중첩문 예시가 한번쯤 생각해 볼 만 한것같다.

if op1 == op2 then
	if X > Y then
    	call Routine1
    else
    	call Routine2
    end if
  else
  	call Routine3
  end if

이와 같은 high level 언어를 어셈블리어로 변환해보면

 

    mov eax, op1
    cmp eax, op2
    jne L2
    ; inner IF-ELSE statement process
    mov eax, X
    cmp eax, Y
    jg L1
    call Routine2
    jmp L3
L1: call Routine1
	jmp L3
L2: call Routine3
L3:

 

 

 

 

AND를  사용한  복합  표현식

 

논리적 AND 연산을 구현할 때, 고급 프로그래밍 언어들의 단락평가 short-circuit evaluation를 고려하자.

( 단락 평가는 논리 연산을 수행할 때, 전체 결과를 결정하기 위해 필요한 최소한의 계산만 수행하는 평가 방식 )

 

예를 들어 if문의 첫 번째 표현식이 false라면, 두 번째 표현식은 스킵된다.

 if (al > bl) AND (bl > cl)
 X = 1;

 

이와 같은 논리는 어셈블리어로 다음과 같이 변환할 수 있다. (다른 방식으로도 가능)

 cmp al,bl	; first expression...
 ja  L1
 jmp next
L1:
 cmp bl,cl	; second expression...
 ja  L2
 jmp next
L2:		; both are true
 mov X,1
next:

추가예시

 if( ebx <= ecx && ecx > edx )
 {
 eax = 5;
 edx = 6;
 }

 

 cmp ebx,ecx
 ja  next
 cmp ecx,edx
 jbe next
 mov eax,5
 mov edx,6
 next:

 

 

 

 

OR을  사용한  복합  표현식

 

OR문 역시 AND 연산과 마찬가지로 단락평가를 고려해야 한다.

 

예를 들어 or문의 첫 번째 표현식이 true라면, 두 번째 표현식은 스킵된다.

 if (al > bl) OR (bl > cl)
 X = 1;

 

 

우리는 여기에서 switch case 문에서 배웠었던 fall-through를 사용할 수 있다.

 cmp al,bl	 ; is AL > BL?
 ja  L1	; yes
 cmp bl,cl	 ; no: is BL > CL?
 jbe next	; no: skip next statement
L1:mov X,1	 ; set X to 1
next:

 

 

 

 

WHILE  루프

 

while 루프는 사실상 IF 문 다음에 루프의 몸체가 나오고, 그 다음에 무조건 루프의 맨 위로 점프하는 것과 같다.

 while( eax < ebx)
 eax = eax + 1;

 

 

이것을 어셈블리어로 구현하면 다음과 같다.

top:cmp eax,ebx	 ; check loop condition
 jae next	 ; false? exit loop
 inc eax	; body of loop
 jmp top	; repeat the loop
next:

 

 

 

 

테이블  기반  선택

 

다중 선택 구조 대신에 테이블 검색을 사용하는 방법이다.

 

이 방법을 사용하기 위해서는 검색 값과 레이블 또는 프로시저의 오프셋을 포함한 테이블을 만들어야 하고 테이블을 검색하려면 루프를 사용해야 한다.

 

이런 방식은 비교를 많이 해야할 때 도움이 된다.

 

 

우선, 조회할 값과 프로시저의 offset을 포함하는 테이블을 생성해보자.

.data
CaseTable BYTE 'A'	 ; lookup value
 DWORD Process_A	; address of procedure
 EntrySize = ($ - CaseTable)
 BYTE 'B'
 DWORD Process_B
 BYTE 'C'
 DWORD Process_C
 BYTE 'D'
 DWORD Process_D
 
NumberOfEntries = ($ - CaseTable) / EntrySize

 

이 코드의 프로시저 offset 테이블을 표현하면 각 프로시저가 어디에 있는지 알 수 있다.

 

 

 

다음으로, 루프를 사용하여 테이블을 검색한다.

일치하는 항목이 발견되면, 현재 테이블 항목에 저장된 프로시저 오프셋을 호출한다.

 mov ebx,OFFSET CaseTable	; point EBX to the table
 mov ecx,NumberOfEntries	; loop counter

L1: cmp al,[ebx]		; match found?
 jne L2	 			; no: continue		
 call NEAR PTR [ebx + 1]	 ; yes: call the procedure
 call WriteString		; display message
 call Crlf
 jmp L3				; and exit the loop
L2: add ebx,EntrySize	 	; point to next entry
 loop L1			; repeat until ECX = 0
L3:

 

 

 

 

 

finite-state machine (FSM)

 

finite-state machine (FSM)는 상태 전이 다이어그램 이라고도 부르며, 입력에 따라 상태가 변경되는 기계나 프로그램을 말한다.

 

 

 FSM은 그래프를 사용해서 표현한다.

정사각형이나 원은 노드라고 하며, 화살표로 표현하는 edge가 있다.

화살표로 표현하는 만큼, directed graph로 불린다.

 

 

각각의 노드는 시작 또는 종료 상태로 지정되고, 종료 상태는 굵은 선의 사각형으로 나타낸다.

 

 

 

FSM은 임의의 기호 시퀀스(문자열)를 받아서 토큰으로 변환하고, 이를 수용 상태(최종 상태)로 전환시킬 수 있다.

언어 규칙(정규 표현식)에 의해 지배되는 문자 시퀀스를 인식하거나 검증하는 데 사용할 수 있다.

 

 

이런 그래프를 이용하는 것으로 프로그램의 제어 흐름을 시각적으로 추적할 수 있다.

게다가 수정이 쉽고 어셈블리 언어로 쉽게 구현할 수 있다.

StateA:
 call Getnext				; read next char into AL
 cmp al,'+'				; leading + sign?
 je StateB				; go to State B
 cmp al,'-'				; leading - sign?
 je StateB				; go to State B
 call IsDigit				; ZF = 1 if AL = digit
 jz StateC				; go to State C
 call DisplayErrorMsg			; invalid input found
 jmp Quit

 

 

상태 A에 대한 flow chart는 다음과 같다.