Gramáticas

Regex?

Infelizmente Expressões Regulares apresentam algumas limitações para a definição de uma linguagem de programação.

As Regex são excelentes, ainda que lentas, para identificação de lexemas.

Muito difícil fazer uma expressão regular para garantir os pares de parênteses.

Muito difícil fazer uma expressão regular para funções e objetos garantindo os escopos.

Gramáticas

A linguagem das linguagens: Uma gramática é uma lista de regras que determina como podem ser criadas e utilizadas todas as strings de uma linguagem;

Noam Chomsky é um dos pesquisadores mais importantes nesta área.

A nós, nesta disciplina, interessam apenas as gramáticas livres de contexto e as regulares. As gramáticas livres de contextos são um superconjunto das gramáticas regulares.

Linguagens e Chomsky

Gramáticas - definição

Uma Gramática Formal: 4-tupla: $$𝑮 := \{𝑵, \Sigma, 𝑷, 𝑺\}$$

• $S\rightarrow \text{símbolo inicial}$
• $\Sigma \rightarrow \text{símbolos terminais}$
• $P \rightarrow \text{regras de produção}$
• $N \rightarrow \text{símbolos não terminais}$

Livres de Contexto

Uma gramática livre de contexto é uma álgebra que descreve um conjunto de strings por meio da definição da estrutura das strings que formarão a linguagem.

Esta definição é recursiva, indicando que cada regra produção pode, ou não, ser utilizada para definir novas regras de produção

$$ STMT \rightarrow \space if \space EXPRESS \space STMT \space else \space STMT$$

Regras de Produção

Os símbolos que aparecem à esquerda da seta, são não terminais e representados por letras latinas maiúsculas $(𝐴, 𝐵, 𝑆, …)$.

O símbolo inicial é o que aparece do lado esquerdo da primeira regra, no nosso caso, na maior parte das vezes: $𝑆$.

Pode ser qualquer símbolo, usaremos o $𝑆$ por convenção.

Exemplo 1

1. $𝑆 \rightarrow 𝐴𝐵$
2. $𝑆 \rightarrow 𝐴𝑆𝐵$
3. $𝐴 \rightarrow a$
4. $𝐵 \rightarrow b$

Vamos produzir a string:“aabb”

Exemplo 1 - Derivando $aabb$

1. $𝑆 \rightarrow 𝐴𝐵$
2. $𝑆 \rightarrow 𝐴𝑆𝐵$
3. $𝐴 \rightarrow a$
4. $𝐵 \rightarrow b$

Exemplo 2

1. $𝑆TMT \space \rightarrow IFSTMT \space | \space outracoisa$
2. $IFSTMT \rightarrow if \space (EXP) \space STMT \space ELSESTMT$
3. $ELSESTMT \rightarrow else \space STMT \space | \space \varepsilon$
4. $EXP \rightarrow 0|1$

Que pode gerar / identificar:

outracoisa

if (0) outracoisa

if (1) outracoisa else if (0) outracoisa else outracoisa

Exercício Formativo 1

Considere a gramática definida por:

1. $𝑺 \rightarrow 𝑨𝑩$
2. $𝑨 \rightarrow \varepsilon | 𝒂𝑨$
3. $𝑩 \rightarrow \varepsilon | 𝒃𝑩$

Encontre uma sequência de substituições para encontrar: $aab$

Gramáticas Regulares

Duas classes de regras de produção.

Lineares à Direita: as regras de produção obedecem: $$𝑨 \rightarrow 𝒘𝑩 \vee 𝑨\rightarrow 𝒘 (𝒘 \in \Sigma^*)$$

Lineares à esquerda: as regras de produção obedecem: $$𝑨 \rightarrow 𝑩𝒘 \vee 𝑨 \rightarrow 𝒘 (𝒘 \in \Sigma^*)$$

Árvores Sintáticas

1. $S$
2. $S \rightarrow ASB$
3. $S \rightarrow aSB$
4. $S \rightarrow aSb$
5. $S \rightarrow aABb$
6. $S \rightarrow aaBb$
7. $S \rightarrow aabb$

Backus-Naur Form - BNF

Em 1957 John Backus, trabalhando na IBM, criou uma linguagem para criar linguagens.

Representa uma gramática.

É mais simples para leitura que a álgebra.

É mais simples para escrita que a álgebra.

Finalmente virou um padrão ISO/IEC 14977 em 1996.

O criador da linguagem define como, e se usará este padrão.

BNF - Original

Começou muito simples e com o tempo foi sendo adaptada as necessidades dos criadores de linguagens.

BNF - Exemplo

1. $\text{<𝑙𝑖𝑠𝑡𝑎> ∷= <𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜>;<𝑙𝑖𝑠𝑡𝑎> | <𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜>}$
2. $\text{<𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜>∷=<𝑙𝑒𝑡𝑟𝑎> <𝑑𝑖𝑔𝑖𝑡𝑜>}$
3. $\text{<𝑙𝑒𝑡𝑟𝑎>∷=𝐴 | 𝐵 |𝐶}$
4. $\text{<𝑑𝑖𝑔𝑖𝑡𝑜>∷=1|2|3|4}$

Funciona segundo os princípios das regras de produção. Uma sequência recursiva de substituição de regras permitindo a criação das sentenças da linguagem.

EBNF

• Removeu os $<$$>$ para os símbolos não terminais.
• Símbolos termais expressos entre aspas.
• Uso $*$ para fechamento e $\{\}$ para multiplicação.
• Uso de $+$ para um ou mais.
• Uso de $?$ para seleção.
• Parênteses $()$ para agrupamento;
• Substitui $∷=$ por $=$.
• O uso da vírgula $,$ para explicitar concatenação.
• O ponto encerra uma regra.

BNF - Exemplo

Considere a seguinte gramática definida em BNF

1. $<𝒑𝒓𝒐𝒈𝒓𝒂𝒎> ::= 𝒃𝒆𝒈𝒊𝒏 <𝒔𝒕𝒎𝒕\_𝒍𝒊𝒔𝒕> 𝒆𝒏𝒅$
2. $<𝒔𝒕𝒎𝒕_𝒍𝒊𝒔𝒕> ::= <𝒔𝒕𝒎𝒕> | <𝒔𝒕𝒎𝒕> ; <𝒔𝒕𝒎𝒕_𝒍𝒊𝒔𝒕>$.
3. $<𝒔𝒕𝒎𝒕> ::= <𝒗𝒂𝒓> = <𝒆𝒙𝒑𝒓>$
4. $<𝒆𝒙𝒑𝒓> ::= <𝒕𝒆𝒓𝒎> + <𝒕𝒆𝒓𝒎> | <𝒕𝒆𝒓𝒎> − <𝒕𝒆𝒓𝒎>$
5. $<𝒕𝒆𝒓𝒎> ::= <𝒗𝒂𝒓> | 𝒄𝒐𝒏𝒔𝒕$
6. $<𝒗𝒂𝒓> ::= 𝒂 | 𝒃 | 𝒄$

Derive o seguinte programa:

$\text{begin } a = b + \text{ const } \text{ end}$

BNF - Exemplo

• $ <program> \Rightarrow \emptyset$
• Regra 1: $ <program> \Rightarrow begin <stmt\_list> \text{ end}$
• Regra 2: $<program> \Rightarrow \text{begin } <stmt> \text{ end}$
• Regra 3: $<program> \Rightarrow \text{begin } <var> = <expr> \text{ end}$
• Regra 6: $<program> \Rightarrow \text{begin } a = <expr> \text{ end}$
• Regra 4: $<program> \Rightarrow \text{begin } a = <term> + <term> \text{ end}$
• Regra 5: $<program> \Rightarrow \text{begin } a = <var> + <term> \text{ end}$
• Regra 6: $<program> \Rightarrow \text{begin } a = b + <term> \text{ end}$
• Regra 5: $<program> \Rightarrow \text{begin } a = b + const \text{ end}$

Começamos do símbolo inicial, neste caso $ <program>$ e recorrentemente vamos procurando regras de substituição na grámática definida.

Parsers Semântica

A palavra parser, que usaremos com frequência, tem o sentido de percorrer, varrer.

Nesta disciplina: técnicas de percorrer uma árvore sintática validando a gramática.

Na literatura, o conceito de parser se confunde com o conceitos de análise sintática. Não são raros os parsers que fazem análise léxica, sintática e semântica.

Parsers

Exemplo

Considerando a gramática a seguir, apresente as derivações necessárias para encontrar “abbcde”, usando Bottom-up parser.

1. $S \rightarrow aABe$
2. $A \rightarrow Abc | b $
3. $B \rightarrow d$

Regra 2: $abbcde \Rightarrow aAbcde$

Regra 2: $abbcde \Rightarrow aAde;$

Regra 3: $abbcde \Rightarrow aABe;$

Regra 1: $abbcde \Rightarrow S;$

A string “abbcde” é válida nesta gramática.