Question Construire un analyseur syntaxique (partie I)


Je fais mon propre langage de programmation basé sur javascript (ouais, c'est fou, mais pour apprendre seulement ... peut être?). Eh bien, je lis des parsers et le premier passage consiste à convertir le code source en jetons, comme:

if(x > 5)
  return true;

Tokenizer à:

T_IF          "if"
T_LPAREN      "("
T_IDENTIFIER  "x"
T_GT          ">"
T_NUMBER      "5"
T_RPAREN      ")"
T_IDENTIFIER  "return"
T_TRUE        "true"
T_TERMINATOR  ";"

Je ne sais pas si ma logique est correcte pour cela. Sur mon analyseur, c'est encore mieux (ou pas?) et y traduire (oui, tableau multidimensionnel):

T_IF             "if"
  T_EXPRESSION     ...
    T_IDENTIFIER     "x"
    T_GT             ">"
    T_NUMBER         "5"
  T_CLOSURE        ...
    T_IDENTIFIER     "return"
    T_TRUE           "true"

J'ai quelques doutes:

  1. Est-ce que mon chemin est meilleur ou pire que le manière originale? Notez que mon code sera lu et compilé (traduit dans un autre langage, comme PHP), au lieu d'être interprété tout le temps.
  2. Après avoir tokenizer, que dois-je faire exactement? Je suis vraiment perdu sur cette passe!
  3. Il y a de bons tutoriels pour apprendre comment je peux le faire?

C'est ça. Au revoir!


17
2018-02-26 11:11


origine


Réponses:


En général, vous voulez séparer les fonctions du tokeniser (également appelé lexer) des autres étapes de votre compilateur ou interprète. La raison en est la modularité de base: chaque passe consomme un type de chose (par exemple, des caractères) et en produit une autre (par exemple, des jetons).

Vous avez donc converti vos personnages en jetons. Maintenant, vous voulez convertir votre liste plate de jetons en expressions imbriquées significatives, et c'est ce qui s'appelle classiquement analyse. Pour un langage de type JavaScript, vous devriez regarder dans analyse récursive de descente. Pour analyser des expressions avec des opérateurs infixes de différents niveaux de priorité, Analyse Pratt est très utile et vous pouvez vous fier à l'analyse syntaxique récursive ordinaire pour des cas particuliers.

Pour vous donner un exemple plus concret basé sur votre cas, je suppose que vous pouvez écrire deux fonctions: accept(token) et expect(token), qui teste le jeton suivant dans le flux que vous avez créé. Vous allez créer une fonction pour chaque type de déclaration ou d'expression dans la grammaire de votre langue. Voici le pseudocode Pythonish pour un statement() fonction, par exemple:

def statement():

  if accept("if"):
    x = expression()
    y = statement()
    return IfStatement(x, y)

  elif accept("return"):
    x = expression()
    return ReturnStatement(x)

  elif accept("{")
    xs = []
    while True:
      xs.append(statement())
      if not accept(";"):
        break
    expect("}")
    return Block(xs)

  else:
    error("Invalid statement!")

Cela vous donne ce que l'on appelle un arbre de syntaxe abstraite (AST) de votre programme, que vous pouvez ensuite manipuler (optimisation et analyse), sortie (compilation) ou exécution (interprétation).


17
2018-02-26 11:35



La plupart des boîtes à outils divisent le processus complet en deux séparé les pièces

  • lexer (aka. tokenizer)
  • analyseur (alias grammaire)

Le tokenizer divisera les données d'entrée en jetons. L'analyseur fonctionnera uniquement sur le "flux" de jeton et construira la structure.

Votre question semble être axée sur le tokenizer. Mais votre seconde solution mélange l’analyseur de grammaire et le tokenizer en une seule étape. Théoriquement c'est aussi possible mais pour un débutant c'est beaucoup plus facile de le faire de la même manière que la plupart des autres outils / framework: gardez les étapes séparées.

Pour votre première solution: je donnerais comme exemple votre exemple:

T_KEYWORD_IF   "if"
T_LPAREN       "("
T_IDENTIFIER   "x"
T_GT           ">"
T_LITARAL      "5"
T_RPAREN       ")"
T_KEYWORD_RET  "return"
T_KEYWORD_TRUE "true"
T_TERMINATOR   ";"

Dans la plupart des langues mots clés ne peut pas être utilisé comme nom de méthode, nom de variable, etc. Cela se reflète déjà au niveau du tokenizer (T_KEYWORD_IF, T_KEYWORD_RET, T_KEYWORD_TRUE).

Le niveau suivant prendrait ce flux et - en appliquant une grammaire formelle - construirait une structure de données (souvent appelée AST - Arbre de syntaxe abstraite) qui pourrait ressembler à ceci:

IfStatement:
    Expression:
        BinaryOperator:
            Operator:     T_GT
            LeftOperand: 
               IdentifierExpression:
                   "x"
            RightOperand:
                LiteralExpression
                    5
    IfBlock
        ReturnStatement
            ReturnExpression
                LiteralExpression
                    "true"
    ElseBlock (empty)

L'implémentation de l'analyseur à la main se fait généralement par certains frameworks. Mettre en œuvre quelque chose comme ça à la main et efficacement est généralement fait dans une université dans la plus grande partie d'un semestre. Donc, vous devriez vraiment utiliser une sorte de framework.

L'entrée d'un cadre d'analyse syntaxique est généralement une grammaire formelle dans une sorte de BNF. Votre partie "if" ressemble à ceci:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ;

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ;

BinaryExpression: LeftOperand BinaryOperator RightOperand;

....

C'est seulement pour avoir l'idée. Analyser un langage réel comme Javascript correctement n'est pas une tâche facile. Mais drôle.


16
2018-02-26 11:57



Est-ce que mon chemin est meilleur ou pire que le manière originale? Notez que mon code sera lu et compilé (traduit dans un autre langage, comme PHP), au lieu d'être interprété tout le temps.

Qu'est ce que le manière originale ? Il existe de nombreuses manières d'implémenter les langues. Je pense que le tien est bien en fait, j'ai essayé une fois de construire un langage moi-même qui traduit en C #, le pirater le langage de programmation. De nombreux compilateurs de langues traduisent dans un langage intermédiaire, c'est assez courant.

Après avoir tokenizer, que dois-je faire exactement? Je suis vraiment perdu sur cette passe!

Après tokenizing, vous devez analyser il. Utilisez un bon framework lexer / parser, tel que le Boost.Spirit, ou Coco, ou autre chose. Il y en a des centaines. Ou vous pouvez implémenter votre propre lexer, mais cela prend du temps et des ressources. Il existe de nombreuses façons d’analyser le code. analyse récursive de descente.

Ensuite, vous devez faire la génération de code. C'est la partie la plus difficile à mon avis. Il y a des outils pour ça aussi, mais vous pouvez le faire manuellement si vous voulez, j'ai essayé de le faire dans mon projet, mais c'était assez basique et bogué, il y a du code utile ici et ici.

Il y a de bons tutoriels pour apprendre comment je peux le faire?

Comme je l'ai suggéré plus tôt, utilisez outils pour le faire. Il y a beaucoup de très bons frameworks d'analyse syntaxique bien documentés. Pour plus d'informations, vous pouvez essayer de demander à certaines personnes qui connaissent ce genre de choses. @ DeadMG, à la Lounge C ++ construit un langage de programmation appelé "Wide". Vous pouvez essayer de le consulter.


1
2018-02-26 11:30