Le développement d'un analyseur simple,
https://stackoverflow.com/questions/391432
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Mon travail de jour inclut le travail pour développer un compilateur comme Pascal. Je travaille tout au long de l'optimisation et la génération de code.
Je voudrais également commencer à apprendre à construire un analyseur simple pour la même langue. Je suis cependant pas vraiment comment s'y prendre. Flex et Bison semblent être le choix. Mais, est-il pas possible d'écrire un analyseur en C ++ ou C #? Je suis un peu la chair de poule avec C.
Yacc ++ soutient C #, mais il est une licence. Je suis à la recherche de toute l'aide que je peux trouver à cet égard. Les suggestions seraient très appréciés.
La solution
Je crois que vous pouvez utiliser ANTLR avec C #. Je ne l'ai jamais essayé moi-même (encore), mais il y a un tutoriel ici qui pourrait vous orienter dans la bonne direction.
Autres conseils
Personnellement, je roule mon propre analyseur et lexer (LL). Voici un exemple très abrégé. Il est en C ++, mais nous espérons que vous pouvez adapter. Il utilise une PARSE_HIGHER macro pour le rendre facile à insérer les opérateurs à différents niveaux de priorité sans changer beaucoup de code.
// routine to scan over whitespace/comments
void ScanWhite(const char* &pc){
while(true){
if(0);
else if (WHITESPACE(*pc)) pc++;
else if (pc[0]=='/' && pc[1]=='/'){
while(*pc && *pc++ != '\n');
}
else break;
}
}
// routine to lex an identifier
bool SeeId(const char* &pc, string sId){
ScanWhite(pc);
const char* pc0 = pc;
if (alpha(*pc)){
sId = "";
while(alphanum(*pc)) sId += (*pc++);
return true;
}
pc = pc0;
return false;
}
// routine to lex a number
bool SeeNum(const char* &pc, double &dNum){
ScanWhite(pc);
const char* pc0 = pc;
if (digit(*pc)){
dNum = 0;
while(digit(*pc)) dNum = dNum * 10 + (*pc++ - '0');
if (*pc == '.'){
double divisor = 1, frac = 0;
while(digit(*pc)){
divisor *= 0.1;
frac += (*pc++ - '0') * divisor;
}
dNum += frac;
}
return true;
}
pc = pc0;
return false;
}
// routine to lex some constant word
bool SeeWord(const char* &pc, const char* sWord){
ScanWhite(pc);
const char* pc0 = pc;
int len = strlen(sWord);
if (strncmp(pc, sWord, len)==0 && !alphanum(pc[len])){
pc += len;
return true;
}
pc = pc0;
return false;
}
// routine to lex a single character like an operator
bool SeeChar(const char* &pc, const char c){
ScanWhite(pc);
const char* pc0 = pc;
if (*pc == c){
pc++;
return true;
}
pc = pc0;
return false;
}
// primitive expression parser
void ParsePrimitiveExpr(const char* &pc, CNode* &p){
double dNum;
char sId[100];
if (0);
else if (SeeNum(pc, dNum)){
p = new CNode(dNum);
}
else if (SeeId(pc, sId)){
// see if its a function call
if (SeeChar(pc, '(')){
p = MakeNewFunctionCallNode(sId);
while(!SeeChar(pc, ')')){
CNode* p1 = null;
ParseExpression(pc, p1);
AddArgumentExprToFunctionCallNode(p, p1);
SeeChar(pc, ','); /* optional comma separator */
}
}
// otherwise its just a variable reference
else {
p = new CNode(sId);
}
}
// handle embedded expressions
else if (SeeChar(pc, '(')){
ParseExpression(pc, p);
if (!SeeChar(pc, ')')) /* deal with syntax error */
}
}
#define PARSE_HIGHER ParsePrimitiveExpr
// product parser
void ParseProduct(const char* &pc, CNode* &p){
PARSE_HIGHER(pc, p);
while(true){
if (0);
else if (SeeChar(pc, '*')){
CNode p1 = null;
PARSE_HIGHER(pc, p1);
p = new CNode('*', p, p1);
}
else if (SeeChar(pc, '/')){
CNode p1 = null;
PARSE_HIGHER(pc, p1);
p = new CNode('/', p, p1);
}
else break;
}
}
#undef PARSE_HIGHER
#define PARSE_HIGHER ParseProduct
// sum parser
void ParseSum(const char* &pc, CNode* &p){
PARSE_HIGHER(pc, p);
while(true){
if (0);
else if (SeeChar(pc, '+')){
CNode p1 = null;
PARSE_HIGHER(pc, p1);
p = new CNode('+', p, p1);
}
else if (SeeChar(pc, '-')){
CNode p1 = null;
PARSE_HIGHER(pc, p1);
p = new CNode('-', p, p1);
}
else break;
}
}
#undef PARSE_HIGHER
// can insert more routines like the above
// to handle move operators
#define PARSE_HIGHER ParseSum
// overall expression parser
void ParseExpression(const char* &pc, CNode* &p){
PARSE_HIGHER(pc, p);
}
Ajout de syntaxe de l'instruction de style Pascal:
void ParseStatement(const char* &pc){
char sId[100];
if(0);
else if (SeeWord(pc, "begin")){
while(!SeeWord(pc, "end")){
ParseStatement(pc);
SeeChar(pc, ';');
}
}
else if (SeeWord(pc, "while")){
CNode* p1 = null;
ParseExpression(pc, p1);
ParseStatement(pc);
/* semantics for while statement */
}
else if (SeeWord(pc, "if")){
CNode* p1 = null;
ParseExpression(pc, p1);
ParseStatement(pc);
if (SeeWord(pc, "else")){
ParseStatement(pc);
}
/* semantics for if statement */
}
else if (SeeWord(pc, "for")){
/* you do it */
}
// handle assignments and subroutine calls
else if (SeeId(pc, sId)){
if(0);
else if (SeeChar(pc, '=')){
CNode* p1 = null;
ParseExpression(pc, p1);
/* semantics for assignment statement */
}
else if (SeeChar(pc, '(')){
CNode* p = MakeNewFunctionCallNode(sId);
while(!SeeChar(pc, ')')){
CNode* p1 = null;
ParseExpression(pc, p1);
AddArgumentExprToFunctionCallNode(p, p1);
SeeChar(pc, ','); /* optional comma separator */
}
}
else {
/* we have a 1-word statement, which is OK in pascal */
}
}
else {
/* syntax error */
}
}
Il faut encore la syntaxe pour l'indexation de tableau, déclaration de variable, et la définition de la fonction, mais je l'espère, il est clair comment faire.
Dans son texte de programmation classique, Algorithmes + Structures de données = Programmes , Niklaus Wirth développe un analyseur de descente récursive entière (en Pascal) pour un simple langage comme Pascal0.
Si vous l'écrire en Java, je vous recommande ANTLR. Il est un analyseur-générateur agréable LL (*) écrit en Java. Il y a un livre formidable pour sur Amazon, aussi.
bison et flex sont les générateurs d'analyseur canoniques. Si vous êtes intéressé par C ++, j'ai trouvé esprit boost utile. Je ne l'ai jamais utilisé pour quoi que ce soit aussi complexe qu'un compilateur bien. Je suis sûr que d'autres auront des suggestions intéressantes pour d'autres langues telles que C # ...
J'ai écrit un analyseur XSLT avec flex et bison. Plus récemment, je fais un projet en utilisant ANTLR, bien que:
est la langue JFig syntaxe claire et efficace (et mieux que le DSL XML Spring Framework)
Je l'ai aimé travailler dans ANTLR beaucoup plus que Flex et Bison. ANTLR vous met en place à un niveau supérieur d'abstraction, à certains égards. Les définitions lexicales et la grammaire de l'analyseur peuvent tous aller dans un seul fichier. (ANTLR va générer le fichier de jeton.)
L'un des éléments clés est la possibilité de définir des grammaires d'arbres. Fondamentalement, vous faire une analyse syntaxique de la grammaire sur la langue d'entrée et ont des actions qui réécrivent à une sortie d'arbre AST très optimale (qui restent en tant que structures de données liées à la mémoire). Vous pouvez ensuite passer cet arbre à un autre analyseur défini dans un fichier analyseur d'arbre séparé. L'analyseur d'arbre est l'endroit où vous faites le travail réel des éléments d'action que vous voulez.
Ceci est une approche agréable que vous pouvez garder la forme AST et retraiter à plusieurs reprises au besoin - décollant nœuds de sous-arbre spécifiques pour traiter contre la base d'actions dernier, etc. Pensez à quelque chose comme un interpretor linguistique. Au lieu d'entrer dans une boucle et de traitement de la langue à partir du sol, encore et encore, peut traiter simplement par sa représentation AST.
Dans mon cas, je l'ai imaginé une usine de haricots pour faire l'injection de dépendance IoC. Mon usine de haricot conserve l'AST d'un descripteur de haricot autour lors de l'exécution. Quand il a besoin de faire (ou récupérer) une nouvelle instance de haricot, je passe juste le sous-arbre descripteur de haricot AST à mon analyseur d'arbre - le résultat est l'instance du bean souhaité (il y a beaucoup de facteurs qui vont pour déterminer comment instancier la haricot demandé, y compris faire des autres haricots qui sont référencés et / ou en appliquant d'autres comportements particuliers via des attributs méta).
Enfin, mon usine actuelle de haricots VISE Java, mais je veux cibler ActionScript3 et C # .NET. ANTLR a le soutien pour le faire.
Comme mentionné précédemment, Terrence Parr a écrit un livre sur la façon d'utiliser ANTLR. Il est destiné aux programmeurs de travail qui ont besoin de faire quelque chose de pratique avec ANTLR (par opposition à un traitement académique du sujet).
Si votre désir C # selon cette Question essayer point Gardens GPPG et Gplex.
Lorsque vous utilisez Lex et Yacc vous n'écrivez pas vraiment quoi que ce soit dans C. Lex est sa propre langue, comme Yacc. Vous écrivez donc l'analyseur lexical dans Lex et l'analyseur Yacc . Cependant, pour Pascal, entrées Lex et Yacc sont déjà .
L'analyseur résultant et lexer ont des interfaces C, ce qui est vrai. Cependant la plupart des langues, y compris C ++, ont des moyens simples pour appeler (ou WRAP) interfaces C.
Je ne suis pas un expert en elle, mais je suis sûr que tous les va ci-dessus pour ANTLR ainsi.
Si vous demandez de le faire dans « C ++ pur » (quoi que cela signifie), regarder dans boost esprit . Je ne vois vraiment pas le point dans la pureté théorique si elle provoque une tonne de plus fonctionne bien.
Ecrire vos propres lexers et parseurs à la main est en fait un peu amusant. Un lexer est l'une des situations très peu où vous pouvez justifier le recours à la fois goto et le préprocesseur. Cependant, je ne dirais pas pour une langue à part entière comme Pascal, si vous pouvez l'éviter. Ce serait beaucoup de travail. Je parle homme-années.
