2018-12-03 3장. 문법 구조(Syntax) 컴퓨터공학과 권기태 프로그래밍언어론.

Presentation on theme: "2018-12-03 3장. 문법 구조(Syntax) 컴퓨터공학과 권기태 프로그래밍언어론."— Presentation transcript:

1 3장. 문법 구조(Syntax) 컴퓨터공학과 권기태 프로그래밍언어론

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

3 가상 컴퓨터 고급 언어 프로그래머는 번역기를 가상의 고급 언어 컴퓨터로 간주 ....... 컴퓨터공학과 권기태 computer
hardware 운영 체제 Power Builder 인터프리터 Cobol 번역기 명령어 C++ Ada 어셈블러 Lisp 가상의 컴퓨터 Assembly 언어 컴퓨터공학과 권기태

4 어휘 구조 프로그래밍 언어의 기본 문자 집합 알파벳 문자 (A - Z) 26개 +아라비아 숫자 (0 - 9) 10개
예) Fortran : 기본 문자 집합 + 13개의 특수문자(+ + - * / ( ) , . $ ‘ : 공백) Algol 60 : 알파벳 대소문자 52개 + 아라비아 숫자 10개 + 28개의 특수문자 문자 코드 체계 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에 적용 컴퓨터공학과 권기태

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

6 예약어 (reserved words) 키워드 (keywords)
프로그래밍 언어 어휘를 구성하는 단어나 기호 형태의 문자 알파벳 프로그램의 변수 이름으로 사용할 수 없음 장점 - 프로그램 가독성 증가, 컴파일러가 기호 테이블을 빠른 시간에 탐색, 구문 에러의 에러 복구가 용이 단점 – 많은 예약어를 기억하기 어려움, 언어 확장시 새로운 예약어가 확장 이전에 사용했던 프로그램의 식별자와 중복 우려 키워드 (keywords) 변수 이름으로 사용 가능 FORTRAN, PL/I은 키워드를 사용 IF IF =THEN THEN THEN = ELSE; 컴퓨터공학과 권기태

7 3.3 문법 구조의 표현 자연언어로 기술된 문장의 분석 => 파싱 컴퓨터공학과 권기태

8 문법 정의 => 생성 규칙 가능한 파스 트리 컴퓨터공학과 권기태

9 BNF (Backus-Naur Form) 표기법
BNF (Backus-Naur Form) 표기법 구문(syntax) 형식을 정의하는 가장 보편적인 표기법 한 언어의 구문에 대한 BNF 정의 언어의 문장을 생성하는 생성 규칙(Production rule)정의 문맥 무관 문법(context-free grammar: 단말기호, 비단말기호,생성규칙,비단말기호인 시작기호로 구성) 생성 규칙 생성 규칙의 왼쪽(정의될 대상), 오른쪽에는 그 대상에 대한 정의가 표현 BNF 표기법에 의한 식별자(identifier)정의 <identifier> ::= <letter>| <identifier><letter> | <identifier><digit> <letter> ::=A | B | C | ... | X | Y | Z <digit> ::=0 | 1 | 2 | ... | 8 | 9 메타기호 ::= 정의하다 , < > 비단말(nonterminal), | 택일기호 컴퓨터공학과 권기태 프로그래밍언어론

10 ALGOL 60의 BNF 예 for 문의 부분적인 정의 생성 규칙에 의해 생성 가능한 문장 컴퓨터공학과 권기태
ALGOL 60의 BNF 예 for 문의 부분적인 정의 생성 규칙에 의해 생성 가능한 문장 컴퓨터공학과 권기태 프로그래밍언어론

11 식(expression)을 표현하는 문장
식(expression)을 표현하는 문장 식을 표현하는 문법의 예 파스 트리 A + B * C 의 유도 컴퓨터공학과 권기태 프로그래밍언어론

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

13 모호한 문법(ambiguous grammar) : 동일한 문장에 대해서 두 가지 서로 다른 파스 트리가 가능한 문법
컴퓨터공학과 권기태

14 if-then-else 다음 문장의 의미는? 모호한 문법 두 개의 파스 트리 컴퓨터공학과 권기태

15 else를 가장 내부의 if와 결합시키는 모호하지 않은 문법
파스 트리 컴퓨터공학과 권기태

16 EBNF (Extened Backus-Naur Form) 표기법
EBNF (Extened Backus-Naur Form) 표기법 BNF 표기법을 확장하여 보다 읽기 쉽고, 간단하게 표현된 표기법 BNF보다 추가된 특수한 의미를 갖는 EBNF의 메타 기호 - 반복 : { }, { } 번 이상 반복 - 선택 : [ ] 또는 1번 선택 - { }, [ ], |, ( ), ::=와 같은 메타 기호를 언어의 terminal로 사용하는 경우 ‘|’, ‘::=‘ 와 같이 인용부호로 묶어 표현 컴퓨터공학과 권기태 프로그래밍언어론

17 EBNF (Extened Backus-Naur Form) 표기법
EBNF (Extened Backus-Naur Form) 표기법 - 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 컴퓨터공학과 권기태 프로그래밍언어론

18 구문 챠트 (syntax chart) 구문 챠트는 그 형태가 순서도와 유사 구문 챠트는 EBNF 와 일대일 대응
구문 챠트 (syntax chart) 구문 챠트는 그 형태가 순서도와 유사 구문 챠트는 EBNF 와 일대일 대응 - 다시 정의될 대상은 네모칸으로 단말 기호는 원이나 타원형으로 표시 이들 사이는 화살표로 연결 - 단말 x X - 비단말 B B 컴퓨터공학과 권기태 프로그래밍언어론

19 - A ::= α1｜α2｜ ｜αn α1,α2, ...αn 가 비단말일 경우
BNF로부터 구문 챠트 유도 - A ::= X1X2 ...Xn ① Xi가 비단말 기호인 경우 Xn X2 X1 A ... ② Xi가 단말기호인 경우 A ... X1 X2 Xn - A ::= α1｜α2｜ ｜αn α1,α2, ...αn 가 비단말일 경우 2 1 n . . . A ... 컴퓨터공학과 권기태 프로그래밍언어론

20 구문 챠트 유도(계속) EBNF A ::= {α} EBNF A ::= [α] EBNF A ::= (α1｜α2)β
구문 챠트 유도(계속) EBNF A ::= {α} EBNF A ::= [α] EBNF A ::= (α1｜α2)β A  A  1 A  컴퓨터공학과 권기태 프로그래밍언어론

21 컴퓨터공학과 권기태 프로그래밍언어론

22 3.9 문법 구조와 프로그램의 신뢰성 구문(SYNTAX) 언어의 신뢰성에 영향 FORTRAN PL/1
3.9 문법 구조와 프로그램의 신뢰성 구문(SYNTAX) 언어의 신뢰성에 영향 FORTRAN PL/1 2.6의 오류(. 대신 , 사용해야 함) DO10I에 2.6 배정으로 인식 DO 10 I = 2.6 A(I) = B + C(I) 10 CONTINUE 다중배정문의 의미(A와 B에 C값 저장) (B = C)의 결과를 A에 저장하는 문장으로 인식 A = B = C 컴퓨터공학과 권기태 프로그래밍언어론

23 Pascal의 변수 선언 구문 챠트 => 두 번째 선언문이 잘못됨 컴퓨터공학과 권기태 프로그래밍언어론