Símbolos terminais e não-terminais

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa


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[editar | editar código-fonte]

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 as regras da gramática. Por exemplo, uma gramática que é definida por duas regras:

  1. x pode se tornar xa
  2. 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 tem 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óico 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 \rarr 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[editar | editar código-fonte]

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[editar | editar código-fonte]

  1. Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools, second edition; Pearson/Addison-Wesley, 2006. Box, p. 43.
  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.
  3. Chomsky, Noam. Syntactic Structures. The Hague: Mouton, 1957.
  4. Ginsburg, Seymour. Algebraic and automata theoretic properties of formal languages. [S.l.]: North-Holland, 1975. 8–9 pp. ISBN 0-7204-2506-9
  5. Harrison, Michael A.. Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company, 1978. 13 pp. ISBN 0-201-02955-3

Referências[editar | editar código-fonte]