Símbolos terminais e não terminais - Terminal and nonterminal symbols

Na ciência da computação , os símbolos terminais e não terminais são os elementos lexicais usados ​​na especificação das regras de produção que constituem uma gramática formal . Os símbolos terminais são os símbolos elementares da linguagem definidos por uma gramática formal. Os símbolos não terminais (ou variáveis ​​sintáticas ) são substituídos por grupos de símbolos terminais de acordo com as regras de produção.

Os terminais e não terminais de uma gramática particular são dois conjuntos disjuntos .

Símbolos terminais

Os símbolos terminais são símbolos literais que podem aparecer nas saídas das regras de produção de uma gramática formal e que não podem ser alterados usando as regras da gramática. Aplicar as regras recursivamente a uma sequência de símbolos de origem geralmente terminará em uma sequência de saída final consistindo apenas de símbolos terminais.

Considere uma gramática definida por duas regras. Usando marcas pictóricas interagindo umas com as outras:

1. O símbolo רpode se tornarди
2. O símbolo רpode se tornarд

Aqui дestá um símbolo de terminal porque não existe nenhuma regra que o transformasse em outra coisa. Por outro lado, רpossui duas regras que podem alterá-lo, portanto, não é terminal. Uma linguagem formal definida ou gerada por uma gramática particular é o conjunto de strings que podem ser produzidas pela gramática e que consistem apenas em símbolos terminais .

Símbolos não terminais

Os símbolos não terminais são aqueles símbolos que podem ser substituídos. Elas também podem ser chamadas simplesmente de variáveis ​​sintáticas . Uma gramática formal inclui um símbolo de início , um membro designado do conjunto de não-terminais a partir do qual todas as cadeias de caracteres na linguagem podem ser derivadas por aplicações sucessivas das regras de produção. Na verdade, a linguagem definida por uma gramática é precisamente o conjunto de strings terminais que podem ser derivadas.

Gramáticas livres de contexto são aquelas em que o lado esquerdo de cada regra de produção consiste em apenas um único símbolo não terminal. Essa restrição não é trivial; nem todas as linguagens podem ser geradas por gramáticas livres de contexto. Aqueles que podem são chamados de linguagens livres de contexto. Essas são exatamente as linguagens que podem ser reconhecidas por um autômato push-down não determinístico . Linguagens livres de contexto são a base teórica para a sintaxe da maioria das linguagens de programação .

Regras de produção

Uma gramática é definida por regras de produção (ou apenas 'produções') que especificam quais símbolos podem substituir quais outros símbolos; essas regras podem ser usadas para gerar strings ou para analisá-los. Cada uma dessas regras tem uma cabeça , ou lado esquerdo, que consiste no fio que pode ser substituído, e um corpo , ou lado direito, que consiste em um fio que pode substituí-lo. As regras são freqüentemente escritas no formato head → body ; por exemplo, a regra a → b especifica que a pode ser substituído por b .

Na formalização clássica de gramáticas generativas proposta pela primeira vez por Noam Chomsky na década de 1950, uma gramática G consiste nos seguintes componentes:

• Um conjunto finito N de símbolos não terminais .
• Um conjunto finito Σ de símbolos terminais que é separado a partir de N .
• Um conjunto finito P de regras de produção , cada regra da forma

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

onde é o operador estrela de Kleene e ∪ denota a união do conjunto , portanto, representa zero ou mais símbolos e N significa um símbolo não terminal . Ou seja, cada regra de produção mapeia de uma sequência de símbolos para outra, onde a primeira sequência contém pelo menos um símbolo não terminal. No caso em que o corpo consiste apenas na string vazia . Pode ser denotado com uma notação especial (freqüentemente Λ , e ou ε ) para evitar confusão.${\ displaystyle {} ^ {*}}$${\ displaystyle (\ Sigma \ cup N) ^ {*}}$

• Um símbolo distinto que é o símbolo inicial .${\ displaystyle S \ in N}$

Uma gramática é formalmente definida como quádrupla ordenada . Essa gramática formal é freqüentemente chamada de sistema de reescrita ou de gramática de estrutura de frase na literatura. ${\ displaystyle \ langle N, \ Sigma, P, S \ rangle}$

Exemplo

Por exemplo, o seguinte representa um número inteiro (que pode ser assinado) expresso em uma variante da forma Backus-Naur :

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

Neste exemplo, os símbolos ( -, 0,1,2,3,4,5,6,7,8,9 ) são símbolos terminais <digit>e <integer>são símbolos não terminais.

Outro exemplo é:

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

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

Neste exemplo, os símbolos a, b, c, d são símbolos terminais e S, A são símbolos não terminais.

Veja também

• Gramática recursiva

Notas

Referências