Einen Abstract Syntax Tree erstellen in C

Question

Ich möchte einen Interpreter schreiben und habe mich mit dem Konzept eines Abstract Syntax Tree beschäftigt. Ich kann mir nur nicht vorstellen wie ich das in Code realisieren soll. Wo fange ich da genau an. Wenn ich diesen Code habe

var a = 1;
var b = 2;
var c = a + b;

Wie kann ich ein Programm in C schreiben das daraus einen AST erstellen kann?

Answer 1

Hier ist ein Beispiel in C++ wie du den Code in einem Abstract Syntax Tree darstellen könntest.

#include <iostream>
#include <vector>

class Token {
 
    private: 
    	std::string type;
    	std::string value; 
 
    public:
        Token() {
            type = "";
            value = "";
        } 
 
        Token(std::string _type, std::string _value) {
            type = _type;
            value = _value;
        }  
 
        ~Token(){};	
 
    	std::string _value() { 
            return value; 
        }
 
    	std::string _type() { 
            return type; 
        } 
 
        std::string str() { 
            return ("Token("+type+","+value+")"); 
        }  
 
};

class ASTNode {
 
    public:        
        std::vector<ASTNode*> child;                    
    	Token token;                
 
        ASTNode() {};                        
 
        ASTNode(Token _token) {
            token = _token;
        }         
 
        ~ASTNode() {}; 
 
        void make_child(ASTNode _node) {
            ASTNode *temp = new ASTNode(_node._token());
            temp->child = _node.child;
            child.push_back(temp);
        }            
 
        Token _token() {
            return token;
        }     
 
        void show(int level) {                
 
            if(level < 2 && level != 0) 
                std::cout << std::string(level*2, ' ') << "Token('" << token._type() << "', '" << token._value() << "')\n";
 
            else 
                std::cout << std::string(level*2, ' ') << "Token('" << token._type() << "', '" << token._value() << "')\n";   
 
            for(auto it = child.begin(); it != child.end(); it++) 
                (*it)->show(level+1);
 
        }
 
};

int main()
{
    
    ASTNode tree = Token("SCRIPT", "");

    ASTNode node = Token("ASSIGN", "=");
    ASTNode left = Token("VAR", "a");
    ASTNode right = Token("INT", "1");
    node.make_child(left);
    node.make_child(right);

    tree.make_child(node);
    
    node = Token("ASSIGN", "=");
    left = Token("VAR", "b");
    right = Token("INT", "2");
    node.make_child(left);
    node.make_child(right);
    
    tree.make_child(node);
    
    node = Token("ASSIGN", "=");
    left = Token("VARIABLE", "c");
    right = Token("ADD", "+");
    
    ASTNode a = Token("VARIABLE", "a");
    ASTNode b = Token("VARIABLE", "b");
    
    right.make_child(a);
    right.make_child(b);
    
    node.make_child(left);
    node.make_child(right);

    tree.make_child(node);
    
    tree.show(0);
    
}

Die Ausgabe sieht so aus (Beispiel auf OnlineGDB):

Token('SCRIPT', '')
  Token('ASSIGN', '=')
    Token('VAR', 'a')
    Token('INT', '1')
  Token('ASSIGN', '=')
    Token('VAR', 'b')
    Token('INT', '2')
  Token('ASSIGN', '=')
    Token('VARIABLE', 'c')
    Token('ADD', '+')
      Token('VARIABLE', 'a')
      Token('VARIABLE', 'b')

Answer 2

Mit Flex und Bison kannst du einen Interpreter erstellen. Erstelle 2 Dateien:

calc.l
calc.y

In calc.l definierst du deine Syntax in EBNF Format.

%{
#include "y.tab.h"
void yyerror (char *s);
int yylex();
%}

%%
"print"				   { return print; }
"printr"			   { return printr; }
"exit"				   { return exit_command; }
[a-zA-Z]			   { yylval.id = yytext[0]; return identifier; }
[0-9]+                 { yylval.num = atoi(yytext); return number; }
[0-9]+\.[0-9]+         { yylval.dec = atof(yytext); return decimal; }
[ \t\n]                ;
[-+=;]           	   { return yytext[0]; }
.                      { ECHO; yyerror ("unexpected character"); }

%%

int yywrap (void) {return 1;}

Und in calc.y kommt die Implementierung.

%{
void yyerror (char *s);
int yylex();
#include <stdio.h>     /* C declarations used in actions */
#include <stdlib.h>
#include <ctype.h>
int symbols[52];
int symbolVal(char symbol);
void updateSymbolVal(char symbol, int val);
float tof(int i);
%}

%union {int num; char id; float dec;}         /* Yacc definitions */
%start line
%token print
%token printr
%token exit_command
%token <num> number
%token <dec> decimal
%token <id> identifier
%type <num> line exp term
%type <id> assignment

%%

/* descriptions of expected inputs corresponding actions (in C) */

line    : assignment ';'		{ ; }
		| exit_command ';'		{ exit(EXIT_SUCCESS); }
		| print exp ';'			{ printf("Printing %d\n", $2); }
        | printr exp ';'		{ printf("Printing %f\n", $2); }
		| line assignment ';'	{ ; }
		| line print exp ';'	{ printf("Printing %d\n", $3); }
        | line printr exp ';'	{ printf("Printing %f\n", $3); }
		| line exit_command ';'	{ exit(EXIT_SUCCESS); }
        ;

assignment : identifier '=' exp  { updateSymbolVal($1,$3); }
			;
exp    	: term                  { $$ = $1;}
       	| exp '+' term          { $$ = $1 + $3; }
       	| exp '-' term          { $$ = $1 - $3; }
       	;
        
term   	: number                { $$ = $1; }
        | decimal               { $$ = tof($1); }
		| identifier			{ $$ = symbolVal($1); } 
        ;

%%

/* C code */

float tof(int i) {
    float f = i + 0.0;
    return f;
}

int computeSymbolIndex(char token)
{
	int idx = -1;
	if(islower(token)) {
		idx = token - 'a' + 26;
	} else if(isupper(token)) {
		idx = token - 'A';
	}
	return idx;
} 

/* returns the value of a given symbol */
int symbolVal(char symbol)
{
	int bucket = computeSymbolIndex(symbol);
	return symbols[bucket];
}

/* updates the value of a given symbol */
void updateSymbolVal(char symbol, int val)
{
	int bucket = computeSymbolIndex(symbol);
	symbols[bucket] = val;
}

int main (void) {
	/* init symbol table */
	int i;
	for(i=0; i<52; i++) {
		symbols[i] = 0;
	}

	return yyparse ( );
}

void yyerror (char *s) {fprintf (stderr, "%s\n", s);}

Das kompilierst du mit

flex calc.l
bison -dy calc.y
gcc -g lex.yy.c y.tab.c -o calc

Und hast einen kleinen Miniinterpreter.