제 4장 프로그래밍 언어의 구문과 구현 기법 4.1 언어 구문 4.2 프로그래밍 언어 구현 기법.

Presentation on theme: "제 4장 프로그래밍 언어의 구문과 구현 기법 4.1 언어 구문 4.2 프로그래밍 언어 구현 기법."— Presentation transcript:

1 제 4장 프로그래밍 언어의 구문과 구현 기법 4.1 언어 구문 4.2 프로그래밍 언어 구현 기법

2 가상 컴퓨터 컴퓨터를 가상의 고급 언어 컴퓨터로 간주 ....... computer hardware 운영 체제 Power
Builder 인터프리터 Cobol 번역기 운영 체제 명령어 C++ Ada 어셈블러 Lisp 가상의 컴퓨터 Assembly 언어

3 4.1 언어 구문 4.1.1 프로그래밍 언어의 어휘 구조 프로그래밍 언어의 기본 문자 집합 알파벳 (A∼Z) 26개
구문 정의 4.1 언어 구문 4.1.1 프로그래밍 언어의 어휘 구조 프로그래밍 언어의 기본 문자 집합 알파벳 (A∼Z) 26개 아라비아 (0∼9) 10개 특수 문자 (+, -, ,, …) 문자 코드 체계 EBCDIC (Extended Binary Coded Decimal Interchange Code) ASCII (American Standard Code for Information Interchange) 유니코드

4 정합순서 (collecting sequence)
구문 정의 정합순서 (collecting sequence) 문자 또는 문자열에 대한 일반적 순서 비트 조합 순서에 영향 받음 예) 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 A < B < C < ... < X < Y < Z 문자 -> 단어 -> 언어 예약어 (reserved word, key word) 프로그램 판독성 증가 기호 테이블 빠른 탐색 많은 예약어 기억하기 어려움 중복여지가 프로그램 혼돈 우려

5 4.1.2 문맥 자유 문법과 BNF BNF (Backus-Naur Form) : context free grammar
구문 정의 4.1.2 문맥 자유 문법과 BNF BNF (Backus-Naur Form) : context free grammar 구문 (Syntax) 형식 정의 보편적 방법 언어의 생성 규칙 정의 메타 기호 ::= 정의하다 < > nonterminal : 다시 정의될 대상 | 택일

6 <identifier><digit>
구문 정의 식별자 정의의 BNF 표기 <identifier> ::= <letter> | <identifier><letter> | <identifier><digit> <letter> ::= A | B | C | … | X | Y | Z <digit> ::= 0 | 1 | 2 | … | 8 | 9

7 예) AB1C <identifier> ::= <identifier><letter>
구문 정의 예) AB1C <identifier> ::= <identifier><letter> ::= <identifier><digit><letter> ::= <identifier><letter><digit><letter> ::= <letter><letter><digit><letter> ::= A <letter><digit><letter> ::= AB <digit><letter> ::= AB1 <letter> ::= AB1C

8 EBNF (Extended Backus-Naur Form) 표기법
구문 정의 EBNF (Extended Backus-Naur Form) 표기법 BNF 확장하여 읽기 쉽고 간단한 표기법 BNF에 추가된 메타 기호 {} : 0번 이상 반복 ( { }07 ) [] : 0번 또는 1번 선택 () : 택일 연산자 ‘ ‘ : terminal 표시

9 EBNF의 예 식별자 If - then - else
구문 정의 EBNF의 예 식별자 <id-name> ::= <alphabet> { <alphanumeric> }07 <alphanumeric> ::= <alphabet> | <digit> <alphabet> ::= A | B | C | … | Z <digit> ::= 0 | 1 | 2 | … | 9 If - then - else <if-statement> ::= if <condition> then <statement> [else<statement>]

10 구문 정의 사칙 연산 BNF <expression> ::= <expression> + <expression> | <expression> - <expression> | <expression> * <expression> | <expression> / <expression> EBNF <expression> ::= <expression>(+|-|*|/)<expression>

11 구문 정의 메타 기호가 terminal 기호 일 때 <BNF-rule> ::= <left-part> ‘::=‘ <right-part> <right-part> ::= <right-part-element> { ‘|’ <right-part-element> }

12 구문 정의 Subpascal 시작부에 대한 EBNF <subpascal> ::=program <ident>；<block> . <block> ::=[<const_dcl>][<var_dcl>]{<proc_dcl>} <compound-st> <const_dcl> ::=const <ident> = <number> {；<ident> = <number> }； <var_dcl> ::=var <ident_list> : <type> {； <ident_list> : <type> }； <ident_list> ::=<ident> {,<ident>} <proc_dcl> ::=procedure <ident>['('<formal_param>')']； <block>； <compound-st> ::=begin <statement> {；<statement>} end

13 4.1.3 구문 도표 구문 도표 (syntax diagram) 구문 도표는 그 형태가 순서도와 유사
구문 정의 4.1.3 구문 도표 구문 도표 (syntax diagram) 구문 도표는 그 형태가 순서도와 유사 구문 구문 도표는 EBNF 와 일대일 대응 다시 정의될 대상은 네모칸으로 terminal 기호는 원이나 타원형으로 표시 이들 사이는 지시선으로 연결

14 구문 정의 구문 도표 그리는 방법 ① terminal x X ② nonterminal B B

15 x2 xn x1 ④ A ::= α1｜α2｜...｜αn ③ A ::= X1X2 ...Xn A X1 X2 Xn ...
구문 정의 ④ A ::= α1｜α2｜...｜αn ③ A ::= X1X2 ...Xn A X1 X2 Xn ... ⓐ Xi가 nonterminal인 경우 ⓑ Xi가 terminal인 경우 x1 x2 xn α2 αn α1

16 ⑤ EBNF A ::= {α} ⑥ EBNF A ::= [α] ⑦ EBNF A ::= (α1｜α2)β A α A α α1 A β
구문 정의 ⑤ EBNF A ::= {α} ⑥ EBNF A ::= [α] ⑦ EBNF A ::= (α1｜α2)β A α A α α2 α1 A β

17 예제 EBNF 구문도표 A ::= x ｜’(‘ B’ )’ B ::= AC C ::= {+A} (조건)
구문 정의 예제 EBNF 구문도표 A ::= x ｜’(‘ B’ )’ B ::= AC C ::= {+A} (조건) VN = { A, B, C } VT = { +, x, (, ) } x B ) ( A C + x ) ( A +

18 Subpascal 구문 도표 구문 정의 subpascal program ident ; block · block const
= number ; var ident : type ‘ ; procedure ident ; ( formal-param ) ; block begin statement end ;

19 4.1.4 파스 트리 파스 트리 원시 프로그램의 문법 검사 과정 중 생성 트리 구문 검사하는 검증 트리
구문 정의 4.1.4 파스 트리 파스 트리 원시 프로그램의 문법 검사 과정 중 생성 트리 구문 검사하는 검증 트리 한 표현이 BNF에 의해 작성될 수 있는지 여부

20 예) TEST1 1 T E S 구문 정의 <identifier> ::=<letter>|
<identifier><digit> <letter> ::=A | B | C | ... | X | Y | Z <digit> ::=0 | 1 | 2 | ... | 8 | 9 <identifier> <digit> <letter> T E S 1

21 <exp> ::= <exp> - <exp> | <exp>
<exp> ::= <exp> - <exp> | <exp> * <exp> | (<exp>) | <number> <number> ::= <number> <digit> | <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <exp> - <number> <digit> * 3 2 5

22 <exp> - <number> <digit> * 3 2 5 - * 3 2 5 이 파스트리에서 불필요하게 표현되어 있는 비단말 기호들을 없애면 추상구문(AST) 트리 혹은 구문트리(syntax tree)가 된다.

23 4.1.5 모호성, 결합성 및 우선순위 예) B33 생성 유도 과정
<identifier> <identifier><digit> <identifier> 3 <identifier> <digit> <identifier> <letter> 3 3 B 3 3 <identifier> <identifier><digit> <identifier><digit><digit> <letter> <digit> <digit> B <digit> <digit> B 3 <digit> B 3 3

24 예) B33 의 파스트리 <identifier> <digit> <letter> B 3

25 예) 3 – 2 * 5 수식의 생성 유도 과정 <exp> <exp> - <exp>
<number> - <exp> * <exp> …. 3 – 2 * 5 <exp> <exp> * <exp> (첫번째 <exp>이 <exp> - <exp>으로 대치 )

26 예) 두가지 서로 다른 파스트리 <exp> <exp> - <exp> 3 <exp> <exp> * <exp> 3 2 2 5 5 * - 같은 문법에서 같은 스트림에 대하여 두가지 이상의 서로 다른 파스트리가 발생하면 이러한 문법은 모호(ambiguous)하다고 한다.

27 예) Unambiguous 문법(분명한 문법)
수식 우선 순위의 문제 해결 <exp> ::= <exp> - <term> | <term> <term> ::= <term> * <factor> | <factor> <factor> ::= (<exp>) | <number> <number> ::= <number> <digit> | <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

28 구문 정의 4.1.6 구문과 프로그램 신뢰성 구문 프로그램의 신뢰성 증대 시키는데 큰 영향

29 예) FORTRAN PL/I DO 10 I = 2.6 2.6의 오류(. 대신 , 사용해야함) A(I) = B + C(I)
구문 정의 예) FORTRAN DO 10 I = 2.6 A(I) = B + C(I) 10 CONTINUE 2.6의 오류(. 대신 , 사용해야함) DO10I에 2.6 배정으로 인식 PL/I A = B = C 다중배정문의 의미(A와 B에 C값 저장) (B = C)의 결과를 A에 저장하는 문장으로 인식

30 If cond1 then if cond2 then s1 else s2
구문 정의 If cond1 then if cond2 then s1 else s2 ① If cond1 then (if cond2 then s1 else s2) If cond1 then (if cond2 then s1) else s2 ② Dangling (현수) else 문제 중첩된 if 문에서 else는 어떤 if의 else 인가? if <cond> then <s> if <cond> then <s> else <s>

31 <s> ::= if <cond> then <s> |
구문 정의 <s> ::= if <cond> then <s> | if <cond> then <s> else <s> | s1 | s2 <cond> ::= cond1 | cond2 ① <s> ② <s> If <cond> then <s> else <s> if <cond> then <s> <s> cond1 If <cond> then <s> else <s> cond1 if <cond> then cond s s2 cond s s2

32 언어별 현수 else 문제의 해결 방안 구문 정의 Algol 60 : - ①의 경우
if cond1 then begin if cond2 then s1 else s2 end - ②의 경우 if cond1 then begin if cond2 s1 end else s2 Algol 68 : if cond1 then if cond2 then s1 else s2 fi fi if cond1 then if cond2 s1 fi else s2 fi PL/I : - ② 의 경우 IF cond1 THEN IF cond2 THEN s1; ELSE s2; 또는 IF cond1 THEN IF cond2 THEN s1; ELSE; ELSE s2; if cond1 then begin if cond2 then s1 then else s2 if cond1 then if cond2 then s1 else else s2 ※ PL/I 과 파스칼에서 일반적으로 사용된 경우 ①의 경우로 해석됨.

33 Sample List (1-1) *PASCAL*
구문 정의 Sample List (1-1) *PASCAL* Program Compare(input, Output); Var x, y, z : integer; Begin z := 7; writeln(‘Type the each variables x, y, z ‘); write (‘ x= ‘); readln (x); write (‘ y= ‘); readln (y); if x < 0 then if y > 5 then z := x + y else z := x + y; writeln(‘x = ‘, x, ‘ y = ‘, y, ‘ z= ‘, z) end.

34 Sample List (1-2) *C* 구문 정의 #include <stdio.h> void main() {
int x, y, z = 7; printf(“ Type the each variables x, y, z\n”); printf(“x = “); scanf(“%d”, &x); printf(“y =“); scanf(“%d”, &y); if (x < 0) if (y > 5) z = x + y; else z = 0; printf(“\n x = %d, y = %d, z = %d\n”, x, y, z); }

35 Sample List (1-3) *JAVA* import java.io.*; public class A {
public static void main(String[] args) throws IOException { String strx; String stry; int x,y,z=7; BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); System.out.println("Type the each variables x, y"); System.out.print("x = "); strx = in.readLine(); x = Integer.parseInt(strx); System.out.print("y = "); stry = in.readLine(); y = Integer.parseInt(stry); if (x < 0) if (y > 5) z = x + y; else z = 0; System.out.println("x = "+ x + ", y = " + y+", z = "+z); }

36 Sample List (1-4) *JAVA* import java.io.*; public class B {
public static void main(String[] args) throws IOException { int x,y,z=7; System.out.println("Type the each variables x, y"); x = System.in.read() - '0'; y = System.in.read() - '0'; if (x < 0) if (y > 5) z = x + y; else z = 0; System.out.println("x = "+ x + ", y = " + y+", z = "+z); }

37 Sample List (2-1) *PASCAL*
구문 정의 Sample List (2-1) *PASCAL* Program Compare(input, Output); Var x, y, z : integer; Begin writeln(‘Type the each variables x, y, z ‘); write (‘ x= ‘); readln (x); write (‘ y= ‘); readln (y); if x < 0 then if y > 5 then z := x + y else else z := 0; writeln(‘x = ‘, x, ‘ y = ‘, y, ‘ z= ‘, z) end.

38 Sample List (2-2) *C* 구문 정의 #include <stdio.h> void main() {
int x, y, z; z = 7; printf(“ Type the each variables x, y, z\n”); printf(“x = “); scanf(“%d”, &x); printf(“y =“); scanf(“%d”, &y); if (x < 0) { if (y > 5) z = x + y; else z = 0; } printf(“\n x = %d, y = %d, z = %d\n”, x, y, z); }

39 Sample List (2-3) *JAVA* import java.io.*; public class A {
public static void main(String[] args) throws IOException { String strx; String stry; int x,y,z=7; BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); System.out.println("Type the each variables x, y"); System.out.print("x = "); strx = in.readLine(); x = Integer.parseInt(strx); System.out.print("y = "); stry = in.readLine(); y = Integer.parseInt(stry); if (x < 0) { if (y > 5) z = x + y; else z = 0; } System.out.println("x = "+ x + ", y = " + y+", z = "+z);

40 Sample List (2-4) *JAVA* import java.io.*; public class B {
public static void main(String[] args) throws IOException { int x,y,z=7; System.out.println("Type the each variables x, y"); x = System.in.read() - '0'; y = System.in.read() - '0'; if (x < 0) { if (y > 5) z = x + y; else z = 0; } System.out.println("x = "+ x + ", y = " + y+", z = "+z);

41 Sample List (3-1) *PASCAL*
구문 정의 Sample List (3-1) *PASCAL* Program Compare(input, Output); Var x, y, z : integer; Begin z := 7; writeln(‘Type the each variables x, y, z ‘); write (‘ x= ‘); readln (x); write (‘ y= ‘); readln (y); if x < 0 then if y > 5 then z := x + y else z := 0; writeln(‘x = ‘, x, ‘ y = ‘, y, ‘ z= ‘, z) end.

42 Sample List (3-2) *C* 구문 정의 #include <stdio.h> void main() {
int x, y, z; z = 7; printf(“ Type the each variables x, y, z\n”); printf(“x = “); scanf(“%d”, &x); printf(“y =“); scanf(“%d”, &y); if (x < 0) { if (y > 5) z = x + y; } else z = 0; printf(“\n x = %d, y = %d, z = %d\n”, x, y, z);

43 Sample List (3-3) *JAVA* import java.io.*; public class A {
public static void main(String[] args) throws IOException { String strx; String stry; int x,y,z=7; BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); System.out.println("Type the each variables x, y"); System.out.print("x = "); strx = in.readLine(); x = Integer.parseInt(strx); System.out.print("y = "); stry = in.readLine(); y = Integer.parseInt(stry); if (x < 0) { if (y > 5) z = x + y; } else z = 0; System.out.println("x = "+ x + ", y = " + y+", z = "+z);

44 Sample List (3-4) *JAVA* import java.io.*; public class B {
public static void main(String[] args) throws IOException { int x,y,z=7; System.out.println("Type the each variables x, y"); x = System.in.read() - '0'; y = System.in.read() - '0'; if (x < 0) { if (y > 5) z = x + y; } else z = 0; System.out.println("x = "+ x + ", y = " + y+", z = "+z);

45 4.2 프로그래밍 언어 구현 기법 구현 방법 번역 기법 (Translation)
프로그래밍 언어 설계 4.2 프로그래밍 언어 구현 기법 구현 방법 번역 기법 (Translation) 어떤 원시(Source) 언어를 입력으로 목적 언어로 된 기능이 동등한 프로그램을 출력해 주는 언어 처리기 인터프리터 기법(Interpretation) 고급 언어로 된 프로그램을 읽어 각 문장을 디코딩하고 실행시키는 언어 처리기

46 번역 기법 (Translation) source 프로그래밍 언어 설계 (원시 언어) target (목적 언어)
translator 로 더 기계어 LINKER 고급 언어 컴파일러 목적 모듈 어셈블리 어셈블러 원 시 프로그램 목 적 입력 자료 실행 결과 로드

47 번역기의 종류 Preprocessor 원시 언어 : 고급 언어 목적 언어 : 고급 언어 Compiler
프로그래밍 언어 설계 번역기의 종류 Preprocessor 원시 언어 : 고급 언어 목적 언어 : 고급 언어 Compiler 원시 언어 : 고급 언어 목적 언어 : 저급 언어(어셈블리, 준 기계어) Assembler 원시 언어 : 어셈블리 언어 목적 언어 : 준기계어 언어

48 Linkage Editor 원시 언어 : 여러 개의 프로그램 목적 언어 : 로드 모듈 생성 (실행 가능한 하나의 기계어)
프로그래밍 언어 설계 Linkage Editor 원시 언어 : 여러 개의 프로그램 목적 언어 : 로드 모듈 생성 (실행 가능한 하나의 기계어) Loader 원시 언어 : 로드 모듈 목적 언어 : 실행 가능한 기계어 (excutable code)

49 프로그래밍 언어 설계 인터프리터 기법(1) 고급 언어로 작성된 원시 프로그램 인터프리터 입력자료 실행 결과

50 프로그래밍 언어 설계 인터프리터 기법(2) 원시 프로그램 중간 형태 코드 입력자료 실행 결과 적당한 번역과정 인터프리터

51 < Java 바이트 코드 컴파일 >
출력 결과 Java 프로그램 바이트코드 컴파일러(javac) Java 가상기계의 바이트코드 인터프리터 Java 가상 기계가 작동하고 있는 실제 기계 < Java 바이트 코드 컴파일 >

52 번역기 종류와 인터프리터 프로그래밍 언어 설계 원시 언어 ( 입력 ) 소프트웨어 프로그램 목적 언어 (출력) 기계어, 준기계어
(목적 모듈) 고급 언어 프로그램 컴파일러 기계어, 준기계어 (목적 모듈) 어셈블러 프로그램 어셈블러 링 커 목적모듈 (준기계어) (linker, linkage editor) 로드 모듈 로 더 로드 모듈 (relocating loader) 실행 가능 기계어 고급 언어 프로그램 Preprocessor 고급 언어 프로그램 원시 언어 (입력) 소프트웨어 프로그램 (하드웨어 기능) 출 력 프로그램이 고급 언어 프로그램 인터프리터 실행된 결과

53 장점 : 실행 시간 효율성 (efficiency) 단점 : 큰 기억 장치 요구
프로그래밍 언어 설계 번역 기법과 인터프리터 기법 비교 번역기 입력 프로그램과 동일한 의미의 목적 언어 프로그램 생성 장점 : 실행 시간 효율성 (efficiency) 단점 : 큰 기억 장치 요구 컴파일러 언어 FORTRAN, ALGOL, PL/I, PASCAL, COBOL C, Ada

54 장점 : 사용자의 적응성 (flexibility)
프로그래밍 언어 설계 인터프리터 중간 언어를 생성 후 중간 언어로 작성된 프로그램을 번역, 실행 장점 : 사용자의 적응성 (flexibility) 단점 : 실행 시 많은 디코딩 시간 요구 인터프리터 언어 LISP, SNOBOL, APL, PROLOG