Bonne approche de l'analyse syntaxique après tokenisation

Question

J'ai écrit un programme dans lequel je lis une chaîne ou un fichier et le marque en bloc. Exemple chaîne: "int w = sad&&s||a|d++ != == < > >= <= -- sadsa++ % int sads = 232.32; if reg string test = \"Hello World\";% % +- + -/* ** false true"

exmaple Sortie:

Token[Type:'Identifier',Value:'int',Line:'1',Position:'3'] 
Token[Type:'Literal',Value:'w',Line:'1',Position:'4'] 
Token[Type:'Assign',Value:'=',Line:'1',Position:'4'] 
Token[Type:'Literal',Value:'sad',Line:'1',Position:'8'] 
Token[Type:'Logical',Value:'&&',Line:'1',Position:'8'] 
Token[Type:'Literal',Value:'s',Line:'1',Position:'11'] 
Token[Type:'Logical',Value:'||',Line:'1',Position:'11'] 
Token[Type:'Literal',Value:'a',Line:'1',Position:'14'] 
Token[Type:'Unknown',Value:'|d',Line:'1',Position:'14'] 
Token[Type:'Literal',Value:'d',Line:'1',Position:'16'] 
Token[Type:'Arithmetic',Value:'++',Line:'1',Position:'16'] 
Token[Type:'Relational',Value:'!=',Line:'1',Position:'18'] 
Token[Type:'Relational',Value:'==',Line:'1',Position:'20'] 
Token[Type:'Relational',Value:'<',Line:'1',Position:'22'] 
Token[Type:'Relational',Value:'>',Line:'1',Position:'23'] 
Token[Type:'Relational',Value:'>=',Line:'1',Position:'24'] 
Token[Type:'Relational',Value:'<=',Line:'1',Position:'26'] 
Token[Type:'Arithmetic',Value:'--',Line:'1',Position:'28'] 
Token[Type:'Literal',Value:'sadsa',Line:'1',Position:'35'] 
Token[Type:'Arithmetic',Value:'++',Line:'1',Position:'35'] 
Token[Type:'Arithmetic',Value:'%',Line:'1',Position:'37'] 
Token[Type:'Identifier',Value:'int',Line:'1',Position:'41'] 
Token[Type:'Literal',Value:'sads',Line:'1',Position:'45'] 
Token[Type:'Assign',Value:'=',Line:'1',Position:'45'] 
Token[Type:'DoubleValue',Value:'232.32',Line:'1',Position:'51'] 
Token[Type:'Semicolon',Value:';',Line:'1',Position:'51'] 
Token[Type:'Identifier',Value:'if',Line:'1',Position:'53'] 
Token[Type:'Literal',Value:'reg',Line:'1',Position:'56'] 
Token[Type:'Identifier',Value:'string',Line:'1',Position:'62'] 
Token[Type:'Literal',Value:'test',Line:'1',Position:'66'] 
Token[Type:'Assign',Value:'=',Line:'1',Position:'66'] 
Token[Type:'StringValue',Value:'Hello World',Line:'1',Position:'78'] 
Token[Type:'Semicolon',Value:';',Line:'1',Position:'78'] 
Token[Type:'Arithmetic',Value:'%',Line:'1',Position:'78'] 
Token[Type:'Arithmetic',Value:'%',Line:'1',Position:'79'] 
Token[Type:'Unknown',Value:'+-',Line:'1',Position:'80'] 
Token[Type:'Arithmetic',Value:'+',Line:'1',Position:'82'] 
Token[Type:'Arithmetic',Value:'-',Line:'1',Position:'83'] 
Token[Type:'Arithmetic',Value:'/',Line:'1',Position:'84'] 
Token[Type:'Arithmetic',Value:'*',Line:'1',Position:'85'] 
Token[Type:'Unknown',Value:'**',Line:'1',Position:'86'] 
Token[Type:'Identifier',Value:'false',Line:'1',Position:'93'] 
Token[Type:'Identifier',Value:'true',Line:'1',Position:'97'] 
Elapsed time: 31 

(Ignore Position, doit être fixé à l'avenir)

Alors maintenant, je ne sais pas vraiment une bonne approche pour interpréter davantage cette afin de lancer moi-même un petit langage de script simple.

Answer 1

Une bonne première approche est de trouver des noms pour chaque chose, comme « opération », « opérande », « littéral », « déclaration », etc.

Ensuite, une fonction qui peut lire chacun de ces à partir de votre flux de jetons, et appelle les autres le cas échéant. Par exemple. Si vous avez:

operation: <operand> <operator> <operand> 
operator: + | - 
operand: <number> | <string> 

etc., alors vous pouvez avoir une fonction (pseudo-code):

Operation parseOperation(tokens) 
{ 
    Operand operand1 = parseOperand(tokens) 
    Operation theOp = new Operation(tokens.fetchNextToken()) 
    Operand operand2 = parseOperand(tokens) 
    theOp.operand[0] = operand1 
    theOp.operand[1] = operand2 
    return theOp 
} 

et mettre en œuvre les autres fonctions d'une manière similaire. Bien sûr, certaines fonctions peuvent avoir à examiner le prochain jeton pour décider quelle autre fonction appeler, ou même anticiper plusieurs jetons.

Ceci est généralement appelé un analyseur de "descente récursive". Chacune des fonctions renvoie un objet qui représente une opération et dont les arguments sont suspendus. C'est essentiellement une structure arborescente, que vous pouvez ensuite parcourir de façon récursive ("depth-first").

Le plus simple est de donner les différents types d'objets que vous définissez DOR vos opérations et les valeurs des méthodes telles que asString() ou AsInt(), puis faire des choses comme:

int Operation::asInt() 
{ 
    int a = operand[0].asInt() 
    int b = operand[1].asInt() 
    return a + b; 
} 

objets qui sont déjà le bon type (comme une classe IntOperand) serait tout simplement retourner leur valeur:

int IntOperand::asInt() 
{ 
    return self.numericValue 
} 

ou autre chose. Les objets qui ne sont pas du bon type produisent une erreur au lieu de renvoyer une valeur, ou se convertissent eux-mêmes. Donc, peu importe la complexité de l'expression, à la fin, vous obtenez un int ou une chaîne ou autre.

Pour exécuter un programme, vous pouvez maintenant demander à l'objet le plus en bas sa valeur.