제2장 구문(Syntax) Reading Chap 4 © 숙대 창병모

2.1 프로그래밍 언어의 정의 © 숙대 창병모

(프로그래밍) 언어 정의 구문법(Syntax) 의미 (Semantics) 프로그래밍 언어 공부하는데 필요한 기본기 구성요소를 이용하여 문장/프로그램을 구성하는 방법 쓰는 방법  겉모양 의미 (Semantics) 문장/프로그램의 의미 씌어진 것의 의미  뜻 프로그래밍 언어 공부하는데 필요한 기본기 어떻게 정의해야 할까요? © 숙대 창병모

QnA 가능한 문장 혹은 프로그램의 개수가 무한하지 않나요? 무한한 것들을 어떻게 유한하게 정의할 수 있나요? © 숙대 창병모

귀납적 정의(Inductive Definition) 처음 들어본 사람? 홀수 1, 3, 5, 7, 9, 11, … 무한한 홀수를 유한한 방법으로 어떻게 정의할까요? a1 = 1 an+1 = an + 2 문법(Grammar) A  1 A  A + 2 © 숙대 창병모

귀납적 증명(Inductive Proof) 처음 들어본 사람? 홀수의 합 n Σ 2k -1 = n2 k=1 무한한 걸 어떻게 증명하지? n = 1일 때 2*1 – 1 = 1 = 12 가정 가정으로부터 다음 증명 n+1 Σ 2k -1 = (n+1)2 © 숙대 창병모

귀납적 정의: 이진수/십진수의 구문법 숫자(D)는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9중 하나이다. 말로 정의 숫자(D)는 수(N)이다. 수 다음에 숫자(ND)가 오면 수(N)이다. Induction Rule 형태 문법 형태 N  D N  D N  ND | ND D is a digit N is a number and D is a digit D is a number ND is a number © 숙대 창병모

이진수: Syntax vs Semantics D  0 | 1 N  D | ND 101 [101] = [0] = 0 [1] = 1 [D] [ND] = [N] * 2 + [D] © 숙대 창병모

십진수: Syntax vs Semantics D  0 | 1 | 2 … | 9 N  D | ND 386 [386] = [0] = 0 [1] = 1 [2] = 2 … [9] = 9 [D] [ND] = [N] * 10 + [D] © 숙대 창병모

수식의 구문 N  N D | D 5, 13, 5 + 13, 5 * 13, (5 + 3), (5 + 3) * 13, … 좀 현실적인 구문은 없나요? 수식 5, 13, 5 + 13, 5 * 13, (5 + 3), (5 + 3) * 13, … 구문법 : 쓰는 방법 E  E * E | E + E | (E) | N N  N D | D D  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 © 숙대 창병모

수식의 의미 | E + E [E * E] = [E] * [E] | (E) [E + E] = [E] + [E] | N 무엇을 수식의 의미라고 생각하세요? 23 * 5 + 12 [23 * 5 + 12] = ? [E * E] = [E] * [E] [E + E] = [E] + [E] [(E)] = [E] [N] © 숙대 창병모

2.2 프로그래밍 언어 구현 © 숙대 창병모

프로그래밍 언어 구현 프로그래밍 언어 구현은 무얼 해야 하나요? 프로그래밍 언어 구현은 어떻게 해야 하나요? 입력 프로그램  Syntax  Semantics  Interpret or Compile 프로그래밍 언어 구현은 어떻게 해야 하나요? 구문법에 맞춰 작성된 프로그램을 입력 받아 그 의미에 맞게 동작하도록 해석하거나 기계어 명령어들로 번역해야 한다. © 숙대 창병모

(프로그래밍) 언어의 구성 의미(Semantics) 어휘구조(Lexical structure) 구문법(Syntax) 단어의 구조, 철자법 구문법(Syntax) 구문 구조 문법을 이용해서 기술 Context-free grammar in BNF(Backus-Naur Form) 의미(Semantics) 프로그램의 의미 자연어를 이용한 기술 수학적 기술 operational semantics denotational semantics axiomatic semantics © 숙대 창병모

인터프리터 vs 컴파일러 소스 프로그램 입력 인터프리터 출력 소스 프로그램 컴파일러 입력 목적 프로그램 출력 © 숙대 창병모

컴파일러 구조 Source program Analysis phases Synthesis phases Target program © 숙대 창병모

컴파일러 구조 See summary in course text, compiler books Source Program Lexical Analyzer (Scanner) Syntax Analyzer (Parser) Semantic Analyzer Intermediate Code Generator Code Optimizer Code Generator Target Program See summary in course text, compiler books © 숙대 창병모

2.3 구문 및 문법 © 숙대 창병모

구문(Syntax) 프로그래밍 언어의 구문구조는 어떻게 표현할 수 있을까 ? 앞에서 살펴본 수식의 구문법 E  E * E N  N D | D D  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 © 숙대 창병모

구문법(Syntax Grammar) 프로그래밍 언어의 구문구조 문장 S 귀납적 정의(Inductive Definition) 문장 S Id = E if E then S else S while E do S … 문맥-자유 문법(CFG:Context-free grammar) 이러한 자기호출 구조를 자연스럽게 표현할 수 있다. © 숙대 창병모

예제 if-then-else 문 단순 수식 S  if E then S | if E then S else S | … | … 단순 수식 E  E * E | E + E | (E) | N N  N D | D D  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 © 숙대 창병모

CFG A CFG consists of: Notational convention a set of terminals T a set of non-terminals N a start symbol S (one of the non-terminals) a set of production rules X  Y1 Y2 … Yn where X  N and Yi  T N  {} Notational convention non-terminals are written upper-case terminals are written lower-case © 숙대 창병모

구문검사 QnA 문법으로부터 유도(derivation)해본다. 그러면 유도는 어떻게 하나요? 어떤 문장 혹은 프로그램이 구문법에 맞는지는 어떻게 검사하나요? 문법으로부터 유도(derivation)해본다. 유도 가능하면 문법에 맞는 문장이고 그렇지 않으면 문법에 맞지 않는 문장이다. 그러면 유도는 어떻게 하나요? © 숙대 창병모

유도(Derivation) 생성 규칙 X  Y1 Y2 … Yn X 는 Y1 Y2 … Yn 으로 대치될 수 있다. 혹은 터미널 심볼 대치할 규칙이 없으므로 일단 생성되면 끝 터미널 심볼은 그 언어의 토큰이다. 핵심 아이디어 1. 시작 심볼 S부터 시작한다. 2. 넌터미널 심볼 X를 생성규칙을 적용하여 Y1 Y2…Yn으로 대치한다. 3. 이 과정을 넌터미널 심볼이 없을 때까지 반복한다. © 숙대 창병모

유도(Derivation) Direct derivation  Derivation * X1 …Xi… Xn  X1 … Xi-1Y1 Y2…Yn Xi+1 … Xn if there is a production Xi  Y1 Y2…Yn Derivation * X1 … Xn * Y1 … Ym if X1 … Xn  …  Y1 … Ym (0 or more direct derivations from X1 … Xn to Y1 … Ym ) © 숙대 창병모

유도 예제 CFG 생성할 스트링: 3 + 15 유도 E  E + E  N + E  D + E  3 + E  … N  N D | D D  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 생성할 스트링: 3 + 15 유도 E  E + E  N + E  D + E  3 + E  … © 숙대 창병모

문법 G 언어 The language L(G) of a CFG G 문법 G에 의해서 정의되는 언어 {a1 … an | S * a1 … an and every ai is a terminal} © 숙대 창병모

예제 L(G) is the language of a CFG G. Strings of balanced parentheses: S  (S) S  a The language is ? © 숙대 창병모

2.4 파스 트리 © 숙대 창병모

유도 및 파스 트리 Derivation tree = Parse tree = Syntax tree 유도과정 혹은 구문구조를 보여주는 트리 유도 트리 = 파스 트리 = 구문 트리 A sequence of production applications S  …  … is a derivation. A derivation can be drawn as a tree: S is the tree's root. If the derivation uses production X  Y1 Y2…Yn, X has children Y1,…,Yn. © 숙대 창병모

유도 예제 CFG 생성할 스트링: 3 + 4 * 5 유도 E  E * E | E + E | (E) | N N  N D | D D  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 생성할 스트링: 3 + 4 * 5 유도 © 숙대 창병모

파스 트리 E E + E 3 E * E 4 5 © 숙대 창병모

유도에 대한 참조(1) A parse tree has terminals at the leaves. non-terminals at the interior nodes. An inorder traversal of the leaves is the original input. The parse tree shows association of operations; 3 + (4 * 5) © 숙대 창병모

유도에 대한 참조(2) 지금까지 좌우선 유도(leftmost derivation)를 각 단계에서 가장 왼쪽 넌터미널이 대치되었음 우우선 유도(Rightmost derivation). 3 + 4 * 5 주의 좌우선 유도와 우우선 유도 모두 같은 파스트리를 갖는다. 차이점은 파스트리에 가지가 추가되는 순서이다. © 숙대 창병모

언어를 한번 정의해보면 어떨까? 언어 이름은 ? Stmt S  x = E | S; S | if E then S | if E then S else S | while E do S | read x | print E Expr E  n | x | true | false | E + E | E – E | E * E | E / E | E == E | E != E | E < E | E > E | !E Prgm P  S 언어 이름은 ? © 숙대 창병모

요약 구문구조 문법을 이용하여 표기 유도(derivation) 파스트리(parse tree) CFG in BNF 좌우선 유도(Leftmost derivation) 우우선 유도(Rightmost derivation) 파스트리(parse tree) © 숙대 창병모

2.4 모호성 © 숙대 창병모

모호성(Ambiguity) * 수식을 위한 문법 E  E * E | E + E | (E) | N 스트링 3 + 4 * 5 이 스트링은 두 개의 파스트리를 갖는다. E + * 5 4 3 E * + 5 4 3 © 숙대 창병모

모호성(2) 모호한 문법(ambiguous grammar) 모호성은 나쁘다 어떤 스트링에 대해 두 개 이상의 좌측 (혹은 우측) 유도를 갖는다. 두 개 이상의 파스 트리를 갖는다. 모호성은 나쁘다 왜 ? © 숙대 창병모

모호성 처리 문법 재작성 예 우선 순위를 적용 모호하지 않도록 재작성 E  E + T | T T  T * F | F F  N | (E) 우선 순위를 적용 © 숙대 창병모

모호성 예: The Dangling Else 모호한 문법 S  if E then S | if E then S else S 이 문장에 대한 두 개의 파스 트리 if e1 then if e2 then s1 else s2 if e1 S s1 s2 e2 if e1 S s1 s2 e2 © 숙대 창병모

모호성 예 : The Dangling Else 모호하지 않는 문법 S  MATCH_IF | UNMATCH_IF MATCH_IF  if E then MATCH_IF else MATCH_IF UNMATCH_IF  if E then MATCH_IF else UNMATCH_IF | if E then S 앞의 문법과 같은 스트링을 생성한다. 주의 모호성을 다루는 일반적인 규칙은 없다. 모호하지 않는 문법으로 자동적인 변환 방법은 없다. © 숙대 창병모

2.5 EBNF와 구문 다이어그램 © 숙대 창병모

EBNF BNF EBNF E  E + T | T T  T * F | F F  N | (E) N  N D | D © 숙대 창병모

구문 다이어그램 구문 다이어그램 예제 각 생성규칙을 다이어그램으로 표현 넌터미널 터미널 화살표 그림 4.11 사각형 원 순서 © 숙대 창병모

2.6 파싱 구현 © 숙대 창병모

지금까지 한 것/앞으로 할 것! Topic Logic Implementation --------------------------------------------- Syntax Grammar Parser Semantics Semantics rules Interpreter Type Typing rules Type checker © 숙대 창병모

recursive-descent parsing 기본 원리 입력 스트링을 좌우선 유도(leftmost derivation)하도록 문법으로부터 직접 파서 프로그램을 만든다. 구현 각 넌터미널 하나의 프로시저(함수,메쏘드) 형태로 구현한다. 프로시저 내에서 생성규칙 우변을 수행 하도록 작성한다. 프로시저 호출 생성 규칙을 적용하는 것! A  B c D A( ) { B( ); match(“c”); D( ); } © 숙대 창병모

예제 Command  Expr ‘\n’ void Command(void) { int result = Expr( ); if (token ==‘\n’) printf(“The result is: %d\n”, result); else error(); } void parse(void) { token = getchar(); Command(); main() { parse(); return 0; } © 숙대 창병모

예제 Expr  Term {+Term} void Expr(void) { Term( ); while (token == “+”) { match(“+”); Term(); } void match(char c) // 현재 토큰 확인 후 다음 토큰 읽기 { if (token == c) token = getchar(); else error(); © 숙대 창병모

예제 그림 4.12 Expr  Term {+Term} 순환-하강 파싱 하면서 동시에 수식의 값을 계산 int Expr(void) { int result = Term( ); while (token == “+”) { match(“+”); result += Term(); } return result; © 숙대 창병모

예제 그림 4.12 Term  Factor {* Factor} 순환-하강 파싱하면서 동시에 항(Term)의 값을 계산 int Term(void) { int result = Factor( ); while (token == “*”) { match(“*”); result *= Factor(); } return result; © 숙대 창병모

숙제 #1 그림 4.12의 순환-하강 파서/계산기 확장 뺄셈(-), 나눗셈(/) 추가 비교연산(==, !=, >, <, !) 추가 문법(EBNF) E  AE | AE == AE | AE != AE | AE > AE | AE < AE | !E AE  T {+ T | -T} T  F {* F | / F} F  N | (E) N  D {D} © 숙대 창병모