Download presentation
Presentation is loading. Please wait.
1
4장 구문(Syntax)
2
(프로그래밍) 언어의 구성 어휘구조(Lexical structure) 구문(Syntax) 의미(Semantics) 단어의 구조
구문 구조 문법을 이용해서 기술 Context-free grammar in BNF(Backus-Naur Form) 의미(Semantics) 프로그램의 의미 자연어를 이용한 기술 수학적 기술 operational semantics, denotational semantics axiomatic semantics
3
4.1 어휘구조(Lexical Structure)
4
어휘구조 어휘구조(Lexical structure) 토큰(Token) ? 토큰의 종류 프로그래밍 언어를 구성하는 단어의 구조
프로그래밍 언어를 구성하는 단어의 이름 토큰의 종류 식별자(identifier) X24, balance, putchar 정수(integer) 12, 350 키워드(keyword) if, while, …
5
토큰 설계 언어의 토큰 정의 토큰 패턴 예 언어의 의미 있는 모든 단어를 정의한다. 토큰을 어떻게 표현할 수 있을까 ?
토큰 패턴 예 Keyword if, for, while, else, … Relop <, <=, =, <>, >, >= Identifier 문자로 시작되는 문자 혹은 숫자들의 스트링 x24, balance, putchar Integer 숫자들의 스트링 314 Literal 문자 스트링 “test string”
6
예제 예 이 문장을 구성하는 토큰들 주의: (,),=,; 들도 토큰이다. Identifier : i,j,z
if (i == j) z = 0; else z = 1; 이 문장을 구성하는 토큰들 Identifier : i,j,z Keyword : if, else Relation op: == Integer : 0, 1 (, ), =, ; 주의: (,),=,; 들도 토큰이다.
7
어휘 분석(Lexical Analysis)
무엇을 하고자 하는가 ? if (i == j) z = 0; else z = 1; 입력은 다음 문자 스트링이다. \tif (i == j)\n\t\tz = 0;\n\telse\n\t\tz = 1; 문제 입력 스트링을 토큰들로 분리해야 한다.
8
토큰의 역할 어휘분석기(lexical analyzer) 어휘분석의 출력
입력 스트링을 토큰 구성 규칙에 따라 토큰들로 분류한다. 어휘분석의 출력 토큰들의 스트림 파서(구문분석기)의 입력이 된다.
9
어휘분석 : 구현 어휘분석 구현은 다음을 해야 한다. 어휘분석기는 “관심 없는” 토큰들을 무시한다.
1. 토큰에 해당하는 부스트링(substring)을 인식한다. 2. 그 토큰의 부스트링을 “값” 혹은 “lexeme”으로 반환한다. 어휘분석기는 “관심 없는” 토큰들을 무시한다. 공백, 주석 등
10
4.2 구문 및 문법
11
구문(Syntax) 프로그래밍 언어의 구문구조는 어떻게 표현할 수 있을까 ?
12
문맥-자유 문법(Context-free Grammar)
프로그래밍 언어의 구문구조 자기호출 구조를 갖는다. 문장 S는 if EXPR then S else S while EXPR do S … 문맥-자유 문법 이러한 자기호출 구조를 자연스럽게 표현할 수 있다.
13
예제 if-then-else 문 단순 수식 S if E then S else S | if E then S | others
E E * E | E + E | (E) | N N N D | D D 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
14
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 productions X Y1 Y2 … Yn where X N and Yi T N {} Notational convention non-terminals are written upper-case terminals are written lower-case
15
CFG에 의해 정의되는 언어 생성 규칙 X Y1 Y2 … Yn 터미널 심볼 핵심 아이디어
대치할 규칙이 없으므로 일단 생성되면 끝 터미널 심볼은 그 언어의 토큰이다. 핵심 아이디어 1. 시작 심볼 S부터 시작한다. 2. 넌터미널 심볼 X를 생성규칙을 적용하여 Y1 Y2…Yn으로 대치한다. 3. 이 과정을 넌터미널 심볼이 없을 때까지 반복한다.
16
유도(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 ) The language L(G) of a CFG G {a1 … an | S * a1 … an and every ai is a terminal}
17
예제 L(G) is the language of a CFG G. Strings of balanced parentheses:
S (S) S The language is ?
18
유도 예제 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 생성할 스트링: 유도 E E + E N + E D + E 3 + E …
19
4.3 파스 트리
20
유도 및 파스 트리 A sequence of production applications 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.
21
유도 예제 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 생성할 스트링: * 5 유도
22
파스 트리
23
유도에 대한 참조(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)
24
유도에 대한 참조(2) 지금까지 좌우선 유도(leftmost derivation)를
각 단계에서 최좌측 넌터미널이 대치되었음 우우선 유도(Rightmost derivation). * 5 주의 좌우선 유도와 우우선 유도 모두 같은 파스트리를 갖는다. 차이점은 파스트리에 가지가 추가되는 순서이다.
25
C Grammar in BNF | declaration-specifiers init-declarator-list ‘;’
translation-unit external-declaration | translation-unit external-declaration external-declaration function-definition | declaration function-definition declaration-specifiers declarator declaration-list compound-statement | declaration-specifiers declarator compound-statement | declarator declaration-list compound-statement | declarator compound-statement declaration declaration-specifiers ‘;’ | declaration-specifiers init-declarator-list ‘;’
26
C Grammar in BNF init-declarator-list init-declarator
init-declarator declarator | init-declarator ‘=‘ initializer declarator pointer direct-declarator | direct-declarator pointer ‘*’ type-qualifier-list pointer | ‘*’ type-qualifier-list | ‘*’ pointer | ‘*’ direct-declarator ID | ‘(‘ declarator ‘)’ | direct_declarator ‘[‘ ‘]’ | direct_declarator ‘[‘ constant_expression ‘]’ | direct_declarator ‘(‘ parameter_type_list ‘)’ | direct_declarator ‘(‘ identifier-list ‘)’ | direct_declarator ‘(‘ ‘)’
27
요약 구문구조 문법을 이용하여 표기 유도(derivation) 파스트리(parse tree) CFG in BNF
좌우선 유도(Leftmost derivation) 우우선 유도(Rightmost derivation) 파스트리(parse tree)
28
4.4 모호성
29
모호성(Ambiguity) * 수식을 위한 문법 스트링 3 * 4 + 5 이 스트링은 두 개의 파스트리를 갖는다.
E E * E | E + E | (E) | N 스트링 3 * 4 + 5 이 스트링은 두 개의 파스트리를 갖는다. E + * 5 4 3 3
30
모호성(2) 모호한 문법(ambiguous grammar) 모호성은 나쁘다
어떤 스트링에 대해 두 개 이상의 좌측 (혹은 우측) 유도를 갖는다. 두 개 이상의 파스 트리를 갖는다. 모호성은 나쁘다 왜 ?
31
모호성 처리 문법 재작성 예 우선 순위를 적용 모호하지 않도록 재작성 E E + T | T T T * F | F
F N | (E) 우선 순위를 적용
32
모호성 예: 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 S2 S1 E2
33
모호성 예 : The Dangling Else
모호하지 않는 문법 E 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 E 앞의 문법과 같은 스트링을 생성한다. 주의 모호성을 다루는 일반적인 규칙은 없다. 모호하지 않는 문법으로 자동적인 변환 방법은 없다.
35
4.5 EBNF와 구문 다이어그램
36
EBNF BNF EBNF E E + T | T T T * F | F F N | (E) N N D | D
37
구문 다이어그램 구문 다이어그램 각 생성규칙을 다이어그램으로 표현 넌터미널 사각형 터미널 원 화살표 순서 예제 그림 4.11
38
4.6 파싱 구현
39
순환-하강 파싱 (recursive-descent parsing)
기본 원리 문법으로부터 직접 파서 프로그램을 만든다. 각 넌터미널 하나의 프로시저(함수,메쏘드)로 구현한다. 프로시저의 동작 생성규칙 우변을 수행하도록 작성한다.
40
예제 Expr Term {+Term} 그림 4.12 void Expr(void) { Term( );
while (token == “+”) { match(“+”); Term(); } 그림 4.12 순환-하강 파싱하면서 동시에 수식의 값을 계산
41
숙제 #2 그림 4.12의 순환-하강 파서 확장 뺄셈(-), 나눗셈(/) 추가 나머지(%)와 거듭제곱(^) 연산
연습문제 4.12, 4.20 참고
Similar presentations
