Symbole terminalowe i nieterminalne - Terminal and nonterminal symbols

W informatyce , symbol terminalny są elementy leksykalne stosowane w określeniu zasad produkcji stanowiące formalną gramatyki . Symbole końcowe to podstawowe symbole języka zdefiniowanego przez gramatykę formalną. Symbole nieterminalne (lub zmienne syntaktyczne ) są zastępowane grupami symboli końcowych zgodnie z regułami produkcji.

Terminale i nieterminale danej gramatyki to dwa rozłączne zbiory .

Symbole terminala

Symbole końcowe to symbole dosłowne, które mogą pojawić się w wyjściach reguł produkcji gramatyki formalnej i których nie można zmienić za pomocą reguł gramatyki. Rekurencyjne stosowanie reguł do źródłowego ciągu symboli zwykle kończy się końcowym ciągiem wyjściowym składającym się tylko z symboli terminala.

Rozważ gramatykę zdefiniowaną przez dwie reguły. Korzystanie ze znaków graficznych wchodzących w interakcję ze sobą:

1. Symbol רmoże stać sięди
2. Symbol רmoże stać sięд

Oto дsymbol końcowy, ponieważ nie istnieje reguła, która zmieniłaby go w coś innego. Z drugiej strony רma dwie reguły, które mogą to zmienić, dlatego jest nieterminalny. Język formalny zdefiniowane lub generowane przez konkretnego gramatyki zestaw łańcuchów, które mogą być wytwarzane przez gramatyki i składać się tylko z symboli zaciskowych .

Symbole nieterminalne

Symbole nieterminalne to te symbole, które można zastąpić. Mogą być również nazywane po prostu zmiennymi składniowymi . Gramatyka formalna zawiera symbol początkowy , wyznaczony element zbioru nieterminali, z którego można wyprowadzić wszystkie łańcuchy w języku poprzez kolejne zastosowania reguł produkcji. W rzeczywistości język zdefiniowany przez gramatykę jest dokładnie zbiorem ciągów końcowych, które można w ten sposób wyprowadzić.

Gramatyki bezkontekstowe to te gramatyki, w których lewa strona każdej reguły produkcji składa się tylko z jednego symbolu nieterminalnego. To ograniczenie nie jest trywialne; nie wszystkie języki mogą być generowane przez gramatyki bezkontekstowe. Te, które można nazwać językami bezkontekstowymi. Są to dokładnie te języki, które mogą być rozpoznane przez niedeterministyczny automat z naciskiem . Języki bezkontekstowe stanowią teoretyczną podstawę składni większości języków programowania .

Zasady produkcji

Gramatyka jest definiowana przez reguły produkcji (lub po prostu „produkcje”), które określają, które symbole mogą zastąpić inne symbole; reguły te mogą być używane do generowania ciągów lub do ich analizy. Każda taka reguła ma nagłówek lub lewą stronę, która składa się z ciągu, który można zastąpić, oraz treść lub prawą stronę, która składa się z ciągu, który może ją zastąpić. Reguły są często pisane w formie head → body ; np. reguła a → b określa, że a może być zastąpione przez b .

W klasycznej formalizacji gramatyk generatywnych zaproponowanej po raz pierwszy przez Noama Chomsky'ego w latach 50. gramatyka G składa się z następujących elementów:

• Skończonego zbioru N z symboli nieterminalowi .
• Skończonego zbioru Σ z symboli końcowych , który jest odłączony od N .
• Skończonego zbioru P od zasad produkcji , każda Reguła postaci

${\ Displaystyle (\ Sigma \ filiżanka N) ^ {*} N (\ Sigma \ filiżanka N) ^ {*} \ rightarrow (\ Sigma \ filiżanka N) ^ {*}}$

gdzie jest operator gwiazdy Kleene i ∪ oznacza zestaw unii , więc reprezentuje zero lub więcej symboli, a N oznacza jeden symbol nieterminal . Oznacza to, że każda reguła produkcji odwzorowuje jeden ciąg symboli na inny, przy czym pierwszy ciąg zawiera co najmniej jeden symbol nieterminalny. W przypadku, gdy ciało składa się wyłącznie z pustego ciągu . Może być oznaczony specjalną notacją (często Λ , e lub ε ) w celu uniknięcia pomyłek.${\ Displaystyle {} ^ {*}}$${\ Displaystyle (\ Sigma \ filiżanka N) ^ {*}}$

• Wyróżniony symbol, który jest symbolem początkowym .${\ Displaystyle S \ w N}$

Gramatyka jest formalnie zdefiniowana jako czwórka uporządkowana . Taka gramatyka formalna jest często nazywana w literaturze systemem przepisywania lub gramatyki struktury frazowej . ${\ Displaystyle \ langle N, \ Sigma, P, S \ rangle}$

Przykład

Na przykład poniższa przedstawia liczbę całkowitą (która może być podpisana) wyrażoną w wariancie postaci Backusa–Naura :

<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<integer> ::= ['-'] <digit> {<digit>}

W tym przykładzie symbole ( -,0,1,2,3,4,5,6,7,8,9 ) są symbolami końcowymi <digit>i <integer>są symbolami niekońcowymi.

Innym przykładem jest:

${\displaystyle {\ce {S -> cAd}}}$

${\displaystyle {\ce {A -> a | ab}}}$

W tym przykładzie symbole a,b,c,d są symbolami końcowymi, a S,A są symbolami nieterminalowymi.

Zobacz też

• Gramatyka rekurencyjna

Uwagi

Bibliografia