실가동(컴퓨터 사이언스

컴퓨터 과학에서 생산 또는 생산 규칙은 새로운 심볼 시퀀스를 생성하기 위해 재귀적으로 수행될 수 있는 심볼 치환을 지정하는 개서 규칙입니다.형식 문법(구체적으로는 생성 문법)의 사양에서는 유한한 $제작물$ 세트 P $(\style$ P $)$ 가 $P$ 주요 구성요소이다.기타 컴포넌트는 비단말기호의 $유한세트$ N(\ $displaystyle$ N $),$ N $(\displaystyle$ N $)$ 에서 $N$ $N$ 된 유한세트(알파벳이라고 함)의 단자기호의 유한세트 $\Sigma$ ((\ $displaystyle \Sigma)$ 및 $\Sigma$ 시작기호의 $S\in N$ S $S\in N$ N(\ $displaystyle$ S $\in$ N)입니다 $S\in N$ .

제한되지 않은 문법의 경우, u $→$ $u\to v$ {\ $displaystyle u$ \to $u\to v$ v $u\to v$ $u\to v$ 입니다. $u$ 서u {\ $displaystyle$ u}와 $u$ v{\ $displaystyle$ v $}$ 는 $v$ 터미널 및 비터미널의 임의의 $u$ 이며u {\ $displaystyle$ u}는 $u$ 빈 문자열이 될 수 없습니다.v{\ $displaystyle$ $\epsilon$ v $}$ 가 $v$ 빈 문자열인 $경우$ , 이 문자열은 $\epsilon$ "\ $displaystyle$ \ $epsilon$ $\lambda$ "\ $displaystyle$ \ $lambda"$ 로 표시됩니다(오른쪽을 공백으로 두는 대신).그래서 생산은 데카르트 제품의 구성원이다.

V

N

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

V

v

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

( V

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

* V

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

{ *

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

{

{ * } \

times

V^ { * } = (

V

^ { * } \

setminus

\

Sigma

^ { * * } } \

Times

V

^

{ * *

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

} 、

$V:=N\cup \Sigma$ 서 V : $V:=N\cup \Sigma$ $V:=N\cup \Sigma$ { $displaystyle$ V : $= N$ \ cup \ $Sigma$ }는 $V:=N\cup \Sigma$ 어휘 $\cup$ , ${\$ { $displaystyle$ { ${}^{*}$ }^{ * }는 ${}^{*}$ Kleene 스타 $V^{*}NV^{*}$ , V $V^{*}NV^{*}$ $N$ V $V^{*}NV^{*}$ { * } NV $V^{*}NV^{*}$ ∗ { * }는 $V^{*}NV^{*}$ 연결, $\cup$ $\setminus$ display , $stylestylestyle$ 、 \ $displaystyle$ , \ cup $\cup$ ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, 。e. 시작 기호가v {\ $displaystyle$ v}( $v$ 오른쪽 단어)에 $나타나지$ 않도록 하려면 카르트 제품 ^[1]기호의 오른쪽에 있는 V $V^{*}$ {\ {\ $displaystyle$ V $^{*}$ 을 $V^{*}$ (를) $(V\setminus \{S\})^{*}$ $(V\setminus \{S\})^{*}$ { $(V\setminus \{S\})^{*}$ ${\$ {\ $displaystyle (V\setminus$ \{ $S\})^*}$ 로 $(V\setminus \{S\})^{*}$ $V^{*}$ 해야 합니다.

촘스키 계층의 다른 형식 문법은 무엇이 생산을 구성하는지에 추가적인 제한을 가한다.문맥이 없는 문법의 경우, 생산의 왼쪽은 단일 비말단 기호여야 합니다.프로덕션의 형태는 다음과 같습니다.

N\to (N\cup \Sigma )^{*

문법 생성

언어로 문자열을 생성하려면 단일 시작 기호로만 구성된 문자열로 시작하고 규칙을 연속적으로 적용하여(임의의 횟수, 임의의 순서로) 이 문자열을 다시 씁니다.터미널만 포함하는 문자열을 얻으면 이 작업이 중지됩니다.언어는 이 방법으로 생성할 수 있는 모든 문자열로 구성됩니다.이 개서 프로세스에서 선택된 특정 일련의 법적 선택에서는 언어에서 특정 문자열이1개 생성됩니다.이 단일 문자열을 생성하는 방법이 여러 개 있을 경우 문법이 모호하다고 합니다.

예를 들어 알파벳이시작 $기호$ S {\ $displaystyle$ S $S$ 와 b{\ $displaystyle$ b $b$ 로 $a$ $a$ 되어 있으며 다음과 같은 규칙이 있다고 가정합니다.

S\rightarrow aSb

. S

S\rightarrow aSb

S\rightarrow aSb

S\rightarrow aSb

b

(표시

스타일 S

\오른쪽

화살표

aSb)

2.

S\rightarrow ba

S\rightarrow ba

S\rightarrow ba

a

S\rightarrow ba

{\

display

S\

right 화살표

ba

}

그런 다음 S $(\displaystyle$ S $S$ 부터 시작하여 적용할 규칙을 선택할 수 있습니다.규칙 1을 선택하면 S $(\displaystyle$ S $)$ 를 $S$ $(\displaystyle aSb)$ 로 $aSb$ $S$ 하고 $문자열$ S $(\displaystyle aSb$ 를 얻습니다.규칙 1을 다시 선택하면 S $(\displaystyle$ S $)$ 를 $S$ $Sb$ $(\displaystyle Ab$ )로 $aSb$ $S$ 하고 $문자열$ $(\displaystyle Abbb$ 를 얻습니다.이 과정은 알파벳 기호( $예$ : \ $displaystyle$ a $\$ $displaystyle$ b $)$ 만 있을 때까지 반복됩니다.규칙 2를 선택하면 S $(\displaystyle$ S $)$ 를 $S$ $(\displaystyle$ ba $)$ 로 $ba$ $S$ 하고 $문자열$ $a$ $a$ $b$ $a$ b $(\displaystyle aababb$ 를 얻습니다.이 일련의 선택지는 S this $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ S b $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ 、 $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ b b $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ b $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ b \ $display style$ Sb \ $Rightarrow aa$ Sbb \ Rightarrow aa Sbb \ $Rightarrow$ aa $aabb$ $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ 를 사용하여 보다 간단하게 작성할 수 있습니다.문법의 언어는 다음 프로세스를 사용하여 생성할 수 있는 모든 문자열의 $\{ba,abab,aababb,aaababbb,\dotsc \}$ 입니다 $\{ba,abab,aababb,aaababbb,\dotsc \}$ b $\{ba,abab,aababb,aaababbb,\dotsc \}$ , $\{ba,abab,aababb,aaababbb,\dotsc \}$ b $\{ba,abab,aababb,aaababbb,\dotsc \}$ , $\{ba,abab,aababb,aaababbb,\dotsc \}$ $\{ba,abab,aababb,aaababbb,\dotsc \}$ $\{ba,abab,aababb,aaababbb,\dotsc \}$ , $\{ba,abab,aababb,aaababbb,\dotsc \}$ $\{ba,abab,aababb,aaababbb,\dotsc \}$ b , $\{ba,abab,aababb,aaababbb,\dotsc \}$ b $\{ba,abab,aababb,aaababbb,\dotsc \}$ $\{ba,abab,aababb,aaababbb,\dotsc \}$ , $}$ { $display$ style \ { $ba$ , $ab$ , $aabb$ , $aabb$ , \ $dotsc$ \ $\{ba,abab,aababb,aaababbb,\dotsc \}$ }

「」를 참조해 주세요.

형식 문법
유한 오토마타
생성문법
L계
재작성 규칙
Backus-Naur 형식(문맥이 없는 문법의 산물을 쓰기 위한 콤팩트 형식)
구 구조 규칙
포스트 표준 시스템(Emil Post의 생산 시스템 - 계산 모델)

레퍼런스

^ Klaus Reinhardt: Wayback Machine에서 Priorityatzahlerautomaten und die Synchronization von Halbspursprachen Archived 2018-01-17 참조; Fakultét Informatik der Universitét Stutt Stutt; 1994 (독일어)

[KR1994-1] Klaus Reinhardt: Wayback Machine에서 Priorityatzahlerautomaten und die Synchronization von Halbspursprachen Archived 2018-01-17 참조; Fakultét Informatik der Universitét Stutt Stutt; 1994 (독일어)

[1]

Search

실가동(컴퓨터 사이언스

네임스페이스

더

문법 생성

「」를 참조해 주세요.

레퍼런스

Search

실가동(컴퓨터 사이언스

문법 생성

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.