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:

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:

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

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:

• 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.

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.

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)

T�picos:

T�picos:

Semana 5 (TP+P)

T�picos:

Semana 6 (T1)

F�rias de P�scoa: n�o houve aula

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.

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)

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)

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).

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.

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.

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).

T�picos:

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.

T�picos:

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