형식 문법

형식 언어 이론에서, 문법(문맥이 주어지지 않을 때, 종종 명확성을 위한 형식 문법이라고 불린다)은 언어의 구문에 따라 유효한 언어의 알파벳으로부터 문자열을 형성하는 방법을 기술한다.문법은 문자열의 의미나 어떤 컨텍스트에서 문자열로 수행할 수 있는 작업을 기술하지 않고 형식만 기술합니다.형식 문법은 형식 언어에서 이러한 문자열에 대한 생성 규칙 집합으로 정의됩니다.

형식 언어 이론, 형식 문법과 언어를 연구하는 학문인 형식 언어 이론은 응용 수학의 한 분야이다.그것의 응용은 이론 컴퓨터 공학, 이론 언어학, 형식 의미론, 수리 논리학 및 기타 분야에서 발견됩니다.

형식 문법은 스트링을 다시 쓰기 위한 규칙 집합이며, "시작 기호"와 함께 다시 쓰기가 시작됩니다.그러므로, 문법은 보통 언어 발생기로 생각됩니다.그러나, 이것은 때때로 특정 문자열이 언어에 속하는지 또는 문법적으로 올바르지 않은지를 결정하는 컴퓨팅 함수인 "인식자"의 기초로 사용될 수도 있습니다.그러한 인식자를 설명하기 위해, 형식 언어 이론은 오토마타 이론으로 알려진 별개의 형식주의를 사용합니다.오토마타 이론의 흥미로운 결과 중 하나는 특정 공식 ^[1]언어에 대한 인식기를 설계하는 것이 불가능하다는 것이다.파싱은 발화(자연어 문자열)를 일련의 기호로 분해하여 언어의 문법에 대해 각각 분석함으로써 인식하는 과정입니다.대부분의 언어들은 구문에 따라 구조화된 발화의 의미를 가지고 있다. 즉, 구성 의미론이라고 알려진 관행이다.그 결과 언어에서 발언의 의미를 설명하는 첫 번째 단계는 그것을 부분별로 분해하고 분석된 형태(컴퓨터 과학에서는 해석 트리, 생성 문법에서는 깊은 구조로 알려져 있음)를 보는 것이다.

역사

이 섹션은 확장해야 합니다.추가하시면 됩니다. (2018년 2월)

파니니의 논문 아스타디아이는 ^[2]산스크리트어의 정식 문법을 기술하기 위한 정식 생산 규칙과 정의를 제공한다."형식"과 "형식"의 용도는 시간이 지남에 따라 해당 작가가 접촉한 분야에 따라 달라졌다.이 개념의 이력 개요는 다음과 같습니다.

도입 예

문법은 주로 문자열을 변환하기 위한 규칙을 다시 쓰는 생산 규칙 집합으로 구성됩니다.각 규칙은 특정 문자열(왼쪽)을 다른 문자열(오른쪽)로 대체하도록 지정합니다.규칙은 왼쪽을 포함하는 각 문자열에 적용할 수 있으며 왼쪽의 오카렌스를 오른쪽의 오카렌스로 치환한 문자열을 생성합니다.

이들 규칙에 의해 완전히 정의되는 반화요일 시스템과 달리 문법은 두 종류의 기호, 즉 비단말기 기호와 종단기호를 더욱 구분합니다.각 왼쪽에 적어도 하나의 비단말기 기호를 포함해야 합니다.또한 시작 기호라고 불리는 특별한 비말단 기호를 구분합니다.

문법에 의해 생성되는 언어는 모든 문자열의 집합으로 정의되며, 비터미널 기호는 어떤 방법으로든 규칙을 적용함으로써 단일 시작 기호로 구성된 문자열에서 생성될 수 있습니다.동일한 단일 문자열을 생성하는 방법이 본질적으로 다를 경우 문법이 모호하다고 합니다.

다음의 예에서는, 단자 기호는 a와 b, 스타트 기호는 S입니다.

예 1

다음과 같은 생산 규칙이 있다고 가정합니다.

$1{\displaystyle }$. S ${\displaystyle \to }$ ${\displaystyle a}$ ${\displaystyle S}$ b$(표시$ 스타일 S$\오른쪽$ 화살표 $aSb)$

2. $S{\displaystyle }$ ${\displaystyle \to }$ ${\displaystyle b}$ a$${\$display$S\$right 화살표$ ba$}$

다음으로 S부터 시작하여 적용할 규칙을 선택할 수 있습니다.규칙 1을 선택하면 문자열 aSb를 얻을 수 있습니다.그런 다음 규칙 1을 다시 선택하면 S를 aSb로 대체하고 문자열 aaSbb를 얻습니다.이제 규칙 2를 선택하면 S를 ba로 대체하고 문자열 aababb를 얻으면 완료됩니다.이 일련의 선택지는 S this${\displaystyle a}$ S b ${\displaystyle 、}$ ${\displaystyle a}$ ${\displaystyle S}$ ${\displaystyle b}$ 、 ${\displaystyle a}$ ${\displaystyle S}$ b b ${\displaystyle 、}$ ${\displaystyle a}$ b ${\displaystyle b}$ b \ $display style$Sb \ $Rightarrow aa$ Sbb \ Rightarrow aa Sbb \ $Rightarrow$ aa $aabb$ $기호$를 사용하여 보다 간단하게 작성할 수 있습니다.

문법의 언어는 무한 집합 $\{{\displaystyle }$ ${\displaystyle a^{}}$ ${\displaystyle {}^{}}$ b ${\displaystyle b^{}}$ n n${\displaystyle {}^{}n}$ n${\displaystyle 0}$ 0${\displaystyle }$} ${\displaystyle =}$ { ${\displaystyle b}$a , ${\displaystyle a}$ ${\displaystyle b}$, ${\displaystyle a}$ ${\displaystyle b}$ , ${\displaystyle a}$ ${\displaystyle b}$ b${\displaystyle }$, a b ${\displaystyle b}$ , ${\displaystyle a}$ b b , b ${\displaystyle b}$ b${\displaystyle }$, . $}$ \ $displaystyle$\ {$a^{n} bab^{n$} \ $mid$n\$geq$\} = \ ${ba$ ,$abba$ , $abscabb,$ bbbbbbbbbb, b입니다.$(특히 displaystyle$ n$)$은 생산 규칙 1이 적용된 횟수를 나타냅니다.이 문법은 문맥이 없고(단일 비터미널만 좌측으로 표시됨) 모호하지 않습니다.

예 2 및 3

대신 다음과 같은 규칙이 있다고 가정합니다.

${\displaystyle 1}$. $S{\displaystyle }$ ${\displaystyle \to }$ \ $displaystyle$S \ $arrow$ a$$}

2. $S{\displaystyle }$ ${\displaystyle \to }$ $($표시 $스타일$ S\$오른쪽$ 화살표$SS)$

3. $a{\displaystyle }$ ${\displaystyle S}$ ${\displaystyle a}$ ${\displaystyle \to }$ $(스타일 aSa\$오른쪽 $화살표$ b$)$

이 문법은 규칙 3으로 인해 문맥이 자유롭지 않으며 규칙 2를 사용하여 S$(\displaystyle$ S$)$의 시퀀스를 생성할 수 있는 방법이 다양하기 때문에 모호합니다.

단, 생성되는 언어는 단순히 \$displaystyle$a $및$/$또는{\displaystyle }$ b$\displaystyle$로 $구성$된 비어 있지 않은 문자열 집합입니다.이것은 쉽게 알 수 있습니다$.S$ {\$displaystyle$ S$\}$에서$b{\displaystyle }$ {\$displaystyle$ b$}$를 생성하려면 규칙 2를 사용하여 ${\displaystyle \mathrm{SSS}}${\$displaystyle SSS$를 2회 생성하고 규칙 1을 2회, 규칙 3을 1회 사용하여$$b {\$displaystyle$ b$\}$를 생성합니다.즉, S$(\displaystyle$ S$)$의 비어 있지 않은 임의의 시퀀스를 생성한 후 원하는 대로 각 시퀀스를$$\$displaystyle$a $또는$ b$(\display b)$로 대체할 수 있습니다.

같은 언어를 문맥이 없고 모호하지 않은 문법에 의해 대신 생성할 수 있습니다. 예를 들어 규칙과 함께 일반 문법이 있습니다.

$1{\displaystyle }$. S ${\displaystyle \to }$ ${\displaystyle a}$ $(스타일$ S\오른쪽 $화살표 aS)$

2. $S{\displaystyle }$ ${\displaystyle \to }$ ${\displaystyle b}$S {$style$ S$\right$ 화살표 $bS}$

${\displaystyle 3}$. $S{\displaystyle }$ ${\displaystyle \to }$\ $displaystyle$S \ $ara$}

$4{\displaystyle }$. S ${\displaystyle \to }$ $(디스플레이 스타일$ S$\오른쪽 화살표$ b$)$

형식적 정의

문법 구문

1950년대에 ^[4][5]노암 촘스키가 처음 제안한 생성 문법의 고전적 형식화에서 문법 G는 다음과 같은 요소로 구성되어 있다.

• G에서 형성된 문자열과 분리되는 비말단 심볼의 유한 집합 N.
• N에서 분리된 단자 기호의 유한 세트$\delta {\displaystyle \mathrm{}}$(\$displaystyle\Sigma$$).$
• 생산 규칙의 유한 집합 P, 형식의 각 규칙

$\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\right 화살표 (\Sigma \cup N)^*}$

여기서 $"{$은 Kleene 스타 연산자이고$$"{$displaystyle$ \cup$}"$은 집합 결합을 나타냅니다.즉, 각 생산 규칙은 1개의 심볼 문자열에서 다른 심볼로 매핑됩니다.첫 번째 스트링(헤드)에는 임의의 수의 심볼이 포함되어 있습니다.단, 이들 중 적어도1개는 비터미널입니다.두 번째 문자열("본문")이 빈 문자열로만 구성되어 있는 경우(즉, 기호를 전혀 포함하지 않음) 혼동을 피하기 위해 특별한 표기법($종종{\displaystyle \mathrm{}}$ ${\\displaystyle \Lambda$ ) 또는 ${\\displaystyle \epsilon$ $）$로 표시할 수 있습니다.

• 시작 기호인 구분 $기호{\displaystyle }$ S${\displaystyle n}$N(\$displaystyle$ S$\in$ N$)$로 문장 기호라고도 합니다.

문법은 공식적으로 튜플$({\displaystyle N,\mathrm{\sigma }}$, ${\displaystyle P,}$ $)$ {$displaystyle(N,\Sigma, P, S$로 정의됩니다.이러한 문법은 ^[6][7]문헌에서는 종종 개서 시스템 또는 구문 구조 문법이라고 불립니다.

형식 문법에 관한 몇 가지 수학적 구성

문법의 연산은 문자열의 관계에 따라 정의할 수 있습니다.

• $문법$이 G ${\displaystyle =}$ (${\displaystyle N}$ , ${\displaystyle \mathrm{\sigma }、}$ ${\displaystyle P}$ ,${\displaystyle S}$) { $displaystyle$ G = ( $N$, \ $Sigma , P$ , $S$)$\}$인 경우, ${\displaystyle \sigma }$ N${\displaystyle {}^{}(}$ $$( ( ${\displaystyle {(}^{}}$ ( in $in$ in in strings strings in in ${\displaystyle \underset{}{g}}$ g g in in in in in in in in$$in in in in in in in in in in in in in in in in in in in in in in in $in$ in in in in in in in in in in in in in given in in in in in in in in in in in in in in in in given in in in in in in in in in

  ${\displaystyle xunderset {G}{\rightarrow }}y\iff \sigma u,v,p,q\in(\Sigma \cup N)^{*}:(x=upv)\wedge(p\rightarrow q\in P)\wedge(y=uqv)}$

• ${\displaystyle \stackrel{}{\underset{}{\mathrm{관계}}}}{\displaystyle \stackrel{}{\underset{}{}}}${\ G${\$ { style } { \$underset$ { * } { \ $underset$ { G $$} { \ rightarrow $}$ } （ G는 0 이상의 스텝으로 파생됨으로 발음됨)는${\displaystyle \underset{g}{}}$G { \ $displaystyle {G}$ { \ $rightarrow }$의 반사적 전이폐쇄로 정의됩니다.
• sententential 형식은 $시작{\displaystyle }$ $기호$S(\$displaystyle$ S$)$에서 한정된 스텝 수로 도출할 수 있는 (\$displaystyle (\Sigma \cup$ N$)^{*})$의${\displaystyle }$멤버입니다.즉, sententententential 형식은 {$}(\$ ${\displaystyle \cup }$ N${\displaystyle {}^{}}$의 멤버입니다${\displaystyle .}$$}{\underset$ {$G}{\rightarrow }}w\$right$\backslash \}\}.$ 비말단 기호를 포함하지 않는 센텐셜 형식($즉,$δ$\displaystyle$ \Sigma$$^{*})을 ^[8]문장이라고 합니다.
• G$(\$$displaystyle$ $G$$)$ ${\displaystyle \mathrm{언어}}$는 G$(\$$displaystyle${L$\}\}($$G)$로 표현되며, G(\$displaystyle$ G$)$

Note that the grammar ${\displaystyle G=(N,\Sigma ,P,S)}$ is effectively the semi-Thue system ${\displaystyle (N\cup \Sigma ,P)}$, rewriting strings in exactly the same way; the only difference is in that we distinguish specific nonterminal symbols, which must be rewritten in rewrite rules, and are only 지정된 시작 $기호{\displaystyle }$S(\$displaystyle$ S$)$에서 비말단 기호 없는 문자열로 다시 쓰기에 관심이 있습니다.

예

이러한 예에서는 set-builder 표기법을 사용하여 형식 언어를 지정합니다.

$문법{\displaystyle }$G(\$displaystyle$ G$)$에 대해 생각해 보겠습니다.$여기$서 N${\displaystyle }$${\displaystyle =}$${\displaystyle }${ $S$ ,$B$$}$ { $displaystyle$ N = { ${\displaystyle S}$$$${\displaystyle 、}$ b ${\displaystyle 、}$$$${\displaystyle c}$ } { $displaystyle$\ $Sigma =$ \$left$ \ {$a$, $b$, $c$\$$right$$ $\}$$$, $S{\displaystyle }$ { $displaystyleft$${\displaystyle }$} = \ displaystyle P$$、

$1{\displaystyle }$. S ${\displaystyle \to }$ ${\displaystyle a}$ ${\displaystyle B}$ ${\displaystyle S}$c { $displaystyle$ S$\right$ 화살표 $aBSC}$

2. $S{\displaystyle }$ ${\displaystyle \to }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}${ $display$ S \ $rightarrow$abc }

3. ${\displaystyle B}$ a ${\displaystyle \to }$ ${\displaystyle a}$ B$$($표시$ 스타일 Ba\$오른쪽$ 화살표 $aB)$

4. ${\displaystyle B}$ b ${\displaystyle \to }$ ${\displaystyle b}$ { $display$Bb \ $rightarrow$ bb$$}

$이$ 문법은 언어${\displaystyle L}$ (${\displaystyle }$G ) ${\displaystyle =}$ { ${\displaystyle a{}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle b^{}}$ n ${\displaystyle c^{}}$ n ${\displaystyle n{}^{}}$n n${\displaystyle 1}$ 1$$} { $display style$L ( G ) = \$left$ \ { a^ { n$}$c^ { $n$} \ $mid n geq$1 \$$right$$ } 를 정의합니다$.$서 n { $displaystyle$a^$${ $n$ } n } \ right $\}$은 $연속$된 $문자열$입니다.따라서 언어는 1개 $이상$의 $a$ $b$ $c{\displaystyle }$$,$ c$,$ $c로 이루어진$ 문자열 집합입니다.

L${\displaystyle }$(${\displaystyle G}$) \ $displaystyle$L ( $G$) 에서의 문자열 파생 예는 다음과 같습니다.

(표기 주: $P{\displaystyle \underset{\mathrm{ii}}{}}$ ${\displaystyle Q}$ ${\displaystyle$ P${\underset {i}{\Rightarrow$}}$Q}$는 "String P generates by production i"로 되어 있으며 생성된 부분은 매번 굵은 글씨로 표시됩니다.)

촘스키 계층

노암 촘스키가 1956년에 ^[4]생성 문법을 처음 공식화했을 때, 그는 그것들을 현재 촘스키 계층으로 알려진 유형으로 분류했다.이러한 유형의 차이는 생산 규칙이 점점 엄격해지고 있기 때문에 공식 언어를 적게 표현할 수 있다는 것입니다.두 가지 중요한 유형은 문맥이 없는 문법(Type 2)과 일반 문법(Type 3)입니다.이러한 문법으로 기술할 수 있는 언어들은 각각 문맥이 없는 언어와 일반 언어라고 불린다.튜링 기계에 의해 받아들여질 수 있는 모든 언어를 표현할 수 있는 제한되지 않은 문법(타입 0)보다 훨씬 덜 강력하지만, 이러한 두 가지 제한된 유형의 문법은 파서가 효율적으로 ^[9]구현될 수 있기 때문에 가장 자주 사용됩니다.예를 들어, 모든 정규언어는 유한상태 머신에 의해 인식될 수 있으며, 문맥이 없는 문법의 유용한 서브셋에는 효율적인 LL 파서를 생성하는 잘 알려진 알고리즘과 문법이 생성하는 언어를 인식하는 LR 파서가 있습니다.

문맥이 없는 문법

문맥이 없는 문법은 각 생성 규칙의 왼쪽이 하나의 비말단 기호로만 구성된 문법입니다.이 제한은 중요하지 않습니다.문맥이 없는 문법으로 모든 언어를 생성할 수 있는 것은 아닙니다.가능한 언어들은 문맥이 없는 언어라고 불립니다.

위에서 정의한 $언어{\displaystyle }$ L$($ $=$ { ${\displaystyle a^{}}$ n ${\displaystyle {}^{}{}^{}}$ ${\displaystyle {}^{}{}^{}}$ c ${\displaystyle n^{}n}$ n n n${\displaystyle 1}$ 1$}$ { $displaystyle$ L(G)=\left$\{a$^{$n}b^{$${\displaystyle n{}^{}}$$}c^{n}\mid$ n$\geq$ 1$\right\}$는 컨텍스트가 없는 언어의${\displaystyle }$펌핑을 사용하여 엄밀하게 증명할 수 있습니다.ft$\{a^{n}b^{n$}\$mid$ n$\geq$ 1$\right\}($최소 $\display style$ a$}$ 뒤에$$ 같은 $수의{\displaystyle }$ b$\display style$ b$\text{'}$s)는 $문법$이 $({$ G_${2$}})로 정의할 수 있으므로 문맥이 없습니다($=$ {$S$left$}\$display $styleft$$S\right$ , $\delta {\displaystyle \mathrm{}}$ ${\displaystyle =}$ {${\displaystyle a}$ , ${\displaystyle b}$ $}$ { $displaystyle$\$Sigma$= \$left$ \ {$a$ ,$b$ \ $right$\ }$$、$S{\displaystyle }$ \ $style$ S$the$ symbol symbol symbol symbol symbol,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

$1{\displaystyle }$. S ${\displaystyle \to }$ ${\displaystyle a}$ ${\displaystyle S}$ b$(표시$ 스타일 S$\오른쪽$ 화살표 $aSb)$

2. $S{\displaystyle }$ ${\displaystyle \to }$ ${\displaystyle a}$ ${\displaystyle b}$\ $display S$\ $arrow$ab

문맥이 없는 언어는 Earley 인식기 등의 알고리즘에 의해${\displaystyle }$O(${\displaystyle {n\mathrm{}}^{}}$ 3$)(\displaystyle O(n^{$3}) 시간(Big O 표기법 참조)으로 $인식$될 수 있습니다.즉, 문맥이 없는 모든 언어에 대해 문자열을 입력으로 사용하여 문자열이 해당 언어의 멤버인지 여부를 O${\displaystyle (}$ $n$ $)($ n ） （ n ^ {$3$} ）$시간$으로 판단하는 머신을 구축할 수 있습니다.$여기$서 n$${ $display style$ n$$}은$$$$ ^[10]문자열의 길이입니다.결정론적 문맥 자유 언어는 선형 ^[11]시간에 인식될 수 있는 문맥 자유 언어의 하위 집합입니다.이러한 일련의 언어 또는 그 서브셋을 대상으로 하는 다양한 알고리즘이 존재합니다.

정규 문법

일반 문법에서는 왼쪽이 다시 하나의 비말단 기호일 뿐이지만 이제 오른쪽도 제한됩니다.오른쪽은 빈 문자열 또는 단일 터미널 기호 또는 단일 터미널 기호 뒤에 비터미널 기호가 이어지는 단일 터미널 기호일 수 있습니다.(더 넓은 정의를 사용하는 경우도 있습니다.단말의 긴 스트링이나 1개의 비터미널을 다른 것 없이 사용할 수 있기 때문에 같은 클래스의 언어를 정의하면서 언어를 쉽게 나타낼 수 있습니다.

위에서 정의한 언어${\displaystyle }${ ${\displaystyle a^{}}$ ${\displaystyle {}^{}{}^{}}$ ${\displaystyle b^{}}$ n${\displaystyle {}^{}n}$ n${\displaystyle 1}$ 1$}$ { $displaystyle \ left$ \ { $a^$ { $n$} $b^$ { $n$} \ $mid$ n$$$geq 1$ \ $right \$ }는$$ 정규가 아니라 언어 $\{{\displaystyle }$ ${\displaystyle a^{}}$ n ${\displaystyle b^{}}$ m${\displaystyle m}$ ${\displaystyle m}$ , n$$ 1$$} { $display style \$ { $a$^ { n { n } b ^ { n } b ^ { $n$} m } \ m } \ m } \ m } \ m { 1 \ m }$$ \ m } \ m $}$ \ m n 1 \ $mid$ e)는 문법 G3({$,$ $A$${\displaystyle ,}$ $}({$ N$=\left\{S, A, B\right$ $\delta {\displaystyle \mathrm{}}$ $=$ {${\displaystyle a,}$ $}$ {$displaystyle$ \$Sigma$=\right$\b},$ {$displaystyle$\Sigma$})$로 정의할 수 있습니다.

1. ${\style S\오른쪽 화살표 aA}$
2. ${\displaystyle A\오른쪽 화살표 aA}$
3. ${\displaystyle A\오른쪽 화살표 bB}$
4. ${\displaystyle B\오른쪽 화살표 bB}$
5. ${\displaystyle B\오른쪽 화살표\epsilon}$

정규 문법에 의해 생성된 모든 언어는 유한 상태 기계에 의해 O${\displaystyle }$(${\displaystyle }$n$$) \ $displaystyle$O ($n$ )${\displaystyle \mathrm{시간}}$ 내에 인식될 수 있습니다.실제 정규 문법은 정규 표현을 사용하는 것이 일반적이지만, 실제로 사용되는 정규 표현의 일부 형태는 정규 언어를 엄격하게 생성하지 않고 그러한 일탈로 인해 선형 인식 성능을 보이지 않습니다.

다른 형태의 생성 문법

촘스키의 원래 형식 문법 계층에 대한 많은 확장과 변형은 언어학자들과 컴퓨터 과학자들에 의해 개발되어 왔으며, 이는 보통 표현력을 증가시키거나 분석하거나 해석하기 쉽게 하기 위해서이다.개발된 문법에는 다음과 같은 형태가 있습니다.

• 트리 결합 문법은 문자열 ^[12]대신 해석 트리에서 다시 쓰기 규칙을 작동시킴으로써 기존의 생성 문법의 표현력을 높입니다.
• 접사 문법과^[13] 속성 문법은^[14][15] 의미 속성과 연산을 통해 재작성 규칙을 증강할 수 있도록 하며, 문법 표현력을 높이거나 실용적인 언어 번역 도구를 구축하는 데 모두 유용합니다.

재귀 문법

재귀 문법은 재귀적인 생산 규칙을 포함하는 문법입니다.예를 들어 A를 맨 왼쪽 기호로 하는 문자열을 생성하기 위해 ^[16]생성 규칙을 통과할 수 있는 비터미널 기호 A가 존재하는 경우 컨텍스트 프리 언어의 문법은 왼쪽 반복적입니다.재귀 문법의 예로는 ^[17]쉼표로 구분된 문장 내의 절이 있습니다.Okoye 계층의 모든 유형의 문법은 ^{[citation needed]}재귀적일 수 있습니다.

분석 문법

해석 알고리즘에 관한 방대한 문헌이 존재하지만, 이러한 알고리즘의 대부분은 해석되는 언어가 처음에는 생성 형식 문법에 의해 기술되며, 목표는 이 생성 문법을 작동하는 파서로 변환하는 것이라고 가정합니다.엄밀히 말하면, 생성 문법은 언어를 해석하는 데 사용되는 알고리즘과 어떤 식으로도 일치하지 않으며, 다양한 알고리즘은 잘 형성된 것으로 간주되는 생산 규칙의 형식에 대해 서로 다른 제약이 있습니다.

대체 접근법은 애초에 분석 문법의 관점에서 언어를 공식화하는 것이며, 이는 언어에 대한 파서의 구조와 의미론에 더 직접적으로 대응한다.분석 문법 형식어의 예는 다음과 같습니다.

• 언어 기계는 제한 없는 분석 문법을 직접 구현합니다.치환 규칙은 출력 및 동작을 생성하기 위해 입력을 변환하는 데 사용됩니다.또한 시스템은 제한 없는 분석 문법의 규칙이 적용되었을 때 어떤 일이 일어나는지 보여주는 lm-diagram을 생성할 수 있습니다.
• TDPL(Top-down parsing language): 1970년대 초에 개발된 매우 미니멀리즘 분석 문법 형식주의로, 하향식 ^[18]파서의 동작을 연구하기 위해 개발되었습니다.
• 링크 문법: 언어학을 위해 설계된 분석 문법의 한 형태로,^[19][20] 단어 쌍 간의 위치 관계를 조사함으로써 구문 구조를 도출합니다.
• PEG(Parsing Expression Grammars): 프로그래밍 언어 및 컴파일러 ^[21]라이터의 실용적인 표현성 요구를 중심으로 설계된 TDPL의 최신 일반화.

「 」를 참조해 주세요.

레퍼런스

외부 링크