5. Context-free 문법 5-1. 서 론 5-2. 유도와 유도 트리 5-3. CFG표기법.

Presentation on theme: "5. Context-free 문법 5-1. 서 론 5-2. 유도와 유도 트리 5-3. CFG표기법."— Presentation transcript:

1 5. Context-free 문법 5-1. 서 론 5-2. 유도와 유도 트리 5-3. CFG표기법

2 5-1. 서 론 프로그래밍언어의 구조를 Context-free문법으로 표현 시 장점 간단하고 이해하기 쉽다.
5-1. 서 론 프로그래밍언어의 구조를 Context-free문법으로 표현 시 장점 간단하고 이해하기 쉽다. 표현된 문법으로부터 자동적으로 인식기를 구현 입력된 프로그램의 구조를 생성규칙에 의해 분해 할 수 있으므로 번역에 유용

3 문법 심벌들의 일반적인 표기법 Terminal 심벌 Nonterminal 심벌
a, b, c와 같은 알파벳 시작 부분의 소문자와 숫자 0,1,2,…,9; +, -와 같은 연산자 기호와 세미콜론, 콤마, 괄호와 같은 구분자 ‘if’또는 ‘then’과 같이 ‘과 ’사이에 표기된 문법 심벌 Nonterminal 심벌 A, B, C와 같은 알파벳 시작 부분의 대문자; S는 보통 시작 심벌(start symbol)을 나타낸다. <stmt>나 <expr>과 같이 <와 >로 묶어서 나타낸 문법 심벌 만약 아무런 언급이 없으면 첫번째 생성 규칙의 왼쪽에 있는 것이 시작 심벌이다. Aa1, Aa2, …, Aak와 같이 생성 규칙의 왼쪽이 모두 A인 경우에, Aa1|a2|…|ak로 간단히 표기 할 수 있다. 이것을 A에 대한 택일 규칙이라 부른다.

4 5-2. 유도와 유도 트리(Derivation Tree)
정의 좌측유도(leftmost derivation) 각 단계에서 문장 형태의 가장 왼쪽에 있는 nonterminal을 대치하는 경우  로 표기 우측 유도(rightmost derivation) 가장 오른쪽에 있는 nonterminal을 대치하는 경우 lm rm

5  예 제 정의 5.2  좌측유도의 경우 좌파스(left parse) 우파스(right parse)
E -E  -(E)  -(E+E)  -(id+E)  -(id+id)  우측유도의 경우 E  -E  -(E)  -(E+E)  -(E+id)  -(id+id) 정의 5.2 좌파스(left parse) 좌측 유도에서 적용된 일련의 생성 규칙 순서 우파스(right parse) 적용된 생성 규칙번호의 역순 lm rm rm rm rm rm

6 E T a F + *  예제 a + a * a 1. E E+T 2. E  T 3. T  T*F 4. T  F
5. F  ( E ) F  a E  E + T E  E + T  T + T  E + T*F  F + T  E + T*a  a + T  E + F*a  a + T*F  E + a*a  a + F*F  T + a*a  a + a*F  F + a*a  a + a*a  a + a*a 좌파스 : 우파스 : E T a F Top-down + * 6 4 1 2 3 Bottom-up 1 4 2 6 3 6 1 4 3 2

7 모호성(Ambiguity) 문법 G에 의해 생성되는 어떤 문장이 두개 이상의 유도
트리를 갖는다면 문법 G는 모호하다(ambiguous)한다.  예제 S if C then S else S S  if C then S S  a C  b S if C then else b a

8 E + * id  예제 E  E+E | E-E | E*E | E/E | E^E | -E | (E) | id
id + id * id 연산자 우선순위를 고려한 동등한 문법 expression   expression + term | expression - term | term term  term * factor | term / factor | factor factor  primary^factor | primary primary  -primary | element element  ( expression ) | id E + * id

9 5-3. CFG 표기법 BNF(Backus-Naur Form) nonterminal 심벌 : <와 >로 묶어서 표기
 예제 <id> ::= <letter> | <id><letter> | <id><digit> <letter> ::= a | b | c |  | y | z <digit> ::= 0 | 1 | 2 |  | 8 | 9

10 EBNF(Extended BNF) 메타 심벌 : 반복되는 부분이나 선택적인 부분을 간결하게 표현하기 위한 특수 심벌  예제
<external-name> ::= <alphabet> {<alphanumeric>}07 <alphanumeric> ::= <alphabet> | <digit> <alphabet> ::= a | b | c | | y | z <digit> ::= 0 | 1 | 2 | | 9

11 문법흐름도 (syntax diagram)
terminal x nonterminal B 생성규칙 A::=X1X2X3 Xi가 nonterminal인 경우 Xi가 terminal인 경우 x B X1 X2 Xn … X1 

12 a1 a2 A … an A a a1 A  a2 택일 생성 규칙 A::=a1|a2|…|an EBNF A ::= [a]
EBNF A ::= (a1 | a2) a1 a2 A … an A a a1 A  a2

13 예제 A ::= a | (B) B ::= AC C ::= {+A} a + ) ( B C A