Fatorações e Expressões Regulares Estendidas

 Fatoração de Produções

N ® a b d | a g d pode ser escrito como N ® a (b | g )d

 Fatoração de Gramática

E® (+ | - |l )T | E(+T | - T)

 Eliminação da Recursão

E® (+ | - | l ) T {+T | - T}*

E® [+ | -] T | E {+T | - T }*

 Gramática G₁₀

1. E® [ ' + ' | ' - ' ] T { ' + ' T | ' - ' T }*
2. T® F { ' * ' F | ' / ' F}*
3. F® P { ' ** ' P }*
4. P® ' i ' | '( ' E ' )'

{ a || b }⁺ = {a , a b a , a b a b a , ... }

 Rescrita de G₁₀

Chamaremos a gramática de G₁₃

 Expressões Regulares Estendidas

Definição:

1-

Uma cadeia de símbolos a é uma expressão regular estendida;

2-

Se a e b são expressões regulares estendidas, a b e a | b são expressões regulares estendidas;

3-

Se a é uma expressão regular estendida, então (a ), [a ] e {a }* são expressões regulares estendidas;

4-

Se a e b são expressões regulares estendidas, { a || b }⁺ é uma expressão regular estendida.

5-

A expressão obtida pela aplicação de b, c e d uma quantidade finita de vezes é uma expressão regular estendida.

 Interpretação de uma Expressão Regular Estendida

{a || b } = a {b a }*

 Expressão Regular Estendida - Gramáticas (ERE - Gramáticas)

São gramáticas livres de contexto em que o lado direito é uma expressão regular estendida.

 Gramática Livre de Contexto e a notação BNF

® ::=

Exemplo: G₁₃

<expressão> ::= [ ' + ' | ' - ' ] { <termo> || ( '+' | '-' ) }⁺

 Grafos Sintáticos

Representam ERE - gramáticas para:

1-

Facilitar a dedução da linguagem gerada.

2-

Melhorar a compreensão das estruturas.

3-

Facilitar a compreensão de certos métodos de analise sintática.