Proposta de Parser

Segue minha proposta de parser para nosso trabalho, eu creio que seja a melhor solução mas aguardo para ver se conseguem encontrar algum erro.
Minha proposta é o de utilizar uma tabela para parser top-down determinístico utilizando os conjuntos FIRST-FOLLOW para nossa gramática ambígua. Eu sei que não se pode fazer isto, pois a gramática é ambígua, mas para nosso caso isto é ótimo.

O problema de utilizar este tipo de parser no caso de uma gramática ambígua é que o método não se torna determinístico, pois em algum momento teremos duas produções distintas a seguir e que casam com a cadeia estudada. Entretanto, como em nosso trabalho todos os casamentos possíveis devem ser encontradas, logo este método se torna adequado porque além de derivar somente em produções que casam com a cadeia, encontra todas as formas de casamento possíveis. A seguir vamos exemplificar o método com uma regra de substituição simples:

a{b*}{b*} → /1a/2

Primeira convertemos para gramática com o método proposto no paper, teremos:

S → aG₁G₂
G₁ → bG₁ | ε
G₂ → bG₂ | ε

Para simplificar a derivação podemos escrever:

S → aA
A → G₁G₂
G₁ → bG₁
G₁ → ε
G₂ → bG₂
G₂ → ε

Em seguida encontramos os conjuntos First e Follow de cada uma das variáveis: S, A, G₁, G₂.

O conjunto FIRST de uma variável x indica quais são os símbolos mais a esquerda que aparecem na derivação a partir de uma variável x.

Uma maneira fácil de se encontrar o conjunto First(x) de uma variável x é analisando todas as produções x → α da gramática. Considerando a como um terminal e A como uma variável, temos a regra:

α = ε ˅ a,                                          First(ε ou a) = {α} = {ε} ou {a}
α = aβ,                                              First(aβ) = {a}
α = A ˄ A → β₁ | β₂ | ...,                  First(A) U= First(β₁) U First(β₂) U First(β₃) U ...
α = Aβ ˄ A não deriva ε                   First(Aβ) U= First(A)
α = Aβ ˄ A deriva ε                          First(Aβ) U= (First(A) - {ε}) U First(β)

Vamos calcular os conjuntos FIRST das variáveis de nosso exemplo. Começando com a primeira produção: S → aA, teremos:

FISRT(S), (S → aA) = FISRT(aA) = a

Continuando teremos:

FIRST(A), (A → G₁G₂) = FIRST(G₁G₂) = {FIRST(G₁) - {ε}} U FIRST(G₂) = {b} U {b, ε} = {b, ε}

FIRST(G₁), (G₁ → bG₁) = FIRST(bG₁) = {b}

FIRST(G₁), (G₁ → ε) = FIRST(ε) = {ε}

FIRST(G₂), (G₂ → bG₂) = FIRST(bG₂) = {b}

FIRST(G₂), (G₂ → ε) = FIRST(ε) = {ε}

Resumindo:

FIRST(S) = a

FIRST(A) = {b, ε}
FIRST(G₁) = {b, ε}
FIRST(G₂) = {b, ε}

Com os conjuntos FIRST, partindo da variável inicial S podemos encontrar a árvore de derivação de uma cadeia, caso a gramática não seja ambigua e não possua produções que derive ε. Não vou dar exemplos pois existem vários na Internet sobre isto, vou seguir para o FOLLOW.

Um problema ocorre quando dentre as produções da gramática exista alguma que derive ε, neste caso não podemos definir qual é o símbolo mais a esquerda produzido pela variável. Por exemplo, tome como base a sentença AB, sendo que A deriva ε, o primeiro símbolo mais a esquerda desta sentença poderá ser também os símbolos que estão mais a esquerda de B, quando A for ε. O objetivo de FOLLOW é justamente resolver este problema.

O conjunto FOLLOW é encontrado através das regras:

A → α ˄ A é o símbolo inicial,               FOLLOW(A) U= {#}
B → αAY,                                             FOLLOW(A) U= FIRST(Y) - {ε}
B → αAY ˄ ε ϵ FIRST(Y),                    FOLLOW(A) U= FOLLOW(B)

Para nosso exemplo teremos:

FOLLOW(S) = {#}
FOLLOW(A) = FOLLOW(S → aA) = FOLLOW(S → aAε) = FOLLOW(S) = {#}
FOLLOW(G₁) = FOLLOW(A → G₁G₂) = FIRST(G₂)-{ε} U FOLLOW(A) = {b} U {#}
FOLLOW(G₁) = FOLLOW(G₁ → bG₁) = FOLLOW(G₁)

FOLLOW(G₂) = FOLLOW(A → G₁G₂) = FOLLOW(A) = {#}

FOLLOW(G₂) = FOLLOW(G₂ → bG₂) = FOLLOW(G₂)

Resumindo:

FOLLOW(S) = {#}
FOLLOW(A) = {#}
FOLLOW(G₁) = {b, #}
FOLLOW(G₂) = {#}

Com os conjuntos FIRST e FOLLOW conseguimos construir nossa tabela de parser para geração das cadeias substituídas. A tabela de parser é uma tabela com pares (A, a), onde para cada produção A → α adicionamos α em (A, a) para todos os terminais a em FIRST(α FOLLOW(A)). Em nosso caso, teremos:

S → aA
FIRST(aA FOLLOW(S)) = a, logo, (S, a) terá S → aA,

A → G₁G₂
FIRST(G₁G₂ FOLLOW(A)) = {b, ε} {#}, logo, (A, b) e (A, #) terão A → G₁G₂,

G₁ → bG₁

FIRST(bG₁ FOLLOW(G₁)) = b, logo (G₁, b) terá G₁ → bG₁,

G₁ → ε

FIRST(ε FOLLOW(G₁)) = {b, #}, logo (G₁, b) e (G₁, #) terão G₁ → ε,

G₂ → bG₂

FIRST(bG₂ FOLLOW(G₂)) = b, logo (G₂, b) terá G₂ → bG₂,

G₂ → ε

FIRST(ε FOLLOW(G₂)) = {#}, logo (G₂, #) terá G₂ → ε,

A tabela fica então:

Voltando agora ao nosso exemplo de regra de substituição inicial: a{b*}{b*} → /1a/2, vamos realizar uma simulação com a tabela de parser e a cadeia abb.
Antes de iniciar adicionamos na cadeia o símbolo de final de cadeia #: abb#. Segue a tabela de parser realizado:

No passo 3, quando temos G1 no topo da pilha e o símbolo b mais a esquerda para casar, temos duas opções na tabela de parser, portanto, neste caso teremos que ramificar nestas duas opções e realizá-las separadamente. Primeiro vamos expandir a ramificação 3.1:

Aqui encontramos outra ambiguidade, seguimos expandindo a ramificação 3.1.1.1:

Agora encontramos o símbolo de final de cadeia e portanto, encontramos um caminho de realizar o match. Percorrendo novamente os estados podemos associar os símbolos da cadeia inicial com seus respectivos grupos G1 e G2.
G1 apareceu primeiro em 3.1.0 e produzir um b, logo em seguida produziu outro b em 3.1.1.1.0 e G2 produziu ε em 3.1.1.1.3. Logo para esta árvore de derivação temos:

G1 = bb
G2 = ε

Voltando e ramificando os que faltam teremos:

Analisando os grupos temos os seguintes casamentos:

G1 = bb, G2 = ε
G1 = b, G2 = b
G1 = ε, G2 = bb

Finalmente, com os grupos definidos, podemos criar as cadeias substituídas da regra de substituição: a{b*}{b*} → /1a/2 que serão:

bba
bab
abb

Caso não tenham entendido alguma coisa me digam.