4장 구문(Syntax)

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

4.1 어휘구조(Lexical Structure)

어휘구조 어휘구조(Lexical structure) 토큰(Token) ? 토큰의 종류 프로그래밍 언어를 구성하는 단어의 구조 프로그래밍 언어를 구성하는 단어의 이름 토큰의 종류 식별자(identifier) X24, balance, putchar 정수(integer) 12, 350 키워드(keyword) if, while, …

토큰 설계 언어의 토큰 정의 토큰 패턴 예 언어의 의미 있는 모든 단어를 정의한다. 토큰을 어떻게 표현할 수 있을까 ? 토큰 패턴 예 Keyword if, for, while, else, … Relop <, <=, =, <>, >, >= Identifier 문자로 시작되는 문자 혹은 숫자들의 스트링 x24, balance, putchar Integer 숫자들의 스트링 314 Literal 문자 스트링 “test string”

예제 예 이 문장을 구성하는 토큰들 주의: (,),=,; 들도 토큰이다. Identifier : i,j,z if (i == j) z = 0; else z = 1; 이 문장을 구성하는 토큰들 Identifier : i,j,z Keyword : if, else Relation op: == Integer : 0, 1 (, ), =, ; 주의: (,),=,; 들도 토큰이다.

어휘 분석(Lexical Analysis) 무엇을 하고자 하는가 ? if (i == j) z = 0; else z = 1; 입력은 다음 문자 스트링이다. \tif (i == j)\n\t\tz = 0;\n\telse\n\t\tz = 1; 문제 입력 스트링을 토큰들로 분리해야 한다.

토큰의 역할 어휘분석기(lexical analyzer) 어휘분석의 출력 입력 스트링을 토큰 구성 규칙에 따라 토큰들로 분류한다. 어휘분석의 출력 토큰들의 스트림 파서(구문분석기)의 입력이 된다.

어휘분석 : 구현 어휘분석 구현은 다음을 해야 한다. 어휘분석기는 “관심 없는” 토큰들을 무시한다. 1. 토큰에 해당하는 부스트링(substring)을 인식한다. 2. 그 토큰의 부스트링을 “값” 혹은 “lexeme”으로 반환한다. 어휘분석기는 “관심 없는” 토큰들을 무시한다. 공백, 주석 등

4.2 구문 및 문법

구문(Syntax) 프로그래밍 언어의 구문구조는 어떻게 표현할 수 있을까 ?

문맥-자유 문법(Context-free Grammar) 프로그래밍 언어의 구문구조 자기호출 구조를 갖는다. 문장 S는 if EXPR then S else S while EXPR do S … 문맥-자유 문법 이러한 자기호출 구조를 자연스럽게 표현할 수 있다.

예제 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

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

CFG에 의해 정의되는 언어 생성 규칙 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 ) The language L(G) of a CFG 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   The language is ?

유도 예제 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  …

4.3 파스 트리

유도 및 파스 트리 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.

유도 예제 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 유도

파스 트리

유도에 대한 참조(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 주의 좌우선 유도와 우우선 유도 모두 같은 파스트리를 갖는다. 차이점은 파스트리에 가지가 추가되는 순서이다.

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 ‘;’

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 ‘(‘ ‘)’

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

4.4 모호성

모호성(Ambiguity) * 수식을 위한 문법 스트링 3 * 4 + 5 이 스트링은 두 개의 파스트리를 갖는다. E  E * E | E + E | (E) | N 스트링 3 * 4 + 5 이 스트링은 두 개의 파스트리를 갖는다. E + * 5 4 3 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 S2 S1 E2

모호성 예 : 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 앞의 문법과 같은 스트링을 생성한다. 주의 모호성을 다루는 일반적인 규칙은 없다. 모호하지 않는 문법으로 자동적인 변환 방법은 없다.

4.5 EBNF와 구문 다이어그램

EBNF BNF EBNF E  E + T | T T  T * F | F F  N | (E) N  N D | D

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

4.6 파싱 구현

순환-하강 파싱 (recursive-descent parsing) 기본 원리 문법으로부터 직접 파서 프로그램을 만든다. 각 넌터미널 하나의 프로시저(함수,메쏘드)로 구현한다. 프로시저의 동작 생성규칙 우변을 수행하도록 작성한다.

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

숙제 #2 그림 4.12의 순환-하강 파서 확장 뺄셈(-), 나눗셈(/) 추가 나머지(%)와 거듭제곱(^) 연산 연습문제 4.12, 4.20 참고