Processamento de Linguagens e Compiladores

Ano Lectivo: 08/09 (2º semestre)

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

Docentes: Pedro Rangel Henriques (406012) + Daniela da Cruz

Teórica (4ªfeira, 10h00-11h00) (5ªfeira, 12h00-13h00)	Teórico-Práticas (TP1: 3ªfeira, 16h00-19h00) (TP2: 6ªfeira, 10h00-13h00)
2009/mar/04-05	2009/mar/03-06
2009/mar/11-12	2009/mar/10-13
2009/mar/18-19	2009/mar/17-20
2009/mar/25-26	2009/mar/24-27
2009/abr/01-02	2009/mar/31-abr/03
2009/abr/08-09 (Páscoa)	2009/abr/07-10 (Páscoa)
2009/abr/15-16	2009/abr/17
2009/abr/22-23	2009/abr/21-24
2009/abr/29-30	2009/abr/28
2009/mai/06-07	2009/mai/05-08
2009/mai/13-14 (tolerância de ponto: "Enterro da Gata")	2009/mai/12-15 (tolerância de ponto: "Enterro da Gata")
2009/mai/20-21	2009/mai/19-22
2009/mai/27-28	2009/mai/26-29
2009/jun/03-04	2009/jun/02-05
2009/jun/10-11 (feriados)	2009/jun/09-13

Semana 1 (T1 + T2)

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 1ª 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 2009.Jun.09 para Avaliação Prática (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 1ªaula e ao longo da 2ªaula, foi definido o conceito de Processador de Linguagens, dados exemplos (Compiladores, Interpretadores e Tradutores/Transformadores específicos), e caracterizadas as 2 grandes fases do Processamento de Linguagens: o Reconhecimento (ou Análise), e a Geração (ou Síntese). Foi apresentada a noção de Representação Intermédia, a separar o FrontEnd do BackEnd, e discutiu-se com detalhe as componentes de optimização e geração de código máquina próprias de um compilador (tendo-se analisado a relação intrínseca entre o Compilador a Arquitectura do Processador e o Sistema Operativo). 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.
Depois caracterizaram-se, ao pormenor e via exemplos, as três fases canónicas da Análise: a Análise Léxica, para converter sequências de caracteres em símbolos terminais da linguagem (os vocábulos do Alfabeot); a Análise Sintáctica, para reconstruir a Árvore de Derivação da frase (a qual descreve a sua forma ou estrutura) a partir da sequência de símbolos; a Análise Semântica, para determinar o valor exacto da frase, completando a árvore com os valores associados aos símbolos.

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, grep.

Resumo:

Na aula foi apresentada a motivação para o uso de expressões regulares como forma de definir padrões de frases a pesquisar em texto, tendo sido usados os utilitários vi, egrep, com os quais se fizeram várias experiências de definição de expressões regulares de forma a introduzir os operadores básicos e os operadores extra.
Foi resolvida a Questão 2 da 1ªFolha de Problemas (Ficha Prática 1). As alienas não resolvidas deverão ser completadas pelos alunos em casa, disponibilizado-se para isso três ficheiros de teste: teste1; teste2; teste3.

Semana 2 (T1 + T2)

Tópicos:

Processamento de Linguagens -- conceitos básicos:
- Análise: Léxica, Sintáctica e Semântica; caracterização de cada uma (In/Out), composição entre elas --- continuação da apresentação de exemplos para consolidar estes conceitos.
- Apresentação da Gramática da Linguagem LISP (adulterada) que servirá de "running-example"
```
    Lisp -> BEGIN SExp END
    SExp -> pal
          | num
          | "(" SExpLst ")"
    SExpLst -> &
          | SExp SExpLst
```
- A Análise Léxica:
  - caracterização rigorosa do problema e ilustração com a gramática LISP.
  - método baseado na pesquisa numa Tabela de Símbolos.
  - método baseado num Autómato Determinista Finito

Semana 2 (TP+P)

Tópicos:

Processamento de Linguagens Regulares:
- Expressões Regulares para definir padrões de frases (ou sub-frases) para pesquisa em texto: Recapitulação do conceito; seu papel na construção de Filtros de Texto; Definição formal; Notação estendida.
- Filtros de Texto: Introdução ao conceito, filtros passa-baixo, passa-alto e transformadores; Exemplos; Desenvolvimento Automático com recurso a Geradores de Programas.
- O Gerador de Programas FLex: Arquitectura; Utilização -- Sistema de Regras de Produção (Condição - Acção) na forma concreta de (ExpressãoRegular {CodigoC})
- Exercícios -- Ficha 1: Problema 3.0 (filtro de Palavras - retirar ESTE, retirar todos menos ESTE, mudar ESTE); Problema 3.3 (Somador - retirar todos os números, deixar passar só os números; escrever a soma dos números).

Semana 3 (T1 + T2)

Tópicos:

Processamento de Linguagens:
- A Análise Léxica:
  - método baseado num Autómato Determinista Finito: algoritmo genérico de reconhecimento.
Autómatos Finitos Determinista e Não-Deterministas:
- conceito e definição informal
- representação de uma ER através de um AD, transformação directa, informal.

Semana 3 (TP+P)

Tópicos:

Processamento de Linguagens Regulares:
- Expressões Regulares para definir padrões de frases (ou sub-frases) para pesquisa em texto.
- Filtros de Texto.
- O Gerador de Programas FLex: Utilização -- Sistema de Regras de Produção (Condição - Acção) na forma concreta de (ExpressãoRegular {CodigoC})
- Exercícios -- Ficha 1: Problema 3.1 (filtro de Palavras - retirar EU: e ESTE: no início da linha, substituir EU por um nome fixo ou ELE por um variável); Problema 3.3 (Somador - escrever a soma de todos os algarismos e de todos os números (retirando só os números, retirando tudo e deixando só os números); apresentar somas parciais quando aparece "="; só somar e apresentar parciais depois de "+" e até novo "+").

Semana 4 (T1 + T2)

Tópicos:

Autómatos Finitos Determinista e Não-Deterministas:
- definição formal de AD e AND.
- transformação informal de um ER para um AD e conversão sistemática de ER para AND.
- conversão de AND para AD; a função epsilon-fecho.
- regras, sistematização e exemplos.

Semana 4 (TP+P)

Tópicos:

Processamento de Linguagens Regulares:
- Expressões Regulares para definir padrões de frases (ou sub-frases) para pesquisa em texto.
- Filtros de Texto.
- O Gerador de Programas FLex: Utilização -- Sistema de Regras de Produção (Condição - Acção) na forma concreta de (ExpressãoRegular {CodigoC})
- Exercícios -- Ficha 1: Problema 3.1 (filtro de Palavras - substituir EU por um nome fixo ELE por um variável) -- análise de variantes, conclusão; Problema 3.2 (Expansor de Abreviaturas - substituição de um conjunto fixo de abreviaturas pelo respectivo termo expandido).

Semana 5 (T1 + T2)

Tópicos:

Autómatos Finitos Determinista e Não-Deterministas:
- representação de um AD em memória (grafo)
- Autómato Reactivo, conceito, definição e aplicações concretas
Processamento de Linguagens:
- A Análise Léxica:
  - reconhecimento dos símbolos terminais através de um Autómato Reactivo: algoritmo genérico de reconhecimento.
- A Análise Sintáctica:
  - Gramática Independente de Contexto (GIC)
  - Parsing Top-Down (TD) e Bottom-Up (BU)

Semana 5 (TP+P)

Tópicos:

Processamento de Linguagens Regulares:
- Expressões Regulares para definir padrões de frases (ou sub-frases) para pesquisa em texto.
- Filtros de Texto.
- O Gerador de Programas FLex: Utilização -- Sistema de Regras de Produção (Condição - Acção) na forma concreta de (ExpressãoRegular {CodigoC})
- Exercícios -- Ficha 1: Problema 3.2 (Expansor de Abreviaturas - substituição de um conjunto fixo de abreviaturas pelo respectivo termo expandido, incluindo o tratamento de prefixos e sufixos eventualmente na mesma palavra). Problema 3.4 (Tratamento de Documentos Anotados em XML - remoção de marcas, balanceamento de marcas de abertura e fecho, validação do fecho por ordem inversa da abertura).

Semana 6 (T1 + T2)

Tópicos:

A Análise Sintáctica:
- Gramática Independente de Contexto (GIC).
- Cadeia de Derivação e Árvore de Derivação, ou Árvore de Parsing.
- Parsing Top-Down (TD) e Bottom-Up (BU).

Semana 6 (TP+P)

Tópicos:

Processamento de Linguagens:
- A Análise Léxica:
  - reconhecimento dos símbolos terminais através de um Autómato Reactivo: geração automática com recurso ao Flex.
- Linguagens e Gramáticas:
  - Concepção de Linguagens e Desenho da respectiva Gramática Independente de Contexto (GIC).
- Exercícios -- Ficha 2: Problema 2.1 (Linguagem para interrogação de Bases de Dados, SQL, restrita ao comando SELECT; Definição da Gramática e geração do respectivo Analisador Léxico).

Semana 7 (T1 + T2)

Tópicos:

A Análise Sintáctica:
- Gramática Independente de Contexto (GIC).
- Cadeia de Derivação e Árvore de Derivação, ou Árvore de Parsing.
- Parser Recursivo-Descendente puro (RD)

Semana 7 (TP+P)

Tópicos:

Processamento de Linguagens:
- A Análise Léxica:
  - reconhecimento dos símbolos terminais através de um Autómato Reactivo: geração automática com recurso ao Flex.
- Linguagens e Gramáticas:
  - Concepção de Linguagens e Desenho da respectiva Gramática Independente de Contexto (GIC).
- Exercícios -- Ficha 2: Problema 2.2 (Linguagem para simulação de uma Máquina de Venda de Chocolates; Definição da Gramática e geração do respectivo Analisador Léxico). Problema 2.4 (Linguagem para anotação de documentos, XML; Definição da Gramática).

Semana 8 (T1 + T2)

Tópicos:

A Análise Sintáctica, Estratégia Top-Down:
- LookAhead das Produções e a Tabela de Parsing LL(1)
- Parser Recursivo-Descendente Genérico e Guiado-por-Tabela (RD)
- Conceito e Algoritmo do Parser LL(1); a stack de símbolos e as acções de parsing.

Semana 8 (TP+P)

Tópicos:

Processamento de Linguagens:
- A Análise Léxica:
  - reconhecimento dos símbolos terminais através de um Autómato Reactivo: geração automática com recurso ao Flex.
- Linguagens e Gramáticas:
  - Concepção de Linguagens e Desenho da respectiva Gramática Independente de Contexto (GIC).
- Exercícios -- Ficha 2 (continuação dos exercícios anteriores para esclarecimento e reforço das ideias base)

Semana 9 (T1 + T2)

Tópicos:

A Análise Sintáctica, Estratégia Bottom-Up:
- Conceito e Algoritmo do Parser LR(); a stack de estados e as acções de parsing.
- O Autómato Determinista LR(0) e as Tabelas de Parsing SLR(1) ACTION e GOTO; construção de um exemplo.

Semana 9 (TP+P)

Tópicos:

Processamento de Linguagens:
- A Análise Sintáctica e Semântica:
  - geração automática de Analisadores Dirigidos pela Sintaxe com recurso ao Yacc.
- Linguagens e Gramáticas:
  - Concepção de Linguagens e Desenho da respectiva Gramática Independente de Contexto (GIC).
- Exercícios -- Ficha 3: Problemas 3.1-a) a d) (Linguagem para descrição de uma lista de notas e cálculo do número de elementos, do somatório e da média; Definição da Gramática e geração do respectivo TDS); Introdução ao Problema 3.1-e) (alteração da gramática anterior para definir uma Linguagem que suporte a descrição da lista de notas de vários alunos identificados pelo nome).
- Comparação do Parsing LL(1) e SLR(1) tomando como caso de estudo a GIC do Problema 3.1a): construção das respectivas Tabelas de Parsing e estudo da evolução da Stack de Parsing (dos símbolos a reconhecer no caso do LL(1) e dos estados alcançados no caso do SLR(1)) para uma frase de entrada concreta.

Semana 10 (T1 + T2)

Tópicos:

A Análise Sintáctica, Estratégia Bottom-Up (cont. das aulas da semana anterior).

Semana 10 (TP+P)

Tópicos:

Processamento de Linguagens:
- A Análise Sintáctica e Semântica:
  - geração automática de Analisadores Dirigidos pela Sintaxe com recurso ao Yacc.
- Linguagens e Gramáticas:
  - Concepção de Linguagens e Desenho da respectiva Gramática Independente de Contexto (GIC).
- Exercícios -- Ficha 3: Problemas 3.4 (Linguagem para anotação de documentos XML; Definição da Gramática e geração do respectivo TDS);

Semana 11 (T1 + T2)

Tópicos:

A Análise Sintáctica, Estratégias Top-Down e Bottom-Up (conclusão deste tópico).
Geração de Código:
- Definição do problema -- geração e optimização;
- Estratégia TDS (Dirigida pela Sintaxe e suportada numa GT) e TDSem (Dirigida pela Semântica e suportada numa GA);
- Esquemas de tradução;
- Máquinas Virtuais, definição e razões para o seu uso (vantagens e desvantagens); exemplos concretos;
- A Máquina de Stack Virtual VM: arquitectura, principio de funcionamento, conjunto de instruções, programas-exemplo

Semana 11 (TP+P)

Tópicos:

Processamento de Linguagens:
- A Análise Sintáctica e Semântica; Geração de Código:
  - geração automática de Compiladores Dirigidos pela Sintaxe com recurso ao Yacc.
- Linguagens e Gramáticas:
  - Concepção de Linguagens e Desenho da respectiva Gramática Independente de Contexto (GIC).
- Exercícios -- Trabalho Prático nuº 2: Análise muito detalhada da Linguagem LogoLISS; sua filosofia e concepção (simbiose das Logo e LISS); sua sintaxe, semântica estática e dinâmica; erros de compilação (sintácticos e semânticos) e erros de execução. Construção de um programa-exemplo correcto, Tabela de Identificadores e Código Gerado.

Semana 12 (T1 + T2)

Tópicos:

Geração de Código:
- Discussão detalhada de Expressão (conceito, representação interna em árvore, sintaxe); geração de Assembly para calcular uma expressão.
- Geração de Código para as instruções de controlo condicional e ciclico

Semana 12 (TP+P)

Tópicos:

Processamento de Linguagens:
- A Análise Sintáctica e Semântica; Geração de Código:
  - geração automática de Compiladores Dirigidos pela Sintaxe com recurso ao Yacc.
- Linguagens e Gramáticas:
  - Concepção de Linguagens e Desenho da respectiva Gramática Independente de Contexto (GIC).
- Exercícios -- Trabalho Prático nuº 2: Desenvolvimento de um Compilador para a Linguagem LogoLISS gerando Assembly da máquina de stack virtual VM; geração do analisador léxico e sintáctico; inicio da análise semântica.

Semana 13 (T1 + T2)

Não houve aulas devido aos feriados nacionais.

Semana 13 (TP+P)

Tópicos:

Processamento de Linguagens:
- A Análise Sintáctica e Semântica; Geração de Código:
  - geração automática de Compiladores Dirigidos pela Sintaxe com recurso ao Yacc.
- Linguagens e Gramáticas:
  - Concepção de Linguagens e Desenho da respectiva Gramática Independente de Contexto (GIC).
- Exercícios -- Trabalho Prático nuº 2: Desenvolvimento de um Compilador para a Linguagem LogoLISS gerando Assembly da máquina de stack virtual VM; análise semântica; inicio da geração de código.

author: prh@di.uminho.pt;
Last modified: sábado, Junho 6, 2009 at 10:01