Processamento de Linguagens e Compiladores
Ano Lectivo: 09/10 (2º semestre)
Sumário das Aulas Teóricas e das Teórico-Práticas (LCC)
Docentes: Pedro Rangel Henriques + Jorge Rocha + JoséJoão Almeida
Semana 1 (T1)
Tópicos:
- Apresentação da Disciplina:
- Objectivos e Funcionamento;
- Avaliação e Trabalhos Práticos;
- Programa e Bibliografia;
- O Processamento de Linguagens na UM (lp@di.um.pt) e o Site www.di.uminho.pt/~gepl/LP;
o Mapa de Conceitos sobre LP.
- Introdução ao tema Processamento de Linguagens -- conceitos básicos:
- Linguagem (Natural, Artificial e Formal), Frase -- estrutura (ou forma) e significado, Gramática;
- Sintaxe e Semântica;
- Processamento, Reconhecimento (ou Análise) e Síntese (ou Geração);
os vários tipos de Processadores e o caso particular dos Compiladores.
- Geração Automática de Processadores.
- Análise: Léxica, Sintáctica e Semântica; caracterização de cada uma (In/Out), composição entre elas.
Resumo:
Na 1ª parte da aula foi apresentada a motivação e grande objectivo da disciplina, a equipe docente
e definido o método de avaliação, com sua componente teórica e prática.
Foram marcadas as datas 2010.Mar.22 e 2010.Maio.17 para entrega dos 2 TPs a realizar ao longo do semestre e
2009.Jun.26 para a Avaliação Teórica (realização do Teste único).
No resto da aula foi definido o conceito de Linguagem (vocabulário e regras gramaticais)
e de Processador de Linguagens;
foram caracterizadas as 2 grandes fases do Processamento de Linguagens:
o Reconhecimento (ou Análise), e a Geração (ou Síntese).
Semana 1 (T2)
Tópicos:
- Introdução ao tema Processamento de Linguagens -- conceitos básicos:
- Linguagem (Natural, Artificial e Formal), Frase -- estrutura (ou forma) e significado, Gramática;
- Sintaxe e Semântica;
- Processamento, Reconhecimento (ou Análise) e Síntese (ou Geração);
os vários tipos de Processadores e o caso particular dos Compiladores.
Resumo:
Nesta aula passaram-se em revisão os conceitos essenciais da aula anterior de modo a consolidar
as bases que suportam esta área de ensino e investigação.
Fez-se a distinção entre Linguagens Naturais e Artificiais (formais) e
entre Linguagens Textuais e Visuais;
foram dados exemplos de Processadores de Linguagens(Compiladores, Interpretadores e Tradutores/Transformadores específicos).
Por fim, introduziu-se, ainda, o conceito de Geração Automática de Programas, como a forma actual
de desenvolver os Processadores de Linguagens a partir da Gramática.
Semana 1 (TP+P)
Tópicos:
- Introdução ao tema Processamento de Linguagens Regulares:
- Expressões Regulares para definir padrões de frases (ou sub-frases) para pesquisa em texto;
Motivação -- os utilitários de Linux: vi, egrep.
- Foi resolvido o exercício 1 da Ficha 1.
Notas:
Semana 2 (T1)
Tópicos:
- Introdução ao tema Processamento de Linguagens -- conceitos básicos (cont.):
- Processamento sistemático baseado no Reconhecimento (ou Análise), Representação interna do Significado e na Síntese (ou Geração);
- Caracterização formal das 3 fases de Análise: Léxica, Sintáctica e Semântica.
Resumo:
O tópico central desta aula foi a caracterização do processo de Reconhecimento como sendo um pipeline de três actividades:
- a Análise Léxica que lê um texto-fonte (sequência de caracteres) e reconhece os Símbolos Terminais (cujo conjunto está pré-definido), construindo uma sequência com os códigos desses Símbolos;
- a Análise Sintáctica, ou Parsing, que recebe uma sequência de Símbolos Terminais e verifica se pode ter sido derivada da Gramática Independente de Contexto (GIC) da Linguagem, devolvendo uma Árvore de Derivação com a combinação das produções usadas na construção da frase;
- a Análise Semântica que que recebe uma Árvore de Derivação válida (correspondente à forma ou estrutura do texto-fonte) e lhe junta os valores concretos dos Símbolos dando-lhe um significado completo.
Semana 2 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Léxica:
- Implementação clássica do Analisador Léxico com base na pesquisa do código numa Tabela de Símbolos;
- Implementação moderna do Analisador Léxico com base na descrição dos Símbolos através de Expressões Regulares e com recurso a um Autómato Determinista Reactivo.
- Expressões Regulares: Definição Formal e exemplos.
Semana 2 (TP)
Tópicos:
- Introdução ao tema Processamento de Linguagens Regulares:
- Expressões Regulares (ERs) para definir padrões de frases (ou sub-frases) para pesquisa em texto;
- Filtros de Texto, programas que transformam texto não-estruturado em texto (ou em outra saída) através da reacção ao reconhecimento de sub-textos (sub-strings);
- Geração automática de Filtros de Texto com base na descrição dos padrões a que se quer reagir através de ERs -- uso do Gerador Flex.
- Foi resolvido o exercício 2.1 da Ficha 1: Filtragem do texto de uma Entrevista com anotações EU e ELE para marcar as falas do entrevistador e do entrevistado.
Semana 3 (T1)
Tópicos:
- Processamento de Linguagens -- Análise Léxica:
- Implementação moderna do Analisador Léxico com base na descrição dos Símbolos através de Expressões Regulares e com recurso a um Autómato Determinista Reactivo.
- A possibilidade de Geração Automática do Analisador Léxico; enquadramento de uma ferramenta como o Flex neste contexto.
- Expressões Regulares:
- Definição Formal e exemplos (cont.);
- Algoritmo de Reconhecimento Recursivo-Descendente; o princípio, vantagens e desvantagens.
Semana 3 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Léxica:
- Implementação moderna do Analisador Léxico com base na descrição dos Símbolos através de Expressões Regulares e com recurso a um Autómato Determinista Reactivo.
- Definição de Autómato de estados finitos Determinista (AD) e implementações alternativas da Função de Transição.
- O Algoritmo de Reconhecimento guiado pela Função de Transição de um AD -- algoritmo iterativo, eficiente e genérico.
- Transformação sistemática de uma ER num AND (Autómato de estados finitos Não-Determinista).
Semana 3 (TP+P)
Tópicos:
- Introdução ao tema Processamento de Linguagens Regulares:
- Filtros de Texto, programas que transformam texto não-estruturado em texto (ou em outra saída) através da reacção ao reconhecimento de sub-strings);
- Geração automática de Filtros de Texto com base na descrição dos padrões a que se quer reagir através de ERs -- uso do Gerador Flex: estrutura geral de uma especificação; exploração de novas facetas; mecanismos de desambiguação.
- Cont. da resolução do exercício 2.1 da Ficha 1: Filtragem do texto de uma Entrevista com anotações EU e ELE para marcar as falas do entrevistador e do entrevistado:
substituição das anotações por palavras fixas e pelo nomes concretos, descritos no próprio texto.
- Discussão da filosofia geral para resolução do exercício 2.2 da Ficha 1 (Expansor de Abreviaturas).
- Implementação complementar de outros pequenos exemplos complementares.
Semana 4 (T1)
Tópicos:
- Processamento de Linguagens -- Análise Léxica:
- Implementação moderna do Analisador Léxico com base na descrição dos Símbolos através de Expressões Regulares e com recurso a um Autómato Determinista Reactivo.
- Definição de Autómato de estados finitos Não-Determinista (AND); exemplos e problemas práticos das transições espontâneas (por &) e das transições para mais de um estado pelo mesmo símbolo.
- A Transformação sistemática de um AND em AD via a função &-fecho() que aglutina os destinos de todos os caminhos de peso &.
- Definição de Autómato de estados finitos Determinista Reactivo (AR) e seu interesse prático para realizar acções de processamento além do reconhecimento.
- O Algoritmo de Processamento (reconhecimento+reacção) guiado pela Função de Transição de um AR -- algoritmo iterativo, eficiente e genérico.
Semana 4 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Léxica (conclusão deste tópico):
- Implementação moderna do Analisador Léxico com base na descrição dos Símbolos através de Expressões Regulares e com recurso a um Autómato Determinista Reactivo.
- As Acções Semânticas típicas a incluir na Função de Reacção ou Resposta de um AR (a executar antes de fazer a Transição de Estado) para produzir um Analisador Léxico a partir de um filtro de texto que encontra todos os Símbolos Terminais (palavras-reservadas, sinais e símbolos variáveis) de uma Linguagem
- Processamento de Linguagens -- Análise Sintáctica (introdução a este tópico):
- Recapitulação do esquema geral de um Processador de Linguagens com o Fronte-End (FE), responsável pelo reconhecimento, e com o Back-End (BE), responsável pela geração ou produção da saída; enquadramento das tarefas do
Analisador Sintáctico ou Parser como 2º patamar do reconhecimento, entre a Análise Léxica e a Semântica.
- A tarefa de reconhecer a forma de um texto e a exigência de recorrer às Regras de composição dos símbolos terminais para formar frases válidas -- Gramática Independente de Contexto;
recurso a uma Árvore de Derivação para reproduzir as Regras usadas e representar a forma.
- Definição formal de Gramática Independente de Contexto (GIC); pequenos exemplos correntes.
Semana 4 (TP+P)
Tópicos:
- Introdução ao tema Processamento de Linguagens Regulares:
- Filtros de Texto, programas que transformam texto não-estruturado em texto (ou em outra saída) através da reacção ao reconhecimento de sub-strings);
- Geração automática de Filtros de Texto com base na descrição dos padrões a que se quer reagir através de ERs -- uso do Gerador Flex; exploração de novas facetas: operador contexto direito e estados de reconhecimento (definição e activação de condições de contexto).
- Resolução do exercício 2.2 da Ficha 1: Expansão de Abreviaturas (primeiro a partir de uma lista fixa de abreviaturas, depois permitindo que o próprio texto contenha as definições das abreviaturas a expandir).
- Análise das soluções apresentadas por cada grupo de trabalho.
Semana 5 (T1)
(aula de substituição dada por JGR)
Tópicos:
Semana 5 (T2)
(aula de substituição dada por JGR)
Tópicos:
Semana 5 (TP+P)
Tópicos:
Não houve aula pelos docentes estarem ausentes; será dada aula de substituição.
Semana 6 (T1)
Férias de Páscoa: não houve aula
Semana 6 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica (introdução a este tópico):
- A tarefa de reconhecer a forma de um texto e a exigência de recorrer às
Regras de composição dos símbolos terminais para formar frases válidas -- Gramática Independente de Contexto;
recurso a uma Árvore de Derivação para reproduzir as Regras usadas e representar a forma.
- Definição formal de Gramática Independente de Contexto (GIC); exemplos de GICs e do processo de derivação
de frases -- Lista de números ou palavras:
1: Frase --> INICIO Lista FIM
2: Lista --> Elem
3: | Elem "," Cauda
4: Cauda --> Lista
5: Elem --> pal
6: | num
e Linguagem Lisp:
1: Lisp --> SExp
2: SExp --> pal
3: | num
4: | "(" SExpLst ")"
5: SExpLst --> SExp SExpLst
6: | &
Semana 6 (TP+P)
Tópicos:
- Processamento de Linguagens Regulares:
- Filtros de Texto, programas que transformam texto não-estruturado em texto (ou em outra saída) através da reacção ao reconhecimento de sub-strings);
- Geração automática de Filtros de Texto com base na descrição dos padrões a que se quer reagir através de ERs -- uso do Gerador Flex; exploração de novas facetas: operador contexto direito e estados de reconhecimento (definição e activação de condições de contexto).
- Resolução do exercício 2.4 da Ficha 1: Filtragem de documentos anotados em XML.
- Implementação de Analisadores Léxicos como reconhecedores de ERs que retornam o código dos símbolos
terminais cada vez que encontram o texto de um símbolo -- recurso ao Gerador Flex.
- Resolução do exercício 2.1 da Ficha 2: Analisador Léxico para uma Query em SQL.
Semana 7 (T1)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- A tarefa de reconhecer a forma de um texto e a exigência de recorrer às
Regras de composição dos símbolos terminais para formar frases válidas -- Gramática Independente de Contexto;
recurso a uma Árvore de Derivação para reproduzir as Regras usadas e representar a forma.
- Parsing Top-Down (TD): Parser Recursivo-Descendente (RD)
- Reconhecimento dos Símbolos Terminais; função especifica para cada versus função genérica parametrizada.
- Reconhecimento dos Símbolos Não-Terminais; função simples, quando não há alternativas.
Semana 7 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- Parsing Top-Down (TD): Parser Recursivo-Descendente (RD)
Semana 7 (TP+P)
Tópicos:
- Processamento de Linguagens Regulares:
Discussão e Avaliação do 1ºTrabalho Prático.
Semana 8 (T1)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- Parsing Top-Down (TD): Parser Recursivo-Descendente (RD)
- Reconhecimento dos Símbolos Não-Terminais; função simples, quando há alternativas; LookAhead(1),
First(1) e Follow(1).
- Exemplo de um Parser RD para reconhecer a linguagem Lisp (Symbolic Expressions)
Semana 8 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- Parsing Top-Down (TD): Parser Recursivo-Descendente (RD)
- Reconhecimento dos Símbolos Não-Terminais; função simples, quando há alternativas; LookAhead(1),
First(1) e Follow(1).
- Tabela de Decisão LL(1) que escolhe a produção em função do Símbolo (N) a reconhecer e do símbolo lido (Tab_LL1)
- Função Recursiva genérica para reconhecimento dos Símbolos Não-Terminais guiada pela Tab_LL1
Semana 8 (TP+P)
Tópicos:
- Processamento de Linguagens Regulares:
Conclusão da Discussão e Avaliação do 1ºTrabalho Prático.
- Implementação de Analisadores Léxicos como reconhecedores de ERs que retornam o código dos símbolos
terminais cada vez que encontram o texto de um símbolo -- recurso ao Gerador Flex.
- Resolução dos exercícios 2.2 e 2.3 da Ficha 2: Desenvolvimento de Analisadores Léxicos para as linguagens de Listas e Lisp.
Semana 9 (T1)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- Parsing Top-Down (TD): Parser (iterativo) LL(1)
- Tabela de Decisão LL(1), generalização para suportar também os símbolos Terminais: escolhe a produção ou aceitação do símbolo/frase em função do símbolo a reconhecer (N ou T, incluindo EOF) e do símbolo lido (Tab_LL1)
- Função Iterativa standard (genérica) para reconhecimento dos Símbolos Não-Terminais e Terminais guiada pela Tab_LL1 -- Parser LL(1)
Semana 9 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- Parsing Bottom-Up (BU): Parser (iterativo) LR(K)
- Função Iterativa standard (genérica) para reconhecimento dos Símbolos Não-Terminais e Terminais guiada pela Tab_LR -- Parser LR
- Tabela de Decisão LR(K) (Tab_LR), conceito e acções possíveis: escolhe a produção a reduzir ou aceitação do símbolo/frase em função do estado de reconhecimento e do símbolo lido.
Semana 9 (TP+P)
Tópicos:
- Implementação de Analisadores Léxicos como reconhecedores de ERs que retornam o código dos símbolos
terminais cada vez que encontram o texto de um símbolo -- recurso ao Gerador Flex.
- Resolução do exercício 2.4 da Ficha 2: Desenvolvimento de um Analisador Léxico para a linguagem XML.
Semana 10 (T1)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- Parsing Bottom-Up (BU): Parser (iterativo) LR(k)
- Recapitulação do algoritmo da Função Iterativa genérica para reconhecimento dos Símbolos Não-Terminais e Terminais guiada pela Tab_LR -- Parser LR
- Tabela de Decisão LR(k) (Tab_LR) como sendo a função de transição do Autómato Determinista de Memória
(push-down automaton) LR(k); apresentação do conceito de Item LR(k).
Semana 10 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- Parsing Bottom-Up (BU): Parser (iterativo) LR(k)
- Recapitulação do conceito de Item LR: distinção entre Item LR(0), LR(1), SLR(1) e LALR(1)
- Construção do Autómato Determinista LR(0): Kernel de um estado; construção completa de um estado através do cálculo do Fecho de um item; transição de um estado para novo estado por um símbolo T ou N; redução num estado --- exemplo para a Lista de números ou palavras (ver GIC dessa linguagem no sumário da aula T2 da Semana 6).
Semana 10 (TP+P)
Tópicos:
- Escrita de Gramáticas Independentes de Contexto (GIC)
- Implementação de Analisadores Sintácticos (Parsers) como reconhecedores de GIC com recurso ao Gerador Yacc.
- Resolução do exercício 1.3 da Ficha 3: Desenvolvimento de um Analisador Sintáctico para a linguagem XML.
Semana 11 (T1)
Tópicos:
- Processamento de Linguagens -- Análise Sintáctica:
- Parsing Bottom-Up (BU): Parser (iterativo) LR(k)
- Tabela de Decisão LR(k) (Tab_LR) como sendo a função de transição do Autómato Determinista de Memória
(push-down automaton) LR(k).
- Construção do Autómato Determinista LR(0): Kernel de um estado; construção completa de um estado através do cálculo do Fecho de um item; transição de um estado para novo estado por um símbolo T ou N; redução num estado; conflitos
LR(0) e resolução --- discussão com base em exemplos.
Semana 11 (T2)
Tópicos:
- Processamento de Linguagens -- Análise Semântica e Tradução:
- Acções Semânticas (AS) e Gramáticas Tradutoras (GT): conceito, definição formal e exemplos
Semana 11 (TP+P)
Tópicos:
- Escrita de Gramáticas Independentes de Contexto (GIC)
- Implementação de Analisadores Sintácticos (Parsers) e Semânticos (Tradutores) como reconhecedores de GT com recurso ao Gerador Yacc.
- Resolução do exercício 1.1 da Ficha 3: Desenvolvimento de um Processador para a linguagem de Listas de Notas.
Semana 12 (T1)
Tópicos:
- Processamento de Linguagens -- Análise Semântica e Tradução:
- A Tabela de Identificadores (TabId): conceito, definição formal, relevância para qualquer Processador de Linguagens, exemplos e implementação na forma de uma Tabela de Hash.
Semana 12 (T2)
Tópicos:
- Processamento de Linguagens -- Tradução:
- A Máquina Virtual VM: conceitos básicos sobre uma Máquina de Stack; arquitectura e conjuntos de instruções Assembly da VM
Semana 12 (TP+P)
Tópicos:
- Escrita de Gramáticas Independentes de Contexto (GIC) e Gramáticas Tradutoras (GT).
- Implementação de Analisadores Sintácticos (Parsers) e Semânticos (Tradutores) como reconhecedores de GT com recurso ao Gerador Yacc.
- Resolução do exercício 1.1 da Ficha 3: Desenvolvimento de um Processador para a linguagem de Listas de Notas.
Semana 13 (T1)
Tópicos:
- Processamento de Linguagens -- Tradução:
- A Máquina Virtual VM: conceitos básicos sobre o princípio de funcionamento de uma Máquina Virtual, algoritmo do simulador; análise detalhada de alguns conjuntos de instruções Assembly em particular (PUSH, LOAD e STORE).
Semana 13 (T2)
Tópicos:
Não houve aula: Feriado Nacional.
Semana 13 (TP+P)
Tópicos:
- Escrita de Gramáticas Independentes de Contexto (GIC) e Gramáticas Tradutoras (GT).
- Implementação de Analisadores Sintácticos (Parsers) e Semânticos (Tradutores) como reconhecedores de GT com recurso ao Gerador Yacc.
- Conclusão do exercício 1.1 da Ficha 3: Desenvolvimento de um Processador para a linguagem de Listas de Notas.
- Apresentação do exercício 1.2 da Ficha 3: Processamento das Declarações de Tipo e variável na Linguagem nLP.
-
Semana 14 (T1)
Tópicos:
- Processamento de Linguagens -- Tradução:
- A Máquina Virtual VM: análise detalhada de alguns conjuntos de instruções Assembly; exemplos.
Semana 14 (T2)
Tópicos:
Não houve aula: Feriado Nacional.
Semana 14 (TP+P)
Tópicos:
- Escrita de Gramáticas Independentes de Contexto (GIC) e Gramáticas Tradutoras (GT).
- Implementação de Analisadores Sintácticos (Parsers) e Semânticos (Tradutores) como reconhecedores de GT com recurso ao Gerador Yacc.
- Reflexão sobre o exercício 1.2 da Ficha 3, implementação: Processamento das Declarações de Tipo e variável na Linguagem nLP.
-
author: prh@di.uminho.pt;
Last modified: sábado, Junho 19, 2010 at 01:59