Análise de resolução por turnos - perguntas

10

Recentemente, deparei com um artigo descrevendo a técnica de análise mencionada no título. Infelizmente, a terminologia usada no referido artigo está um pouco além da minha compreensão, por isso tenho tentado entender o algoritmo de construção de maneira mais intuitiva. Acredito que consegui ( esta apresentação foi a fonte do momento ah-ha), mas uma verificação da correção de alguém familiarizado com a técnica ou a terminologia contida nela seria muito apreciada.

Vou descrever minha opinião sobre a solução (se estiver correta, acredito que poderia ser útil para outras pessoas que tentam entender a técnica) e fazer perguntas adicionais posteriormente. Para garantir que não há mal-entendido, eu vou usar a seguinte notação padrão: , A , B , C , . . . N , . . . X , Y , Z N T , α , βa,b,c,...TA,B,C,...N...X,Y,ZNT e, como no papel, um i co para denotar número regra i . No entanto, provavelmente usarei nomes diferentes para conceitos do que o artigo original.α,β,γ,...{NT}Aiωi

Além disso, em toda a descrição, a relação de equivalência é usada.κ0

Construção

Existem dois tipos de itens dentro do autômato de análise: itens LR simples (0) do formato que chamo de itens de turno e itens do formato A i α β , m , n que eu chamo de resolução itens ; eles dizem ao analisador para empurrar n símbolos de volta ao fluxo de entrada e depois reduzir pelo número de regra m no primeiro símbolo de β .AiαβAiαβ,m,nnmβ

S0S$S0S$

q

  1. AiαβqXqXβ

  2. AiωBjαAβ,i,0BjαAβ

  3. Aiαβ,m,nXβXNXjωXjωAiαβ,m,nXqXqCiαXβ,m,nqCiαXβ,m,n+1q

  4. Aiω,m,nBjαAβ,m,nBjαAβ

É claro que isso é apenas um esboço; na verdade, um fechamento do estado deve ser calculado primeiro e só então podemos lidar com transições / turnos e resoluções.

r0,0$

Questões

O primeiro é, obviamente, se o processo descrito acima está correto.

κκ0FOLLOWLM

E o final é sobre resolução de conflitos. O artigo descreve bem o que constitui uma inadequação em um autômato de resolução de turnos; existe uma maneira de resolver essas inadequações, semelhante às formas de resolver conflitos em um analisador de LR tradicional? Poderia algo como a resolução de conflitos no estilo yacc via precedência e associatividade ser implementado em um gerador de analisador ShRe?

Obrigado se você ler tudo isso e quaisquer respostas serão muito apreciadas :)

Jakub Lédl
fonte
sugira migrar essa pergunta para a história. quanto ao artigo, parece ser um algoritmo muito complexo que "provavelmente" (?) não foi implementado por ninguém. a idéia principal parece ser combinar lookahead arbitrário, mas também com análise de tempo linear ...? mas quantas aplicações seriam aceitáveis ​​com um algoritmo superlinear mais simples, mais padrão? alguma idéia, qual aplicativo funcionaria melhor com essa abordagem? você tem um ou conhece um?
vzn
11
Um exercício teórico muito bom (embora eu não tenha examinado os detalhes técnicos). Dado que a potência total da LR (k) nem sempre é usada, pode-se pensar no impacto prático. Eu vejo dois problemas com esse tipo de trabalho: (1) como o algoritmo se torna mais complexo, ainda é possível para a mente humana mexer na gramática e entender as consequências, quando acontece que não funciona. É um fato frequente que técnicas altamente sofisticadas sejam muito gratificantes quando funcionam, mas pioram as coisas quando não funcionam. (2) será linear nos casos em que os algoritmos gerais de CF não são lineares.
babou

Respostas:

0

Verifique se isso é discutido na enciclopédica D. Grune, CJH Jacobs, "Parsing Techniques: a Practical Guide" (Spinger, 2008). Caso contrário, talvez seja semelhante o suficiente a uma técnica discutida.

vonbrand
fonte