정규 문법과 문맥 자유 문법

정규 문법과 문맥 자유 문법

위는 Noam Chomsky의 4 가지 언어 유형이다.
안으로 들어갈수록 문법의 제약, 구속력이 강해진다고 보면 된다

context-senstive가 한국어, 영어 등이라 생각하면 된다

이 4가지 언어 유형 중 정규 문법과 문맥 자유 문법이 프로그래밍 언어에 딱 맞아서

정규 문법을 이용하여 어휘 분석(lexical analysis)을 수행하고, 문맥 자유 문법을 이용하여 구문 분석(syntax analysis)을 수행합니다.

대부분의 프로그래밍 언어의 오류를 찾기 위해서 문맥 자유 문법을 사용한다

정규 문법(regular grammar)

모든 규칙이 다음과 같은 형태를 가지는 문법을 말합니다.

A -> aB

A -> a

A -> ε

A와 B는 비터미널 심볼(nonterminal symbol)
a는 터미널 심볼(terminal symbol)
ε는 빈 문자열(empty string)을 나타냅니다.

정규 문법은 주로 언어의 구문 분석에 사용되며, 정규 표현식(regular expression)과 같은 형식 언어(formal language)의 기본적인 표현 방법 중 하나입니다.

비터미널 심볼(nonterminal symbol)

• 다른 비터미널 심볼 또는 터미널 심볼로 대체될 수 있습니다.
• 예를 들어 위의 정규 문법에서 A가 다른 비터미널 심볼이나 터미널 심볼로 대체될 수 있다는 의미입니다.

Right-linear G 와 Left-linear G

A -> βB | β ; right-linear G

A -> Bβ | β ; left-linear G

A -> ε

이 문법은 두 개의 버전이 있는 오른쪽 선형 문법과 왼쪽 선형 문법을 모두 포함하는 문맥-자유 문법(Context-Free Grammar)입니다.

비터미널 심볼 A와 B가 있으며, β는 터미널과 비터미널 심볼의 임의 조합입니다.
ε는 빈 문자열(empty string)을 나타냅니다.

오른쪽 선형 문법 버전에서는 A가 βB 또는 β와 일치하는 경우입니다.
여기서 β는 A의 오른쪽에 배치됩니다.

왼쪽 선형 문법 버전에서는 A가 Bβ 또는 β와 일치하는 경우입니다.
여기서 β는 A의 왼쪽에 배치됩니다.

종료 규칙은 A -> ε입니다.
이 규칙은 A가 빈 문자열(empty string)과 일치하는 경우를 나타냅니다.

• right-linear G와 left-linear G의 차이 = 규칙의 형태와 비터미널 노드의 위치
  • right-linear G는 모든 규칙이 A -> βB 또는 A -> β 형태
    • 비터미널 노드가 오른쪽에 위치합니다.
  • left-linear G는 모든 규칙이 A -> Bβ 또는 A -> β 형태
    • 비터미널 노드가 왼쪽에 위치합니다.

문맥자유 문법(context-free grammar)

A -> β

• 하나의 비터미널 심볼 A는 하나 이상의 비터미널 또는 터미널 심볼 β로 대체 가능
• A는 논터미널 집합의 원소 비터미널 심볼 A는 문법에서 다른 심볼을 생성하기 위한 규칙의 좌변에 사용됩니다.
• β는 논터미널 집합 또는 터미널 집합의 원소
  • 비터미널 심볼 A를 생성하기 위해 사용될 수 있는 비터미널 또는 터미널 심볼들의 조합
• β ∈ (N ∪ T)* : 비터미널 또는 터미널 심볼들의 임의의 조합이 될 수 있습니다.

문맥 자유 문법은 정규 문법과 다른 점이 있습니다.

문맥 자유 문법은 비터미널 심볼이 하나 이상의 심볼로 대체될 수 있는 반면, 정규 문법은 비터미널 심볼이 오직 하나의 터미널 또는 비터미널 심볼로 대체될 수 있습니다.

또한, 문맥 자유 문법은 괄호 쌍이나 재귀적인 구조를 나타내는데 유용합니다

정규 문법 VS 문맥 자유 문법 : 변환으로 알아보자

문맥 자유 문법의 형식과 달리, 정규 문법에서는 A가 단일 터미널 심볼(a) 또는 다음 비터미널 심볼(B)을 따라오는 형태여야 합니다.

따라서 A -> β를 정규 문법으로 표현하려면 A가 단일 터미널 심볼 또는 다음 비터미널 심볼을 따라오는 규칙으로 변경해야 합니다.

예를 들어, A -> β를 정규 문법으로 표현하면 다음과 같이 됩니다.

A -> aB | a | bB | b | ...

이 규칙은 A가 a 또는 b와 함께 나타날 수 있으며, 다음 비터미널 심볼이 B일 수도 있고 없을 수도 있다는 것을 나타냅니다.

결론

문맥 자유 문법에서는 논터미널 심볼이 어떤 터미널 심볼 또는 논터미널 심볼의 시퀀스로 치환될 수 있는 모든 경우를 표현합니다.
따라서, A -> β라는 규칙에서 β는 논터미널 심볼 또는 터미널 심볼의 시퀀스로 구성될 수 있으며, 경우의 수를 모두 포함하고 있습니다.

반면에 정규 문법에서는 A -> β라는 규칙에서 β는 터미널 심볼의 시퀀스로만 구성되어야 하고, 경우의 수를 모두 포함하지는 않습니다.

레퍼런스

• [[문맥 자유 문법]]
• [[정규 문법]]