Chapter 4 – 프로그래밍 언어의 구문과 구현 기법

Presentation on theme: "Chapter 4 – 프로그래밍 언어의 구문과 구현 기법"— Presentation transcript:

1 Chapter 4 – 프로그래밍 언어의 구문과 구현 기법
Outline 4.1 언어 구문 4.2 프로그래밍 언어 구현 기법

2 4.1 언어 구문 언어 정의 – 구문, 의미. 컴퓨터 – 프로그램을 실행 할 수 있는 알고리즘 + 자료구조 집합.
언어 정의 – 구문, 의미. 자연어 정의, 형식 정의 구문 형식 정의 – BNF, EBNF, 구문 도표 컴퓨터 – 프로그램을 실행 할 수 있는 알고리즘 + 자료구조 집합. 하드웨어 컴퓨터 (실제 컴퓨터) 소프트웨어 시뮬레이터 컴퓨터 가상 컴퓨터 (virtual computer)

3 4.1 언어 구문 가상 컴퓨터 고급 언어 프로그래머는 컴퓨터를 가상의 고급 언어 컴퓨터로 간주 ....... 가상의 C++
Ada 컴퓨터 운영체제 명령어 번역기 Ada 번역기 C++ 번역기 가상의 Assembly 언어 컴퓨터 운영체제 가상의 Cobol 컴퓨터 어셈블러 Cobol 번역기 Computer Hardware Lisp 인터프리터 가상의 Lisp 컴퓨터 Power Builder 인터프리터 가상의 Power Builder 컴퓨터

4 4.1 언어 구문 relational < ≤ = > ≠ boolean ￢ ∧ ∨ ⊃ ≡ arithmetic ↑ ×
프로그래밍 언어의 기본 문자 집합 알파벳 문자 (A - Z) 26개 +아라비아 숫자 (0 - 9) 10개 예) Fortran : 기본 문자 집합 + 13개의 특수문자(+ + - * / ( ) , . $ ‘ : 공백) Algol 60 : 알파벳 대소문자 52개 + 아라비아 숫자 10개 + 28개의 특수문자 Algol60의 특수 문자 relational < ≤ = > ≠ boolean ￢ ∧ ∨ ⊃ ≡ arithmetic ↑ × + - special , 10 : ； ' Б ( ) [ ] ”

5 4.1 언어 구문 문자 코드 체계 EBCDIC (Extended Binary Coded Decimal Interchange Code) IBM에서 제안, 8비트 조합 코드 ASCII (American Standard Code for Information Interchange) ANSI에서 제안, 7비트 조합 코드(128개의 문자 표현) 영문자 대소문자 52개 + 숫자 10개 + 33개의 특수문자 +33개의 제어문자 유니 코드 (Uni code) 16 bit ISO표준 규격 Java에 시행

6 4.1 언어 구문 정합 순서(collating sequence) 어휘 구조 용어 언어에 제공된 문자 순서 일반 순서 지킴.
예) 0 < 1< 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 A < B < C < < X < Y < Z 특수 문자 순서 (?) 코드 체계 따름 (구현시 결정) 프로그래머 정의 가능 (RPG, Snobol) 어휘 구조 용어 어휘 토큰 언어 구성자 식별자, 미리 정의 된 식별자, 예약어 구분자, 분리자

7 4.1 언어 구문 어휘 토큰 (lexical token), 어휘 요소 (lexical element), 어휘 단위 (lexical unit) 언어 구성자 (language construct) 식별자 [프로그래밍 언어에서] (identifier [in programming language) 미리 정의된 식별자 (predefined identifier)

8 4.1 언어 구문 예약어 (reserved words 또는 key words)
언어 어휘를 구성하는 단어나 기호 형태의 문자 알파벳 프로그램의 변수 이름으로 사용할 수 없음 장점 - 프로그램 판독성 증가, 컴파일러가 기호 테이블을 빠른 시간에 탐색 단점 – 많은 예약어를 기억하기 어려움, 언어 확장시 새로운 예약어가 확장 이전에 사용했던 프로그램의 식별자와 중복 우려

9 4.1 언어 구문 BNF (Backus – Naur Form) 표기법 구문(syntax) 형식을 정의하는 가장 보편적인 표기법
언어의 문장을 생성하는 생성 규칙(Production rule)정의 생성 규칙 생성 규칙의 왼쪽(정의될 대상), 오른쪽에는 그 대상에 대한 정의가 표현 BNF 표기법에 의한 식별자(identifier)정의 메타기호 ::= 정의하다, < > 비단말(nonterminal), | 택일기호 <identifier> ::= <letter>| <identifier><letter> | <identifier><digit> <letter> ::=A | B | C | ... | X | Y | Z <digit> ::=0 | 1 | 2 | ... | 8 | 9

10 4.1 언어 구문 EBNF (Extended Backus – Naur Form) 표기법
BNF보다 추가된 특수한 의미를 갖는 EBNF의 메타 기호 반복 : { }, { } 번 이상 반복 선택 : [ ] 또는 1번 선택 { }, [ ], |, ( ), ::=와 같은 메타 기호를 언어의 terminal로 사용하는 경우, ‘|’, ‘::=‘ 와 같이 인용부호로 묶어 표현 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

11 4.1 언어 구문 구문 도표 (Syntax diagram) 구문 도표는 그 형태가 순서도와 유사
구문 도표는 EBNF 와 일대일 대응 다시 정의될 대상은 네모칸으로 단말 기호는 원이나 타원형으로 표시하고 이들 사이는 지시선으로 연결 단말 X 비단말 B X B

12 4.1 언어 구문 구문 도표 (Syntax diagram) 구문 도표 그리는 방법  Xi가 비단말 기호인 경우
Xn X2 X1 A ... A ... X1 X2 Xn 2 1 n . . . A

13 4.1 언어 구문 구문 도표 (Syntax diagram) 구문 도표 그리는 방법 EBNF A ::= {α}
 A  1 A 

14 4.1 언어 구문 구문 도표 (Syntax diagram) 예제 EBNF 구문도표 A ::= x | ‘(‘B’)’
B ::= AC C ::= {+A} (조건) VN = {A, B, C} VT = { +, x, (, ) } x ( ) B A C + x ( A ) +

15 ; · = : ( ) Subpascal 시작부 구문 도표 subpascal program ident block const
number var procedure begin statement type : end ( formal-param ) ’

16 4.1 언어 구문 파스 트리 (parse tree) T E S 1
원시 프로그램의 문법을 검사하는 과정에서 내부적으로 생성되는 트리 형태의 자료구조 한 표현이 BNF에 의해 작성될 수 있는지 여부를 나타냄 예 - 식별자에 대한 BNF 를 통해 다음 TEST1 에 대한 파스 트리 작성 <identifier> <digit> <letter> T E S 1 <identifier> ::=<letter>| <identifier><letter> | <identifier><digit> <letter> ::=A | B | C | ... | X | Y | Z <digit> ::=0 | 1 | 2 | ... | 8 | 9

17 4.1 언어 구문 모호성, 결합성 및 우선 순위 서로 다른 유도 과정을 거쳐 B33을 생성한다.
<identifier> <identifier> <digit> <identifier> <identifier> <digit> 3 <identifier> <letter> B 3 3 <identifier> <identifier> <digit> <identifier> <digit> <digit> <letter> <digit> <digit> B <digit> <digit> B 3 <digit> B 3 3 <identifier> <digit> <letter> B 3 파스 트리

18 4.1 언어 구문 모호성, 결합성 및 우선 순위 다른 유도가 다른 파스 트리를 구성할 수 있다. 예) 3 – 2 * 5
<exp> - 3 * 2 5 <exp> <exp> - <exp> <exp> - <exp> * <exp> ( 두 번째 <exp> 이 <exp> * <exp> 로 대치) <number> - <exp> * <exp> …… 파스 트리 <exp> * - 3 2 5 <exp> <exp> * <exp> <exp> - <exp> * <exp> ( 첫 번째 <exp> 이 <exp> - <exp> 로 대치) <number> - <exp> * <exp> …… 파스 트리

19 4.1 언어 구문 모호성, 결합성 및 우선 순위 모호 (ambiguous) : 같은 스트리에 대해서 두 가지 서로 다른 파스 트리가 발생 모호성 제거

20 4.1 언어 구문 모호성, 결합성 및 우선 순위 순위 폭포(precedence cascade) : 새 비단말기호(<term>)와 문법 규칙을 추가하여 문법의 우선순위를 정함. 7-3-2 파싱 시 동일한 표현이 좌-결합 or 우-결합의 두 가지로 표현 <exp> ::= <exp> - <exp> | <term> <term> ::= <term> * <term> | (<exp>) | <number>

21 4.1 언어 구문 모호성, 결합성 및 우선 순위 BNF 문법에 좌순환 규칙을 사용하면 좌-결합을 지원할 수 있다.
<exp> ::= <exp> - <exp>를 <exp> ::= <exp>-<term>으로 대치하면 좌-결합으로 파싱된다. 우순환 규칙 (<exp> ::= <term> - <exp>)은 우-결합 파스 트리를 파싱

22 4.1 언어 구문 모호성, 결합성 및 우선 순위 표 4.5는 표 4.4의 문법이 우선 순위와 좌-결합으로 인해 모호성을
갖지 않는다. <표 4.5> 표 4.4의 개정문법 <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

23 4.1 언어 구문 구문과 프로그램 신뢰성 구문 (SYNTAX) 언어의 신뢰성에 영향 FORTRAN PL/I
2.6의 오류(. 대신 , 사용해야 함) DO10 I에 2.6 배정으로 인식 DO 10 I = 2.6 A(I) = B + C(I) 10 CONTINUE 다중배정문의 의미(A와 B에 C값 저장) (B = C)의 결과를 A에 저장하는 문장으로 인식 A = B = C

24 4.1 언어 구문 구문과 프로그램 신뢰성 현수(dangling) else 문제 예제
중첩된 if 문에서 else는 어떤 if의 else인가? 예제 if c1 then if c2 then S1 else S ① if c1 then (if c2 then S1 else S2) ② if c1 then (if c2 then S1) else S2 해석 각 언어에서 해결책 Algol60： Algol68： ① if c1 then begin if c2 then S1 else S2 end ① if c1 then if c2 then S1 else S2 fi fi ② if c1 then begin if c2 then S1 end else S ② if c1 then if c2 then S1 fi else S2 fi PL/I : Pascal : ② IF c1 THEN IF c2 THEN S1;ELSE S2; ② if c1 then begin if c2 then S1 end else S2 또는 또는 IF c1 THEN IF c2 THEN S1;ELSE;ELSE S2; if c1 then if c2 then S1 else else S2 ※ PL/1과 pascal은 일반적으로 ①의 경우로 해석

25 4.2 프로그래밍 언어 구현 기법 컴퓨터 : 프로그램을 저장하여 실행할 수 있는 알고리즘과 자료의 총괄 집합
Actual computer(hardware), software simulated computer 예) Cobol computer (가상 컴퓨터) 번역기 구성 번역된 프로그램 실행 hardware + software (virtual computer) 이론적으로 고급 언어를 기계언어로 하는 hardware 구성 가능 속도, 적응성, 비용 증가 저급 수준의 언어를 기계 언어로 하는 컴퓨터 제공 언어구현 사용자 : 고급언어 프로그래밍 기계 : 저급 언어 프로그래밍

26 4.2 프로그래밍 언어 구현 기법 번역 기법

27 4.2 프로그래밍 언어 구현 기법 번역기의 종류 컴파일러(compiler) 어셈블러(assembler)
원시 언어 :고급 언어 목적 언어 : 실제 기계 언어에 가까운 저급 언어 저급 언어에는 준기계어 형태 또는 어셈블리 언어 어셈블러(assembler) 원시 언어 : 어셈블리 언어 목적 언어 : 준기계어 형태 링키지 에디터(linkage editor) 여러 개의 프로그램(재배치 형태 기계어)을 묶음 로드 모듈 생성 로드 모듈 : 어느 정도 실행 가능한 하나의 기계어 프로그램

28 4.2 프로그래밍 언어 구현 기법 번역기의 종류 로더(loader) 프리프로세서(preprocessor)
기계어 프로그램(로드 모듈)을 실제 실행 가능한 기계어로 번역해서 주기억 장치에 적재 프리프로세서(preprocessor) 원시 언어와 목적 언어가 모두 고급 언어인 번역기 고급 언어 프로그램을 다른 고급 언어로 번역 후, 출력된 고급 언어를 이미 구현된 방법으로 실행시킬 때 사용 고급 언어에 대한 언어 확장하여 구현 시 유용 (C++, concurrent C)

29 입력 자료 인터프리터 결과 실행 4.2 프로그래밍 언어 구현 기법 고급 언어 원시 프로그램 인터프리터 기법
고급 언어 기계를 다른 기계에서 소프트웨어로 시뮬레이션하는 방법 고급 언어 원시 인터프리터 실행 결과 입력 자료 프로그램

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

31 (I/O routine등 일부 code는 simulation)
4.2 프로그래밍 언어 구현 기법 인터프리터 기법과 번역 기법의 비교 번역기 - 입력 프로그램과 동일한 의미의 목적 언어 프로그램 생성 인터프리터 - 직접 입력 프로그램을 실행하는 것 순수 번역 기법 (Assembly 등 저급 언어 가능) 순수 시뮬레이션 기법 (JCL, APL 등) 번역 효율적인 부분(반복 수행부와 수식 계산 등) 존재 원시 코드의 simulation이 효율적인 부분(I/O routine 등) 존재 순수 번역 기법이나 순수 시뮬레이션 기법은 실제로 거의 존재치 않음 simulation Translation (object 모듈 발생) 적응성 효율성 (I/O routine등 일부 code는 simulation)

32 4.2 프로그래밍 언어 구현 기법 번역 기법의 장단점 인터프리터 기법의 장단점
장점 - 실행 시간 효율성 제공 (한번 디코딩으로 반복 실행) 단점 - 번역된 프로그램이 큰 기억 장치 요구 (I/O routine 등) 인터프리터 기법의 장단점 번역 기법과 장단점이 반대임 사용자 적응성(flexibility) 제공

33 4.2 프로그래밍 언어 구현 기법 하이브리드 기법 프로그램을 실행시키기 쉬운 형태로 번역한 후, 그 번역된 형태의
프로그램을 디코드하여 시뮬레이션으로 실행 현 대부분의 인터프리터 언어가 이 방법을 따름 중간 형태 코드가 저급이면 번역 기법으로 간주되기도 함

34 4.2 프로그래밍 언어 구현 기법 컴파일러 언어 인터프리터 언어
Fortran, Algol, PL/I, Pascal, Cobol, C, Ada 컴파일러 방법의 장점 기계어로 번역된 것을 하드웨어 인터프리터가 디코드하여 실행 빠른 프로그램 실행(효율성) 인터프리터 언어 Lisp, Snobol 4, APL, Prolog 구현 방법 번역기가 중간언어를 생성 후, 중간언어로 작성된 프로그램을 소프트웨어 인터프리터로 실행 하이브리드 방법 컴파일러 방법보다 실행 시간이 비효율적이나 사용자 적응성 제공

35 슬라이드 쇼가 끝났습니다.

36 용 어 정리

37 어휘 토큰 (lexical token), 어휘 요소 (lexical element), 어휘 단위 (lexical unit)
용어 국제 표준 규격 lexical token 어휘 토큰 lexical element 어휘 요소 lexical unit 어휘 단위 A string of one or more characters of the alphabet of a programming language that, by convention, represents an elemental unit of meaning. <Example> A literal such as 2G5 or an identifier such as last_name in Pascal. 규약에 의거하여 기본 의미 단위를 표현하는, 한 개 이상의 프로그램 언어의 알파벳 문자로 구성된 문자열 <예> 2G5와 같은 리터럴 또는 Pascal에서 last_name과 같은 식별자

38 언어 구성자 (language construct)
용어 국제 표준 규격 language construct 언어 구성자 A syntactically allowable part of a program that may be formed from one or more lexical tokens in accordance with the rules of a programming language. 프로그래밍 언어의 규칙에 따라서 한 개 이상의 어휘 토큰으로 형성되며, 구문적으로 허용된 프로그램의 일부

39 identifier (in programming language) 식별자 (프로그래밍 언어에서)
용어 국제 표준 규격 identifier (in programming language) 식별자 (프로그래밍 언어에서) A lexical token that names a language construct. <Examples> the names of variables, arrays, records, labels, procedures, etc. <NOTE> An identifier usually consists of a letter optionally followed by letters, digits, or other characters. 언어 구성자를 명명하는 어휘 토큰 <예> 변수, 배열, 레코드, 레이블, 프로시저 등의 이름 <주> 식별자는 일반적으로 문자가 맨 앞에 오고 그  뒤에 영문자, 숫자, 또는 그 밖의 문자가 0개 이상 따라오도록 구성된다.

40 미리 정의된 식별자 (predefined identifier)
용어 국제 표준 규격 predefined identifier 미리 정의된 식별자 An identifier that is defined as part of a programming language. <Example> A reserved word. <NOTE> If a predefined identifier is not reserved, then a declaration using that identifier redefines its meaning for the scope of the declaration. 프로그래밍 언어의 일부로 정의된 식별자이다. <예> 예약어 <주> 미리 정의된 식별자가 예약되어 있지 않다면, 그 식별자를 사용한 선언으로 선언의 영역에서 식별자의 의미를 재정의 할 수 있다.

41 예약어 (reserved words or key words)
용어 국제 표준 규격 reserved word 예약어 A predefined identifier that cannot be redefined by a programmer. <NOTE> Not all programming languages have reserved words. 프로그래머가 재정의할 수 없는 미리 정의된 식별자 <주> 모든 프로그래밍 언어가 예약어를 가지고 있는 것은 아니다.

42 모호성 제거 용어 국제 표준 규격 15.01.09 disambiguation 모호성 제거
The action of determining which language construct, of several whit the same sequence of lexical tokens, is referred to by a particular occurrence within a program. 동일한 어휘 토큰 순서를 가진 다수의 언어 구성자 중 어떤 언어 구성자를 프로그램 내의 특정 사건이 참조하는지 결정하는 행위