Syntax Definition Formalism

O Syntax Definition Formalism (SDF) é uma meta-sintaxe usada para definir gramáticas livres de contexto. Este formalismo é capaz de expressar todo o conjunto de linguagens geradas a partir de uma gramática livre de contexto. Sua versão atual é a SDF2. O ASF+SDF Meta-Environment é a ferramenta mais utilizada para a definição de linguagens utilizando o SDF, nela são disponibilizados um analisador sintático e um gerador de analisador sintático. Ambos utilizam a abordagem de um analisador sintático SGLR(Sigla para o inglês Scannerless GLR Parser) para o reconhecimento de expressões. O processo de reconhecimento terá como resultado uma árvore sintática ou, no caso da gramática conter ambigüidades uma floresta de árvores sintáticas. Essa floresta de árvores é um conjunto de todas as árvores sintáticas resultantes das ambigüidades encontradas durante o reconhecimento da expressão dada como entrada.

Tela do ASF+SDF Meta-Environment com a gramática *DrawingCommands* definida.

Visão Geral

O SDF é um formalismo para descrever gramáticas para linguagens de programação, linguagens de aplicação, linguagem específica de domínio, formato de dados e outros tipos de linguagens formais. Seu objetivo principal é a descrição da sintaxe de uma linguagem, mas também fornece um conjunto de ferramentas para a geração de um analisador sintático para a linguagem definida.^[1]

Este formalismo é baseado em sua maioria nos conceitos das gramáticas livres de contexto. Uma outra forma de definir uma gramática livre de contexto é o EBNF. O SDF fornece um conjunto de recursos adicionais que a torna mais apta a descrever a sintaxe de linguagens de programação extremamente complexas. Estes recursos irão auxiliar principalmente no caso de descrever linguagens que não são originalmente concebidas para serem formalmente definidas ou terem analisadores sintáticos definidos para elas.^[1]

Ciclo de Vida de uma Definição SDF

Toda gramática definida através do SDF tem um ciclo de vida associado. Este é definido pelos seguintes passos:

O usuário escreve um módulo contendo a gramática SDF, isso inclui as suas regras de produção e regras de desambiguações.
Os vários módulos serão unidos em uma única definição.
A definição é dada como entrada para a ferramenta sdf2table:
1. A parte da definição da sintaxe será verificada para a localização de erros triviais. Este processo é executado pela ferramenta sdfchecker.
2. A sintaxe e as construções de desambiguação são normalizadas.
3. A sintaxe é usada para gerar uma tabela do analisador SLR(1), onde as construções de desambiguações serão usadas para filtrar as reduções a partir da tabela sintática.
A tabela sintática resultante do processo anterior pode ser usada pela ferramenta sglr(um analisador sintático SGLR) para reconhecer as cadeias de caracteres da entrada.
A ferramenta sglr lê o código fonte que é dado como entrada e gera a floresta de árvores sintáticas ou expõe os erros encontrados no programa.
Outras ferramentas podem usar a floresta de árvores sintáticas para fazer processamentos sobre essa representação do código fonte.

Noções Básicas^[1]

As especificações escritas em SDF são organizadas em módulos. Estes módulos são utilizados para dividir especificações maiores e mais complexas em partes mais simples e focadas em um contexto específico do problema. Desta forma a estrutura básica de uma especificação SDF é dada da seguinte forma:

module <ModuleName>
       <ImportSection>*
       <ExportOrHiddenSection>*

Onde cada módulo deve conter no mínimo um nome que irá lhe identificar para seu uso posterior. O atributo <ModuleName> é o ponto onde deve ser definido de um módulo. Os outros atributos da definição tratam da importação ou uso de outros módulos e da visibilidade de definições que estão contidas neste módulo.

Comentários

Os comentários em SDF são definidos através dos símbolos %% e %. O símbolo %% define uma comentário de linha. Já o símbolo % define um comentário em bloco, onde uma símbolo inicial % inicia o bloco e uma outra ocorrência do símbolo % finaliza o bloco.

Um exemplo simples de comentário pode ser visto abaixo:

module basic/Comments
  ...

  %% Comentário de linha

  %
    Comentário com várias linhas ou de bloco.
  %
  ...

Símbolos

Os símbolos em SDF são construções que podem ser utilizadas para representar terminais ou não terminais dentro da especificação da gramática.

Os símbolos literais são cadeias de caracteres que são encontrados dentro do vocabulário da linguagem, logo este são caracterizados como terminais da gramática. Os símbolos literais podem ser definidos através da cadeia de caracteres envolvida por aspas duplas.

Os símbolos de categoria são equivalentes aos não-terminais de uma gramática. Estes tipo de símbolos devem ser declarados na seção sorts da definição SDF. Estes tipos de símbolos podem ser parametrizados assim permitindo uma abordagem mais dinâmica a gramática.

A seção sorts dentro de uma definição SDF serve para declarar os símbolos de categoria utilizados na especificação. Fazendo uso desta seção é possível utilizar a ferramenta sdfchecker para efetuas algumas verificações na especificação, como por exemplo a verificação se os tipos utilizados na especificação foram declarados.

Um exemplo da definição dos dois tipos de símbolos da gramática da linguagem Java é dado abaixo:

...
sorts Class

lexical syntax
  "class" -> Class
...

Neste exemplo o símbolo de categoria é dado através de Class e de símbolo literal através de "class".

Classe de Caracteres

É possível descrever classes de caracteres nas especificações SDF. Estas classes são descritas através de uma linguagem semelhante a de expressões regulares.

Também são definidos operadores de classe de caracteres onde estes vão relacionar duas classes de caracteres. São os operadores de classe de caracteres :

~: Define a classe complementar a classe operada.
/: Define a classe da diferença entre a classe mais a esquerda e a classe mais a direita.
/\: Define a classe resultado da interseção das duas classes operadas.
\/: Define a classe resultado da união das duas classes operadas.

Alguns exemplos do uso destes operadores:

  ~[0-5]           -> Any_6a9 %% Qualquer valor entre 6 e 9, inclusive.
  [0-1] \/ [2-3]   -> Any_0a3 %% Qualquer valor entre 0 e 3, inclusive.
  [a-c] /\ [b-d]   -> Any_bc  %% Qualquer caractere podendo ser b ou c.

Operador Opcional

O operador opcional é utilizado quando se é necessário definir que um símbolo deve acontecer zero ou uma e apenas uma vez. Este operador é um pós-fixo em relação ao símbolo que se quer denotar a opcionalidade, o símbolo ? é usado para estabelecer a ocorrência opcional. Um exemplo utilizando as definições de visibilidade da linguagem Java é dado abaixo:

  ...
  %% Declarações referente as palavras reservadas de controle de acesso Java
  "private"         -> Visibility
  "public"          -> Visibility
  "protected"       -> Visibility

  %
  Definição do padrão para declaração parcial de classes em Java, onde pode
  ou não ser declarado o tipo de visibilidade.
  %
  Visibility? Class -> Class_Access
  ...

Seqüência

Uma seqüência representa uma um conjunto ordenado de símbolos onde a ordem é definida pelo fluxo em que os símbolos vão aparecendo dentro dos delimitadores de seqüência. O símbolo (...) define uma seqüência. Apesar dessa forma primária da definição das seqüências também é possível definir-lá através da simples cadeia de símbolos, como por exemplo: Visibility? Class onde este é equivalente a (Visibility? Class).

Repetições

A repetição expressa que um determinado símbolo pode aparecer várias vezes. Existem dois operadores que tem significados diferentes para a quantidade de repetições que o símbolo deve apresentar. São eles:

String*: Estabelece que o símbolo de categoria String pode acontecer zero ou mais vezes.
String+: Estabelece que o símbolo de categoria String pode acontecer uma ou mais vezes.

Estes operadores de repetição ainda podem ser definidos para tratar caso de definição de listas. Logo, pode-se definir separadores para tais. Um exemplo de uma linguagem simples com definição de listas onde os elementos podem ser cadeias de caracteres ou listas pré-definidas pode ser visto na seção de exemplos através do módulo List.

Escolha

O operador de escolha representa a seleção de uma das alternativas expressas em conjunto com o operador. Logo, se temos "true"|"false" então o símbolo irá reconhecer as cadeias de caracteres "true" e "false". É importante notar que o operador é associativo à direita, isso quer dizer que se for especificado Bool ","| Bool ";" isso será equivalente a Bool (","| Bool) ";" ao invés de (Bool ",")|(Bool ")).

Layout

O LAYOUT é um tipo especial de símbolo de categoria que já pré-definido em todos os módulos SDF. Este símbolo é utilizado para definir quais os símbolos literais serão utilizados para formatação da entrada. Este símbolo só pode ser definido dentro da seção lexical syntax. Um exemplo comum de definição para o símbolo de layout é dada abaixo:

[\ \t\n] -> LAYOUT

Nesta os espaços, tabulação e quebra de linha são utilizados como layout para a gramática.

Seção Lexical Syntax

A seção Lexical Syntax é o local onde serão descritos os elementos básicos do programa. Nesta seção geralmente são definidas as associações entre alguns símbolos variáveis da gramática, como por exemplo os identificadores de funções e variáveis da linguagem. Um exemplo de definição de lexical syntax pode ser visto abaixo:

module Java

  imports basic/Whitespace %% Importação do módulo que define comentários

exports
  sorts Class Visibility
  lexical syntax
    "class"         -> Class
    "private"       -> Visibility
    "public"        -> Visibility
    "protected"     -> Visibility
    Visibility? Class -> Class_Access

Seção Context-free Syntax

A seção Context-free Syntax é o local onde deve ser descrita a estrutura de alto nível das sentenças da linguagem. Esta seção é composta basicamente de um conjunto de regras de produção. É importante notar que entre cada elemento descrito no lado esquerdo de uma regra de produção será inserido um símbolo de Layout antes de ser gerada a árvore sintática pelo analisador sintático.

Logo abaixo é mostrado um exemplo de uma definição da seção context-free syntax antes e depois de serem inseridos os símbolos de layout:

context-free syntax
  "{" Stat* "}" -> Block

Depois da inserção dos símbolos de layout:

"{" LAYOUT? Stat* LAYOUT? "}" -> Block

Exemplos

O exemplo abaixo define uma linguagem simples para expressões da lógica proposicional utilizando SDF:

 module basic/Booleans %% Definição do nome do módulo

 exports
   sorts Boolean %% Declaração dos símbolos de categorias utilizados.
   context-free start-symbols Boolean %% Símbolo de categoria inicial da gramática

 context-free syntax
    "true"                      -> Boolean
    "false"                     -> Boolean
    lhs:Boolean "|" rhs:Boolean -> Boolean {left} %% Notação especial para associatividade a esquerda.
    lhs:Boolean "&" rhs:Boolean -> Boolean {left} %% Logo, as expressões mais a esquerda serão resolvidas primeiro.
    "not" "(" Boolean ")"       -> Boolean
    "(" Boolean ")"             -> Boolean

  %% Nesta seção são declaradas as prioridades entre operadores.
  context-free priorities
    Boolean "&" Boolean -> Boolean > %% O operador "&" será resolvido primeiro que o "|".
    Boolean "|" Boolean -> Boolean

Neste exemplo é definida uma linguagem para tratar de primitivas de desenho gráfico.

module DrawingCommands

imports basic/Whitespace

exports
  context-free start-symbols CMND
  sorts NAT COORD CMND

  lexical syntax
    [0-9]+ -> NAT %% Declaração do tipo para os números naturais

  context-free syntax
    "(" NAT "," NAT ")" -> COORD %% Uma coordenada é composta por dois números naturais (NAT).
    "line" "to" COORD   -> CMND  %% Um comando sempre está relacionado com um coordenada (COORD).
    "move" "to" COORD   -> CMND

Seu equivalente em EBNF:

<COORD> ::= "(" <NAT> "," <NAT> ")"
<CMND>  ::= "line" "to" <COORD> | "move" "to" <COORD>

Neste exemplo é definida uma linguagem para criação de listas. Estas listas podem ser atribuídas à variáveis ou podem ser compostas de variáveis e cadeias de caracteres. São utilizados dois módulos externos para definir as cadeias de caracteres e os layouts da entrada. Além disso, todos os símbolos definidos no módulo são públicos, logo poderão ser utilizados por outros módulos posteriormente. Segue abaixo a listagem da especificação:

module List

imports
  basic/Strings    %% Importa a definição para a representação de um cadeia de caracteres.
  basic/Whitespace %% Importa a definição para comentários.

exports
  context-free start-symbols S

  sorts S List Expression IdCon Asterisk

  lexical syntax
    %% Definição de um identificador.
    %% Todo identificador deve ser iniciado com uma letra e pode conter -,_ e números
    head:[A-Za-z] tail:[A-Za-z\-\_0-9]* -> IdCon

    "--" ~[\n]* [\n]                  -> LAYOUT    %% Definição para comentários de linha
    "/*" (~[\*] | Asterisk)* "*/"     -> LAYOUT    %% Definição para comentários de bloco
    [\*]                              -> Asterisk

  %% Construções para desambiguação da gramática
  lexical restrictions
    Asterisk -/- [\/]
    IdCon -/- [A-Za-z]

  context-free syntax
   List*                     -> S
   IdCon "=" Expression ";"  -> List
   {(String|IdCon) ","}+     -> Expression

Um pequeno exemplo de código fonte reconhecido pela gramática especificada através do módulo List acima.

Labc = "abc";
L2 = Labc, "a", "c";
L3 = L2;

Ferramentas

Referências

↑ ^a ^b ^c Brand, Mark van den; Klint, Paul; Vinju, Jurgen (22 de Outubro de 2007). «The Syntax Definition Formalism SDF». Consultado em 15 de Outubro de 2008

Outras Referências

Bergstra, J. A.; Heering, J.; Klint, P (1989). Algebraic Specification. [S.l.]: ACM Press/Addison-Wesley. ISBN 0-201-41635-2
Vinju, Jurgen (19 de Outubro de 2007). «SDF Disambiguation Medkit for Programming Languages». Consultado em 15 de Outubro de 2008

[Brand2007-1] Brand, Mark van den; Klint, Paul; Vinju, Jurgen (22 de Outubro de 2007). «The Syntax Definition Formalism SDF». Consultado em 15 de Outubro de 2008

[1]