단자 및 단자 이외의 기호

컴퓨터 과학에서 단자와 비단자 기호는 형식 문법을 구성하는 생산 규칙을 규정하는 데 사용되는 어휘적 요소들이다.단자 기호는 공식 문법에 의해 정의된 언어의 기본 기호다.비터미널 기호(또는 구문 변수)는 생산 규칙에 따라 터미널 기호 그룹으로 대체된다.null

특정 문법의 단자와 비단어는 두 개의 불연속 집합이다.null

단자 기호

말단 기호는 형식 문법의 생산 규칙의 산출물에 나타날 수 있는 문자 그대로의 기호로, 문법의 규칙을 사용하여 변경할 수 없다.규칙을 기호의 소스 문자열에 재귀적으로 적용하면 일반적으로 터미널 기호로만 구성된 최종 출력 문자열에서 종료된다.null

두 가지 규칙으로 정의된 문법을 고려하십시오.서로 상호 작용하는 그림 표시 사용:

기호ר될 수 있다ди
기호ר될 수 있다д

여기д다른 것으로 바꾸는 규칙이 없기 때문에 터미널 기호가 된다.다른 한편으로는ר그것을 바꿀 수 있는 두 가지 규칙이 있다, 그러므로 그것은 말단적이지 않다.특정 문법에 의해 정의되거나 생성되는 형식 언어는 문법에 의해 생성될 수 있고 단자 기호만으로 구성된 문자열 집합이다.null

비단어 기호

비터미널 기호는 교체할 수 있는 기호들이다.그것들은 단순히 통사변수라고도 불릴 수 있다.공식 문법에는 시작 기호가 포함되어 있는데, 시작 기호는 언어의 모든 문자열이 생산 규칙의 연속적인 적용에 의해 파생될 수 있다.사실 문법에 의해 정의된 언어는 정확히 그렇게 파생될 수 있는 말단 문자열들의 집합이다.null

문맥 없는 문법이란 각 생산 규칙의 왼쪽이 단 하나의 비단어 기호로만 구성된 문법이다.이 제한은 비독점적이다; 모든 언어가 문맥이 없는 문법들에 의해 생성될 수 있는 것은 아니다.문맥 없는 언어라고 불릴 수 있는 언어들.이것들은 정확히 비결정론적 푸시다운 오토매틱에 의해 인식될 수 있는 언어들이다.문맥 없는 언어는 대부분의 프로그래밍 언어의 구문에 대한 이론적 기초가 된다.null

생산규칙

문법은 어떤 기호가 어떤 다른 기호를 대신할 수 있는지 명시하는 생산 규칙(또는 '생산')에 의해 정의된다; 이 규칙들은 문자열을 생성하거나 그것들을 구문 분석하는 데 사용될 수 있다.그러한 각 규칙에는 교체할 수 있는 문자열로 구성된 머리 또는 왼쪽, 그리고 이를 대체할 수 있는 문자열로 구성된 몸통 또는 오른쪽이 있다.규칙들은 종종 머리 → 몸통 형식에 쓰여진다. 예를 들어, a → b는 a를 b로 대체할 수 있다고 규정한다.null

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

비터미널 기호의 유한 집합 $N$ .
$N$ 과 분리되는 단자 기호의 유한 집합 $σ$ .
양식의 각 규칙인 $생산$ 규칙의 유한 집합 P

{\displaystyle(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\오른쪽 화살표(\Sigma \cup N)^{*}}}}

여기서

∗{\

은

{}^{{*}}

(는

(\Sigma \cup N)^{*}

클렌 스타 운영자이고

(\Sigma \cup N)^{*}

은 세트 유니언을 의미하므로 (

(\Sigma \cup N)^{*}

union N

){\

은 0개

(\Sigma \cup N)^{*}

이상의 기호를 나타내며,

N

은 하나의 비터미널 기호를 의미한다.즉, 각 생산 규칙은 한 줄의 기호에서 다른 문자열로 매핑되며, 첫 번째 문자열에는 최소한 하나의 비터미널 기호가 포함되어 있다.몸이 오로지 빈 끈으로 구성되는 경우.^{[note 1]}혼동을 피하기 위해 특수 표기법(

종종

λ,

e

또는

ε

)으로 표기할 수 있다.

시작 기호인 구별 $S\in N$ 기호 $S\in N$ $S\in N$ $S\in N$ ${\displaystyle S\in$ N $}.$

문법은 순서가 정해진 4중 $\langle N,\Sigma ,P,S\rangle$ $\langle N,\Sigma ,P,S\rangle$ N $\langle N,\Sigma ,P,S\rangle$ , $\langle N,\Sigma ,P,S\rangle$ , P $\langle N,\Sigma ,P,S\rangle$ , $\langle N,\Sigma ,P,S\rangle$ $\langle N,\Sigma ,P,S\rangle$ $\langle N,\Sigma ,P,S\rangele$ 로 정의된다 $\langle N,\Sigma ,P,S\rangle$ 이러한 공식 문법은 종종 문헌에서 재쓰기 시스템 또는 구문 구조 문법이라고 불린다.^[3]^[4]null

예

예를 들어, 다음은 Backus-Naur 형식의 변형으로 표현되는 정수(서명될 수 있음)를 나타낸다.

<자리> ::='0' '1' '2' '3' '4' '5' '6' '7' '9' '9' ::=['-] {자리}

이 예에서는 기호(기호)를 참조하십시오.-0,1,2,3,4,5,6,7,8,9)은 단자 기호 및<digit>그리고<integer>말단 기호가 아닌 것 같아^{[note 2]}

또 다른 예는 다음과 같다.

{\ce {S -> cAd

{\ce {A -> ab}

이 예에서 기호 $a,b,c,d$ 는 단자 기호, $S,A$ 는 단자 기호다.null

참고 항목

재귀문법

메모들

^ 그것은 전혀 상징을 포함하고 있지 않다.
^ 이 예는 "0056" 또는 "0000"과 같은 선행 0이 있는 문자열과 "-0" 및 "-00000"과 같은 음의 0 문자열을 지원한다.

참조

^ Chomsky, Noam (1956). "Three Models for the Description of Language". IRE Transactions on Information Theory. 2 (3): 113–123. doi:10.1109/TIT.1956.1056813.
^ Chomsky, Noam (1957). Syntactic Structures. The Hague: Mouton.
^ Ginsburg, Seymour (1975). Algebraic and automata theoretic properties of formal languages. North-Holland. pp. 8–9. ISBN 0-7204-2506-9.
^ Harrison, Michael A. (1978). Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. pp. 13. ISBN 0-201-02955-3.

[3] 그것은 전혀 상징을 포함하고 있지 않다.

[6] 이 예는 "0056" 또는 "0000"과 같은 선행 0이 있는 문자열과 "-0" 및 "-00000"과 같은 음의 0 문자열을 지원한다.

[Chomsky1956-1] Chomsky, Noam (1956). "Three Models for the Description of Language". IRE Transactions on Information Theory. 2 (3): 113–123. doi:10.1109/TIT.1956.1056813.

[Chomsky1957-2] Chomsky, Noam (1957). Syntactic Structures. The Hague: Mouton.

[4] Ginsburg, Seymour (1975). Algebraic and automata theoretic properties of formal languages. North-Holland. pp. 8–9. ISBN 0-7204-2506-9.

[5] Harrison, Michael A. (1978). Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. pp. 13. ISBN 0-201-02955-3.

[1]

[2]

[note 1]

[3]

[4]

[note 2]

Search

단자 및 단자 이외의 기호

네임스페이스

더

목차

단자 기호

비단어 기호

생산규칙

예

참고 항목

메모들

참조