La Machine à État fini analyseur
Je voudrais analyser une auto-conçu format de fichier avec un FSM-comme analyseur en C++ (c'est un teach-myself-c++-the-hard-way-by-doing-something-big-and-difficult type de projet :)). J'ai un segmentées en chaîne avec des retours à la ligne signifiant la fin d'un euh... ligne. Voir ici pour un exemple d'entrée. Tous les commentaires et d'ordure, est filtré, j'ai donc un std::string comme ceci:
global \n { \n SOURCE_DIRS src \n HEADER_DIRS include \n SOURCES bitwise.c framing.c \n HEADERS ogg/os_types.h ogg/ogg.h \n } \n ...Explication de syntaxe:
- { } sont étendues, et les mots avec des majuscules signifient que la liste des options/fichiers est à suivre.
- \n seulement important dans une liste d'options/fichiers, signifiant la fin de la liste.
J'ai donc pensé que le FSM serait simple/suffisamment extensible pour mes besoins/connaissances. Aussi loin que je peux (et veux que mon fichier de conception de l'être), je n'ai pas besoin simultanées états ou quelque chose de compliqué comme ça. Certains de la conception/mise en œuvre des questions:
- Dois-je utiliser un
enumou d'un résuméclass+ dérivés pour mes états? Le premier est probablement mieux pour les petites syntaxe, mais pourrait devenir laid plus tard, et la deuxième est l'exact opposé. Je penche pour la première, pour sa simplicité.enumexemple et exemple de classe. EDIT: ce sujet cette suggestion pourgoto, je pensais qu'ils étaient mal en C++? - Lors de la lecture d'une liste, j'ai besoin de ne PAS ignorer
\n. Ma façon préférée de l'aide de l'stringviastringstream, va ignorer\npar défaut. J'ai donc besoin de façon de dire (la même!)stringstreamde ne pas ignorer les retours à la ligne lorsqu'un certain état est activé. - Va de la simple
enumétats suffire pour le multi-niveau de l'analyse (étendues au sein des étendues{...{...}...}) ou qui ont besoin de hacky implémentations? - Voici le projet d'états que j'ai en tête:
upper: lit mondiale, exe, lib+ noms de cible...normal: à l'intérieur d'un champ d'application capable de lire les SOURCES..., de créer des variables utilisateur...list: ajoute des éléments à une liste jusqu'à ce qu'un saut de ligne est rencontré.
Chaque application aura une sorte de conditionnelle (par exemple, win32:global { gcc:CFLAGS = ... }) et devront être traitées exactement de la même manière de tous les cotés (même dans le list de l'état, élément par élément).
Merci pour toute entrée.
La Machine À État Fini.
LOL, édité à préciser.
goto est pas mal. Abusé goto est le mal. Utilisé correctement goto peut rendre le code plus facile à lire et à suivre, et l'un de l'utilisation correcte des cas, je sais de pour eux, c'est exactement dans le codage Smqs. Pourquoi tant insister sur goto être le mal? Religion.Le problème c'est que l'abus crée des monstres indéchiffrable.
OriginalL'auteur rubenvb | 2010-06-21
Vous devez vous connecter pour publier un commentaire.
Si vous avez de nidification étendues, puis une Machine à états Finis est pas la bonne façon de faire, et vous devriez regarder dans un Contexte de Libre-Grammaire de l'analyseur. Un LL(1) analyseur peut être écrite comme un ensemble de récursive funcitons, ou un LALR(1) analyseur peut être écrit à l'aide d'un analyseur générateur comme les Bisons.
Si vous ajoutez une pile à un FSM, vous obtenez en automate à pile territoire. Un automate à pile déterministe est équivalent à un contexte exempt de grammaire (bien qu'un automate à pile déterministe est strictement moins puissants). LALR(1) analyseur de générateurs de réellement générer un automate à pile déterministe en interne. Une bonne conception du compilateur manuel couvrira l'algorithme exact par lequel l'automate à pile est construit à partir de la grammaire. (De cette façon, l'ajout d'une pile n'est pas "hacky".) Cet article de Wikipédia décrit également la façon de construire les LR(1) automate à pile à partir de votre grammaire, mais l'OMI, l'article n'est pas aussi claire qu'elle pourrait l'être.
Si votre étendues nid seulement finitely de profondeur (c'est à dire que vous avez le
upper,normaletlistniveaux, mais vous n'avez pas imbriquéelists ou imbriquésnormals), alors vous pouvez utiliser un FSM sans pile.J'ai édité ma réponse pour répondre à votre commentaire. Vous êtes suggérer des modifications qui ont une très bonne base théorique, et a été formalisé dans les moindres détails. Je suggère de lire sur la conception du compilateur pour en savoir plus sur la façon dont les choses sont mises en œuvre aujourd'hui dans l'analyseur de générateurs.
Je compte sur l'appui illimité de nidification, quelque chose comme
SOURCES main.cpp win32:{ msvc:class_winmsvc.cpp gcc:class_wingcc.cpp} mac:{ class_mac.cpp otherstuff.cpp }. Peut-être pas le meilleur codé projet qui aura besoin de cela, mais il semble assez puissant pour moi. Cela soulève la question de la nécessité de maintenir l'ordre dans la pile, de savoir exactement où vous êtes dans le champs d'application. Serait-ce que prendre soin de soi, ou besoin d'une attention particulière? MerciOriginalL'auteur Ken Bloom
Il y a deux étapes de l'analyse d'un texte de flux d'entrée pour l'analyse:
l'Analyse Lexicale: C'est où votre flux d'entrée est divisé en unités lexicales. Il ressemble à une séquence de caractères et génère des jetons (comme pour le mot dans les langues parlées ou écrites). Des machines à états finis sont très bons à l'analyse lexicale à condition que vous avez fait de bons choix de conception sur la structure lexicale. À partir de vos données ci-dessus, individal lexèmes serait des choses comme vos mots-clés (par exemple "global"), les identifiants (par exemple, "bit à bit", "SOURCES"), symbolique tokesn (par ex. "{" "}", ".", "/"), des valeurs numériques, d'échapper à des valeurs (par exemple, "\n"), etc.
Syntaxique /Grammatic Analyse: Lors de la génération d'une séquence de tokens (ou peut-être alors que vous êtes en train de faire), vous devez être en mesure d'analyser la structure afin de déterminer si la séquence de jetons est compatible avec votre langage de conception. Vous avez généralement besoin d'une sorte d'analyseur pour cela, mais si la structure de la langue n'est pas très compliqué, vous pourriez être en mesure de le faire avec une machine à état fini à la place. En général (et puisque vous voulez des structures de nidification dans votre cas en particulier), vous devrez utiliser l'une des techniques Ken Bloom décrit.
Donc, en réponse à vos questions:
J'ai trouvé que pour les petits des générateurs de jetons, une matrice d'état /transition valeurs convient, quelque chose comme
next_state = state_transitions[current_state][current_input_char]. Dans ce cas, lenext_stateetcurrent_statesont certains types d'entiers (y compris, éventuellement, un type énuméré). Entrée des erreurs sont détectées lors de la transition d'un état non valide. La fin d'un jeton est identifié en fonction de l'état d'identification valide endstates sans transition valide à la disposition d'un autre état étant donné le prochain caractère. Si vous êtes inquiet au sujet de l'espace, vous pouvez utiliser un vecteur de cartes à la place. Faire les états des classes est possible, mais je pense que c'est sans doute chose la plus difficile que vous avez besoin.Lors de la lecture d'une liste, j'ai besoin de ne PAS ignorer \n.
Vous pouvez soit créer un jeton appelé "\n", ou plus généraliser échapper à jeton (un identificateur précédé d'une barre oblique inverse. Si vous parlez d'identifier les sauts de ligne dans le source, puis ceux-ci sont simplement des personnages dont vous avez besoin pour créer des transitions dans votre état de matrice de transition (être conscient de la differnce entre Unix et Windows les sauts de ligne, cependant, vous pouvez créer un FSM qui fonctionne sur soit).
le simple enum états suffire pour le multi-niveau de l'analyse (étendues au sein des étendues {...{...}...}) ou qui ont besoin de hacky implémentations?
C'est là que vous aurez besoin d'une grammaire ou d'un automate à pile, à moins que vous ne peut garantir que l'imbrication de ne pas dépasser un certain niveau. Même alors, il va probablement faire de votre FSM très complexe.
Voici le projet d'états que j'ai en tête: ...
Voir mon commments sur lexicales et grammaticales de l'analyse ci-dessus.
string/jeton, pas un seulchar. #2 était en fait uniostreamquestion précise: est-il possible de les "espaces" définition d'un flux (lorsque par exemple, en utilisantoperator>>de lire un nouveau jeton). Merci pour vos commentaires.Je suppose que mon point est que vous avez besoin de faire une distinction claire entre ce qui est possible avec la FSM base de l'analyse lexicale et ce qui ne l'est pas. Si vous avez déjà fait la tokenisation, ensuite, en fonction de votre question, vous avez besoin pour commencer à travailler sur quelque chose pour effectuer le syntaxiques / grammatic analyse. Cela signifie probablement une grammaire, pas un FSM.
Comment sur une grammaire mis en œuvre dans un FSM(+pile=automate à pile)? Je ne veux pas écrire encore une description de la grammaire, je le veux lire et de la production en C++. Je pense (sûrement pour mon exemple) qu'un FSM(+pile) est plus que possible de la grammaire des trucs, non?
Basé sur ce que vous avez décrit, un automate à pile fonctionne. La question est de savoir si vous pouvez développer un déterministe PDA qui sera plus facile à mettre en œuvre et à l'utilisation qu'un non-déterministe. Basé sur ce que je vois, probablement, vous pouvez définir un déterministe PDA, mais je ne sais pas pour sûr.
OriginalL'auteur andand
Pour l'analyse j'essaie toujours d'utiliser quelque chose de déjà fait ses preuves: ANTLR avec ANTLRWorks qui est d'une grande aide pour la conception et l'essai d'une grammaire. Vous pouvez générer du code C/C++ (et d'autres langues), mais vous avez besoin pour construire le ANTLR exécution de ces langues.
Bien sûr, si vous trouvez flex ou bison plus facile à utiliser, vous pouvez les utiliser aussi (je sais qu'ils ne produisent que le C et le C++ mais j'ai peut-être mal puisque je n'ai pas utilisé pendant un certain temps).
OriginalL'auteur INS