정규 문법

정규 문법(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 -> β 형태
    • 비터미널 노드가 왼쪽에 위치합니다.

레퍼런스

• 정규 문법
• 정규 문법 표현하는 방법
• 문법의 표기법
• 비결정적 오토마타? 2 - 필기
• 정규 언어, 정규 문법, 유한 오토마타의 동치 관계
• 프로그래밍 언어 정의하는 방법
• M - 3장 구문 복습
• BNF (Backus-Naur Form)
• 정규 문법의 연산 순서
• 정규 문법과 문맥 자유 문법
• M - 구문 - 체크포인트
• R - 카카오 개발자 - 2021년 회고
• 어휘 분석(lexical analysis)
• M - 형식 언어 복습
• M - 문맥 자유 문법
• M - 3.1 컴파일러의 이해 노트 정리
• M - 3장 구문 필기

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>