정규 문법과 문맥 자유 문법

정규 문법과 문맥 자유 문법

---

전 컴퓨터 언어 테스트를 공부 하고 있는데 머리를 감싸는 데 문제가 있다는 생각이 하나 있습니다.

정규 문법 이 더 간단하고 모호함을 포함 할 수 없지만 프로그래밍 언어에 필요한 많은 작업을 수행 할 수 없다는 것을 이해했습니다 . 또한 문맥없는 문법 은 모호성을 허용하지만 프로그래밍 언어 (회문과 같은)에 필요한 몇 가지 사항을 허용 한다는 것을 이해했습니다 .

내가 문제를 겪고있는 것은 일반 문법 비 터미널 이 터미널 또는 비 터미널 다음에 터미널에 매핑 될 수 있거나 컨텍스트없는 비 터미널이 터미널과 비 터미널의 모든 조합에 매핑 된다는 것을 알면 위의 모든 것을 어떻게 도출 할 수 있는지 이해하는 것 입니다. .

누군가가이 모든 것을 통합하도록 도울 수 있습니까?

---

일반 문법은 오른쪽 또는 왼쪽 선형이지만 문맥 자유 문법은 기본적으로 터미널과 비 터미널의 조합입니다. 따라서 정규 문법이 문맥없는 문법의 하위 집합임을 알 수 있습니다.

예를 들어 회 문의 경우 형식은 다음과 같습니다.

S->ABA
A->something
B->something

회문은 오른쪽 또는 왼쪽 선형이어야하고 양쪽에 비 터미널을 가질 수 없기 때문에 정규 문법으로 표현할 수 없다는 것을 분명히 알 수 있습니다.

정규 문법은 모호하지 않기 때문에 주어진 비 터미널에 대해 단 하나의 생산 규칙이있는 반면 문맥없는 문법의 경우에는 둘 이상이있을 수 있습니다.

---

여러분이 생각하고 싶은 것은 다양한 펌핑 기본형이라고 생각합니다. 유한 오토마타가 정규 언어를 인식 할 수 있습니다. 컨텍스트 프리 언어에는 스택이 필요하고 컨텍스트 감지 언어에는 두 개의 스택이 필요합니다 (전체 튜링 머신이 필요하다고 말하는 것과 동일).

그래서 우리가 정규 언어 에 대한 펌핑 기본형에 대해 생각해 보면, 본질적으로 모든 정규 언어는 x , y , z의 세 부분으로 나눌 수 있으며 , 여기서 언어의 모든 인스턴스는 xy * z입니다. (여기서 *는 Kleene 반복, 즉 0 개 이상의 y 복사본입니다 .) 기본적으로 확장 할 수있는 하나의 "비 터미널"이 있습니다.

이제 문맥없는 언어는 어떻습니까? 언어 의 문자열을 5 개 부분 인 uvxyz로 나누고 언어의 모든 인스턴스가 i ≥ 0 인 경우 uv ⁱ xy ⁱ z 에있는 상황없는 언어에 대한 유사한 펌핑 기본형 이 있습니다. 이제 두 개의 "비 터미널" 이 있습니다. " 같은 숫자를 가지고 있는 한 복제하거나 펌핑 할 수 있습니다 .

---

일반 문법과 문맥 자유 문법의 차이 : (N, Σ, P, S) : 터미널, 비 터미널, 프로덕션, 시작 상태 터미널 기호

● 형식 문법으로 정의 된 언어의 기본 기호

● abc

비 말단 기호 (또는 구문 변수)

● 생산 규칙에 따라 터미널 기호 그룹으로 대체

● ABC

일반 문법 : 오른쪽 또는 왼쪽 일반 문법 오른쪽 일반 문법, 모든 규칙은 형식을 따릅니다.

1. B → a 여기서 B는 N의 비 터미널이고 a는 Σ의 터미널입니다.
2. B → aC 여기서 B와 C는 N에 있고 a는 Σ에 있습니다.
3. B → ε 여기서 B는 N이고 ε은 빈 문자열, 즉 길이가 0 인 문자열을 나타냅니다.

정규 문법을 남겼고, 모든 규칙은 형식을 따릅니다.

1. A → a 여기서 A는 N에서 비 터미널이고 a는 Σ에서 터미널입니다.
2. A → Ba 여기서 A와 B는 N에 있고 a는 Σ에 있습니다.
3. A → ε 여기서 A는 N이고 ε은 빈 문자열입니다.

문맥 자유 문법 (CFG)

○ 모든 생산 규칙이 V → w 형식 인 공식 문법

○ V는 단일 비 터미널 기호입니다.

○ w는 터미널 및 / 또는 비 터미널 문자열입니다 (w는 비어있을 수 있음).

---

정규식

• 어휘 분석의 기초
• 일반 언어를 나타냅니다.

문맥 자유 문법

• 파싱의 기초
• Represent language constructs

---

Regular grammar:- grammar containing production as follows is RG:

V->TV or VT
V->T

where V=variable and T=terminal

RG may be Left Linear Grammar or Right Liner Grammar, but not Middle linear Grammar.

As we know all RG are Linear Grammar but only Left Linear or Right Linear Grammar are RG.

A regular grammar can be ambiguous.

S->aA|aB
A->a
B->a

Ambiguous Grammar:- for a string x their exist more than one LMD or More than RMD or More than one Parse tree or One LMD and One RMD but both Produce different Parse tree.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

this Grammar is ambiguous Grammar because two parse tree.

CFG:- A grammar said to be CFG if its Production is in form:

   V->@   where @ belongs to (V+T)*

DCFL:- as we know all DCFL are LL(1) Grammar and all LL(1) is LR(1) so it is Never be ambiguous. so DCFG is Never be ambiguous.

We also know all RL are DCFL so RL never be ambiguous. Note that RG may be ambiguous but RL not.

CFL: CFl May or may not ambiguous.

Note: RL never be Inherently ambiguous.

---

A grammar is context-free if all production rules have the form: A (that is, the left side of a rule can only be a single variable; the right side is unrestricted and can be any sequence of terminals and variables). We can define a grammar as a 4-tuple where V is a finite set (variables), _ is a finite set (terminals), S is the start variable, and R is a finite set of rules, each of which is a mapping V
regular grammar is either right or left linear, whereas context free grammar is basically any combination of terminals and non-terminals. hence we can say that regular grammar is a subset of context-free grammar. After these properties we can say that Context Free Languages set also contains Regular Languages set

---

Basically regular grammar is a subset of context free grammar,but we can not say Every Context free grammar is a regular grammar. Mainly context free grammar is ambiguous and regular grammar may be ambiguous.

---

a regular grammer is never ambiguous because it is either left linear or right linear so we cant make two decision tree for regular grammer so it is always unambiguous.but othert than regular grammar all are may or may not be regular

참고URL : https://stackoverflow.com/questions/559763/regular-vs-context-free-grammars