Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
UNISO
Universidade de Sorocaba
Uma técnica de representação muito utilizada para as linguagens regulares são as chamadas expressões regulares. Bibliotecas que dão suporte ao uso de expressões regulares estão disponíveis na maioria das linguagens de programação e são muito usadas para busca em textos e para validação de entrada textual (para formulários de entrada de dados, por exemplo).
Uma outra técnica de representação usada para linguagens regulares são os autômatos finitos. Autômatos finitos e expressões regulares são equivalentes, ou seja, todo padrão que pode ser representado por uma técnica também pode ser representada pela outra.
Os autômatos finitos podem ser utilizados para organizar os padrões léxicos de uma linguagem, facilitando a implementação direta de um analisador léxico para ela. Ou seja, com os autômatos finitos podemos criar analisadores léxicos para linguagens mais complexas, e de maneira mais sistemática e confiável do que vimos no exemplo da linguagem de expressões.
Para criar um analisador léxico dessa forma devemos definir os autômatos finitos que representam os padrões associados a cada tipo de token, depois combinar esses autômatos em um único autômato, e então implementar o autômato finito resultante como um programa.
As expressões regulares descrevem padrões simples de texto de forma compacta e sem ambiguidade.
Por exemplo, o padrão que descreve todas as strings formadas com caracteres a e b que começam com a e terminam com b pode ser escrito como a expressão regular a(a|b)*b (a construção dessa expressão será explicada em breve).
Existem várias sintaxes e representações diferentes para expressões regulares, dependendo da linguagem ou biblioteca utilizada.
Cada expressão regular (ER) é uma string que representa um conjunto de strings; também podemos dizer que uma ER representa um padrão que é satisfeito por um conjunto de strings.
A maioria dos caracteres representam eles mesmos em uma expressão regular. Por exemplo, o caractere a em uma ER representa o próprio caractere a. A ER a representa um padrão que poderia ser descrito em português como “o conjunto de strings que possuem um caractere a”. Obviamente só existe uma string dessa forma: a string "a".
Colocando um padrão após o outro realiza a concatenação dos padrões. Começando com caracteres simples, se juntarmos um a e um b formamos a expressão ab, que representa a string que contém um a seguido por um b, ou seja, a string "ab".
Mas o poder das Expressões Regulares vem de alguns caracteres que não representam eles mesmos; esses são caracteres especiais. Um caractere especial bastante usado é o *, que representa zero ou mais repetições de um padrão.
Por exemplo, a expressão a* representa strings com zero ou mais
caracteres a. A string vazia satisfaz esse padrão e corresponde a zero repetições; outras strings satisfeitas pelo padrão são "a", "aa", "aaa", etc.
O asterisco representa zero ou mais repetições do padrão que vem antes, não só de um caractere: a expressão (ab)* representa , "ab", "abab", "ababab", etc. Mas pelas regras de precedência das expressões, ab* é o mesmo que a(b*), que representa um a seguido por zero ou mais caracteres b, e não é igual a (ab)*.
Outro caractere especial importante é a barra vertical, que representa opções nas partes de um padrão. Por exemplo a|b representa a ou b, ou seja, as strings "a" e "b".
Isso nos leva ao exemplo apresentado antes: a(a|b)*b é uma expressão regular formada por três partes concatenadas em sequência: a, depois (a|b)* e por fim b. Isso significa que uma string que satisfaz essa expressão deve começar com um caractere a, seguido por caracteres que satisfazem opadrão (a|b)* e terminando com um caractere b.
O padrão (a|b)* é satisfeito por zero ou mais repetições do padrão (a|b), que por sua vez é um padrão que é satisfeito por caracteres a ou b.
Ou seja, (a|b)* é um padrão que representa zero ou mais repetições de caracteres a ou b. Alguns exemplos de cadeias que são representadas pela expressão a(a|b)*b:
• "ab" (zero repetições do padrão interno (a|b)*)
• "aab"
• "abb"
• "aabbbb"
• "abbaabab"
Já vimos que o caractere especial * representa zero ou mais repetições de um padrão. O caractere especial + é similar, mas representa uma ou mais repetições; a única diferença é que o caractere + causa a obrigatoriedade de pelo menos uma repetição do padrão. A expressão a+ representa as strings "a", "aa", "aaa", etc., sem incluir a string vazia.
O caractere especial ? representa partes opcionais em um padrão, ou seja, zero ou uma repetição de um determinado padrão. A expressão b?a+ representa strings com uma ou mais repetições de a, podendo começar opcionalmente com um b.
As classes de caracteres são uma notação adicional para representar opções de um caractere em um padrão. A classe [abc] representa apenas um caractere, que pode ser a, b ou c. Isso é o mesmo que a expressão (a b c), e a notação de classes é apenas um atalho, principalmente quando existem várias opções.
A expressão [0123456789] representa um caractere que é um dígito numérico. Adicionando um caractere de repetição temos [0123456789]+, que representa strings contendo um ou mais dígitos. Essas são exatamente as strings, como "145" ou "017", que representam constantes inteiras.
Quando uma classe inclui vários caracteres em uma sequência, como o exemplo anterior, podemos usar intervalos para tornar as expressões mais compactas. Por exemplo, a expressão [0123456789] pode ser igualmente representada pelo intervalo [0-9]. A expressão [a-z] representa uma letra minúscula.
Podemos usar vários intervalos em uma classe. Por exemplo, [A-Za-z] representa uma letra maiúscula ou minúscula, e [0-9 A-Z a-z] representa um dígito ou letra. Note que cada classe ainda representa apenas um caractere; os intervalos apenas criam novas opções para esse caractere.
Algumas classes especiais podem ser usadas como abreviações. Por exemplo [:alpha:] representa um caractere alfabético (ou seja, é o mesmo que [A-Za-z]), e [:alnum:] representa um caractere alfabético ou um dígito. Outras classes especiais úteis são [:space:] para caracteres de espaço em branco, [:upper:] para caracteres maiúsculos e [:lower:] para caracteres minúsculos.
Existe a classe especial [:digit:] para dígitos, mas em geral é mais compacto escrever [0-
9]. É importante lembrar que essas classes especiais, assim como os intervalos, só podem ser usadosdentro de classes de caracteres, ou seja, não é possível ter uma expressão que seja apenas [:alpha:]; é preciso colocar a classe especial [:alpha:] dentro de uma classe, resultando na expressão [[:alpha:]], que representa um caractere que pode ser qualquer letra (maiúscula ou minúscula).
Uma outra notação útil com classes é a negação. Usar um caractere ˆ no começo de uma classe representa “caracteres que não estão na classe”. Por exemplo, [ˆ0-9] representa um caractere que não é um dígito de 0 a 9. A negação também pode ser usada com classes especiais: ˆ[:alnum:] representa um caractere que não é uma letra ou dígito.
Um outro tipo de caracteres especiais são os metacaracteres. Um metacaractere é um caractere especial que pode representar outros caracteres. O exemplo mais simples é o metacaractere ., que pode representar qualquer caractere. A expressão a.*b representa strings que começam com a, terminam com b e podem ter qualquer número de outros caracteres no meio, por exemplo "a0x13b".
As sequências de escape são iguais as que existem na linguagem C: \n representa um caractere de nova linha, \t um caractere de tabulação, etc. A barra invertida (\) também pode ser usada para desativar a interpretação especial de um caractere especial. Por exemplo, se quisermos um caractere + em uma expressão regular que representa o símbolo de soma, e não a repetição de uma ou mais vezes, devemos usar \+.
As gramáticas livres de contexto estão associadas às linguagens livres de contexto. Assim como a classe das linguagens regulares é usada na análise léxica, a classe das linguagens livres de contexto é essencial para a análise sintática. Aqui não vamos nos preocupar com linguagens livres do contexto em geral, apenas usando as gramáticas como ferramentas para fazer a análise sintática.
Uma gramática livre do contexto G é especificada por quatro componentes: o conjunto de símbolos terminais T, o conjunto de símbolos variáveis (ou não-terminais) V, o conjunto de produções P e o símbolo inicial S, sendo que o símbolo inicial deve ser um dos símbolos variáveis.
As gramáticas funcionam como um formalismo gerador, similar às expressões regulares: começando pelo símbolo inicial, é possível usar as produções para gerar cadeias ou sentenças da linguagem que desejamos. Os símbolos terminais representam símbolos que aparecem na linguagem, enquanto que os símbolos variáveis são usados como símbolos auxiliares durante as substituições.
Um exemplo para ilustrar as gramáticas livres de contexto.
O primeiro exemplo é uma linguagem bastante simples que gera cadeias que são palíndromos. Um palíndromo é uma palavra ou frase que é lida da mesma forma de frente para trás e de trás para frente, como “roma e amor” ou “socorram-me, subi no ônibus em marrocos”.
Vamos trabalhar com palíndromos construídos com um alfabeto bastante limitado, de apenas dois símbolos: a e b. Alguns palíndromos nesse alfabeto são abba, aaa e ababa.
Existem dois tipos de palíndromos, que podemos chamar de palíndromos pares e palíndromos ímpares.
Os palíndromos pares, como abba, contêm um número par de símbolos, com a segunda metade igual ao reverso da primeira metade. No caso de abba, as metades são ab e ba, sendo que a segunda metade, ba, é o reverso da primeira, ab. Cada símbolo em uma metade deve ocorrer na outra também.
Os palíndromos ímpares, como ababa, possuem um número ímpar de símbolos, com uma primeira parte, um símbolo do meio, e uma última parte; a última parte é o reverso da primeira, mas o símbolo do meio pode ser qualquer um. No caso do alfabeto com símbolos a e b, tanto ababa quanto abbba são palíndromos ímpares com primeira e última partes idênticas, mas símbolos do meio diferentes.
A gramática para essa linguagem de palíndromos tem dois símbolos terminais (a e b), um símbolo variável (S) que também é o símbolo inicial, e quatro produções:
Cada uma dessas produções representam uma forma em que o símbolo S pode ser transformado para gerar cadeias da linguagem. O símbolo r representa uma cadeia vazia, ou seja, uma cadeia sem nenhum símbolo. Quando temos várias produções para o mesmo símbolo variável, como no caso da gramática para palíndromos, podemos economizar espaço usando a seguinte notação:
Todas as produções para o símbolo S aparecem na mesma linha, separadas por barras. Podemos ler essa gramática como “S pode produzir aSa ou bSb ou . . . ”.
O processo de geração de uma cadeia seguindo as regras de produção de uma gramática é chamado de derivação.
Vamos começar estabelecendo algumas definições necessárias:
Uma sentença em uma gramática é uma sequência de símbolos terminais. Para a gramática de palíndromos com a e b, abba é uma sentença.
Uma forma sentencial de uma gramática é uma sequência de símbolos terminais e variáveis.
Uma forma sentencial pode ser formada apenas por símbolos variáveis, apenas por símbolos terminais, ou uma mistura dos dois tipos. Dessa forma, toda sentença é uma forma sentencial, mas uma forma sentencial que inclua algum símbolo variável não é uma sentença. Para a gramática de palíndromos em a e b, aSa é uma forma sentencial (mas não é sentença), enquanto aaa é uma forma sentencial que também é uma sentença.
Uma derivação na gramática G é uma sequência de formas sentenciais tal que:
1. A primeira forma sentencial da sequência é apenas o símbolo inicial da gramática G
2. A última forma sentencial é uma sentença (ou seja, só tem símbolos terminais)
3. Cada forma sentencial na sequência (exceto a primeira) pode ser obtida da forma sentencial anterior pela substituição de um símbolo variável pelo lado direito de uma de suas produções
Um exemplo simples de derivação na gramática de palíndromos é:
Essa derivação tem apenas duas formas sentenciais: S, que é o símbolo inicial, e a, que é uma sentença.
Para separar as formas sentenciais em uma derivação usamos o símbolo ). A derivação
demonstra que a cadeia a é uma sentença da linguagem gerada pela gramática, e ela é obtida a partir
do símbolo S pelo uso da terceira produção da gramática, S a.
Como especificado pela produção, substituímos o símbolo S pelo símbolo a, gerando assim a segunda forma sentencial; nesse caso, a segunda forma sentencial já é uma sentença, e a derivação termina por aí (até porque não existem mais símbolos variáveis na forma sentencial).
Uma derivação com um passo a mais seria:
A sentença gerada nessa derivação é aa. No primeiro passo da derivação, substituímos o símbolo S por aSa, usando a sua primeira produção. No segundo passo o símbolo S entre os dois a é substituído pela cadeia vazia (a última produção na gramática), desaparecendo e deixando apenas os dois a’s.
Agora vejamos a derivação para gerar a cadeia abba:
Os dois primeiros passos mostram S sendo substituído por aSa e bSb, nesta ordem. O último passo mais uma vez substitui o S pela cadeia vazia, fazendo com que ele desapareça da forma sentencial.
Para gerar ababa a derivação é similar, mudando apenas no último passo:
Um exemplo mais similar às linguagens de programação é uma linguagem simples para expressões aritméticas.
Aqui veremos uma gramática para uma linguagem de expressões aritméticas formadas por números inteiros e as quatro operações básicas.
Diferente do exemplo anterior dos palíndromos, para a linguagem de expressões não é interessante trabalhar com caracteres isolados. Afinal, vimos como criar um analisador léxico justamente para agrupar os caracteres em tokens, o que facilita muito a análise sintática.
Por isso, nesse exemplo e em praticamente todos daqui para a frente, os símbolos terminais não serão caracteres, mas sim tokens.
Alguns tokens são formados por apenas um caractere, mas para a gramática não faz diferença; a análise sintática vai ser realizada com base nos tokens.
Para a linguagem de expressões, temos tokens de três tipos: números, operadores e pontuação. Os operadores são os símbolos para as quatro operações, e o tipo pontuação é para os parênteses.
Cada token tem um tipo e um valor; um token do tipo operador vai ter um valor associado que determina qual dos quatro operadores o token representa. O mesmo acontece com o valor dos tokens de tipo pontuação: o valor especifica se é um parêntese abrindo ou fechando.
Para os tokens de tipo número, o valor é o valor numérico do token.
Uma gramática para a linguagem de expressões é a seguinte:
Essas produções representam o fato que uma expressão pode ser:
• Uma soma (ou multiplicação, subtração, divisão) de duas expressões
• Uma expressão entre parênteses
• Uma constante numérica (representada aqui por um token de tipo num)
Todos os símbolos nas produções dessa gramática são variáveis ou são tokens; para deixar a notação mais leve, usamos o caractere + para representar um token de tipo operador e valor
que representa um operador de soma.
Isso não deve causar problema; deve-se apenas lembrar que todos os terminais são
tokens. No caso do token de tipo num, o valor dele não aparece na gramática porque não é relevante para a estrutura sintática da linguagem.
Qualquer token de tipo número, independente do valor, faz parte dessa mesma produção (diferente dos tokens de operadores).
Vejamos algumas derivações nessa gramática. Começando por uma expressão simples, 142 + 17.
A sequência de tokens associada a essa expressão é <num, 142> <op, SOMA> <num, 17>.
Na derivação a seguir vamos representar os tokens da mesma forma que na gramática (ou seja, <op, SOMA> vira apenas +, e qualquer token de tipo número é representado apenas como num):
Em cada passo de derivação substituímos um símbolo variável pelo lado direito de uma de suas produções. Na derivação anterior, quando chegamos na forma sentencial E + E, temos a opção de substituir o E da esquerda ou o da direita; no caso, escolhemos o da esquerda. Mas o resultado seria o mesmo se tivéssemos começado pelo E da direita. Apenas a sequência de passos da derivação apareceria em outra ordem, mas o resultado final seria o mesmo, e a estrutura sintática da expressão seria a mesma.
Podemos estabelecer algumas ordens padronizadas, por exemplo em uma derivação mais à esquerda, quando há uma escolha de qual símbolo variável substituir, sempre escolhemos o símbolo mais à esquerda (como no exemplo anterior). Da mesma forma podemos falar de uma derivação mais à direita.
Mas existe uma forma melhor de visualizar uma derivação, uma forma que deixa mais clara a estrutura sintática de cada sentença derivada, e que não depende da ordem dos símbolos variáveis substituídos. Essa forma são as árvores de derivação.
Uma alternativa para representar derivações em uma gramática é usar as árvores de derivação ao invés de sequências lineares de formas sentenciais que vimos até agora. Uma árvore de derivação é semelhante às árvores sintáticas que vimos antes, mas incluem mais detalhes relacionados às produções da gramática utilizada.
Uma árvore sintática não inclui nenhuma informação sobre símbolos variáveis da gramática, por exemplo. Mais à frente, um dos nossos objetivos será obter a árvore sintática de um
programa, mas para fazer a análise sintática é importante entender as árvores de derivação.
Em uma árvore de derivação, cada nó é um símbolo terminal ou variável. As folhas da árvore são símbolos terminais, e os nós internos são símbolos variáveis. Um símbolo variável V vai ter como filhos na árvore os símbolos para os quais V é substituído na derivação. Por exemplo, sejam as seguintes derivações na gramática de expressões:
As árvores de derivação correspondentes são:
Vemos que quando o símbolo E é substituído apenas por num, o nó correspondente na árvore só tem um filho. Quando o símbolo E é substituído por E +E, isso significa que o nó correspondente na árvore terá três filhos
Para uma árvore, não importa a ordem de substituição dos dois símbolos E na forma sentencial E +E; qualquer que seja a ordem, a árvore de derivação será a mesma.
Entretanto, existem sentenças geradas por essa gramática de expressões para as quais nós podemos encontrar mais de uma árvore de derivação. Quando temos mais de uma árvore de derivação para uma mesma sentença, dizemos que a gramática é ambígua! E a ambiguidade é um problema que deve ser eliminado!
O exemplo anterior demonstra um problema importante que pode ocorrer com gramáticas livres de contexto: ambiguidade. Uma gramática é ambígua quando existe pelo menos uma sentença gerada pela gramática que pode ser gerada de duas ou mais formas diferentes; ou seja, essa sentença terá duas ou mais árvores de derivação diferentes.
A ambiguidade é um problema pois significa que uma mesma sentença pode ter duas estruturas sintáticas diferentes, na mesma gramática. A estrutura sintática de uma sentença vai influenciar no seu significado e como ela é interpretada pelo compilador, por exemplo.
Desta forma, uma gramática ambígua para uma linguagem de programação significa que certos programas poderiam funcionar de duas (ou mais) maneiras diferentes, dependendo de como o compilador interprete as partes ambígua.
Obviamente é importante que uma linguagem tenha programas que funcionem sempre de uma mesma maneira, caso contrário o programador teria dificuldade para aprender como trabalhar com a linguagem.
No exemplo da gramática de expressões, uma ambiguidade ocorre quando misturamos operadores como soma e multiplicação. Na expressão 6 * 5 + 12, deve ser efetuada primeiro a soma ou a multiplicação?
Em termos de estrutura sintática, a pergunta é se a expressão é
1. uma soma, com operando esquerdo 6 * 5 e operando direito 12
2. ou uma multiplicação com operando esquerdo 6 e operando direito 5 + 12
Nós somos acostumados com a convenção de sempre fazer multiplicações e divisões antes de somas e subtrações, então para nós o mais natural é seguir a primeira interpretação. Mas a gramática que vimos não estabelece nenhuma interpretação, possibilitando as duas. Para essa mesma sentença, nesta gramática, duas árvores de derivação podem ser construídas:
Duas árvores de derivação para a sentença 6 * 5 + 12
Cada uma das árvores representa uma das duas interpretações para a expressão. A árvore da esquerda representa a primeira interpretação: para realizar a soma é necessário obter o valor dos seus dois operandos, sendo que o operando esquerdo da soma é a multiplicação 6 * 5; portanto, a multiplicação seria realizada primeiro. A árvore direita da figura anterior representa a segunda interpretação, que seria calcular primeiro a soma 5 + 12 e depois multiplicar por 6.
O que queremos é que a própria gramática evite a ambiguidade, determinando apenas uma das duasárvores de derivação para uma sentença como 6 * 5 + 12, e que essa árvore corresponda à interpretação esperada: que a multiplicação deve ser efetuada antes da soma.
Para isso precisamos construir uma nova gramática, que codifica nos símbolos variáveis os diferentes níveis de precedência dos operadores:
Essa gramática tem três símbolos variáveis E, T e F (que podemos pensar como expressão, termo e fator). Cada um representa um nível de precedência.
• o símbolo E representa a precedência mais baixa, onde estão os operadores de soma e subtração.
• T representa o próximo nível de precedência, com os operadores de multiplicação e divisão.
• F representa o nível mais alto de precedência, onde ficam os números isolados e as expressões entre parênteses; isso significa que o uso de parênteses se sobrepõe à precedência de qualquer operador, como esperado.
Esta gramática gera as mesmas sentenças que a primeira gramática de expressões que vimos, mas sem ambiguidade. Nesta gramática, existe apenas uma árvore de derivação para a sentença 6 * 5 + 12
Árvore de derivação para a sentença 6 * 5 + 12 na nova gramática
A árvore gerada é mais complexa do que as árvores ambiguas anteriores, mas essa complexidade adicional é necessária para evitar a ambiguidade.
Toda linguagem de programação tem uma parte para expressões aritméticas, relacionais e lógicas.
Isso significa que a gramática para uma linguagem de programação vai incluir uma parte para expressões.
Essa parte da gramática de qualquer linguagem de programação segue a mesma ideia vista no último exemplo: é usado um símbolo variável para cada nível de precedência. Como as expressões em uma linguagem de programação completa pode ter vários níveis de precedência (bem mais do que três), essa acaba se tornando uma parte grande da gramática da linguagem. A seguir veremos um exemplo de gramática para uma linguagem de programação simples.
Agora que já vimos as características das gramáticas livres de contexto e alguns exemplos, vamos ver uma gramática para uma linguagem de programação simples, que demonstra o tipo de situações com as quais teremos que lidar para criar o analisador sintático de um compilador.
Anotem o link da pasta!
Será utilizada para disponibilização dos materiais e dos slides das aulas!
Orientações
https://goo.gl/RQRr9i