3장 구문과 의미론 2017. 3. 22 순천향대학교 컴퓨터공학과 하상호

목차 구문 의미론 BNF 표기법 문법과 유도 파스 트리 모호성 연산자 우선순위 확장된 BNF 연산 의미론 공리 의미론 표기 의미론

서론 언어 기술을 위한 방법 구문(syntax) 의미론(semantics) 예제: C의 if 문장 식, 문장, 프로그램 단위의 형태 또는 구조에 대한 형식 의미론(semantics) 식, 문장, 프로그램 단위의 의미 예제: C의 if 문장 구문: if(<식>) <문장> 의미:

서론 범용적 구문 표기법이 존재하나, 의미론의 경우 아직 부재 구문과 의미론은 언어의 정의를 제공 언어 정의를 사용하는 사람들 언어의 평가자 언어 구현자 언어 사용자 (프로그래머)

구문 기술: 용어 알파벳(alphabet) 문장(sentence) 언어(language) 어휘항목(lexeme) 언어 기호들의 집합 문장(sentence) 알파벳 문자들로 구성된 문자열 언어(language) 문장들의 집합 어휘항목(lexeme) 가장 낮은 수준의 구문 단위 수치 리터럴, 연산자, 특수어 등 프로그램은 어휘항목들로 구성된 문자열 토큰(token) 어휘 항목의 한 분류 Ex. In C, index = 2 * count + 17;

언어의 형식적 정의 언어 인식기 언어 생성기 언어 생성기와 인식기간의 관계 언어 L의 알파벳으로 구성된 입력 문자열을 읽어들여서 L에 속하는지를 판단(accept/reject)하는 인식 장치 R을 고려 R이 L의 모든 문자열을 수락하면, R은 L의 기술이다. Ex. 컴파일러의 구문분석기 언어 생성기 언어의 문장들을 생성하는데 사용될 수 있는 장치 특정 문장의 구문이 올바른지를 판단하기 위해서, 문장 구문과 생성기의 구조를 비교하여 결정 Ex. 문법 언어 생성기와 인식기간의 관계 형식 언어와 컴파일러 설계 이론의 연구 성과

구문 기술 형식적 방법 문맥-자유 문법(context-free grammars) 1950년대 중반, Noam Chomsky(1928~)에 의해서 개발 자연 언어에 대한 구문 기술 목적으로 4가지 유형 언어 생성기 정의 프로그래밍 언어 기술에 유용한 2가지 유형 정의 정규 문법(regular grammars) 문맥-자유 문법 BNF(Backus-Naur Form)(1959) 구문을 기술하는 표기법 John Backus가 고안 (Algol 58 기술) 이를 Peter Naur가 수정(Algol 60 기술) BNF는 문맥자유 문법과 동일

BNF 기본 사항 프로그래밍 언어를 기술하기 위한 메타 언어(metalanguage) 추상화를 통한 구문 구조 유형 표현 추상화는 구문 변수로 사용 논터미널 기호(nonterminal symbols) 또는 터미널(terminals) 터미널은 어휘항목 또는 토큰 규칙 표현 (또는 생성(production)) LHS, RHS로 구성 LHS(left-hand side): 한 개의 논터미널로 표현 RHS(right-hand side): 터미널과 논터미널들로 구성된 문자열로 표현 Ex. <ident_list> → identifier | identifier,<ident_list> <if_stmt> → if <logic_expr> then <stmt>

BNF 기본 사항 문법 (BNF 기술) 한 개 이상의 규칙들로 구성 시작 기호(start symbols)은 문법에 포함된 특정 논터미널 기호 형식적 정의 G = (N, T, S, P) N: 논터미널들의 집합 T: 터미널들의 집합 S ∈ N: 시작 기호 P: 생성 규칙들의 집합

BNF 규칙 한 규칙이 두 개 이상의 RHS를 포함 가능 <stmt>  <single_stmt> <stmt>  begin <stmt_list> end | begin <stmt_list> end

BNF 규칙 리스트 명세: 재귀를 사용하여 기술 <ident_list>  ident | ident, <ident_list>

BNF 기본 사항 BNF 단순하나, 프로그래밍 언어의 구문 대부분을 기술 구조들의 리스트 표현 구조들의 순서 표현 깊이에 제한 없는 중첩 구조 표현 연산자 우선순위, 결합법칙 표현 등

문법과 유도 문법은 언어를 정의하기 위한 생성장치 언어의 문장들은 문법의 시작 기호(start symbol)로부터 시작되는 일련의 규칙 적용을 통하여 생성된다. 이러한 일련의 규칙 적용을 유도(derivation)라 부른다.

예제: 문법 “begin A = B+C; B=C end”의 문장이 문법 G1으로부터 생성되는가? 문법 G1 <program> → begin <stmt_list> end <stmt_list> → <stmt> | <stmt>; <stmt_list> <stmt> → <var> = <expression> <var> → A | B | C <expression> → <var> + <var> | <var> - <var> | <var> “begin A = B+C; B=C end”의 문장이 문법 G1으로부터 생성되는가?

유도(derivations) 유도 방법 문법의 시작 기호부터 시작 유도의 각 단계를 ‘A => B’로 표현 B는 현 단계의 문자열, A는 이전 단계의 문자열 A에 포함된 한 개의 논터미널을 그 논터미널의 정의로 대체한다 이를 A로부터 B를 유도한다(derive)라고 읽는다 유도 단계의 각 문자열을 문장 형태(sentential form)이라 부른다 유도 단계의 문자열에 논터미널이 존재하지 않으면 유도는 종료된다. 이 때의 문자열을 문장(sentence)라 한다.

유도(derivations)  

예제: 유도 “begin A = B+C;”의 문장이 문법 G1으로부터 생성되는가? 문법 G1 <program> → begin <stmt_list> end <stmt_list> → <stmt> | <stmt>; <stmt_list> <stmt> → <var> = <expression> <var> → A | B | C <expression> → <var> + <var> | <var> - <var> | <var> “begin A = B+C;”의 문장이 문법 G1으로부터 생성되는가?

유도 방식 최좌단 유도(leftmost derivation) 최우단 유도(rightmost derivation) 각 단계의 문장형태에 존재하는 여러 개의 논터미널중에서 가장 좌측에 위치한 논터미널이 규칙 적용을 위해서 선택된다. 최우단 유도(rightmost derivation) 각 문장형태에서 가장 우측에 위치한 논터미널이 규칙 적용을 위해서 선택된다.

Example: 유도 “A = B * (A + C )”의 문장에 대한 최좌단 유도를 보여라. 문법 G2 <assign>  <id> = <expr> <id>  A | B |C <expr>  <id> + <expr> | <id> * <expr> | (<expr>) | <id>

파스 트리(parse tree) 문법은 언어 문장들에 대한 계층적 구조를 자연스럽게 표현

파스 트리(parse tree) Ex. 다음 문법으로부터 생성된 문장 “A=B*(A+C)”의 파스 트리는? <assign>  <id> = <expr> <id>  A | B |C <expr>  <id> + <expr> | <id> * <expr> | (<expr>) | <id>

파스 트리(parse tree) Ex. “A=B*(A+C);”의 파스 트리 문장에 대한 계층적 구조 표현 내부 노드: 논 터미널 잎 노드: 터미널 <assign>  <id> = <expr> <id>  A | B |C <expr>  <id> + <expr> | <id> * <expr> | (<expr>) | <id>

파스 트리와 유도 파스 트리는 유도의 계층적 표현 문장 “A=B*(A+C);”에 대한 유도와 파스 트리는? <assign>  <id> = <expr> <id>  A | B |C <expr>  <id> + <expr> | <id> * <expr> | (<expr>) | <id>

예제 다음 문법을 사용하여 다음 문장에 대한 최좌단 유도와 파스 트리를 보여라. 문장: A = A + ( B * C) <assign>  <id> = <expr> <id>  A | B |C <expr>  <id> + <expr> | <id> * <expr> | (<expr>) | <id>

예제 다음 문법을 사용하여 다음 문장에 대한 파스 트리를 보여라. 문장: A = A + B * C <assign>  <id> = <expr> <id>  A | B |C <expr>  <expr> + <expr> | <expr> * <expr> | (<expr>) | <id>

문법의 모호성 정의 주어진 문법 G가 2개 이상의 다른 파스 트리를 갖는 문장형태를 생성하면, G는 모호하다(ambiguous)라고 말한다.

문법: 모호한 식 <expr>  <expr> <op> <expr> | const <op>  / | - “5 – 3 / 2”의 식은 모호한가?

문법: 모호하지 않는 식 문법 상에 연산자 우선순위를 명세하라. <expr>  <expr> <op> <expr> | const <op>  / | -

문법: 모호하지 않는 식 문법 상에 연산자 우선순위를 명세하라. <expr>  <expr> <op> <expr> | const <op>  / | - 새로운 논터미널을 도입하라: ‘/’이 ‘+’보다 우선순위가 높게