Problemas do Parser

No caminho de volta hoje pensei sobre o assunto que discutimos e cheguei a conclusão de que realmente pode dar problema. Caso a regra seja:

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

Podemos converter a regra para a gramática:

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

Simplificado:

S → aA
A → G₁B
B → G₂C
C → bD
D → b
G₁ → bG₁ | ε
G₂ → bG₂ | ε

Grupo FIRST:


First(S) = a
First(A) = b
First(B) = b
First(C) = b
First(D) = b
First(G₁) = b, ε
First(G₂) = b, ε

Grupo FOLLOW:


Follow(S) = #
Follow(A) = #
Follow(B) = #
Follow(C) = #
Follow(D) = #
Follow(G₁) = b
Follow(G₂) = b


Tabela de Parser:

S → aA

FIRST(aA FOLLOW(S)) = a

A → G₁B

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

B → G₂C

FIRST(G₂C FOLLOW(B)) = {b, ε}{b}

C → bD

FIRST(bD FOLLOW(C)) = b

D → b

FIRST(b FOLLOW(D)) = b

G₁ → bG₁

FIRST(bG₁ FOLLOW(G₁)) = b

G₁ → ε

FIRST(ε FOLLOW(G₁)) = {ε}{b}

G₂ → bG₂

_{FIRST(bG2 FOLLOW(G2)) = b}

G₂ → ε

FIRST(ε FOLLOW(G₂)) = {ε}{b}

Podemos seguir a seguinte derivação com a cadeia abbb:

(abbb) S → aA
(bbb) A → G₁B
(bbb) G₁ → ε
(bbb) B → G₂C
(bbb) G₂ → ε
(bb) C → bD
(b) D → b

Ou seja, esta derivação não termina corretamente, logo temos que descartá-la. Caso fizéssemos uma tabela de parser LL 2, 3 ou maior, é possível fazer a derivação de forma determinística.
Temos que prever este tipo de derivações que não terminam corretamente e derivações diferentes também podem gerar as mesmas cadeias substituídas.

Pode-se perguntar então se é útil ter todo este trabalho para no final termos um parser não determinístico. Não me lembro agora qual, mas vi em um paper a informação de que sim. Mesmo que uma linguagem seja LL 2, 3, 4 é viável utilizar um parser LL(1) e tratar o não determinismo. Por outro lado, lá diz que é muito viável também utilizar um parser LL(1) ao invés de um parser simples não determinístico pois evitaria muitas derivações desnecessárias.

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.

Conclusão

Felipe,




Na verdade a adicao da secao D (q era C.1) e uma pequena mudanca na conclusao...



O Vitor esta pondo a referencia 15 e ai vai mandar a versao para impressao.

Última versão

Alguma Grande alteração nesta ultima versão, alem da formatação dos simbolos de gramática ( que ficou bom por sinal)


???

Problema- Linguagem não ambigua

Pessoal, surgiu um problema.


Considere a regra {b*}{b*}a -> \1a\2

De acordo com o método de conversão para gramática, teríamos:

G=ABC

A=bA
e associado com o índice 1

B=bB
e associado com o índice 2

C=a



Que pode ser reescrita como:

R1 G=MC

R2 M=AB

R3 A=bA associado com o índice 1

R4 A=e associado com o índice 1

R5 B=bB associado com o índice 2

R6 B=e associado com o índice 2

R7 C=a



só frescura, não mudou nada.



Agora fazendo o parser sobre a cadeia bba temos: R1 -> MC -(R2)> ABC -(R4)> BC -(R5)> bBC -(R5)> bbBC -(R6)> bbC -(R7)> bba

A sequencia fica R(1,2,4,5,5,6,7), porém teríamos a mesma cadeia com as derivações R(1,2,3,4,5,6,7), ou seja, a gramática é ambigua para este método.





Li isto no livro linguagens formais. Em uma linguagem nao-ambigua existe apenas uma unica arvore de derivacao.

logo, nosso sistema sera ambiguo e nosso parser tera q funcionar sobre gramatica ambigua

Referências

Segue...




Falta uma das referencias do Manasseis que nao encontrei de jeito algum

na net (posso substituir se voce nao tiver) e terminar aquela questao a

esquerda e o planejamento...

Ajustes Finais

Manda por favor o texto final. Preciso incluir as referencias e fazer a ultima checagem. Vou reescrever a introducao ja que o Vitor achou que estava ruim.... Darei os ajustes finais mas preciso trabalhar na ultima versao que tivermos.

Gramática ambigua

Pessoal segue minha parte referente a Casamento de Cadeias por parser, Ce ainda pretendo adicionar mais alguma coisa referente ao quue o parser deve fazer ao encontrar uma gramática ambigua em seu caminho ( parser LL não pose utilizar uma gramática ambigua) assim que concluir eu mando o .doc .




Obs.

Utlizei como referencia o livro do Ullman - compiladores principios tecnica e ferramentas de 1995, notas de aulas dos alunos do prof carlos henrrique (ITA) http://winandy.site.voila.fr/LLk_NotasAula.pdf, e este material da federal da Bahia: https://disciplinas.dcc.ufba.br/pastas/MATA61/20092/aulas/Compiladores-ASintatica-Aula2.pdf e este da Unicamp: http://calhau.dca.fee.unicamp.br/wiki/images/e/e6/CompAnalSint.pdf

C. Casamento das Cadeias por Analizador Sintático

No sistema de reescrita de expressões regulares as cadeias serão substituídas se somente se “casarem” com a expressão regular de uma dada regra Ri do sistema. O casamento de uma cadeia com uma expressão regular pode ser realizada de diversas formas, porém o método escolhido para o sistema de reescrita de expressões regulares é a utilização de um analisador sintático top-down (parser) que utilize análise LL com busca recursiva com retrocesso (backtracking) sobre uma gramática gerada através do método de conversão de expressões regulares para gramática proposto anteriormente.

Antes de efetuar a operação de casamento sobre uma determinada regra de reescrita, o parser deverá verificar se a gramática que será utilizada para realizar as a respectiva operação de casamento possui ou não infinitas produções recursivas à esquerda ou é ambígua, pois estes tipos de gramática podem levar analisador a um laço infinito, impedindo que as demais regras de reescrita sejam aplicadas a uma determinada cadeia.



Para solucionar o problema das infinitas produções recursivas à esquerda é necessário eliminar estas produções recursivas da gramática em questão, convertendo-a, adicionando um novo símbolo não terminal para torná-la uma recursão a direita, como segue o exemplo:



Dada a gramática:



A --> Aa

A --> b







Gramática convertida:



A’ --> bA’



A’ --> aA’



A’ --> e

Correção

Vitor estou lendo os artigos e fazendo algumas correções, assim que terminar eu mando para todos. Imagino que vou terminar só no sabado de manhã, mas vamos conversando.

O livro do Ullman

Preciso saber o que estão fazendo, se já leram o que passei, se já olharam as referências, se está tudo certo, se possuem o livro do Ullman sobre compiladores para poder escrever e verificar a parte de parser, etc... etc... etc...

Problema: Conversão ER para gramática regular

Olá Pessoal,




Surgiu um pequeno problema, no algoritmo de conversão de ER para gramática regular que mostrei na terça não tenho certeza de que ele não gera gramática recursiva pela direta. Caso a gramática seja recursiva pela direta, ao fazer o backtracking o algoritmo encontrará a recursão e nunca irá percorrer a árvore.

Não sei porque não consegui estudar gramática ainda, alguém sabe como verificar se uma gramática é recursiva pela diretia?



-Outra coisa, não ficou muito bem ainda definido como realizar as substituições nas cadeias a partir da árvore de análise sintática.



-Caso tenhamos que realizar alguma conversão na gramática não sei se podemos perder as sub-expressoes do operador {} da ER.



-Uma gramática ambígua pode ser utiliza no parsing LL?



Estou escrevendo os textos, caso alguém possa responder estas questões e/ou a solução ...

Trabalho - Andamento

Pessoal,




Segue os trabalhos que tenho no meu computador.



Infelizmente surgiu um imprevisto e amanhã logo depois do almoço vou ter que viajar. No final de semana não estarei on-line, pois tenho aula sábado e domingo o dia todo, portanto será muito difícil de conseguir responder aos e-mails e entrar na Internet.

Aonde vou estar, para ajudar, a Internet é limitada e talvez não consiga passar mais os pdf para vocês, peço para que cada um olhe as referência e veja se faltou algum pdf para que eu possa mandar ainda hoje.



Estou acabando a fundamentação do problema ainda, quase nem dormi hoje, pois como não tenho prática para escrever demoro um pouco.

Peço para que olhem e arrumem os textos, principalmente o resumo que ficou uma bosta. Não sei se o Manasseis e o Felipe estão acostumados a escrever, mas seria legal ver uma lista de sugestões sobre o que escrevi, provavelmente existem alguns erros.

Já o Rodrigo, acho que é o melhor de nós sobre as regras ABNT e de citação já que fez a tese, seria legal já ir colocando as referências e as formas de citar corretamente os trabalhos no texto.



Logo eu passo o que escrevi já no modelo do word para ajudar.



Irá faltar somente a proposta da solução e inovação, que vou fazer hoje ainda.

O estado da arte e correlação com os outros trabalhos pode ser uma breve descrição já que creio que o nosso sistema seja algo novo e provavelmente não exista paper sobre eles. Existe uma secção estado da arte, apêndice A, no trabalho zanutto.pdf. Creio que olhando este apêndice e mais alguns paper seja possível fazer algumas linhas fácil. Quem poderia se dispor a fazer esta parte?







Att,



Vitor

fundamentação do problema

Pessoal,




Demorei porque estava estudando um pouco sobre os sistemas de reescrita.



Estou escrevendo sobre a fundamentação do problema, que dividi em sistemas de reescrita e nosso projeto. A primeira parte da fundamentação do problema eu fiz e está em anexo. Quando acabar sobre nosso projeto, agente fecha o item fundamentação do projeto.



Fiz tudo forma das normas e faltou arrumar as citações. Vejam ai também as citações e me digam as que vocês não possuem para eu passar via e-mail.



Enviei junto um pdf para verificarem quando abrir no word se perdeu algum símbolo das notações.







Falow