형식 문법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

형식 문법은 문자열을 변환하는 규칙들의 집합으로, 시작 기호로부터 규칙을 적용하여 문자열을 생성하는 데 사용된다. 생성 문법은 비단말 기호, 단말 기호, 생성 규칙, 시작 기호로 구성되며, 촘스키 위계에 따라 무제약 문법, 문맥 의존 문법, 문맥 자유 문법, 정규 문법으로 분류된다. 생성 규칙은 문자열을 다른 문자열로 바꾸는 규칙으로, 좌변에는 비단말 기호가 포함되어야 하고, 우변은 비단말 기호와 단말 기호의 조합으로 구성된다. 형식 문법은 트리 인접 문법, 접사 문법, 속성 문법 등으로 확장될 수 있으며, 언어를 파싱하는 데 사용되는 분석 문법 형식으로는 하향식 파싱 언어, 링크 문법, 파싱 표현 문법 등이 있다.

더 읽어볼만한 페이지

오토마타 이론 - 유한 상태 기계
유한 상태 기계는 입력에 따라 상태를 바꾸는 추상적인 기계 모델로, 초기 상태, 전이 함수, 종료 상태 등으로 구성되며 결정적/비결정적 유한 오토마타로 나뉘어 다양한 분야에 활용된다.
오토마타 이론 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
통사론 - 관계절
관계절은 주절 내 명사를 수식하는 절로, 제한적/계속적 관계절, 종속/자유 관계절 등으로 나뉘며 언어별 구성 방식에 따라 여러 유형으로 분류된다.
통사론 - 구 (언어학)
구는 언어학에서 핵과 수식 요소로 구성되어 명사구, 동사구 등으로 나뉘며, 문장 구조 분석에 사용되는 문법 단위이다.
형식 언어 - 문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다.
형식 언어 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.

형식 문법
기본 정보
형식 문법의 추상적인 예.
분야	컴퓨터 과학 언어학
역사
개발자	노엄 촘스키
개발 시기	1956년
종류
종류	생성 문법
특징
관련 개념	형식 언어 오토마타 이론 촘스키 위계
구성 요소
구성 요소	생성 규칙 비단말 기호 단말 기호 시작 기호

2. 생성 문법의 정의 및 기본 원리

생성 문법은 특정 문자열에서 시작하여 정해진 규칙에 따라 새로운 문자열을 만들어내는 방식이다. 예를 들어 다음과 같은 규칙을 보자.

:# $S \,\rightarrow\, aSb$

:# $S \,\rightarrow\, ba$

여기서 $S$ 에서 시작해서 문자열을 생성하면, $ba, abab, aababb, aaababbb$ 와 같은 문자열들이 만들어진다. 예를 들어, $aababb$ 는 $S \,\Rightarrow\, aSb \,\Rightarrow\, aaSbb \,\Rightarrow\, aababb$ 와 같은 과정을 거쳐 생성된다.

좀 더 일반적인 생성 문법의 정의는 다음과 같다. 생성 문법 $G = (N, \Sigma, P, S)$ 는 다음 요소들로 구성된다.^[2]^[3]

중간 기호 (N): 유한한 비단말 기호들의 집합.
말단 기호 (Σ): 유한한 단말 기호들의 집합.
생성 규칙 (P): 유한한 규칙들의 집합. 각 규칙은 $(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*}$ 형태를 가진다.
시작 기호 (S): 문자열 생성을 시작하는 특별한 비단말 기호 ( $S \in N$ ).

여기서

\boldsymbol{L}(G)

는 생성 문법

G

로부터 만들어지는 모든 문자열의 집합을 의미한다.

문법은 주로 문자열을 변환하는 규칙인 생산 규칙으로 구성된다. 각 규칙은 좌변의 문자열을 우변의 문자열로 바꾼다. 규칙은 좌변을 포함하는 문자열에 적용될 수 있으며, 좌변을 우변으로 대체하여 새로운 문자열을 만든다.

문법은 세미-튜 시스템과 유사하지만, 비단말 기호와 단말 기호를 구분한다는 차이점이 있다. 또한, 시작 기호라는 특별한 비단말 기호가 존재한다.

문법에 의해 생성되는 언어는 시작 기호로부터 규칙을 반복 적용하여 만들 수 있는, 비단말 기호가 없는 모든 문자열의 집합이다. 만약 동일한 문자열을 생성하는 서로 다른 방법이 존재한다면, 그 문법은 모호하다고 한다.

예를 들어, 단말 기호는 ''a''와 ''b''이고 시작 기호는 ''S''인 경우를 생각해 보자.

1950년대 노엄 촘스키가 처음 제안한 생성 문법의 형식은 다음과 같다.^[2]^[3]

비단말 기호의 유한 집합 ''N''
단말 기호의 유한 집합 $\Sigma$ (''N''과는 상호 배타적)
생성 규칙의 유한 집합 ''P''. 각 규칙은 다음 형식을 갖는다.

::

(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*}

:여기서

{*}

는 클레이니 스타 연산자이고

\cup

는 합집합을 나타낸다. 즉, 각 생성 규칙은 적어도 하나의 비단말 기호를 포함하는 문자열(머리)을 다른 문자열(본문)로 매핑한다.

''시작 기호''(또는 ''문장 기호'')인 구별되는 기호 $S \in N$

문법은 튜플

(N, \Sigma, P, S)

로 공식적으로 정의된다.

문법의 연산은 문자열 간의 관계를 통해 정의된다.

문법 $G = (N, \Sigma, P, S)$ 가 주어졌을 때, 문자열에 대한 이항 관계 $\underset G \Rightarrow$ ( "G는 한 단계로 유도된다" )는 다음과 같이 정의된다.
: $x \underset G \Rightarrow y \iff \exists u, v, p, q \in (\Sigma \cup N)^*: (x = upv) \wedge (p \rightarrow q \in P) \wedge (y = uqv)$
관계 $\overset * {\underset G \Rightarrow}$ ( "G는 0번 이상 단계로 유도된다" )는 $\underset G \Rightarrow$ 의 반사적 추이 폐쇄로 정의된다.
문장 형태는 시작 기호 $S$ 에서 유한한 단계로 유도될 수 있는 $(\Sigma \cup N)^*$ 의 구성원이다. 즉, 문장 형태는 $\left\{ w \in (\Sigma \cup N)^* \mid S \overset * {\underset G \Rightarrow} w \right\}$ 의 구성원이다. 비단말 기호가 없는 문장 형태(즉, $\Sigma^*$ 의 구성원)를 "문장"이라고 한다.^[7]
$G$ 의 ''언어''는 $\boldsymbol{L}(G)$ 로 표기하며, $G$ 에 의해 구축된 문장의 집합으로 정의된다.

예를 들어,

N = \left \{S, B\right \}

,

\Sigma = \left \{a, b, c\right \}

이고,

S

가 시작 기호이며,

P

가 다음 생성 규칙들로 구성된 문법

G

를 생각해 보자.

: 1.

S \rightarrow aBSc

: 2.

S \rightarrow abc

: 3.

Ba \rightarrow aB

: 4.

Bb \rightarrow bb

이 문법은 언어

L(G) = \left \{ a^{n}b^{n}c^{n} \mid n \ge 1 \right \}

을 정의한다. 여기서

a^{n}

은 ''n''개의 연속적인

a

로 구성된 문자열을 나타낸다. 즉, 이 언어는 1개 이상의

a

와, 그 뒤에 같은 개수의

b

와

c

가 순서대로 나타나는 문자열들의 집합이다.

L(G)

에 있는 문자열 생성 예시는 다음과 같다.

$\boldsymbol{S} \underset 2 \Rightarrow \boldsymbol{abc}$
$\begin{align} \boldsymbol{S} & \underset 1 \Rightarrow \boldsymbol{aBSc} \\$

& \underset 2 \Rightarrow aB\boldsymbol{abc}c \\& \underset 3 \Rightarrow a\boldsymbol{aB}bcc \\& \underset 4 \Rightarrow aa\boldsymbol{bb}cc\end{align}

$\begin{align}$

\boldsymbol{S} & \underset 1 \Rightarrow \boldsymbol{aBSc} \underset 1 \Rightarrow aB\boldsymbol{aBSc}c \\& \underset 2 \Rightarrow aBaB\boldsymbol{abc}cc \\& \underset 3 \Rightarrow a\boldsymbol{aB}Babccc \underset 3 \Rightarrow aaB\boldsymbol{aB}bccc \underset 3 \Rightarrow aa\boldsymbol{aB}Bbccc \\& \underset 4 \Rightarrow aaaB\boldsymbol{bb}ccc \underset 4 \Rightarrow aaa\boldsymbol{bb}bccc \end{align}

(

P \underset i \Rightarrow Q

는 "문자열 P가 생산 i를 통해 문자열 Q를 생성한다"는 의미이며, 생성된 부분은 매번 굵은 글씨로 표시 )

2. 1. 생성 규칙

생성 규칙은 문자열을 다른 문자열로 바꾸는 규칙으로, 좌변과 우변으로 구성된다. 좌변에는 적어도 하나의 비단말 기호가 포함되어야 하며, 우변은 비단말 기호와 단말 기호의 조합으로 구성된다.^[4]

생성 규칙의 예시는 다음과 같다.

:1.

S \rightarrow aSb

:2.

S \rightarrow ba

이 규칙에서 'a'와 'b'는 단말 기호, 'S'는 비단말 기호이자 시작 기호이다. 규칙 1은 "S를 aSb로 바꿀 수 있다"는 의미이고, 규칙 2는 "S를 ba로 바꿀 수 있다"는 의미이다.

이 규칙을 이용하여 문자열을 생성하는 과정은 다음과 같다. 먼저 시작 기호 S에서 시작한다. 규칙 1을 적용하면 S는 aSb가 된다. 다시 규칙 1을 적용하면 aSb는 aaSbb가 된다. 마지막으로 규칙 2를 적용하면 aaSbb는 aababb가 된다. 이 과정을 기호로 나타내면 다음과 같다.

:

S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb

이러한 방식으로 생성될 수 있는 모든 문자열의 집합을 이 문법의 언어라고 한다. 이 예시에서 문법의 언어는 다음과 같다.

:

\{a^nbab^n \mid n \geq 0 \} = \{ba, abab, aababb, aaababbb, \dotsc \}

여기서

a^n

은 a가 n번 반복되는 것을 의미한다. 이 문법은 문맥 자유 문법이며, 모호하지 않다.

1950년대 노엄 촘스키가 제안한 생성 문법의 형식화에서, 문법 ''G''는 다음과 같은 구성 요소로 구성된다.^[2]^[3]

비단말 기호의 유한 집합 ''N''
단말 기호의 유한 집합 $\Sigma$ (''N''과는 상호 배타적)
생성 규칙의 유한 집합 ''P''. 각 규칙은 다음 형식을 갖는다.

::

(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*}

:여기서

{*}

는 클레이니 스타 연산자이고

\cup

는 합집합을 나타낸다. 즉, 각 생성 규칙은 적어도 하나의 비단말 기호를 포함하는 문자열(머리)을 다른 문자열(본문)로 매핑한다.

''시작 기호''(또는 ''문장 기호'')인 구별되는 기호 $S \in N$

2. 2. 단말 기호와 비단말 기호

비단말 기호는 다른 기호로 대체될 수 있는 중간 단계의 기호이며, 단말 기호는 더 이상 다른 기호로 대체될 수 없는 최종적인 기호이다. 형식 문법은 생산 규칙을 통해 문자열을 변환하는데, 이때 비단말 기호와 단말 기호 두 종류의 기호를 사용한다.

예를 들어, 다음과 같은 생성 규칙을 가진 문법을 생각해 보자.

: 1.

S \longrightarrow aSb

: 2.

S \longrightarrow ba

여기서 ''a''와 ''b''는 단말 기호이고, ''S''는 비단말 기호이자 시작 기호이다. 이 문법에서

S

는

aSb

또는

ba

로 대체될 수 있다.

aSb

에서 다시

S

는

aSb

또는

ba

로 대체될 수 있다. 이러한 과정을 반복하면

ba, abab, aababb, aaababbb

등과 같은 문자열을 생성할 수 있는데, 이 문자열들은 모두 단말 기호로만 구성되어 있다.

생성 문법은 일반적으로 다음과 같은 요소로 구성된다.^[2]^[3]

비단말 기호의 유한 집합 $N$
단말 기호의 유한 집합 $\Sigma$ ( $N$ 과 상호 배타적이다.)
생성 규칙의 유한 집합 $P$
시작 기호 $S \in N$

2. 3. 시작 기호

시작 기호는 문법에서 문자열 생성을 시작하는 특별한 비단말 기호이다. 형식 문법 G^영어는 (N, Σ, P, S)로 요약되며, 여기서 S가 시작 기호에 해당한다.^[21]^[22]

생성 문법은 문자열 변환 규칙의 집합이다. 어떤 언어의 문자열을 생성하려면 먼저 하나의 "시작" 문자만으로 이루어진 문자열에서 시작하여 규칙을 적절한 횟수만큼 적용하여 문자열을 바꿔나간다. 이때 시작 문자가 시작 기호이다.

2. 4. 예시

생성 문법은 특정 문자열에서 시작하여 여러 생성 규칙에 따라 문자열을 만들어 내는 방법이다. 예를 들어, 다음과 같은 규칙을 가진 문법이 있다고 가정해 보자.

:1.

S \rightarrow aSb

:2.

S \rightarrow ba

이 문법에서

S

로부터 생성될 수 있는 문자열은

ba, abab, aababb, aaababbb

등이다. 예를 들어,

aababb

는

S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb

와 같은 과정을 통해 생성할 수 있다.

이 문법의 언어는 무한 집합

\{a^nbab^n \mid n \geq 0 \} = \{ba, abab, aababb, aaababbb, \dotsc \}

이며, 여기서

a^k

는

a

가

k

번 반복된 것이다. 이 문법은 문맥 자유 문법이며(왼쪽에는 단일 비단말 기호만 나타남) 모호하지 않다.

다른 예시로, 다음과 같은 규칙을 가진 문법을 생각해 볼 수 있다.

:1.

S \rightarrow a

:2.

S \rightarrow SS

:3.

aSa \rightarrow b

이 문법은 규칙 3 때문에 문맥 자유 문법이 아니며, 규칙 2를 사용하여

S

의 시퀀스를 생성하는 여러 가지 방법이 있기 때문에 모호하다. 이 문법이 생성하는 언어는

a

와/또는

b

로 구성된 모든 비어 있지 않은 문자열의 집합이다.

동일한 언어는 문맥 자유적이고 모호하지 않은 문법으로 대체 생성될 수 있다. 예를 들어, 다음과 같은 규칙을 가진 정규 문법을 사용할 수 있다.

:1.

S \rightarrow aS

:2.

S \rightarrow bS

:3.

S \rightarrow a

:4.

S \rightarrow b

3. 촘스키 위계

촘스키 위계는 노엄 촘스키가 1956년에 생성 문법을 처음 공식화했을 때 제시한 형식 문법의 분류 체계이다.^[2] 촘스키 위계는 생성 규칙에 따른 제약의 정도에 따라 문법을 분류하며, 표현 가능한 언어의 범위가 달라진다. 이 중 가장 중요한 두 가지 유형은 ''문맥 자유 문법''(Type 2)과 ''정규 문법''(Type 3)이다. 이 문법들로 표현 가능한 언어는 각각 ''문맥 자유 언어''와 ''정규 언어''라고 불린다.^[8] 제한 없는 문법(Type 0)은 튜링 기계가 허용하는 모든 언어를 표현할 수 있지만, 문맥 자유 문법과 정규 문법은 파서를 효율적으로 구현할 수 있어 더 자주 사용된다.^[8]

3. 1. 무제약 문법 (Type 0)

촘스키 위계에서 형식 문법은 생성 문법 제약의 양에 따라 무제약 문법부터 시작하여 0~3 타입으로 분류된다. 이는 노엄 촘스키가 1956년 생성 문법을 체계적으로 정의하면서 구성한 것이다.^[1]

3. 2. 문맥 의존 문법 (Type 1)

촘스키 위계에서 형식 문법은 생성 문법 제약의 양에 따라 무제약 문법부터 시작하여 0 ~ 3 타입으로 분류된다. 이는 노엄 촘스키가 1956년 생성 문법을 체계적으로 정의하면서 구성한 것인데, 재귀 문법은 규정하고 있지 않다.

3. 3. 문맥 자유 문법 (Type 2)

촘스키 위계에서 형식 문법은 생성 문법 제약의 양에 따라 무제약 문법부터 0 ~ 3 타입으로 분류된다. 이는 1956년 노엄 촘스키가 생성 문법을 체계적으로 정의하면서 구성한 것으로, 재귀 문법은 규정하고 있지 않다.

'''문맥 자유 문법'''은 각 생성 규칙의 왼쪽이 단일 비단말 기호로만 구성된 문법이다. 이러한 제한은 모든 언어를 문맥 자유 문법으로 생성할 수 없게 하며, 문맥 자유 문법으로 생성할 수 있는 언어를 ''문맥 자유 언어''라고 한다.

L(G) = \left \{ a^{n}b^{n}c^{n} \mid n \ge 1 \right \}

는 문맥 자유 언어에 대한 펌핑 보조정리를 사용하여 문맥 자유 언어가 아님을 엄격하게 증명할 수 있다. 반면,

\left \{ a^{n}b^{n} \mid n \ge 1 \right \}

(최소 1개의

a

다음에 같은 수의

b

가 오는 경우)는 문맥 자유 언어이며,

N=\left \{S\right \}

,

\Sigma=\left \{a,b\right \}

,

S

를 시작 기호로 하는 문법

G_2

와 다음 생성 규칙으로 정의할 수 있다.

: 1.

S \rightarrow aSb

: 2.

S \rightarrow ab

문맥 자유 언어는 빅 오 표기법을 ''참조''하여 얼리 파서와 같은 알고리즘을 통해

O(n^3)

시간 내에 인식할 수 있다. 즉, 모든 문맥 자유 언어에 대해 문자열을 입력으로 받아 해당 문자열이 언어의 구성원인지 여부를

O(n^3)

시간 내에 결정하는 기계를 구축할 수 있으며, 여기서

n

은 문자열의 길이이다.^[9] 결정적 문맥 자유 언어는 문맥 자유 언어의 하위 집합으로, 선형 시간 내에 인식할 수 있다.^[10]

3. 3. 1. 문맥 자유 문법과 한국어

한국어는 교착어의 특성상 어미와 조사의 결합이 복잡하여 문맥 자유 문법만으로는 완벽하게 분석하기 어렵다.^[24]

3. 4. 정규 문법 (Type 3)

촘스키 위계에서 형식 문법은 생성 규칙에 제약이 얼마나 있는지에 따라 0~3 타입으로 분류된다. 노엄 촘스키가 1956년에 생성 문법을 체계적으로 정의하면서 이를 구성하였다.^[21] 정규 문법(Type 3)은 이 중 가장 제한적인 문법이다.

정규 문법에서 좌변은 단일 비단말 기호만 가능하며, 우변은 빈 문자열, 단일 단말 기호, 또는 단일 단말 기호 다음에 비단말 기호가 오는 형태만 허용된다.

정규 문법으로 생성된 모든 언어는 유한 상태 기계로 선형 시간 내에 인식될 수 있다. 정규 문법은 정규 표현식으로 표현되기도 하지만, 정규 표현식이 항상 정규 언어만을 생성하는 것은 아니다.

예를 들어, 언어

\left \{ a^{n}b^{m} \mid m,n \ge 1 \right \}

(최소 1개의

a

다음에 최소 1개의

b

가 오는 경우)는 정규 문법으로 표현 가능하다. 반면,

\left \{ a^{n}b^{n} \mid n \ge 1 \right \}

는 정규적이지 않다. 이는 정규 언어를 이해하는 오토마톤보다 문맥 자유 언어를 이해하는 오토마톤이 더 많은 정보를 유지해야 하기 때문이다.

3. 4. 1. 정규 문법과 한국어

촘스키 위계에서 정규 문법은 생성 규칙의 좌변은 하나의 비단말 기호만 위치하지만, 우변에도 제한이 가해진다. 우변은 하나의 종단 문자 또는 하나의 종단 문자와 하나의 비단말 기호로 구성된 문자열 중 하나만 허용된다. (널리 채택된 정의로, 복수의 종단 문자로 구성되는 문자열 또는 하나의 비단말 기호 중 하나라고 말할 수도 있다. 어느 쪽이든 같은 클래스의 언어를 의미한다.)

정규 문법으로 생성되는 언어는 모두 유한 오토마타로 선형 시간 내에 인식된다. 실제로는 정규 문법은 정규 표현식으로 표시되는 것이 일반적이지만, 정규 표현식이 반드시 정규 문법을 나타내기 위해서만 사용되는 것은 아니다.

\left \{ a^{n}b^{m} | m,n > 0 \right \}

로 표시되는 언어(하나 이상의 'a' 다음에 하나 이상의 'b'가 이어짐)를 정의하는 문법

G3

을 예로 들 수 있다.

G3

은

N=\left \{S, A,B\right \}

,

\Sigma=\left \{a,b\right \}

로 구성되며, 시작 기호

S

와 다음 생성 규칙으로 정의된다.

: 1.

S \rightarrow aA

: 2.

A \rightarrow aA

: 3.

A \rightarrow bB

: 4.

B \rightarrow bB

: 5.

B \rightarrow b

: 6.

S \rightarrow \epsilon

4. 생성 문법의 확장

형식 문법의 촘스키(Chomsky) 원래 계층에 대한 많은 확장과 변형이 언어학자와 컴퓨터 과학자에 의해 개발되었으며, 일반적으로 표현력을 높이거나 분석 또는 구문 분석을 더 쉽게 만들기 위해 개발되었다. 대표적인 문법 형태는 다음과 같다.

트리 인접 문법
접사 문법^[12]
속성 문법^[13]^[14]

이러한 문법들은 형식 문법에 대한 촘스키의 원래 계층에 대해 언어학자나 정보공학자들이 독자적인 확장이나 파생을 시도한 결과물이다. 그 목적은 표현력을 강화하거나 구문 분석을 쉽게 하기 위함이었다. 그러나 표현력이 강화된 형식 문법은 자동화된 도구에 의한 구문 분석이 어려워지는 경향이 있다.

4. 1. 트리 인접 문법 (Tree-Adjoining Grammar)

트리 인접 문법(Tree-adjoining grammar)은 문자열뿐만 아니라 구문 분석 트리에서 재작성 규칙이 작동하도록 하여 기존의 생성 문법의 표현력을 향상시킨다.^[11] ^[25]

4. 2. 접사 문법 (Affix Grammar) 및 속성 문법 (Attribute Grammar)

트리 인접 문법은 문자열뿐만 아니라 구문 분석 트리에서 재작성 규칙이 작동하도록 하여 기존의 생성 문법의 표현력을 향상시킨다.^[11]

접사 문법^[12]과 속성 문법^[13]^[14]은 의미 속성 및 연산을 통해 재작성 규칙을 보강하여, 문법의 표현력을 높이고 실용적인 언어 번역 도구를 구축하는 데 유용하다.

5. 분석 문법

분석 문법은 생성 문법과 반대로, 주어진 문장이 특정 문법에 맞는지 분석하는 데 사용되는 문법 체계이다. 파싱 알고리즘에 관한 많은 연구가 있지만, 대부분은 파싱할 언어가 생성 문법에 의해 기술되고, 이 생성 문법을 작동하는 파서로 변환하는 것을 목표로 한다. 하지만 생성 문법은 언어 파싱에 사용되는 알고리즘에 항상 대응되는 것은 아니며, 다양한 알고리즘은 잘 구성된 것으로 간주되는 생성 규칙의 형식에 대해 서로 다른 제약 조건을 갖는다.

이와 달리, 언어를 분석 문법의 관점에서 형식화하는 접근 방식이 있다. 이는 해당 언어의 파서 구조 및 의미와 더 직접적으로 연결된다. 분석 문법 형식의 예시는 다음과 같다.

하향식 파싱 언어(TDPL): 1970년대 초에 하향식 파싱의 동작을 연구하기 위해 개발된 매우 단순한 분석 문법 형식이다.^[17]
Yacc
[http://languagemachine.sourceforge.net The Language Machine]: 제한 없는 분석적 문법을 직접 구현한 것이다. 치환 규칙은 입력을 변환하여 출력 및 동작을 생성한다. 이 시스템은 제한 없는 분석적 문법의 규칙을 적용했을 때 어떤 일이 일어나는지를 도식화할 수도 있다.

자연어에 대해서도 전산 언어학이나 자연어 처리 등에서 분석 문법이 필요하며, 연구되고 있다.

5. 1. 파싱 표현 문법 (Parsing Expression Grammar, PEG)

파싱 표현 문법(Parsing Expression Grammar, PEG)은 TDPL을 더욱 범용화한 것으로, 프로그래밍 언어나 컴파일러 제작자가 실용적인 표현을 위해 설계한 것이다.

5. 2. 링크 문법 (Link Grammar)

링크 문법은 언어학자들이 설계한 분석적 문법의 한 형식이다. 단어 간의 소유 관계를 조사하여 문장 구조를 파악한다.

6. 한국어와 생성 문법

노엄 촘스키가 1956년 생성 문법을 체계적으로 정의하면서 촘스키 위계에서 형식 문법은 생성 문법의 제약의 양에 따라 무제약 문법부터 시작하여 0~3 타입으로 분류하였다.

참조

_[1] 서적 Formal Languages and Computation: Models and Their Applications https://books.google[...] CRC Press
_[2] 논문 Three models for the description of language 1956-09
_[3] 서적 Syntactic Structures Mouton
_[4] 논문 Structurally and Arithmetically Controlled Grammars https://typeset.io/p[...] 2024-11-05
_[5] 서적 Algebraic and automata theoretic properties of formal languages North-Holland
_[6] 서적 Introduction to Formal Language Theory Addison-Wesley Publishing Company
_[7] 웹사이트 Sentential Forms http://www.seas.upen[...] 2019-11-13
_[8] 서적 Parsing Techniques – A Practical Guide Ellis Horwood
_[9] 논문 An Efficient Context-Free Parsing Algorithm http://ra.adm.cs.cmu[...] 2020-05-19
_[10] 논문 On the translation of languages from left to right 1965-07
_[11] 논문 Tree Adjunct Grammars https://www.scienced[...]
_[12] 간행물 Affix Grammars North Holland Publishing Company
_[13] 논문 Semantics of Context-Free Languages https://www.csee.umb[...]
_[14] 논문 Semantics of Context-Free Languages (correction)
_[15] 웹사이트 Notes on Formal Language Theory and Parsing http://www.cs.may.ie[...] 2017-08-28
_[16] 뉴스 Songbirds grasp grammar, too http://www.newspaper[...] 2006-04-27
_[17] 학위논문 The TMG Recognition Schema http://bford.info/pa[...] 1970-02
_[18] 보고서 Parsing English with a Link Grammar
_[19] 논문 Parsing English with a Link Grammar
_[20] 학위논문 Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking https://dspace.mit.e[...] 2002-09
_[21] 논문 Three Models for the Description of Language
_[22] 서적 Syntactic Structures Mouton
_[23] 서적 Parsing Techniques—A Practical Guide Ellis Horwood
_[24] 논문 An Efficient Context-Free Parsing Algorithm 1970-02
_[25] 논문 Tree Adjunct Grammars
_[26] 간행물 Affix Grammars North Holland Publishing Company
_[27] 논문 Semantics of Context-Free Languages
_[28] 논문 Semantics of Context-Free Languages (correction)
_[29] 학위논문 The TMG Recognition Schema 1970-02
_[30] 학위논문 Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking 2002-09
_[31] 보고서 Parsing English with a Link Grammar
_[32] 논문 Parsing English with a Link Grammar

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com