Embed Size (px)
Citation preview
Linguagens, sintaxe e semântica
LNCC UFRJ
Linguagens naturais e formais
Linguagens naturais
Linguagem formal
Um conjunto finito e não-vazio cujos elementos são símbolos
Qualquer cadeia finita de símbolos justapostos – inclusive a vazia,
Qualquer subconjunto L de *
Coleção de todas as strings construídas a partir de
Em princípio não existem regras
para construir uma linguagem.
Entretanto, ao criar uma linguagem,
estamos cheios de segundas
intenções – e assim precisaremos de regras para atingi-las!
Para = { 0, 1 }, temos = { , 0, 1, 00, 01, 10, 11, 000,
001, ... }. A partir daí poderemos construir
diversas linguagens, que serão muito úteis, conforme veremos.
Atenção!
Termos
técnicos
Um símbolo é
uma entidade
atômica
Uma string é
só uma cadeia
de símbolos
Uma linguagem
formal é só um
conjunto de
strings
Exemplo
{ ,,,, A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, [, ] }
Coleção de símbolos para descrever jogos de
baralho
Exemplo – continuação
, , 8, 9, A, 2, A23,
, 55555, JQKA,
4, 7, A, 7,
10JQKA, [A,K], etc
Strings
{ A, 2, ... , 7, J, Q, K,
A, 2, ... , 7, J, Q, K,
A, 2, ... , 7, J, Q, K,
A, 2, ... , 7, J, Q, K,
[A,A,2], ... , [7, Q,5 ],
etc }
Uma linguagem
Envolve a atribuição de
um significado a cada
string de uma linguagem
Gramática
Gramática
Uma forma de definir uma linguagem formal L
a partir de um alfabeto
Gramática
N – um conjunto de
símbolos não-terminais
T – um conjunto de
símbolos terminais
S – um símbolo especial: o
símbolo de partida
P – um conjunto de produções
N T
Componentes
de uma
gramática
Os não-terminais ...
O conjunto N dos
símbolos não-terminais
As classes gramaticais
Em inglês,
tokens
Os terminais ...
O conjunto T dos
símbolos terminais
Os lexemas da linguagem
Apesar dos não-terminais serem usados na construção,
eles não aparecem na sentença acabada
As produções ...
O conjunto P das
produções
As regras gramaticais
Uma derivação ...
Produções
, 2, 7, A, [3, J, K]
São strings admissíveis em linguagens para jogos de baralho
, 3A, 17, [J, K, A]
Strings não admissíveis em linguagens para jogos de baralho
carta: um valor seguido de um naipe
mão : um conjunto de 3 cartas (p/ex.)
naipe? valor?
As wff’s
Assim, a linguagem formal
é o conjunto de todas
as suas wff ’s
Apenas um nome
mais enfático
para as strings
produzidas
Exemplo
{ /, jan, fev, ..., dez, 0, 1 2, 3, 4, 5, 6, 7, 8, 9 }
Alfabeto de uma linguagem para descrever datas no
calendário
Produções
6/jan/2009, 1/abr/1998, 14/jul/1872
Datas são wff’s (strings admissíveis) no
calendário gregoriano
46/jan/2009, abr/1/1998
Não são wff’s
data: o dia, seguido do mês, seguido do ano;
separados pela barra
Dia? Mês? Ano?
Metalinguagem -BNF
Metalinguagem
{
Linguagem auxiliar utilizada
para descrever mais claramente
a linguagem formal
} ,
Metalinguagem
Pode ser uma linguagem natural como o português ou inglês, ou outra linguagem formal
O formalismo de Backus-Naur (BNF)
John Warner Backus
• O “pai” do FORTRAN;
• Participou decisivamente
na criação do ALGOL.
Peter Naur
Criador do ALGOL, junto com
Backus e outros
O formalismo de Backus-Naur
J. W. Backus desenvolveu, especificamente para a ALGOL 58, um método para descrever linguagens de programação, que veio a ser
conhecido como a forma normal de Backus.
Tal método foi revisado e expandido por Peter Naur para a ALGOL 60; por sugestão de Donald Knuth, foi renomeado
como a forma normal de Backus-Naur
Filadelfia, 07/12/1928 Professor do MIT
Noam Chomsky
Exemplo
dígito 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Símbolo terminal
Separador de alternativas Nome do
identificador da classe
Exemplo – produção
dígito 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
natural dígito | dígito natural
Observe que a definição de natural é
recursiva
Regras de produção
natural dígito | dígito natural
Os elementos são escritos
sequencialmente
da esquerda para a direita
dígito 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Os elementos são escolhidos
de uma lista;
a ordem não importa
A EBNF e os diagramas de caminho
EBNF
O EBNF não é mais poderoso que o BNF;
apenas é mais facilitador – mais prático.
Nele são incluídas notações para repetição
e para elementos opcionais
No EBNF os símbolos terminais são
escritos entre aspas “ ”
e os não-terminais diretamente, sem os
A EBNF
Um elemento opcional é escrito
entre colchetes [ a ];
O elemento a pode ser incluído ou descartado
A repetição de um ou mais elementos
é descrita pela utilização de chaves:
• ( a )+ indica a repetição do a pelo menos uma vez;
• ( a )* indica a repetição do a zero ou mais vezes.
Exemplo dígito “0” | “1” | ... | “9”
inteiro [ “ - ” | “ + ” ] dígito ( dígito )*
São produções de inteiro:
-1, +21, 9, 12047, etc
inteiro [ “ - ” | “ + ” ] ( dígito )+
Apesar da notação usada ser praticamente a mesma, há uma grande diferença entre o significado de definições léxicas e sintáticas: uma definição
léxica opera sobre os caracteres individuais do fluxo de entrada, ao passo que uma definição sintática opera no fluxo de tokens gerado pela análise
léxica. Todas as utilizações da BNF no próximo capítulo, Análise léxica, são definições léxicas; já nos capítulos subsequentes são definições sintáticas.
EBNF e diagramas sintáticos
A B
Representação gráfica
EBNF
AB
A seguido de B
Significado
Representação gráfica
EBNF
Significado
A
A ou nada
[ A ]
EBNF
e diagramas
sintáticos Representação gráfica
EBNF
A | B
ou A ou B
Significado
A
B
EBNF e diagramas sintáticos
Representação gráfica
EBNF
Significado
A
Sequência de zero
ou mais A ’s
( A )*
Representação gráfica
EBNF
Significado
Sequência de um
ou mais A ’s
( A )+
A
EBNF e diagramas sintáticos
Representação gráfica
EBNF
Significado
Símbolo
terminal
a
a
a
b
z
Representação gráfica
EBNF
a | b | ... | z
Exemplo
+
Um número binário pode ser
constituído por apenas um bit, como 0 ou 1, ou por
vários, como 110.
Diagrama sintático
Para gerar 110: • Você sai de número binário no
diagrama, passa por bit e escolhe 0.
• Volta, passa novamente por bit e escolhe 1.
• Torna a voltar, passa por bit mais uma vez e escolhe 1.
bit número
binário
sinal
sinal
-
bit
0
1
Python, EBNF e diagramas de sintaxe
Mais adiante no curso, teremos a oportunidade de trabalhar com a EBNF para definição da
sintaxe da Linguagem Python.
Todo o manual de referência da linguagem, em The Python Language Reference
é construído utilizando a EBNF; confira em Python v2.6.5 documentation
A seguir exibiremos alguns exemplos.
A definição de nome em Python
nome ::= letra_min ( letra_min | “_” )* letra_min ::= “a”...”z”
_
letra_min nome
letra_min
letra_min
b
z
a
O comando print
print cmd_print
expr >>
,
,
expr
expr
, expr ,
O comando print
O comando print avalia uma expressão por vez e escreve o objeto resultante
na saída padrão (veja a seguir). Se um objeto não é uma string ele é
convertido antes numa string, usando as regras para conversão de strings.
Então ela é escrita (a resultante ou a original).
É colocado (escrito) um espaço antes que cada objeto seja (convertido e)
escrito, a menos que o sistema de saída acredite que foi posicionado no início
de uma linha.
Este é o caso quando:
1. ainda foi escrito nenhum caractere na saída padrão
2. o último caractere escrito na saída padrão é ‘ \n’ , ou
3. a última operação de escrita na saída padrão não foi um comando print.
(Por essa razão, em alguns casos pode ser funcional escrever uma string
vazia para a saída).
O comando if
if cmd_if expr : seq
elif expr : seq
else : seq
O comando if
O comando if é usado para execução condicional.
Ele seleciona exatamente uma das sequências avaliando as
expressões uma a uma até achar uma que seja verdadeira (true –
veja a seção Operações booleanas para as definições de true e
false); então essa sequência é executada (e nenhuma outra parte
do comando if é executado ou avaliado). Se todas as expressões
são falsas, é executada a sequência associada à clausula else
(caso esteja presente).
