Linguagens Formais,
Lex & Yacc
Vladimir Oliveira Di Iorio
1
Introdução
2
Linguagens Formais
• Linguagens formais são linguagens cuja sintaxe (e
geralmente semântica) é precisamente definida, sem
ambigüidades.
• São diferentes de linguagens naturais, recheadas de
imprecisões e ambigüidades.
• Exemplos de linguagens formais: linguagens de
programação como C, C++, Pascal, Java, linguagens
de consulta como SQL.
3
Exemplo
• Uma definição para o comando UPDATE da
linguagem SQL, usando estilo BNF:
UPDATE [TRANSACTION transaction] {table | view}
SET col = <val> [, col = <val> …]
[WHERE <search_condition> | WHERE CURRENT OF cursor];
• Exemplo de um comando válido:
UPDATE CLIENTE SET DATA_INCLUSAO = CURRENT DATE;
4
Objetivos do Curso
• Estudar fundamentos teóricos de linguagens formais:
– alfabetos, palavras e linguagens;
– expressões regulares;
– gramáticas regulares e livres de contexto.
• Apresentar ferramentas no estilo Lex, para
processamento de entradas usando linguagens
regulares.
• Apresentar ferramentas no estilo Yacc, para
processamento de entradas usando linguagens livres
de contexo.
• Dar exemplos de utilização de ferramentas Lex e
Yacc, na construção de filtros, pequenos
interpretadores e compiladores.
5
Visão Geral - Expressões Regulares
• Expressões regulares são um formalismo usado para
definir o formato correto de uma cadeia de
caracteres.
• São usados símbolos de um alfabeto qualquer,
juntamente com operadores especiais, como '*' e '+'.
• Um exemplo: a+ b c*
Essa expressão define que as cadeias válidas são
aquelas que iniciam com uma seqüência não vazia
de símbolos 'a', seguidos de exatamente um símbolo
'b', seguido de uma seqüência possivelmente vazia
de símbolos 'c'.
6
Visão Geral - Autômatos
• Autômatos finitos são um formalismo equivalente às
expressões regulares, que usa representação em
forma de grafo.
• Autômato finito equivalente à expressão a+ b c* :
a
b
c
a
Estado inicial
Estado final
7
Visão Geral - Gramáticas
• Gramáticas são mais um formalismo usado para
definir o formato correto de uma cadeia de
caracteres.
• Os símbolos são classificados como terminais e não
terminais, e são usadas regras de reescrita para os
símbolos não terminais.
• Gramática equivalente à expressão a+ b c* :
<S> ->
<A> ->
<B> ->
a<A>
a<A> | b<B> | b
c<B> | c
8
Visão Geral - Lex
• Ferramentas no estilo Lex utilizam uma
especificação baseada em expressões regulares.
• A partir dessa definição, Lex gera automaticamente
um programa que simula o comportamento de
autômatos equivalentes às expressões fornecidas.
• O programa lê uma entrada e verifica se essa
entrada está no formato especificado.
• Enquanto verifica a entrada, pode executar algumas
ações (trechos de programa) desejadas.
9
Visão Geral - Yacc
• Ferramentas no estilo Yacc funcionam de maneira
parecida com Lex - mas utilizam uma especificação
baseada em gramáticas.
• O formalismo de gramáticas é mais poderoso que o
de expressões regulares e autômatos, assim é
possível gerar programas que processam entradas
mais complexas.
• Da mesma forma que Lex, Yacc pode associar ações
(trechos de programa) a cada regra da gramática. À
medida que a entrada é processada, ações
adequadas são executadas. Essas ações podem ser,
por exemplo, a interpretação ou compilação da
10
entrada.
Visão Geral - Lex & Yacc
• Um compilador ou interpretador pode ser gerado
rapidamente usando Lex e Yacc em conjunto.
• Lex é geralmente usado para separar uma entrada
em unidades léxicas. No caso de uma linguagem de
programação, por exemplo, pode identificar um
número real como "1.23" ou uma palavra-chave
como "begin".
• Yacc pode usar as unidades léxicas produzidas por
Lex e verificar se essas unidades formam uma
entrada válida. Enquanto isso pode, por exemplo,
compilar a entrada.
11
Visão Geral - Lex & Yacc
entrada
regras
léxicas
regras
sintáticas
Lex
Yacc
Analisador
Léxico
saída
Analisador
Sintático
12
História
• O primeiro compilador para uma linguagem de
programação de alto nível foi desenvolvido para a
linguagem FORTRAN, na década de 50.
• Na época, a teoria de linguagens formais ainda não
estava estabelecida (Chomsky, 1959).
• Foi necessário um esforço gigantesco, e a utilização
de um grande número de programadores.
13
História
• Atualmente, com a utilização de ferramentas como
Lex e Yacc, é possível construir rapidamente um
compilador.
• O processo de geração automática utilizado por essas
ferramentas, em geral, produz analisadores quase tão
rápidos quanto os escritos totalmente à mão.
14
Linguagens Formais
15
Alfabetos e Palavras
• Um alfabeto é um conjunto finito de símbolos
distintos.
• Exemplo: Σ = {a,b,c}
é um alfabeto formado pelos símbolos a, b e c.
• Uma palavra sobre um alfabeto Σ é uma seqüência
de comprimento finito formada com símbolos desse
alfabeto.
• Algumas palavras sobre o alfabeto Σ = {a,b,c} :
abc , bcaabbac , b
• A palavra de comprimento zero é representada por λ .
16
Linguagens
• Seja Σ um alfabeto qualquer. O conjunto de todas as
palavras sobre Σ é denotado por Σ* .
• Por exemplo, se Σ = {a,b,c} , então
Σ* = {λ, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, ...}
• Uma linguagem sobre um alfabeto Σ é qualquer
subconjunto de Σ* .
• Linguagens sobre Σ = {a,b,c} :
{a, ab, bbc}
{aa, ab, ac, ba, bb, bc, ca, cb, cc}
todas as palavras que começam com a
17
Linguagens
• Outras linguagens sobre Σ = {a,b,c} :
todas as palavras de comprimento par
{λ, a, b, c}
{λ}
{}
Σ*
• A concatenação de 2 palavras será representada por
sua justaposição. Por exemplo, sejam uma palavra x
= abc e uma palavra y = bb .
A concatenação de x com y é representada por
xy = abcbb .
18
Concatenação de linguagens
• Se X e Y são duas linguagens,
a concatenação de X com Y, denotada por XY,
é a seguinte linguagem:
XY = { palavras xy tais que x  X e y  Y }
Ou seja, são as palavras formadas pela
concatenação de uma palavra qualquer de X
com uma palavra qualquer de Y
(prefixo pertence a X, sufixo pertence a Y).
19
Concatenação de linguagens
• Por exemplo, sejam
X = {a,b,c} e Y = {abb,ba} .
Então
XY = {aabb,aba,babb,bba,cabb,cba}
• A concatenação de X consigo mesma n vezes é Xn :
Xn = X X X ... X X
(n vezes)
• Por definição, X0 é o conjunto {λ}:
X0 = {λ}
20
Concatenação de linguagens
• Outros exemplos, com X = {a,b,c}
e Y = {abb,ba} :
X0 = {λ}
X1 = X = {a,b,c}
X2 = XX = {aa,ab,ac,ba,bb,bc,ca,cb,cc}
X3 = X2X = {aaa,aab,aac,aba,abb,abc,aca,acb,acc,
baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,
caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc}
Y2 = YY = {abbabb,abbba,baabb,baba}
21
Exercícios
Considere o alfabeto Σ = {a,b,c}. Seja L1 a linguagem das
palavras que começam com o símbolo 'a', e L2 a linguagem
das palavras que terminam com o símbolo 'b'.
1. O conjunto {a,b,c} é uma linguagem sobre Σ ?
2. Qual a menor linguagem que pode ser criada com esse
alfabeto (menor número de palavras) ?
3. Qual é o resultado da concatenação de L1 com L2 ?
4. Qual é o resultado da união de L1 com L2 ?
5. A união de 2 linguagens pode resultar em uma linguagem
menor que as outras duas?
6. A concatenção de 2 linguagens pode resultar em uma
linguagem menor que as outras duas?
22
Fecho de Kleene
• A operação X*, denominada Fecho de Kleene de X,
é definida como a união de Xi ,
com i variando de 0 a infinito:
X* = X0  X1  X2  X3  ...
Ou seja, X* consiste de todas as palavras que se pode
construir a partir dos elementos de X .
• Por exemplo, se X = {a,b,c} e Y = {abb,ba} :
X* = {λ,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,...}
Y* = {λ,abb,ba,abbabb,abbba,baabb,baba,abbabbabb,...}
23
Expressões Regulares
24
Expressões Regulares - Definição
• Para definir expressões regulares, vamos usar as
seguintes abreviações:
– o conjunto {a} será representado simplesmente por a ;
– {a,b,c,...} será representado por a  b  c ...
• O conjunto de expressões regulares sobre um alfabeto
Σ qualquer é definido como:
1. os conjuntos { } e λ são expressões regulares;
2. para todo símbolo a de Σ, a é uma expressão regular;
3. se x e y são expressões regulares sobre Σ, então também
são expressões regulares: x  y , xy e x* .
25
Expressões Regulares - exemplos
• ab
linguagem formada apenas pelas palavras a e b
• abb  aa  ac
linguagem formada exatamente pelas palavras
abb, aa e ac, ou seja, {abb,aa,ac}
• a*
linguagem (infinita) de todas as palavras formadas
apenas com o símbolo a
26
Expressões Regulares - exemplos
• (a  b) (ab  bb)
denota a linguagem {aab,abb,bab,bbb}
• (a  b)*
a linguagem {λ,a,b,aa,ab,ba,bb,aaa,...} :
• (aa)*
palavras só com a, e com comprimento par
(inclui a palavra nula)
27
Expressões Regulares - exemplos
• Outras abreviações:
– x+ é usado para abreviar xx* ;
– x2 é usado para abreviar xx ;
– x3 para abreviar x2x etc.
• (a2)+
palavras só com a, e com comprimento par maior
que zero (não inclui a palavra nula)
• a (a  b  c)*
Linguagem sobre {a,b,c} das palavras que começam
com o símbolo a
28
Expressões Regulares - exemplos
• a (a  b  c)* b
Linguagem sobre {a,b,c} das palavras que começam
com o símbolo a e terminam com b
• (b  c) (a  b  c)*  λ
Linguagem das palavras sobre {a,b,c} que não
começam com o símbolo a
29
Expressões Regulares - exercícios
•
Que linguagens são essas?
1.
(a  b)* b (a  b)*
2.
(a  b)* a (a  b)* a (a  b)*
3.
(a  b  c) (a  b  c) (a  b  c)
4.
(b* a b* a b*) *
30
Expressões Regulares - exercícios
•
Construa expressões regulares para:
1. Linguagem das palavras de comprimento par
sobre o alfabeto {a,b,c}.
2. Linguagem das palavras sobre o alfabeto {a,b,c}
que contenham exatamente um símbolo c .
31
Expressões Regulares - restrições
• As linguagens que podem ser especificadas por
expressões regulares são chamadas de
linguagens regulares.
• Mas expressões regulares não podem ser usadas
para especificar qualquer linguagem desejada.
• Muitas linguagens não conseguem ser especificadas
com expressões regulares, necessitando de
formalismos mais poderosos.
32
Expressões Regulares - restrições
• Exemplos de linguagens que não são regulares:
– Linguagem cujas palavras têm o formato anbn,
para qualquer n. Ou seja:
{ λ, ab, aabb, aaabbb, ... }
– Linguagem sobre alfabeto { a, b, (, ) } com
aninhamento correto de parêntesis abrindo e fechando.
33
Lex - Gerador de
Analisadores Léxicos
34
Lex - Gerador de
Analisadores Léxicos
• Ajuda a escrever programas cuja entrada pode ser
descrita por meio de expressões regulares.
• Principais utilizações:
– transformações simples e extração de padrões
em textos;
– separação da entrada em unidades léxicas, como
preparação para um analisador sintático.
• Os exemplos utilizados nesta apresentação seguirão
o formato do programa JFlex, um clone de Lex que
gera código em Java.
35
Lex - fonte
• Um texto fonte para LEX é composto de:
– lista de expressões regulares;
– fragmentos de programa associados a cada
expressão.
• Quando o fonte é submetido ao LEX, um programa é
automaticamente gerado. Esse programa:
– lê um arquivo de entrada;
– particiona a entrada em cadeias que "casam" com
as expressões regulares definidas;
– executa os fragmentos de programa associados
às expressões "casadas";
– escreve no arquivo de saída.
36
Lex - esquema de funcionamento
fonte
Lex
entrada
Yylex
Yylex
(programa
gerado)
saída
37
Lex - exemplo com JFlex
• Um exemplo, usando o gerador JFlex:
1
2
3
4
.%%
.%standalone
.%%
.\t { System.out.print("TAB"); }
• Como na maioria dos clones de Lex, o fonte é
dividido em 3 seções, separadas por "%%".
• No JFlex, as seções são:
1. código do usuário a ser incluído;
2. opções e declarações;
3. regras e ações associadas.
38
Lex - exemplo com JFlex
1
2
3
4
.%%
.%standalone
.%%
.\t { System.out.print("TAB"); }
Uma regra
Essa opção indica que o programa gerado poderá ser
executado diretamente (não será usado dentro de um
analisador sintático).Ação (fragmento de programa)
Expressão regular
associada à expressão
39
Lex - exemplo com JFlex
1
2
3
4
.%%
.%standalone
.%%
.\t { System.out.print("TAB"); }
• Essa regra "casa" com um caractere "\t" (tabulação) da
entrada. Se isso acontecer, o código entre chaves é
executado.
• Se a entrada não casa com nenhuma regra, a ação default
é executada: escrever o caractere diretamente na saída.
• Ou seja, esse "programa" Lex serve para ler uma entrada
e trocar as tabulações por "TAB".
40
Lex - usando o JFlex
• Supondo que o fonte abaixo esteja no arquivo ex1.flex:
1
2
3
4
.%%
.%standalone
.%%
.\t { System.out.print("TAB"); }
Executa jflex,
gerando Yylex.java
> jflex ex1.flex
Reading "ex1.flex"
Constructing NFA : 6 states in NFA
Converting NFA to DFA : ..
4 states before minimization, 3 states in minimized DFA
Writing code to "Yylex.java"
gera Yylex.class
> javac Yylex.java
41
Lex - executando analisador gerado
• Supondo que o texto abaixo esteja no arquivo teste.txt:
teste...
Esta linha comeca com tab
Esta com 2 tabs
fim.
> java Yylex teste.txt
teste...
TABEsta linha comeca com tab
TABTABEsta com 2 tabs
• Para gerar a saída no arquivo saida.txt:
> java Yylex teste.txt > saida.txt
42
Lex - expressões regulares
• Expressões regulares usadas em regras:
– caracteres de texto: letras, dígitos, caracteres
especiais como '\t', '\n' etc.
– operadores: usados como funções especiais das
expressões regulares.
• Na maioria das versões de Lex, os operadores são:
"\[]ˆ-?.*+|()$/{}%<>
• Os operadores podem ser utilizados como caracteres
de texto, se vierem precedidos de um caractere de
escape ('\') ou se estiverem entre aspas duplas.
• Nas slides seguintes, veremos o funcionamento de
alguns operadores.
43
Lex - expressões regulares
• Classes de caracteres:
[abc]
casa com um dos caracteres a, b ou c
[a-zA-Z] casa com uma letra minúscula ou maiúscula
[^a-zA-Z] casa com qualquer coisa, exceto letras
• Caractere arbitrário:
.
casa com qualquer caractere, exceto newline
• Exclusivos de JFlex:
[:letter:]
isLetter( )
[:digit:]
isDigit( )
[: lowercase:]
isLowerCase( )
[:uppercase:]
isUpperCase( )
44
Lex - expressões regulares
• Expressões repetidas (* e +):
a*
casa com qualquer número consecutivo de a's
(incluindo zero repetições)
a+
casa com uma ou mais ocorrências de a
[A-Za-z][A-Za-z0-9]*
definição usual de "identificador"
• Alternação e agrupamento ( | ):
(ab|cd)
casa com ab ou cd
45
Lex - expressões regulares
• Expressão opcional (?):
ab?c casa com ac ou abc;
(ab|cd+)?(ef)*
casa com abefef , efefef , cdef, ou cddd
mas não com abc , abcd , ou abcdef
• Macros e repetições:
{digit} casa com a definição da expressão regular
digit (seção de definições)
a{n}
casa com n vezes a concatenação de a
46
Lex - escolha de regras
•
Como ocorre a escolha das regras para
casamento?
1. À medida que a entrada é lida, o analisador
procura a regra que possibilita o casamento
com a mais longa possível seqüência de
caracteres da entrada.
2. Se mais de uma regra possibilita o
casamento com a seqüência mais longa, a
escolha é feita pela ordem em que as regras
aparecem na fonte.
47
Lex - escolha de regras
• Supondo que o fonte abaixo esteja no arquivo ex2.flex:
1
2
3
4
5
6
. %%
. %standalone
. Identifier = [a-zA-Z][a-zA-Z0-9]*
. %%
. abc { System.out.println("-----\"abc\""); }
. {Identifier} { System.out.println("-----id"); }
> jflex ex2.flex
Reading "ex2.flex"
Constructing NFA : 16 states in NFA
Converting NFA to DFA : ......
8 states before minimization, 6 states in minimized DFA
Writing code to "Yylex.java"
> javac yylex.java
48
Lex - escolha de regras
• Supondo que o texto abaixo esteja no arquivo teste.txt:
abcde
abc
abc123
123abcd
123abc
> java Yylex teste.txt
• O que será impresso???
49
Lex - escolha de regras
1
2
3
4
5
6
.%%
.%standalone
.Identifier = [a-zA-Z][a-zA-Z0-9]*
.%%
.abc { System.out.println("-----abc"); }
.{Identifier} { System.out.println("-----id"); }
Saída:
Entrada:
abcde
abc
abc123
123abcd
123abc
-----id
-----abc
-----id
123-----id
123-----abc
50
Lex - objetos acessados nas ações
• Dentro das ações associadas às regras, alguns
objetos e métodos podem ser acessados pelos
trechos de programa.
• Esses objetos e métodos, gerados automaticamente
pelo analisador, possuem nomes que iniciam com
"yy", para evitar conflito com objetos do código
inserido pelo usuário.
• Exemplos: o texto que foi "casado" com a regra, a
linha e coluna atuais etc.
• Nos próximos slides, veremos esses e outros
exemplos de objetos e métodos acessíveis dentro
das ações associadas às regras.
51
Lex - objetos acessados nas ações
• String yytext() : retorna a seqüência de
caracteres que foi casada com a regra.
• int yylength() : retorna o comprimento da
seqüência casada.
• int yyline : contém o número da linha atual.
• int yycolumn : contém o número da coluna atual,
na linha atual.
52
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
.%%
.
.%standalone
.%class Ex3 /* define nome da classe gerada */
.%unicode
/* permite usar caracteres unicode */
.%line
/* permite usar yyline */
.%column
/* permite usar yycolumn */
.
.FimdeLinha = \r|\n|\r\n
.CharTexto = [^\r\n]
.Espaco = {FimdeLinha} | [ \t]
.
.ComentLinha = "//" {CharTexto}* {FimdeLinha}
.
.Ident = [a-zA-Z][a-zA-Z0-9]*
.Inteiro = 0 | [1-9][0-9]*
.
.
53
19
20
21
22
23
24
25
26
27
28
.
%%
.
.
{ComentLinha}
{ /* despreza */ }
.
{Espaco}
{ /* despreza */ }
.
{Ident}
{ System.out.println ("id=" + yytext()
.
+" linha= "+ yyline +" coluna = "+ yycolumn); }
.
{Inteiro}
{ System.out.println ("int=" + yytext()); }
.
.
.|\n
{ throw new Error("Caractere Ilegal <"
. +yytext()+">"); }
Entrada:
abcde
// linha comentada
abc
abc123
123abcd
123abc
Saída:
id=abcde linha= 0 coluna = 0
id=abc linha= 2 coluna = 0
id=abc123 linha= 3 coluna = 0
int=123
id=abcd linha= 4 coluna = 3
int=123
id=abc linha= 8 coluna = 3
54
Lex - exercícios
• Inserir um caractere inválido (ex: "@") no arquivo de
entrada e executar a especificação anterior.
• Responder: é possível construir uma especificação
Lex que reconheça fórmulas matemáticas sintaticamente
corretas, com operandos, operadores e parêntesis
aninhados?
Exemplo:
12*((5 + 2) / (3 - 1))
55
Lex - uso com analisador sintático
• No exemplos exibidos até agora, Lex é usado para
gerar um programa que processa toda a entrada de
uma vez.
• Como explicado anteriormente, outra importante
utilização de Lex é na separação da entrada em
unidades léxicas, para ser usado em conjunto com
um analisador sintático.
56
Lex - uso com analisador sintático
regras
léxicas
regras
sintáticas
Lex
Yacc
entrada
saída
Yylex
Yyparse
57
Lex - uso com analisador sintático
• Quando Lex é usado em conjunto com um analisador
sintático, uma classe Main não é gerada.
• Lex gera um método yylex que retorna a unidade
léxica que foi extraída do texto de entrada.
• O método yylex deve ser seguidamente executado
pelo analisador sintático, para obter essas unidades
sintáticas, chamadas tokens.
• Algumas ações devem conter comandos return, que
retornam o token que foi extraído, para o analisador
sintático.
58
1
2
3
4
5
6
7
8
9
.import java_cup.runtime.Symbol;
.
Usa classe Symbol
.%%
.
definida em java_cup
.%cup
Usa java_cup
.%debug
....
.
Diretiva para teste: cria
.%%
uma função Main artificial
...
{Ident} {
return new Symbol(sym.IDENT, yytext());
}
...
Retorna um token.
O código do token é definido
no analisador sintático.
59
Gramáticas
60
Gramáticas - Definição
• Gramáticas são um formalismo utilizado para
especificação de linguagens.
• Em uma gramática, os símbolos são classificados
como terminais (símbolos que formam as palavras
da linguagem) e não terminais.
• Os símbolos não terminais são também chamados
de variáveis.
• O processo de geração de palavras é denominado
derivação, e consiste em regras de reescrita dos
símbolos não terminais.
61
Gramáticas - Exemplo
• Exemplo:
<S> ->
<A> ->
<B> ->
a<A>
a<A> | b<B> | b
c<B> | c
• No exemplo acima, símbolos entre < > são
considerados como não terminais ( <S>, <A>, <B> ).
Os demais são os símbolos terminais ( a, b, c ).
• Cada regra é composta de um lado esquerdo e um
lado direito, separados por -> .
• O único tipo de gramática que vamos estudar são
as gramáticas livres de contexto, em que o lado
esquerdo é apenas uma variável (não terminal).
62
Gramáticas - Exemplo
• Exemplo:
<S> ->
<A> ->
<B> ->
a<A>
a<A> | b<B> | b
c<B> | c
• As regras <B> -> c<B> | c são uma abreviação
para as regras <B> -> c<B> e <B> -> c .
• Uma das variáveis é denominada símbolo inicial.
Para simplificar, vamos supor que seja o símbolo do
lado esquerdo da primeira regra (neste caso, <S> ).
• Outra simplificação: geralmente, usa-se maiúsculas
para variáveis e minúsculas para terminais,
dispensando <> .
63
Gramáticas - Derivação
• Exemplo:
S ->
A ->
B ->
aA
aA | bB | b
cB | c
• Uma derivação é uma seqüência de palavras
formadas por símbolos terminais e variáveis, onde
cada palavra é derivada da anterior.
• Uma palavra y é derivada de x (escrevemos x => y)
se y pode ser obtida substituindo uma variável v de x
por algum lado direito das regras de v.
• Por exemplo, são válidas as seguintes relações :
aabB => aabc , aaA => aaaA , ABAB => AcAB
64
Gramáticas - Derivação
• Exemplo:
S ->
A ->
B ->
aA
aA | bB | b
cB | c
• Exemplo de derivação :
aaA => aaaA => aaaaA => aaaabB => aaaabcB
• Usa-se a abreviação =>* para indicar derivação em 0
ou mais passos: aaA =>* aaaabcB
• Derivações de interesse, para uma gramática, são
aquelas cuja primeira palavra é o símbolo inicial, e a
última palavra contém apenas símbolos terminais.
65
Linguagem de uma gramática
• Exemplo:
S ->
A ->
B ->
aA
aA | bB | b
cB | c
• Derivações de palavras com terminais a partir de S :
S => aA => aaA => aab
S => aA => abB => abcB => abccB => abccc
S =>* aaabcc
• A linguagem gerada por uma gramática é o
conjunto de palavras apenas com símbolos
terminais, derivadas a partir do símbolo inicial.
66
Exercícios
1.
Usando a gramática abaixo:
S ->
A ->
B ->
2.
3.
aA
aA | bB | b
cB | c
mostre todos os passos das seguintes derivações:
S =>* ab
S =>* aaabcc
Qual é a palavra de menor comprimento, apenas
com símbolos terminais, que pode ser derivada a
partir do símbolo inicial da gramática acima?
Qual é a linguagem gerada pela gramática
acima?
67
Linguagem de uma gramática
• Exemplo:
S ->
A ->
B ->
aA
aA | bB | b
cB | c
• A linguagem gerada pela gramática acima é o
conjunto de palavras sobre {a,b,c} que começam
com a (uma ou mais ocorrências), seguido de
exatamente um b, seguido de qualquer número de c.
• Ou seja, a linguagem gerada por essa gramática é:
a+bc*
• MAS: gramáticas podem gerar linguagens bem mais
complexas que as expressas por expressões
regulares!
68
Regulares X Livres de Contexto
• Gramáticas com regras cujo lado esquerdo é apenas uma
variável são chamadas gramáticas livres de contexto.
• As linguagens geradas por gramáticas livres de contextro
são chamadas linguagens livres de contexto.
• As gramáticas regulares são um subconjunto das
gramáticas livres de contexto. São aquelas com regras
cujo lado direito é λ, ou é composto apenas de um
terminal, ou então um terminal seguido de uma variável.
• A gramática usada nos exemplos anteriores é regular.
• As linguagens geradas por gramáticas regulares são
chamadas de linguagens regulares.
69
Gramáticas Livres de Contexto
• Exemplo:
S ->
aSb | λ
• Algumas palavras geradas pela gramática acima:
S
S
S
S
=>
=>
=>
=>
λ
aSb => ab
aSb => aaSbb => aabb
aSb => aaSbb => aaaSbbb => aaabbb
• Qual é a linguagem gerada pela gramática acima?
Resposta: o conjunto de palavras sobre {a,b} com o
formato anbn , n ≥ 0.
70
Gramáticas Livres de Contexto
• Exemplo:
S ->
B ->
aSB | λ
bb
• Algumas palavras geradas pela gramática acima:
S
S
S
S
=>
=>
=>
=>
=>
λ
aSB => aB => abb
aSB => aaSBB => aaBB => aabbB => aabbbb
aSB => aaSBB => aaaSBBB => aaaBBB => aaabbBB =>
aaabbbbB => aaabbbbbb
• Qual é a linguagem gerada pela gramática acima?
É o conjunto de palavras sobre {a,b} com o formato
71
anb2n , n ≥ 0.
Gramáticas Livres de Contexto
• Exemplo:
S ->
A ->
aSbb | A
Ac | λ
• Algumas palavras geradas pela gramática acima:
S
S
S
S
=>
=>
=>
=>
=>
A => λ
aSbb =>
aSbb =>
aSbb =>
aAcccbb
aAbb => abb
aaSbbbb => aaAbbbb => aacbbbb
aAbb => aAcbb => aAccbb => aAcccbb =>
=> acccbb
• Qual é a linguagem gerada pela gramática acima?
É o conjunto de palavras sobre {a,b,c} com o formato
72
ancmb2n , m,n ≥ 0.
Exercício
• Construir uma gramática sobre o alfabeto
{ a, b, c, +, -, (, ) }
para gerar fórmulas matemáticas sintaticamente
corretas em que a, b e c são operandos, + e - são
operadores, e os parêntesis são corretamente
aninhados.
73
Árvores de Derivação
• Exemplo:
S ->
B ->
aSB | λ
bb
• Árvore de derivação para a palavra aaabbbbbb:
S
a S B
a S B
a S B
λ
bb
bb
bb
74
Árvores de Derivação
• Exemplo:
S ->
B ->
aSB | λ
bb
• Árvore de derivação para a palavra aaabbbbbb:
S
a
S B
a S B
a S B
λ
bb
bb
bb
75
Árvores de Derivação
• Exemplo:
S ->
B ->
aSB | λ
bb
• Árvore de derivação para a palavra aaabbbbbb:
S
a
a
S B
a S B
λ
bb
S B
bb
bb
76
Árvores de Derivação
• Exemplo:
S ->
B ->
aSB | λ
bb
• Árvore de derivação para a palavra aaabbbbbb:
S
a
a
a
λ
S B
bb
S B
S B
bb
bb
77
Árvores de Derivação
• Exemplo:
S ->
B ->
aSB | λ
bb
• Árvore de derivação para a palavra aaabbbbbb:
S
a
a
a
λ
S B
bb
S B
S B
bb
bb
78
Árvores de Derivação
• Exemplo:
S ->
B ->
aSB | λ
bb
• Árvore de derivação para a palavra aaabbbbbb:
S
a
a
a
λ
S B
bb
S B
S B
bb
bb
79
Árvores de Derivação
• Exemplo:
S ->
B ->
aSB | λ
bb
• Árvore de derivação para a palavra aaabbbbbb:
S
a
a
a
λ
S B
bb
S B
S B
bb
bb
80
Árvores de Derivação
• Exemplo:
S ->
B ->
aSB | λ
bb
• Árvore de derivação para a palavra aaabbbbbb:
S
a
a
a
λ
S B
bb
S B
S B
bb
bb
81
Árvores de Derivação e Ambigüidade
• Exemplo:
S
X
Y
A
C
XC | AY
aXb | λ
bYc | λ
aA | λ
cC | λ
Duas árvores de
derivação diferentes
para a palavra
S
S
X C
A Y
a X b
λ
->
->
->
->
->
c C
a A
c
λ
abc.
b Y c
λ
82
Ambigüidade
• Algumas gramáticas são ambíguas. Isso significa que
uma mesma palavra (só com terminais) pode ser
derivada de duas formas diferentes, mesmo que seja
sempre escolhida uma mesma ordem para substituição
das variáveis.
• Duas gramáticas diferentes podem gerar a mesma
linguagem, sendo uma das gramáticas ambígua e a
outra não ambígua.
• Gramáticas ambíguas não são muito adequadas para a
construção automática de analisadores sintáticos.
• Algumas linguagens são inerentemente ambíguas.
Isso quer dizer que é impossível construir uma
gramática não ambígua que gere essas linguagens.
83
Yacc - Gerador de
Analisadores Sintáticos
(Yacc =Yet Another Compiler-Compiler)
84
Yacc - Gerador de
Analisadores Sintáticos
• Auxilia no processo de definição do formato da
entrada para um programa.
• Uma especificação Yacc:
– regras que descrevem a estrutura da entrada;
– ações que devem ser executadas quando cada
regra é utilizada;
• Os exemplos utilizados nesta apresentação seguirão
o formato do programa Javacup, um clone de Yacc
que gera código em Java.
85
Yacc - exemplo usando Javacup
1
2
3
4
5
6
7
8
9
10
11
12
13
14
.import java_cup.runtime.*;
.
.terminal PTVIRG, MAIS, MENOS, INTEIRO;
.non terminal expr_list, expr_ptv, expr;
.
.expr_list ::=
.
expr_list expr_ptv
Declaração de símbolos
. | expr_ptv;
.expr_ptv ::=
terminais e não terminais
. expr PTVIRG;
.
expr
::=
. expr MAIS expr
. | expr MENOS expr
Gramática: lista de regras
. | INTEIRO;
separadas por ";" .
86
Yacc - geração de um analisador
• A especificação apresentada tem como símbolos
terminais: PTVIRG, MAIS, MENOS e INTEIRO.
• Se esse símbolos corresponderem a ';', '+', '-' e
números inteiros, respectivamente, então a
linguagem reconhecida é uma lista de expressões
separadas por ';'. O operadores são '+' e '-' .
• Para gerar um analisador sintático, vamos usar o
Javacup (supondo especificação em um arquivo
ex1.cup) :
> java java_cup.Main ex1.cup
java_cup é um programa
escrito em Java!
87
Yacc - conflitos na gramática
> java java_cup.Main ex1.cup
Opening files...
Parsing specification from standard input...
...
*** Shift/Reduce conflict found in state #9
...
*** More conflicts encountered than expected -parser generation aborted
...
• A gramática utilizada possui várias ambigüidades,
que causam conflitos no analisador sintático.
88
Yacc - conflitos na gramática
• Por exemplo, considere a entrada:
1 - 2 + 3;
expr_list
expr_list
OU
expr_ptv
expr_ptv
expr ;
expr ;
expr + expr
expr - expr
INTEIRO
1
expr + expr
INTEIRO INTEIRO
2
3
expr - expr
INTEIRO
1
INTEIRO
INTEIRO
3
2
89
Yacc - reescrevendo especificação
1
2
3
4
5
6
7
8
9
10
11
12
13
14
.import java_cup.runtime.*;
.
.terminal PTVIRG, MAIS, MENOS, INTEIRO;
.non terminal expr_list, expr_ptv, expr;
.
.expr_list ::=
.
expr_list expr_ptv
. | expr_ptv;
.expr_ptv ::=
. expr PTVIRG;
Ambigüidades
.
expr
::=
. INTEIRO MAIS expr
. | INTEIRO MENOS expr
. | INTEIRO;
eliminadas
90
Yacc - reescrevendo especificação
• Supondo nova especificação em um arquivo ex2.cup :
> java java_cup.Main ex2.cup
Opening files...
Parsing specification from standard input...
Checking specification...
...
Writing parser...
Closing files...
------- CUP v0.10k Parser Generation Summary ------0 errors and 0 warnings
...
0 productions never reduced.
0 conflicts detected (0 expected).
Code written to "parser.java", and "sym.java".
----------------------------------------------------
91
Yacc - arquivos gerados
• Os arquivos gerados pelo Javacup foram parser.java
e sym.java. O primeiro contém o analisador sintático
(parser). O segundo contém uma definição para
símbolos terminais.
• Conteúdo do arquivo sym.java:
1
2
3
4
5
6
7
8
.public class sym {
. public static final
. public static final
. public static final
. public static final
. public static final
. public static final
.}
int
int
int
int
int
int
MAIS = 3;
PTVIRG = 2;
error = 1;
MENOS = 4;
EOF = 0;
INTEIRO = 5;
92
Yacc - especificando "scanner"
• Falta especificar um procedimento que extrai os
tokens do arquivo de entrada, classificando-os como
PTVIRG, MAIS, MENOS ou INTEIRO.
• Esse procedimento é geralmente chamado de
scanner.
• Isso será feito usando um analisador léxico
automaticamente gerado com JFlex.
93
Yacc - especificando "scanner"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
.import java_cup.runtime.*;
.%%
.
Usa classe Symbol, definida
.%cup
em java_cup.runtime,
.FimdeLinha = \r|\n|\r\n
e os códigos de sym.java.
.Espaco = {FimdeLinha} | [ \t]
.Inteiro = 0 | [1-9][0-9]*
.
.%%
.
{Espaco}
{ /* despreza */ }
.
{Inteiro}
{ return new Symbol (sym.INTEIRO); }
.
"+"
{ return new Symbol (sym.MAIS); }
.
"-"
{ return new Symbol (sym.MENOS); }
.
";"
{ return new Symbol (sym.PTVIRG); }
.
.
.|\n
{ throw new Error("Caractere Ilegal <"+
. yytext()+">"); }
94
Yacc - especificando "Main"
• Finalmente, falta especificar uma função Main, que
irá fazer as inicializações necessárias e chamar o
analisador sintático.
• O analisador sintático, por sua vez, irá chamar o
analisador léxico para extrair os tokens do arquivo de
entrada.
95
Yacc - especificando "Main"
1
2
3
4
5
6
7
8
9
10
11
12
13
.import java.io.*;
.
.class Main {
. static public void main(String argv[]) {
.
/* Inicia o parser */
.
try {
.
parser p = new parser(new Yylex(System.in));
.
Object result = p.parse().value;
.
} catch (Exception e) {
.
e.printStackTrace();
. }
.}
}.
96
Yacc - procedimento completo
• Suponha que tenhamos então os seguintes arquivos:
– ex2.cup : especificação que será submetida ao
Javacup;
– ex2.flex : especificação que será submetida ao JFlex;
– Main.java : contém a função Main.
• O procedimento completo para gerar um analisador
sintático será:
> java java_cup.Main ex2.cup
...
> jflex ex2.flex
...
> javac Main.java
97
Yacc - usando o analisador gerado
> java Main
1+2;
1-2+3;
^Z
> java Main
1+2;
1-2+3;
1 1;
Syntax error
Couldn't repair and continue parse
...
98
Yacc - valores e ações
• Um analisador que só verifica a sintaxe de uma
entrada tem pouca utilidade.
• Ferramentas como Javacup permitem associar
valores aos símbolos e ações às regras.
• Uma ação é um trecho de programa que é associado
a uma regra. Pode ser executado em qualquer ponto
da derivação, quando a regra é utilizada.
• Um valor pode ser associado a um símbolo terminal
no analisador léxico. No analisador sintático, um
valor pode ser associado a um símbolo não terminal,
recursivamente.
99
Yacc - valores no JFlex
1
2
3
4
5
6
7
8
9
10
• A classe Symbol possui construtores que permitem a
especificação de um valor (Object) associado ao token.
• Trecho da nova especificação para o JFlex:
Valor associado
.{Espaco} { /* despreza */ }
ao token.
.
.{Inteiro} {
. int aux = Integer.parseInt (yytext());
. return new Symbol (sym.INTEIRO, new Integer(aux));
.}
.
."+" { return new Symbol (sym.MAIS); }
."-" { return new Symbol (sym.MENOS); }
. { return new Symbol (sym.PTVIRG); }
";"
100
Yacc - valores no Javacup
• No Javacup, na declaração de símbolos terminais e não
terminais, pode-se especificar um TIPO associado.
• Trecho da nova especificação para o Javacup:
1
2
3
4
5
6
7
.terminal PTVIRG, MAIS, MENOS;
.
.terminal Integer INTEIRO;
.
.non terminal Object expr_list, expr_ptv;
.
.non terminal Integer expr;
Tipo associado
ao símbolo.
101
Yacc - valores no Javacup
• As ações são trechos de programa delimitados por {: ... :}.
• A cada token, é possível associar um identificador, para
que o seu valor possa ser acessado dentro da ação.
• Trecho da nova especificação para o Javacup:
1
2
.expr_ptv ::=
. expr:e {: System.out.println("= " + e); :} PTVIRG;
Usa o valor de e
Delimitadores
dentro da ação.
de ação.
Imprime valor da expressão,
imediatamente antes de
reconhecer ';' .
102
Yacc - valores no Javacup
• A palavra-chave RESULT indica o valor do símbolo
da esquerda da regra sendo utilizada.
• Trecho da nova especificação para o Javacup:
1
2
3
4
5
6
7
8
expr
.
::=
. INTEIRO:n MAIS expr:e
. {: RESULT = new Integer(n.intValue() + e.intValue()); :}
. | INTEIRO:n MENOS expr:e
. {: RESULT = new Integer(n.intValue() - e.intValue()); :}
. | INTEIRO:n
. {: RESULT = n; :}
. ;
103
Yacc - usando o analisador gerado
• Suponha especificações em ex3.cup e ex3.flex:
> java java_cup.Main ex3.cup
...
> jflex ex3.flex
...
> javac Main.java
> java Main
1;
= 1
1+1;
= 2
1-1;
= 0
O
1-2-3;
= 2
^Z
???
problema é a incorreta
associatividade!
104
Exercício
• Usando a gramática abaixo:
expr_list ->
expr_list expr_ptv
| expr_ptv
expr_ptv -> expr PTVIRG
expr ->
INTEIRO MAIS expr
| INTEIRO MENOS expr
| INTEIRO
construir a árvore de derivação de : 1 - 2 - 3;
105
Yacc - associatividade
• Derivação de: 1 - 2 - 3;
expr_ptv
expr ;
Associatividade
à direita!
INTEIRO - expr
1
INTEIRO - expr
2
INTEIRO
3
106
Yacc - alterando associatividade
• Trecho da nova especificação para o Javacup,
implementando associatividade à esquerda para os
operadores '+' e '-' :
1
2
3
4
5
6
7
8
expr
.
::=
. expr:e MAIS INTEIRO:n
. {: RESULT = new Integer(e.intValue() + n.intValue()); :}
. | expr:e MENOS INTEIRO:n
. {: RESULT = new Integer(e.intValue() - n.intValue()); :}
. | INTEIRO:n
. {: RESULT = n; :};
. ;
107
Yacc - associatividade à esquerda
• Derivação de: 1 - 2 - 3;
expr_ptv
expr ;
expr - INTEIRO
expr - INTEIRO
INTEIRO
Associatividade
à esquerda!
3
2
1
108
Yacc - usando o analisador gerado
• Suponha especificações em ex4.cup e ex4.flex:
> java java_cup.Main ex4.cup
...
> jflex ex4.flex
...
> javac Main.java
> java Main
1;
= 1
1+1;
= 2
1-1;
= 0
OK!
1-2-3;
= -4
^Z
109
Yacc - associatividade e precedência
• A associatividade de operadores é uma característica tão
importante em gramáticas que a maioria dos clones de
Yacc possuem diretivas para simplificar sua
especificação.
• Suponha que, além dos operadores representados por
MAIS e MENOS, a gramática possua VEZES e DIVISAO.
• As diretivas abaixo determinam a precedência e a
associatividade desses operadores:
1
2
precedence
.
left MAIS, MENOS;
precedence
.
left VEZES, DIVISAO;
110
Yacc - associatividade e precedência
• Usando as diretivas apresentadas, não é mais
necessário construir as regras de modo que a
derivação defina a associatividade e precedência.
• Trecho da nova especificação:
1
2
3
4
5
6
7
8
9
10
expr
.
::=
. expr:e1 MAIS expr:e2
. {: RESULT = new Integer(e1.intValue()+e2.intValue());
. | expr:e1 MENOS expr:e2
. {: RESULT = new Integer(e1.intValue()-e2.intValue());
. | expr:e1 VEZES expr:e2
. {: RESULT = new Integer(e1.intValue()*e2.intValue());
. | expr:e1 DIVISAO expr:e2
. {: RESULT = new Integer(e1.intValue()/e2.intValue());
. ...
:}
:}
:}
:}
111
112