Processamento de Linguagens

Ano Lectivo: 09/10 (2º semestre)

Sumário das Aulas Teóricas e das Teórico-Práticas (LEI)

Docentes: Pedro Rangel Henriques + João Saraiva + Daniela da Cruz

Teórica (2ªfeira, 09h00-10h00)	Teórica (5ªfeira, 14h00-15h00)	Teórico-Práticas (TP2: 2ªfeira, 16h00-18h00) (TP2: 3ªfeira, 09h00-11h00) (TP3: 3ªfeira, 11h00-13h00) (TP1: 5ªfeira, 09h00-11h00)
2010/02/22	2010/02/25	2010/02/22-23
2010/03/01	2010/03/04	2010/03/01-02
2010/03/08	2010/03/11	2010/03/08-09
2010/03/15	2010/03/18	2010/03/15-6
2010/03/22	2010/03/25	2010/03/22-23
2010/03/29	2010/04/01	2010/03/29-30
2010/04/05	2010/04/08	2010/04/05-06
2010/04/12	2010/04/15	2010/04/13
2010/04/19	2010/04/22	2010/04/19-20
2010/04/26	2010/04/29	2010/04/26-27
2010/05/03	2010/05/06	2010/05/03-04
2010/05/10	2010/05/13	2010/05/10-11
2010/05/17	2010/05/20	2010/05/17-18
2010/05/24	2010/05/27	2010/05/24-25
2010/05/31	2010/06/03	2010/05/31-01
2010/06/07	2010/06/10	2010/06/07-08

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)

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

Por falta de alunos (apareceram 0) o turno TP2 (3ªf das 09h00 as 11h00) não funcionou.
Foi mudado para 4ªf das 11h00 às 13h00 (mesma sala DI-A2) começando a funcionar na próxima semana.

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 de outros pequenos exemplos complementares, para explorar algumas novas facetas.

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 Front-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)
  - Reconhecimento dos Símbolos Não-Terminais; função simples, quando há alternativas; LookAhead e Condição-LL(1).
  - Exemplo de um Parser RD em C para reconhecer uma Lista de Números e Palavras

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 02:00