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

Presentation on theme: "3장 (2) 구문과 의미론 2017. 4. 3 순천향대학교 컴퓨터공학과 하상호."— Presentation transcript:

1 3장 (2) 구문과 의미론 순천향대학교 컴퓨터공학과 하상호

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

3 연산자 우선순위 다음 문법에서 연산자 우선순위는?
<expr>  <expr> <op> <expr> | const <op>  / | - <expr>  <expr> - <term> | <term> <term>  <term> / const| const

4 연산자 우선순위 문법 상에 연산자 우선순위를 부여
파스 트리의 낮은 위치의 연산자가 높은 위치의 연산자보다 높은 우선순위를 갖는다. 이와 같이 파스 트리상에 연산자 우선순위가 표현되게 하는 문법을 작성하여 모호성을 제거할 수 있다.

5 예제 다음 문법 G는 모호한가? “A = B + C * A”의 문장을 생각하라. 문법 G3
<assign>  <id> = <expr> <id>  A | B |C <expr>  <expr> + <expr> | <expr> * <expr> | (<expr>) | <id>

6 연산자 우선순위 다음 문법에서 연산자의 우선순위는?: =, +, *, ()
<assign>  <id> = <expr> <id>  A | B |C <expr>  <expr> + <expr> | <expr> * <expr> | (<expr>) | <id>

7 예제: 연산자 우선순위 다음의 연산 우선순위가 표현되게 주어진 문법을 수정하라:
‘=‘ < ‘+’ < ‘*’ < () Hint: 새로운 논터미널을 도입하라. <assign>  <id> = <expr> <id>  A | B |C <expr>  <expr> + <expr> | <expr> * <expr> | (<expr>) | <id>

8 예제: 연산자 우선순위 다음 문법은 모호한가? “A = A + B*C”, “A = A*B+C”에 대한 파스 트리를 그려라,
<assign>  <id> = <expr> <id>  A | B |C <expr>  <expr> + <term> | <term> <term>  <term> * <fact> | <fact> <fact>  (<expr>)| <id>

9 연산자 결합규칙 다음 문법은 모호한가? 연산자 결합규칙도 문법상에 표현할 수 있다.
<expr> -> <expr> + <expr> | const <expr> -> <expr> + const | const 연산자 결합규칙도 문법상에 표현할 수 있다.

10 연산자 결합규칙 규칙에서 LHS가 RHS의 처음에 오면, 그 규칙은 좌 순환적(left recursive)이라 한다.
규칙에서 LHS가 RHS의 맨 끝에 오면, 그 규칙은 우 순환적(right recursive)이라 한다. 좌 순환 규칙은 좌결합 법칙을 명세하고, 우 순환 규칙은 우결합 법칙을 명세한다. Ex. 다음 문법에서 각 연산자의 결합규칙은? <assign>  <id> = <expr> <id>  A | B |C <expr>  <expr> + <term> | <term> <term>  <term> * <fact> | <fact> <factor>  <exp> ** <factor> | <exp> <exp>  (<expr>)| <id>

11 If-then-else 문법 다음 문법은 모호한가? <stmt> -> <if-stmt> | …
<if-stmt> -> if <logic_expr> then <stmt> | if <logic_expr> then <stmt> else <stmt> * 다음 문장을 고려하라: if <logic_expr> then if <logic_expr> then <stmt> else<stmt>

12 If-then-else 문법 문법 수정 <stmt> -> <matched> | <unmatched> <matched> -> if <le> then <matched> else <matched> | <non_if_stmt> <unmatched> -> if <le> then <stmt> | if <le> then <matched> else <unmatched> else-있는 if문과 If가 아닌 모든 문장 else-없는 if문

13 문제 다음 문법에 대해서 답하라. 연산자 우선순위는? 연산자 결합법칙은?
우선순위가 +, *보다 높은 단항 연산자 –를 추가하라. <assign>  <id> = <expr> <id>  A | B |C <expr>  <expr> + <term> | <term> <term>  <term> * <fact> | <fact> <fact>  (<expr>)| <id>

14 확장 BNF(EBNF)

15 예제: EBNF 다음 BNF를 EBNF로 나타내라.
<expr>  <expr> + <term> | <expr> - <term> | <term> <term>  <term> * <factor> | <term> / <factor> | <factor>

16 예제: EBNF 다음 BNF를 EBNF로 표현하라.
<assign>  <id> = <expr> <id>  A | B |C <expr>  <expr> + <term> | <expr> - <term> | <term> <term>  <term> * <factor> | <term> / <factor> | <factor> <factor>  <exp> ** <factor> | <exp> <exp>  (<expr>) | <id>

17 BNF, EBNF의 최근 변경사항 구분 최근 변경사항 => : 선택사항 표현 [] 아랫첨자 opt 사용
Ex. proc  name(parameterListopt) 다중선택표현 () “one of” 사용 Ex. Operator  one of + * - / < > 수직바 ‘|’ 각 RHS를 단순히 별도의 줄에 표현 Example: in C statement: for( expr-1opt ; expr-2opt; expr-3opt) statement if (expression) statement while (expression) statement …

18 Test 문제#1 다음에서 L(G)에 속하는 것은? bbaabb bbaba bbaaaabb Abaabb G:
<S>  <A> a <B> b <A>  <A> b | b <B>  a<B> | a

19 Test 문제#1 L(G) = ? Note: Given G = (∑, N, T, S, P),
<S>  <A> a <B> b <A>  <A> b | b <B>  a<B> | a Note: Given G = (∑, N, T, S, P), L(G) = {s | S =>* s} where s ∈ ∑*