목차
📁 Context Free Grammar(CFG)
📌 Context Free Grammar란 문맥을 고려하지 않고 항상 동일한 문자열을 표현하는 문법이다.
CFG는 Terminal, nonterminal, production으로 구성되어있고, 각 요소의 의미는 다음과 같다.
Terminal이란 기초 기호(literal)를 뜻한다.
Nonterminal이란 production에 의해 최종적으로 terminal로 치환되는 기호를 말한다.
Production(rule)이란 nonterminal을 치환하는 규칙을 말한다.
CFG와 각 요소의 예시는 다음과 같다.
위 요소들을 이용하여 정의된 CFG의 엄밀한 정의는 다음과 같다.
위 정의로 표현된 예시는 다음과 같다.
Context Free Grammar는 Regular Expression에 비해 풍부한 표현력을 제공한다.
예를 들면 다음과 같다.
대부분의 프로그래밍 언어는 regular language가 아니기 때문에 regular expression만 사용하기에는 표현력이 부족하다.
그렇기 때문에 CFG(문맥 자유 문법)의 풍부한 표현력을 활용하여 Context-free language로 정의하는 방법을 이용한다.
CFG로 RE가 표현 가능한 모든 언어를 표현할 수 있지만,
regular language에 대해서는 RE가 더 간결한 표현방식을 제공하기 때문에 언어를 정의할 때 CFG와 RE를 함께 사용한다.
Regular Expression : 어휘목록 정의
Context-free grammar : 구문구조 정의
📁 Backus-Naur Form(BNF)
Backus-Naur Form(BNF)란 Context free Grammar 기술을 위한 표기법이다.
John Backus와 Peter Naur가 ALGOL58 및 ALGOL60을 기술하기위해 정의했다.
단순화를 위해 앞으로의 포스팅에서는 아래와 같이 정의한다.
CFG를 BNF로 표기한 것의 예시는 다음과 같다.
📁 String Generatin from CFG
📌 derivation(유도)란 Nonterminal에 production을 적용하여 치환하는 과정이다.
Context free grammar로부터 문자열을 생성하는 과정은 다음과 같다.
먼저 시작 nonterminal부터 시작하여 모든 nontermianl에 대해 production을 반복적용한다.
이는 Production의 LHS를 RHS로 치환하는 것이다.
마지막으로 Terminal만 남으면 문자열 생성이 완료된 것이다.
예시는 다음과 같다.
📁 String acceptance in CFG
📌 Parse(파스)란 production을 역으로 적용하는 과정이다.
📌 Parsing(파싱)이란 parse를 통해 문자열이 언어에 속하는지 판단하는 과정이다.
문자열 s가 언어 L(G)에 속하는지 여부를 판단하는 과정은 다음과 같다.
문자열에 production을 역으로 적용한다.
이는 production의 RHS를 LHS로 치환하는 것이다.
문자열이 시작 nonterminal로 치환될때까지 반복적용하고,
시작 nonterminal로 치환되면 문자열 s가 언어 L(G)에 속해있는것이다.
예시는 다음과 같다.
📝 CFG와 Parsing 예시
📁 Parse tree(derivation tree)
📌 Parse tree란 parse과정 및 유도 과정을 나타내는 트리형 자료구조이다.
각 노드는 terminal 또는 nonterminal이다.
- Internal node : nonterminal
- Root node : 시작 nonterminal
- Leaf node : terminal (or symbol)
트리의 부모, 자식 관계는 production에 의한 치환 관계이다.
리프 노드를 좌측부터 우측으로 나열하면 대상 문자열이다.
예시는 다음과 같다.
📝 derivation 예시
📝 parsing 예시
📁 Derivation order
Leftmost derivation(좌측우선유도)
Rightmost derivation(우측우선유도)
📁 Ambiguous grammar
