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

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

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

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

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

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

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

예제: 연산자 우선순위 다음 문법은 모호한가? “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>

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

연산자 결합규칙 규칙에서 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>

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>

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문

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

확장 BNF(EBNF)  

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

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

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 …

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

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 ∈ ∑*