[프로그래밍 언어론]Context Free Grammar에 대한 설명

소개글

Context Free Grammar에 대한 이론과 실제 문법을 통한 적용 예를 레포트로 작성

목차

없음

본문내용

►개요
-언어학자 Chomsky가 제시한 4가지 언어 유형중 하나 : 프로그래밍 언어의 구문 을 이해하는데 유용하다고 판단해서 사용하게 됨
-문장에 있는 임의의 변수는 그 변수를 좌변으로 같는 생성 규칙에 의하여 치환 될 수 있다는 개념
ex)문법 G는 Context Free Grammar라고 가정하고
G = {{S}, {a, b}, S, P}일 경우에
S -> aSa
S -> bSb
S -> λ
일때 이 문법에 의한 유도는
S => aSa => aaSaa => aabSbaa => aabbaa 로 이루어 진다.
여기서 이문법에 의해 정의되는 언어를 발견할수 있다.
문법 L = {a, b}^n

-Context Free Grammar의 4가지 구성 요소
1. terminal 기호 : token
2. nonterminal 기호
3. 생성규칙
왼쪽은 nonterminal 기호 => 오른쪽은 terminal 기호 or nonterminal 기호
4. 출발기호 : nonterminal 기호로, 만약 언급이 없다면 첫 번째 생성규칙에 왼쪽에 있는 nonterminal 기호가 출발 기호가 된다.

ex)10진수 연산의 표기 방식을 예로 들면

<expr> -> <expr> + <expr>
| <expr> + <digit>
| <digit>
<digit> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

참고 자료

없음