Construindo árvores de análise com análise de redução de deslocamento

Question

Estou experimentando análise no meu tempo livre e queria implementar um analisador de redução de deslocamento para uma gramática muito simples.Li muitos artigos online, mas ainda estou confuso sobre como criar árvores de análise.Aqui está um exemplo do que eu quero fazer:

---

Gramática:

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

Aqui está um exemplo de entrada:

1 + 1 + 1 + 1

Isso, após a tokenização, torna-se:

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

---

Eu entendi aquilo:

1. Mudança significa colocar o primeiro token de entrada na pilha e removê-lo da entrada
2. Reduzindo significa substituir um ou mais elementos da pilha por um elemento gramatical

Então, basicamente, isso deveria acontecer:

Step 1:
    Stack:
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Stack is empty. Shift.

Step 2:
    Stack: TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.

Step 3:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 4:
    Stack: Expr TKN_Op 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 5:
    Stack: Expr TKN_Op TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.
    // What should I check for reduction? 
    // Should I try to reduce incrementally using 
    // only the top of the stack first, 
    // then adding more stack elements if I couldn't
    // reduce the top alone?

Step 6:
    Stack: Expr TKN_Op Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: Expr TKN_Op Expr can be reduced to Expr. Reduce.

Step 7:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: ...
    // And so on...

Apesar de "o que reduzir?" dúvida, não tenho ideia de como construir corretamente uma árvore de análise.A árvore provavelmente deveria ficar assim:

1    +    o
          |
     1    +    o
               |
          1    +    1

Devo criar um novo nó na redução?

E quando devo adicionar filhos ao nó recém-criado/quando devo criar um novo nó raiz?

Answer 1

A coisa simples e óbvia a fazer é criar um nó de árvore em cada redução e adicionar os nós da árvore dos elementos gramaticais que foram reduzidos a esse nó da árvore.

Isso é facilmente gerenciado com uma pilha de nós executada em paralelo à pilha de "tokens de deslocamento" usada pelo analisador bruto.Para cada redução para uma regra de comprimento N, a pilha de tokens de deslocamento é encurtada em N e o token não terminal é colocado na pilha de deslocamentos.Ao mesmo tempo, encurte a pilha de nós removendo os N nós superiores, crie um nó para o não terminal, anexe os N nós removidos como filhos e empurre esse nó para a pilha de nós.

Esta política funciona até mesmo com regras que possuem comprimento zero no lado direito:crie um nó de árvore e anexe o conjunto vazio de filhos a ele (por exemplo, crie um nó folha).

Se você pensar em uma "mudança" em um nó terminal como uma redução (dos caracteres que formam o terminal) ao nó terminal, então as mudanças no nó terminal se encaixam perfeitamente.Crie um nó para o terminal e coloque-o na pilha.

Se você fizer isso, obterá uma "árvore de sintaxe/análise concreta" que corresponde à gramática isomorficamente.(Fazemos isso para uma ferramenta comercial que ofereço).Há muitas pessoas que não gostam dessas árvores concretas, porque elas contêm nós para palavras-chave, etc., o que realmente não agrega muito valor.É verdade, mas essas árvores são extremamente fáceis de construir e extremamente fáceis de entender porque a gramática é a estrutura da árvore.Quando você tem 2.500 regras (como fazemos para um analisador COBOL completo), isso é importante.Isso também é conveniente porque todo o mecanismo pode ser totalmente integrado à infraestrutura de análise.O engenheiro gramatical simplesmente escreve regras, o analisador executa, voila, uma árvore.Também é fácil mudar a gramática:apenas mude, voila, você ainda terá árvores de análise.

No entanto, se você não quiser uma árvore concreta, por exemplo, quiser uma "árvore de sintaxe abstrata", então o que você precisa fazer é deixar o engenheiro gramatical controlar quais reduções geram nós;geralmente adicionamos algum anexo processual (código) a cada regra gramatical a ser executada em uma etapa de redução.Então, se qualquer anexo processual produzir um nó, ele será retido em uma pilha de nós.Qualquer anexo processual que produza um nó deve anexar nós produzidos pelos elementos da direita.Se houver, é isso que YACC/Bison/...a maioria dos mecanismos de análise de redução de deslocamento o fazem.Leia sobre Yacc ou Bison e examine uma gramática.Esse esquema lhe dá muito controle, ao preço de insistir para que você assuma esse controle.(Para o que fazemos, não queremos tanto esforço de engenharia na construção de uma gramática).

No caso da produção de CSTs, é conceitualmente simples remover nós “inúteis” das árvores;fazemos isso em nossa ferramenta.O resultado é muito parecido com um AST, sem o esforço manual para escrever todos os anexos processuais.

Answer 2

A razão do seu problema é que você tem um conflito de mudança/redução em sua gramática:

expr: expr OP expr
    | number

Você pode resolver isso de 2 maneiras:

expr: expr OP number
    | number

para operadores associativos à esquerda, ou

expr: number OP expr
    | number

para associativos corretos.Isso também deve determinar o formato da sua árvore.

A redução geralmente é feita quando uma cláusula é detectada completa.No caso associativo correto, você começaria no estado 1 que espera um número, o coloca na pilha de valores e muda para o estado 2.No estado 2, se o token não for um OP, você poderá reduzir um número para um expr.Caso contrário, pressione o operador e mude para o estado 1.Quando o estado 1 for concluído, você poderá reduzir o número, o operador e a expressão para outra expressão.Observe que você precisa de um mecanismo para "retornar" após uma redução.O analisador geral começaria então no estado 0, digamos, que iria imediatamente para o estado 1 e aceitaria após a redução.

Observe que ferramentas como yacc ou bison tornam esse tipo de coisa muito mais fácil porque trazem todo o maquinário de baixo nível e as pilhas.