Símbolos terminais e não terminais

Na Ciência da Computação, símbolos terminais e não terminais são os elementos léxicos usados na especificação das regras de produção que constituem uma gramática formal. O terminais e não terminais de uma gramática particular são dois conjuntos disjuntos.

Símbolos Terminais

Símbolos terminais são caracteres literais que podem aparecer nas entradas ou saídas das regras de produção de uma gramática formal e não podem ser quebradas em unidades "menores". Para ser preciso, símbolos terminais não podem ser modificados usando nas regras da gramática. Por exemplo, uma gramática que é definida por duas regras:

x pode se tornar xa
x pode se tornar ax

tem a como um símbolo terminal, porque não existe regra que poderia modificá-lo em algo. (Por outro lado, x têm duas regras que podem modificá-lo, então ele é um não terminal.) Uma linguagem formal definida (ou gerada) por uma gramática particular é o conjunto de cadeias que podem ser produzidas pela gramática e que consiste apenas de símbolos terminais; não terminais que não consistem inteiramente de terminais podem não aparecer nos lexemas que são tidos como pertencentes à linguagem.

No contexto da análise sintática, em oposição a teoria das linguagens de programação e compiladores, os termos "símbolos terminais" e "token" são frequentemente tratados como sinônimos. Citando o chamado Dragon Book:

Em um compilador, o analisador léxico ler os caracteres do programa fonte, agrupa-os de acordo com o significado léxico em unidades chamadas lexemas, e produz tokens de saída representado esses lexemas. Um token consiste em dois componentes, um nome simbólico e um valor de atributo. Os nomes simbólicos são símbolos abstratos que são usados pelo parser para análise sintática. Frequentemente, podemos chamar esses nomes simbólicos de terminais, desde que eles apareçam como símbolos terminais na gramática da linguagem de programação. O valor de atributo, se estiver presente, é um apontador para a tabela de símbolos que contém informações adicionais sobre o token. Essa informação adicional não faz parte da gramática, então na nossa discussão de análise sintática, frequentemente nos referimos aos tokens e símbolos terminais como sinônimos.^[1]

Símbolos terminais, ou simplesmente, terminais, são símbolos elementares da linguagem definida por uma gramática formal.

Símbolos não terminais

Símbolos não terminais, ou simplesmente não terminais, são os símbolos que podem ser substituídos; portanto existem cadeias compostas por uma combinação de terminais e não terminais símbolos. Eles podem ser chamados de variáveis sintáticas. Uma gramática formal inclui uma variável inicial, um membro designado do conjuntos de não terminais do qual todas as cadeias podem ser derivadas por sucessivas aplicações das regras de produção. De fato, a linguagem definida por uma gramática é precisamente o conjunto de cadeias terminais que podem ser derivadas.

Gramáticas Livres de Contexto são aquelas gramáticas que o lado esquerdo de cada regra de produção consiste de 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. As que podem são chamadas linguagens livres de contexto. Essas são exatamente as linguagens que podem ser reconhecidas por um autômato com pilha. Linguagens livres de contexto são a base teórica para a maioria das linguagens de programação.

Regras de produção

Uma gramática é definida por regras de produção que especifica quais lexemas podem substituir outros lexemas; essas regras podem ser usada para a geração de cadeias, ou para dividir as cadeias. Cada uma dessas regras tem uma cabeça (head), ou lado esquerdo, que consiste na cadeia que pode ser substituída, e um corpo (body), ou lado direito, que consiste na string que pode substituir. Regras são frequentemente escritas na forma $<head\rightarrow body>$ ; por exemplo, a regra z0 → z1 diz que z0 pode ser substituído por z1.

Na formalização classica de gramáticas geradoras, inicialmente proposta por Noam Chomsky na década de 1950,^[2]^[3] uma gramática G consiste nos seguintes componentes:

Um conjunto finito $N$ de símbolos não terminais.
Um conjunto finito $\Sigma$ de símbolos terminais que são disjuntos de $N$ .
Um conjunto finito $P$ de regras de produção, onde cada regra é da forma

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

onde

{}^{*}

é o Fecho de Kleene e

\cup

indica união de conjuntos, então

$(\Sigma \cup N)^{*}$ 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 cadeia de símbolos para outra, onde a primeira cadeia contém pelo menos um símbolo não terminal. No caso do corpo consistir unicamente de cadeia vazia—i.e., que não contém símbolo nenhum— pode ser descrito com uma notação especial (frequentemente $\Lambda$ , $e$ ou $\epsilon$ ) para evitar confusões.

Um símbolo distinto $S\in N$ é o símbolo inicial.

Uma gramática é definida formalmente por uma quadrupla ordenada $<N,\Sigma ,P,S>$ . Uma gramática formal é frequentemente chamada de um sistema de cadeia reescrito ou uma gramática irrestrita na literatura.^[4]^[5]

Exemplo

O exemplo a seguir mostra um inteiro (que pode ser negativo) expressado como uma derivação da Forma de Backus–Naur:

<inteiro> ::= ['-'] <dígito> {<dígito>}
<dígito> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Nesse exemplo, os símbolos (-,0,1,2,3,4,5,6,7,8,9) são terminais e <dígito> e <inteiro> são símbolos não terminais.

Notas

↑ Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, second edition; Pearson/Addison-Wesley, 2006. Box, p. 43.
↑ Chomsky, Noam (1956). «Three Models for the Description of Language». IRE Transactions on Information Theory. 2 (2): 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. [S.l.]: 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. 13 páginas. ISBN 0-201-02955-3

Referências

Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, second edition; Pearson/Addison-Wesley, 2006. Section 2.2 (beginning on p. 42). Note that this section only discusses context-free grammars.
http://osr507doc.sco.com/en/tools/Yacc_specs_symbols.html

[1] Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, second edition; Pearson/Addison-Wesley, 2006. Box, p. 43.

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

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

[4] Ginsburg, Seymour (1975). Algebraic and automata theoretic properties of formal languages. [S.l.]: 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. 13 páginas. ISBN 0-201-02955-3

[1]

[2]

[3]

[4]

[5]