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

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, ... \in T$$A, B, C, ... \in N$$... X, Y, Z \in N \cup T$ 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.$\alpha, \beta, \gamma, ... \in \{N \cup T\}^*$$A \xrightarrow{i} \omega$$i$

Além disso, em toda a descrição, a relação de equivalência é usada.$\kappa_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 β .$A \xrightarrow{i} \alpha \bullet \beta$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$n$$m$$\beta$

$S' \xrightarrow{0} S \$$$S' \xrightarrow{0} \bullet S \$$

$q$

1. $A \xrightarrow{i} \alpha \bullet \beta$$q \xrightarrow{X} q'$$X$$\beta$

2. $A \xrightarrow{i} \omega \bullet$$B \xrightarrow{j} \alpha A \bullet \beta, i, 0$$B \xrightarrow{j} \alpha A \beta$

3. $A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$\beta$$X \in N$$X \xrightarrow{j} \bullet \omega$$X \xrightarrow{j} \omega$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$q \xrightarrow{X} q'$$C \xrightarrow{i} \alpha \bullet X \beta, m, n$$q$$C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$$q'$

4. $A \xrightarrow{i} \omega \bullet, m, n$$B \xrightarrow{j} \alpha A \bullet \beta, m, n$$B \xrightarrow{j} \alpha A \beta$

É 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.

$r_{0,0}$$\$$

Questões

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

$\kappa$$\kappa_0$$FOLLOW_{LM}$

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 :)

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.