analyse syntaxique d'expression: comment tokenizer

Question

Je cherche à tokenizer Java / expressions JavaScript comme dans le code Javascript. Mon entrée sera une chaîne contenant l'expression, et la sortie doit être un tableau de jetons.

Quelle est la meilleure pratique pour faire quelque chose comme ça? Ai-je besoin d'itérer la chaîne ou est-il une expression régulière qui le fera pour moi?

Je en ai besoin pour être en mesure de soutenir:

• chaîne et nombre littéraux (simples et doubles cités, en citant échapper)
• Opérateurs mathématiques de base et booléens et comparateurs (+, -, *, /, et, non, <,>, etc.)
• notation de point et le support pour l'accès aux objets de récursivité (foo.bar, foo [ 'bar'], foo [2] [prop])
• Parenthèses avec imbrication
• opérateur ternaires (foo bar: 'baz')
• Les appels de fonction (foo (bar))

Je veux en particulier pour éviter d'utiliser eval() ou quelque chose du genre pour des raisons de sécurité. Par ailleurs, eval() ne tokenizer l'expression pour moi de toute façon.

Answer 1

Apprendre à écrire un analyseur récursif-descente. Une fois que vous comprenez les concepts, vous pouvez le faire dans toutes les langues: Java, C ++, JavaScript, SystemVerilog, ... peu importe. Si vous pouvez gérer les chaînes, vous pouvez analyser.

analyse syntaxique récursif-descente est une technique de base pour l'analyse qui peut facilement être codé à la main. Ceci est utile si vous n'avez pas accès à (ou ne voulez pas tromper avec) un générateur d'analyseur.

Dans un analyseur récursif-descente, toutes les règles de grammaire est traduit à une procédure qui analyse la règle. Si vous avez besoin de se référer à d'autres règles, alors vous le faites en les appelant - ils sont juste des procédures

.

Un exemple simple: expressions comportant des nombres, l'addition et la multiplication (ce qui illustre la priorité de l'opérateur). Tout d'abord, la grammaire:

expr ::= term
         | expr "+" term

term ::= factor
         | term "*" factor

factor ::= /[0-9/+ (I'm using a regexp here)

Maintenant, pour écrire l'analyseur (qui comprend le lexer, vous pouvez jeter les deux descente récursive ensemble). Je ne l'ai jamais utilisé JavaScript, donc nous allons essayer cela dans (mon rouillées) Java:

class Parser {
  string str;
  int idx; // index into string

  Node parseExpr() throws ParseException
  {
    Node op1 = parseTerm();
    Node op2;

    while (idx < str.size() && str.charAt(idx) == '+') {
      idx++;
      op2 = parseTerm();
      op1 = new AddNode(op1, op2);
    }
    return op1;
  }

  Node parseTerm() throws ParseException
  {
    Node op1 = parseFactor();
    Node op2;

    while (idx < str.size() && str.charAt(idx) == '*') {
      idx++;
      op2 = parseFactor();
      op1 = new MultNode(op1, op2);
    }
    return op1;
  }

  Node parseFactor() throws ParseException
  {
    StringBuffer sb = new StringBuffer();
    int old_idx = idx;

    while (idx < str.size() && str.charAt(idx) >= '0' && str.charAt(idx) <= '9') {
      sb.append(str.charAt(idx));
      idx++;
    }
    if (idx == old_idx) {
      throw new ParseException();
    }
    return new NumberNode(sb.toString());
  }
}

Vous pouvez voir comment chaque règle de grammaire se traduit par une procédure. Je n'ai pas testé; c'est un exercice pour le lecteur.

Vous devez également vous soucier de la détection d'erreur. Un compilateur monde réel a besoin de récupérer d'erreurs parse pour tenter d'analyser le reste de son entrée. Un analyseur d'expression d'une ligne comme celui-ci n'a pas besoin d'essayer la récupération du tout, mais il n'a pas besoin de déterminer qu'une erreur d'analyse syntaxique existe et le signaler. La meilleure façon de faire cela si votre langue permet est de lancer une exception, et l'attraper au point d'entrée à l'analyseur. Je n'ai pas détecté toutes les erreurs possibles de syntaxe dans mon exemple ci-dessus.

Pour plus d'informations, consultez la rubrique « analyseur LL » et « analyseur de descente récursive » dans Wikipedia. Comme je l'ai dit au début, si vous pouvez comprendre les concepts (et ils sont simples par rapport aux concepts sous-jacents LALR (1) la fermeture de configuration de la machine d'état), vous êtes autorisé à écrire un analyseur pour les petites tâches dans toutes les langues, tant que vous avez une certaine capacité de chaîne rudimentaire. Profitez de la puissance.

Answer 2

Pour lexers simples où la vitesse est pas critique, je l'habitude d'écrire une expression régulière pour chaque type de jeton et tenter à plusieurs reprises pour correspondre chacun à son tour, avec le début de l'entrée. (Assurez-vous de ne pas le vent avec un algorithme O (n ^ 2)!) Un outil comme lex donnera un lexer plus efficace car elle combine les expressions rationnelles dans une machine d'état.

Answer 3

Vous devez implémenter un analyseur lexical. Vous pouvez utiliser js / cc pour le faire ou vous pouvez mettre en œuvre un automate fini par vous-même.

Depuis, officiellement, la langue que vous manipulerons est régulier, vous pouvez utiliser une expression régulière. Mais je ne recommed pour vous.

Althougth Je ne l'ai jamais utilisé js / cc, je voudrais essayer avec elle d'abord, et si cela ne fonctionne pas, je voudrais essayer de construire un analyseur lexical par moi-même.