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.
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
- 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
- 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:
- 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
- add one more synthesized attribute:
- 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
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 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:
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
GUIÃO DA AULA:
A simple arithmetic expression language.
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.
Continuação do estudo do tópico Qualidade de Linguagens
* 2º SEMESTRE ***
Continuação do estudo do tópico Qualidade de Linguagens
Continuação do estudo do tópico Qualidade de Linguagens
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
Continuação do estudo do tópico Qualidade de Linguagens
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
Continuação do estudo do tópico Qualidade de Linguagens
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
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:
Continuação do estudo do tópico Qualidade de Linguagens
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
Continuação do estudo do tópico Qualidade de Linguagens
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
Não houve aula: férias de Páscoa.
Não houve aula: feriado nacional para comemorar a Revolução dos Cravos.
Introdução do estudo do tópico Qualidade de Gramáticas
Discussão do estado do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos.
Introdução do estudo do tópico Qualidade de Gramáticas
Palestra sobre Gramáticas de Atributos e Geradores de Compiladores dada pelo Prof. Eric van Wik:
Estudo do tópico Qualidade de Gramáticas e Métricas
Discussão do estado do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos.
Estudo do tópico Qualidade de Gramáticas e Métricas
Discussão do estado do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos.
Manhã totalmente dedicada ao projeto integrado (PI).
Conclusão do Ano Letivo relativo ao Módulo de EG.
Fecho do tópico Qualidade de Gramáticas e Métricas
Discussão do estado do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos.
Submissão do artigo coletivo sobre Métricas para Avaliação de Qualidade de Especificações / Modelos UML (paper CoRTA2011)