Engenharia Gramatical
Sumários
27 de Setembro de 2010
- 1. Apresentação da UCE30-EL e em particular do Módulo de EG e ATS:
- Apresentação da Equipe Docente, dos Objectivos e do modo de Funcionamento e Avaliação;
- Introdução e Motivação para a área de Processamento de Linguagens e para o desenvolvimento baseado em Gramáticas e em Geradores de Compiladores.
11 de Outubro de 2010
- 2. Revisão do conceito de Linguagem e sua relação com Gramática:
- Apresentação sumária dos critérios a observar quando se faz o design de uma Linguagem:
- Satisfação dos Requisitos pedidos no enunciado
- Satisfação das Restrições explicitadas no enunciado
- Procura de Legibilidade
- Procura de Simplicidade na utilização para escrever frases.
- 3. Revisão do conceito de Gramática Indepedente de Contexto (GIC) e de Gramática Tradutora (GT); sua definição formal.
- Resolução do Exemplo1: desenho de uma Linguagem e escrita da respectiva Gramática com variantes (ver aqui GIC e GT).
18 de Outubro de 2010
- 3. Revisão do conceito de Gramática Indepedente de Contexto (GIC) e de Gramática Tradutora (GT); sua definição formal.
- Resolução do Exemplo1: desenho de uma Linguagem e escrita da respectiva Gramática com variantes (ver aqui Exemplos-de-Frases e GT).
25 de Outubro de 2010 (aula dada pelo prof. Eric Van Wyk)
- 3. Introdução (prática/pragmática) o conceito de Gramática de Atributos (GA)para especificar a semântica estática e dinâmica de uma linguagem.
- Introdução ao Gerador de Processadores de Linguagens baseado em GAs Silver.
- Exemplo1 (Gramática Genea para definir uma Linguagem para Genealogia e Demografia): desenho de uma Linguagem e escrita da respectiva Gramática com variantes.
GUIÃO DA AULA:
Attribute Grammars (AGs):
- support Semantic Analysis specifications;
- as opposed to Translation Grammars, TG (as those supported by Yacc and other parser generators) that are primarily used for syntactic analysis, although can describe some limited semantic work, AGs are more general and more powerful.
Main phases of a Compiler or Translator:
Syntactic Analysis
- scanning and parsing
- verify or determine the syntactic structure of the program/expression
- generate a tree representing this structure
Semantic Analysis
- compute concrete values and types for variables and expressions
- non-syntactic checks - semantic constraints:
* are all variables in a program declared ?
* are all expressions type correct ?
- report the errors
- report on some characteristics of the program
Optimization
- rewrite the program into a more efficient form
Code Generation
- generate a translation to another language
AGs
- are really for semantic analysis, but can be useful for other tasks as well.
- aim is to decorate the syntax tree with attributes describing the semantics
- think of each node in a syntax tree as an object; we want to compute values for fields (attributes) on these objects such as "type", "isCorrect", "errors", etc.
Yacc semantic actions give us a single unnamed, untyped attribute
Silver is a research prototype AG system developed by my group at Minnesota.
An AG is a CFG with
- set of attributes; attributes have a name and a type
- occurrence relation - what attributes appear on what nonterminals
- defining equations - for computing the value of those attributes
Example 1
Consider a familiar example, the
Genealogia language introduced in the previous lessons.
- show Silver code for Genealogia (no attributes, only parsing)
- show what errors look like in Silver specs
- parse errors, binding errors, type errors ...
Consider also the following
valid sentence of
Genealogia language:
( "Joe" "Smith" M 1955, "Beth" "Johnson" F 1957 )
( "Jane" "Martin" F 1940, "Sam" "Smith" M 1935 )
{
"Mike" M 1965, "Betty" F 1967
}
( "Marvin" "Van Wyk" M 1945, "Lois" "Ter Louw" F 1945 )
{
"Eric" M 1967,
"Kevin" M 1970,
"Stacie" F 1971
}
Next, add
report attribute
- only one synthesized attribute:
synthesized attribute report :: String occurs on Geneology, Families, Family,....
- print simple report
- the solution (more verbose than the Yacc solution, but much more fomal and clear) is split
into the following files:
Geneology.sv +
Person.sv +
Children.sv +
Terminals.sv and
Main.sv plus
silver-compile .
Example 2
Count the number of children and add it the part of the report
generated on the parents
- add one more synthesized attribute:
synthesized attribute numChildren :: Integer occurs on ChildList;
- then the solution is obtained just changing the following file:
Children.sv
Exercise (Example 3)
- use the birth data associated with each child, and compute the year of oldest child's birth
"First child born in ..." - if any children.
- the solution developed by one student, composed by the following files:
Geneology.sv +
Person.sv +
Children.sv .
Example 4
Semantic constraints can be specified as Boolean attributes,
or a "list of errors" attribute
Compute "isCorrect :: Boolean" to check that oldest child born
at least 15years before the youngest parent.
- now some more synthesized attributes must be added:
synthesized attribute isCorrect::Boolean occurs on Geneology, Families, Family ;
synthesized attribute youngestBirthYear:: Integer occurs on Parent, Parents ;
synthesized attribute year::Integer occurs on Year ;
synthesized attribute oldestBirthYear :: Integer occurs on ChildList, Children ;
synthesized attribute birthYear :: Integer occurs on Child ;
- then the solution is obtained changing the following file:
Geneology.sv +
Person.sv +
Children.sv
Exercise (Example 5)
- resulting error message is not so good. Instead replace isCorrect
with errors :: String
Example 6
Inherited attributes, the way to make contextual information accessible after or before the substring where it appears avoiding any global variable.
- Evolve the previous grammar because the resulting error message is still not as good as it could be.
Maybe we'd like a message of the form "Child X born in Y after parents born in Z"
- pass down age of youngest parent (plus 15years) as an inherited attribute
- generate the error message, arguably, at the point in which the error occurs.
- now an inherited attribute must be defined and some additional synthesized attributes must be added:
inherited attribute earliestPossibleBirthYear::Integer occurs on Children, ChildList, Child ;
synthesized attribute errors::String occurs on Geneology, Families, Family, Children, ChildList, Child ;
synthesized attribute youngestBirthYear::Integer occurs on Parent, Parents ;
attribute birthYear::Integer occurs on Child ;
- then the solution is obtained changing the following file:
Geneology.sv +
Children.sv and
Main.sv
Exercise (Example 7)
- add an inherited attribute "currentYear" - set it at the root and
pass it down to all children so that we can compute the child ages
and put them into the report.
- the solution developed by one student, composed by the following files:
Geneology.sv +
Person.sv +
Children.sv +
Terminals.sv and
Main.sv plus
Sample source-text
08 de Novembro de 2010
- 3. Definição formal de Gramática de Atributos (GA) para especificar a semântica estática e dinâmica de uma linguagem (consolidação teórica da introdução prática da última aula).
15 de Novembro de 2010
- Continuação da introdução às GA, às árvores de sintaxe abstrata (AST) e à ferramenta Silver (fazer aqui o download da versão mais recente: SilverNov2010), agora com um novo exemplo para criar uma calculadora de expressões "dc -- desktop calculator language".
GUIÃO DA AULA:
A simple arithmetic expression language.
Consider the Silver specification for "dc" (directory grammars/tutorials/dc ans subdirectory bin).
1. The concrete syntax in
Expr.sv (respective terminal symbols in
TerminalsDC.sv) ensures that operator precedence and
associativity is preserved.
Notice that this Expr.sv version already includes the extension proposed to the students as an working example during the class -- DC Expr now support Logical (and, or, not) and Relational Operators (at moment, jut Equal)
2. A higher order attribute, ast_Expr, is used to compute a tree using
the abstract productions. On this, we compute the value of the
expression since the grammar is simpler. See again
Expr.sv and also the functions defined in
DC.sv
3. In
BetterPP.sv we see the use of inherited attributes. These are
passed down the tree and used to determine when parenthesis need to be used.
To obtain a Compiler and use it, the common files
Main.sv and
silver-compile are also developed and included in the directory.
22 de Novembro de 2010
- Não dei aula por estar na Universidade Nacional de SanLuis, Argentina, no contexto da visita anual do projecto de cooperação bilateral Quixote (aula dada por JJ, a compensar ainda em dezembro).
29 de Novembro de 2010
- Não dei aula por estar na Universidade Nacional de SanLuis, Argentina, no contexto da visita anual do projecto de cooperação bilateral Quixote (aula dada por JJ, a compensar ainda em dezembro).
06 de Dezembro de 2010
- Introdução ao tópico Qualidade de Linguagens
- Enquadramento do tema e justificação da sua necessidade enquanto propósito geral da engenharia aquando do desenvolvimento de um novo produto;
- Caracterização do produto em causa: protocolo de comunicação para um Emissor transmitir a um Recetor determinada informação no sentido de obter uma resposta/reação do Receptor após processar a mensagem (frase da linguagem);
- Identificação dos Critérios que permitem definir qualidade de uma linguagem: Legibilidade (aprendizagem, escrita e compreensão) e Eficácia;
- Factores que tem impacto nos critérios de qualidade -- a identificar e caracterizar na proxima aula;
- Identificação dos factores que determinam a aceitação de uma linguagem: cultura/experiência anterior; disponibilidade do processador e da documentação; dimensão e envergadura do ambiente de desenvolvimento.
13 de Dezembro de 2010
- Esta aula foi totalmente aproveitada para os Grupos fazerem a apresentação (1ªfase) do Projecto Integrado.
03 de Janeiro de 2011
- Continuação da introdução às GA, às árvores de sintaxe abstrata (AST) e à ferramenta Silver (fazer aqui o download da versão mais recente Silver-0.3.1: http://melt.cs.umn.edu/silver/downloads.html), agora com um novo exemplo para desenvolver um compilador para a linguagem de programação "simple".
10 de Janeiro de 2011
- Esta aula foi aproveitada para os Grupos fazerem a apresentação (1ªfase/2ªetape - demo) do Projecto Integrado.
17 de Janeiro de 2011
Continuação do estudo do tópico
Qualidade de Linguagens
- Revisão dos Critérios que permitem definir qualidade de uma linguagem: Legibilidade (aprendizagem, escrita e compreensão) e Eficácia;
- Razões para se estudar uma Linguagem de Programação de segundo Sebesta:
- Aumentar a capacidade de exprimir ideias por escrito;
- Aumentar a sabedoria para fazer uma boa escolha da LP a usar num caso concreto;
- Aumentar a capacidade de aprender novas linguagens;
- Aumentar a percepção sobre a importância da implementação;
- Melhorar a compreensão sobre todo o domínio da programação;
- Classificação das Linguagens de Programação:
- Quanto à cronologia e grau de abstracção (1ª, 2ª, 3ª e 4ª gerações)
- Quanto ao estilo do processamento (compilada/interpretada)
- Quanto ao estilo de programação (imperativa/declarativa)
- Quanto à forma de organizar código (monolítica/modular)
- Quanto à forma de execução (sequencial/concorrente)
- Quanto ao sistema de tipos (fracamente/fortemente tipadas)
- Quanto à forma de expressão (textuais/visuais)
- Quanto à abrangência (domínio geral, GPL/específico, DSL)
* 2º SEMESTRE ***
21 de Fevereiro de 2011
Continuação do estudo do tópico
Qualidade de Linguagens
- Etudo das Características que influenciam os Critérios que permitem definir qualidade de uma linguagem:
- Expressividade; Clareza e Abstração
28 Fevereiro 2011
Continuação do estudo do tópico
Qualidade de Linguagens
- Estudo das Características que influenciam os Critérios que permitem definir qualidade de uma linguagem:
- Expressividade; Clareza e Abstração
Tabela que relaciona as Carateristicas da Linguagem com os Critérios de Qualidade:
| Característica | Aprendizagem | Escrita | Compreensao | Reconhecimento |
| Expressividade | + | + | + | - |
|---|
Tabela que compara várias Linguagens de Programação, segundo as Caraterísticas Identificadas
| Característica | Assembly | Fortran | Basic | Pascal | C | Prolog | ML | C# | Perl | Ruby | PHP | SQL |
| CL1-Expressividade | nS | s | nS | B | B- | s | B | MB | B- | B- | B | MB |
| CL2-Documentação |
| CL3-Unicidade |
| CL4-Consistência |
| CL5-Extensibilidade |
| CL6-Escalabilidade |
| CL7-Paradigma |
| CL8-Fiabilidade |
nS - não Satisfaz, B - Bom, S - Satisfaz
07 de Março de 2011
- Não houve aula --- 2ªf de Entrudo.
14 de Março de 2011
- Esta aula foi aproveitada para os Grupos fazerem a apresentação (2ªfase/1ªetape) do Projecto Integrado.
21 Março 2011
Continuação do estudo do tópico
Qualidade de Linguagens
- Estudo das Características que influenciam os Critérios que permitem definir qualidade de uma linguagem:
- Expressividade; Clareza e Abstração
- Documentação (comentários de linha e bloco, anotações para manuais e meta-informação);
- Unicidade (singularidade de formas para expressar a mesma coisa).
Tabela que relaciona as Carateristicas da Linguagem com os Critérios de Qualidade:
| Característica | Aprendizagem | Escrita | Compreensão | Reconhecimento |
| Expressividade | ++ | ++ | + | - |
| Documentação | - | - | ++ | X |
| Unicidade | + | - | + | + |
Tabela que compara várias Linguagens de Programação, segundo as Caraterísticas Identificadas
| Característica | Assembly | Fortran | Basic | Pascal | C | Prolog | ML | C# | Perl | Ruby | PHP | SQL |
| CL1-Expressividade | nS | s | nS | B | B- | s | B | MB | B- | B- | B | MB |
| CL2-Documentação | s | s | s | s | S | s | s | MB | B | S | S | S |
| CL3-Unicidade | nS | S | S | nS | NS | S | S | nS | NS | NS | NS | B |
| CL4-Consistência |
| CL5-Extensibilidade |
| CL6-Escalabilidade |
| CL7-Paradigma |
| CL8-Fiabilidade |
nS - não Satisfaz, B - Bom, S - Satisfaz
28 Março 2011
Continuação do estudo do tópico
Qualidade de Linguagens
- Estudo das Características que influenciam os Critérios que permitem definir qualidade de uma linguagem:
- Consistência
- Escalabilidade
Tabela que relaciona as Carateristicas da Linguagem com os Critérios de Qualidade:
| Característica | Aprendizagem | Escrita | Compreensão | Reconhecimento |
| Expressividade | ++ | ++ | + | - |
| Documentação | - | - | ++ | X |
| Unicidade | + | - | + | + |
| Consistência | ++ | + | + | X |
| Extensibilidade | | | | |
| Escalabilidade | X | X | X | X |
Tabela que compara várias Linguagens de Programação, segundo as Caraterísticas Identificadas
| Característica | Assembly | Fortran | Basic | Pascal | C | Prolog | ML | C# | Perl | Ruby | PHP | SQL |
| CL1-Expressividade | nS | s | nS | B | B- | s | B | MB | B- | B- | B | MB |
| CL2-Documentação | s | s | s | s | S | s | s | MB | B | S | S | S |
| CL3-Unicidade | nS | S | S | nS | NS | S | S | nS | NS | NS | NS | B |
| CL4-Consistência | S | S | s | B | s | B | B | B | NS | NS | NS | B |
| CL5-Extensibilidade |
| CL6-Escalabilidade | nS | S | nS | S | B | S | S | B | B | S | B | B |
| CL7-Paradigma |
| CL8-Fiabilidade |
nS - não Satisfaz, B - Bom, S - Satisfaz
4 Abril 2011
Discussão do processo de avaliação; ponto de situação.
Abertura de uma discussão/investigação alargada sobre o processo de Avaliação de Qualidade e Métricas em Engenharia:
- Receção das monografias escritas pelos alunos sobre métricas em geral, métricas em linguagens de modelação (UML) e gramáticas; apreciação geral e definição dos desenvolvimentos futuros --- ver relatórios escritos inseridos na parte final do item "Questões, Fichas Práticas e Notas" da página deste módulo.
Continuação do estudo do tópico
Qualidade de Linguagens
- Estudo das Características que influenciam os Critérios que permitem definir qualidade de uma linguagem:
- Extensibilidade léxica, sintática e semântica.
- Modularidade
Tabela que relaciona as Carateristicas da Linguagem com os Critérios de Qualidade:
| Característica | Aprendizagem | Escrita | Compreensão | Reconhecimento |
| Expressividade | ++ | ++ | + | - |
| Documentação | - | - | ++ | X |
| Unicidade | + | - | + | + |
| Consistência | ++ | + | + | X |
| Extensibilidade | - | ++ | ? | - |
| Escalabilidade | X | X | X | X |
| Modularidade | x | ++ | + | X |
| Fiabilidade | | | | |
Tabela que compara várias Linguagens de Programação, segundo as Caraterísticas Identificadas
| Característica | Assembly | Fortran | Basic | Pascal | C | Prolog | ML | C# | Perl | Ruby | PHP | SQL |
| CL1-Expressividade | nS | s | nS | B | B- | s | B | MB | B- | B- | B | MB |
| CL2-Documentação | s | s | s | s | S | s | s | MB | B | S | S | S |
| CL3-Unicidade | nS | S | S | nS | NS | S | S | nS | NS | NS | NS | B |
| CL4-Consistência | S | S | s | B | s | B | B | B | NS | NS | NS | B |
| CL5-Extensibilidade | s | s | s | S | B | S | S | B | B | B | S | s |
| CL6-Escalabilidade | nS | S | nS | S | B | S | S | B | B | S | B | B |
| CL7-Modularidade | nS | nS | nS | S | s | nS | S | B | B | B | S | nS |
| CL8-Fiabilidade |
nS - não Satisfaz, B - Bom, S - Satisfaz
11 Abril 2011
Continuação do estudo do tópico
Qualidade de Linguagens
- Estudo das Características que influenciam os Critérios que permitem definir qualidade de uma linguagem:
- Fiabilidade: type-checking; verificação dinâmica de limites; error-handling
Tabela que relaciona as Carateristicas da Linguagem com os Critérios de Qualidade:
| Característica | Aprendizagem | Escrita | Compreensão | Reconhecimento |
| Expressividade | ++ | ++ | + | - |
| Documentação | - | - | ++ | X |
| Unicidade | + | - | + | + |
| Consistência | ++ | + | + | X |
| Extensibilidade | - | ++ | ? | - |
| Escalabilidade | X | X | X | X |
| Modularidade | X | ++ | + | X |
| Fiabilidade | x | + | X | - |
Tabela que compara várias Linguagens de Programação, segundo as Caraterísticas Identificadas
| Característica | Assembly | Fortran | Basic | Pascal | C | Prolog | ML | C# | Perl | Ruby | PHP | SQL |
| CL1-Expressividade | nS | s | nS | B | B- | s | B | MB | B- | B- | B | MB |
| CL2-Documentação | s | s | s | s | S | s | s | MB | B | S | S | S |
| CL3-Unicidade | nS | S | S | nS | NS | S | S | nS | NS | NS | NS | B |
| CL4-Consistência | S | S | s | B | s | B | B | B | NS | NS | NS | B |
| CL5-Extensibilidade | s | s | s | S | B | S | S | B | B | B | S | s |
| CL6-Escalabilidade | nS | S | nS | S | B | S | S | B | B | S | B | B |
| CL7-Modularidade | nS | nS | nS | S | s | nS | S | B | B | B | S | nS |
| CL8-Fiabilidade | S | B | S | B | nS | nS | B | B | nS | nS | nS | B |
nS - não Satisfaz, B - Bom, S - Satisfaz
18 Abril 2011
Não houve aula: férias de Páscoa.
25 Abril 2011
Não houve aula: feriado nacional para comemorar a Revolução dos Cravos.
02 Maio 2011
Introdução do estudo do tópico
Qualidade de Gramáticas
- Apresentação dos Critérios que permitem definir qualidade de uma linguagem -- Compreensão, Derivação e Manutenção; Eficiência no Processamento e na Geração -- tendo em consideração o duplo papel de uma Gramática (GIC e GA): especificação formal de uma linguagem (para ser consumida por um Ser Humano que vai escrever frases nessa linguagem); e especificação formal de um programa/processador (para ser consumida por um Gerador).
Discussão do estado do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos.
09 Maio 2011
Introdução do estudo do tópico
Qualidade de Gramáticas
- Apresentaçãoos Critérios que permitem definir a qualidade de uma linguagem -- Compreensão, Derivação e Manutenção; Eficiência no Processamento e na Geração -- tendo em consideração o duplo papel de uma Gramática (GIC e GA): especificação formal de uma linguagem (para ser consumida por um Ser Humano que vai escrever frases nessa linguagem); e especificação formal de um programa/processador (para ser consumida por um Gerador).
- Apresentação dos Factores que mais influenciam Critérios introduzidos na última aula para definir a qualidade de uma linguagem: número de símbolos e de produções; clareza dos identificadores dos símbolos; número de produções unitárias; comprimentos dos lados esquerdos das produções; notação usada (pure/extended BNF); esquema de recursividade; modularidade; e complexidade sintática.
16 Maio 2011
Palestra sobre Gramáticas de Atributos e Geradores de Compiladores dada pelo Prof. Eric van Wik:
- Extensão de GA com novo símbolos e produções; forma de lida com a extensão durante a geração.
Estudo do tópico
Qualidade de Gramáticas e
Métricas
- Apresentação das Métricas de Tamanho, de Forma e Lexicográficas relacionadas com os Factores que mais influenciam os Critérios de Qualidade de uma Gramática.
Discussão do estado do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos.
23 Maio 2011
Estudo do tópico
Qualidade de Gramáticas e
Métricas
- Revisão das Métricas de Tamanho, de Forma e Lexicográficas relacionadas com os Factores que mais influenciam os Critérios de Qualidade de uma Gramática.
- Resolução de vários exercícios sobre calculo de Métricas aplicadas a diferentes GIC (com base nos exercícios da edição 2009/2010).
Discussão do estado do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos.
30 Maio 2011
Manhã totalmente dedicada ao projeto integrado (PI).
06 de Junho 2011
Conclusão do Ano Letivo relativo ao Módulo de EG.
Fecho do tópico
Qualidade de Gramáticas e
Métricas
- Balanço sobre as Métricas de Tamanho, de Forma e Lexicográficas relacionadas com os Factores que mais influenciam os Critérios de Qualidade de uma Gramática através da resolução e discussão do exercício 5 de transformação e cálculo de métricas de uma dada GIC (da edição 2009/2010).
Discussão do estado do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos.
13 de Junho 2011
- Manhã parcialmente dedicada ao fecho de ATS e ao projeto integrado (PI).
Submissão do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos UML (
paper CoRTA2011)
Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.