À quoi ressemble la règle de production CFG dans le code?

Question

Il y a tellement d'informations là-bas mais pas de ça aide vraiment un noob comme moi. J'ai lu beaucoup d'articles sur les langages sans contexte et l'automatisation du pushdown. Maintenant, j'essaie de comprendre comment certaines choses pourraient ressembler au code.

laisse supposer que nous avons défini un langage tel que:

L = {am bn | m >= n} 

nous donner les règles de production suivantes:

S -> B |^
B -> aBb | A 
A -> aA | a 

Comment exactement cela ressemble dans le code de pseudo? Je suppose que toutes les règles de production sont 1 état défini comme S1 ou sont tous des états séparés? De toute façon, je ne sais pas et ce serait génial si quelqu'un pouvait m'aider à comprendre comment cela fonctionne. Je sais que nous analysons les caractères d'une entrée et en fonction de quelle entrée nous recevons l'une des règles s'applique en poussant un symbole dans notre pile PDA.

Answer 1

Il existe plusieurs façons de convertir un CFG en un morceau de code qui effectue l'analyse réelle, chacun avec ses forces et ses faiblesses. Certains algorithmes, comme l'algorithme CYK, l'algorithme d'Unger et (mon préféré) l'algorithme d'Earley peuvent prendre en entrée un CFG arbitraire et une chaîne, puis utiliser la programmation dynamique pour déterminer une arborescence d'analyse pour cette chaîne si elle existe. Le fonctionnement de ces algorithmes ne ressemble pas à votre automate à pile, car ils fonctionnent en remplissant des tables de valeurs tout en traitant les caractères un à la fois.

Certains algorithmes d'analyse, en particulier LR (1) et la famille générale des parseurs LR, conservent plus directement une pile d'analyse et utilisent un contrôle à états finis pour piloter l'analyseur. Les analyseurs LR (1) ne peuvent pas gérer tous les CFG possibles - ils ne peuvent gérer que des CFG déterministes - mais des variantes comme les parseurs GLR peuvent gérer toutes les grammaires en exécutant essentiellement plusieurs piles en parallèle. Les outils de génération de compilateurs bison et yacc génèrent des parseurs dans cette famille, et si vous regardez comment fonctionnent leurs fichiers d'entrée, vous aurez une idée de la façon dont les CFG sont encodés dans le logiciel. LL (1) Les parseurs et les analyseurs de retour arrière simples fonctionnent de haut en bas et utilisent généralement une pile (souvent la pile des appels d'exécution) pour analyser les chaînes d'entrée. Cependant, ils ne peuvent pas gérer toutes les grammaires. Le générateur d'analyseur ANTLR produit des parseurs dans cette famille.

Les analyseurs Packrat fonctionnent en utilisant des CFG modifiés qui codent les priorités de l'ordre d'exécution des opérations. Le code utilisant ces analyseurs tend à refléter étroitement la forme de la grammaire. Les combinateurs d'analyseurs sont une autre technique moderne où la logique d'analyse ressemble beaucoup à la CFG.

Je recommanderais de suivre un cours sur les compilateurs ou de prendre une copie de «Techniques d'analyse syntaxique: un guide pratique» par Grune et Jacobs si vous souhaitez en savoir plus à ce sujet. Qu'est-ce que vous voulez que votre code fasse précisément?