2 Implémentez une analyse syntaxique simple en Java

introduction

Il y a une analyse syntaxique dans le processus d'implémentation du compilateur. Suite de Implémentation d'une analyse de phrase simple en Java Je voudrais implémenter une analyse syntaxique très primitive en Java.

Ce que vous voulez faire avec l'analyse syntaxique

Confirmez ce que vous voulez faire dans l'implémentation. Supposons que la chaîne de caractères du programme soit une opération à quatre règles. Dans l'analyse syntaxique, l'ordre dans lequel les quatre règles sont calculées est analysé. Considérez la formule suivante comme exemple.

a = 3 + 4 * 5

Comme vous pouvez le voir en un coup d'œil, il est calculé à partir de la pièce entre parenthèses dans l'ordre ci-dessous.

  1. (4 * 5)
  2. (3 + (4 * 5))
  3. (a = (3 + (4 * 5)))

L'analyse de syntaxe utilise cet ordre. Dans le programme actuel, il existe des définitions de fonctions et des appels. Dans un souci de simplicité, nous cherchons d'abord à pouvoir analyser les quatre règles et les affectations aux variables.

Comment exprimer la commande

Je comprends que je souhaite passer commande. Réfléchissez à la manière d'exprimer l'état ordonné dans l'implémentation. Commençons par une partie de l'exemple de formule, «4 * 5». Article précédent a décomposé l'expression en jetons. Lorsque «4 * 5» est décomposé en jetons, il devient «4», «» et «5». Ici, afin d'exprimer l'état de «4 * 5», ajoutez une variable de champ afin que vous puissiez voir que le jeton «» a un jeton «4» à gauche et un jeton «5» à droite. Je vais vous donner. Plus précisément, j'ajouterai «left» et «right» à l'implémentation de la classe Token dans l'article précédent.

Token.java



public class Token {

    public String kind;
    public String value;
    public Token left;
    public Token right;

    @Override
    public String toString() {
        return kind + " \"" + value + "\"";
    }

    public String paren() {
        if (left == null && right == null) {
            return value;
        } else {
            StringBuilder b = new StringBuilder();
            b.append("(");
            if (left != null) {
                b.append(left.paren()).append(" ");
            }
            b.append(value);
            if (right != null) {
                b.append(" ").append(right.paren());
            }
            b.append(")");
            return b.toString();
        }
    }

}

Vous pouvez maintenant exprimer l'état de «4 * 5» en donnant à la «gauche» du jeton «*» le jeton «4» et à la «droite» le jeton «5». Ensuite, l'état de «3 + (4 * 5)» est exprimé. De la même manière, laissez le jeton + gauche avoir le jeton 3et ladroite avoir le jeton `. Ici, le jeton «» a les jetons «4» et «5» à gauche et à droite dans l'explication précédente. En d'autres termes, c'est "4 * 5". En résumé, il y a des jetons «+», des jetons «3» à «gauche», des jetons «4 * 5» à «droite», et l'état de «3 + (4 * 5)» peut être exprimé. Sur une note différente, j'ai également ajouté paren (), qui représente l'état entre parenthèses, à la classe Token pour vérifier le contenu.

Comment commander

Ensuite, examinons comment effectuer cette commande. Dans l'exemple d'expression, trois opérateurs apparaissent. Il y en a trois: =, + et *. Ce sont ces opérateurs qui sont à la base de la commande. Dans l'ordre que j'ai confirmé par ce que je voulais faire dans l'analyse syntaxique, «» était le numéro 1, «+» était le numéro 2 et «=» était le numéro 3. Ici, la valeur numérique du degré de venue en premier est attribuée à l'opérateur qui vient en premier dans cet ordre. Plus précisément, attribuez «60» à «», «50» à «+» et «10» à «=». Sur la base de ce degré, nous mettrons les parenthèses en premier à partir de celui avec le plus grand nombre. Puisque «*» vaut «60» et que le degré est le plus grand, il est placé entre crochets en premier, Puisque «=» vaut «10» et que le degré est le plus petit, il sera mis entre crochets à la fin.

Essayez de mettre en œuvre en Java

Passez à la mise en œuvre. Jetons un coup d'œil à certaines des classes qui effectuent une analyse syntaxique.

Le premier définit son fonctionnement par rapport à la signification du jeton. degrés définit le degré d'ordre des opérateurs. «factorKinds» définit le «genre» de jetons aux extrémités gauche et droite d'une expression, comme «un» jeton et «3» jetons. «binaryKinds» définit le «genre» du jeton qui vient au milieu de l'expression, comme le jeton «=» ou le jeton «+». rightAssocs est un ordre à = jetons qui nécessite un traitement spécial et en est la définition.

Parser.java


public class Parser {

    private Map<String, Integer> degrees;
    private List<String> factorKinds;
    private List<String> binaryKinds;
    private List<String> rightAssocs;

    public Parser() {
        degrees = new HashMap<>();
        degrees.put("*", 60);
        degrees.put("/", 60);
        degrees.put("+", 50);
        degrees.put("-", 50);
        degrees.put("=", 10);
        factorKinds = Arrays.asList(new String[] { "digit", "variable" });
        binaryKinds = Arrays.asList(new String[] { "sign" });
        rightAssocs = Arrays.asList(new String[] { "=" });
    }

Il s'agit de la partie d'initialisation avant l'analyse syntaxique ultérieure. Vous recevrez une liste de jetons décomposés par lexique. Analysez cette liste de jetons. Puisqu'il est pratique de gérer la terminaison dans l'analyse, ajoutez le jeton «eob» qui représente la terminaison à la fin de la liste de jetons. Définissez également l'index ʻi` sur 0 pour faire référence à la liste de jetons du début à la fin.

Parser.java


    private List<Token> tokens;
    private int i;
    
    public Parser init(List<Token> tokens) {
        i = 0;
        this.tokens = new ArrayList<Token>(tokens);
        Token eob = new Token();
        eob.kind = "eob";
        eob.value = "(eob)";
        this.tokens.add(eob);
        return this;
    }

C'est une fonction de se référer à la liste de jetons dans l'ordre. token () est le token que vous regardez actuellement dans la liste de token. next () retourne le jeton d'intérêt et avance la position d'intérêt à la suivante.

Parser.java


    private Token token() throws Exception {
        if (tokens.size() <= i) {
            throw new Exception("No more token");
        }
        return tokens.get(i);
    }

    private Token next() throws Exception {
        Token t = token();
        ++i;
        return t;
    }

Je vais entrer dans l'explication de la partie à analyser. lead () analyse les jetons aux extrémités gauche et droite de l'expression, tels que ʻa et 3`, et renvoie ce jeton.

Parser.java


    private Token lead(Token token) throws Exception {
        if (factorKinds.contains(token.kind)) {
            return token;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

degree () renvoie le degré de priorité du jeton. bind () attribue les jetons gauche et droit aux jetons d'opérateur et retourne les jetons d'opérateur assignés.

Parser.java


    private int degree(Token t) {
        if (degrees.containsKey(t.value)) {
            return degrees.get(t.value);
        } else {
            return 0;
        }
    }

    private Token bind(Token left, Token operator) throws Exception {
        if (binaryKinds.contains(operator.kind)) {
            operator.left = left;
            int leftDegree = degree(operator);
            if (rightAssocs.contains(operator.value)) {
                leftDegree -= 1;
            }
            operator.right = expression(leftDegree);
            return operator;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

Regardons de plus près bind (). bind () prend le jeton à gauche de l'expression et le jeton opérateur de l'expression comme arguments. bind () attribue d'abord le jeton à gauche au jeton d'opérateur ʻoperator.left. Le jeton attribué à ʻoperator.right assigne la valeur de retour qui a appelé ʻexpression () . Expliquons quel type de jeton ʻexpression () retourne. Lorsque vous appelez ʻexpression () , passez le degré de priorité du jeton d'opérateur comme argument. Le degré passé est comparé dans ʻexpression () au degré de l'opérateur qui suit dans la liste de jetons. Si plus ou moins passé, ʻexpression () retourne le jeton avant le jeton d'opérateur suivant. Par exemple, dans la formule ci-dessous, considérez quand bind ()est utilisé comme argument,left est 6 et ʻoperator est +.

6 + 7 - 8

«L'expression ()» est appelée avec un degré de «+» de «50» et est comparée au degré suivant de «-» 50 ». Puisque le degré est le même, il renvoie le jeton «7» qui précède le «-». Ensuite, il retourne à bind () et 7 est assigné à ʻoperator.right. Maintenant bind () renvoie le + ʻassocié à 6 + 7. Si «leftDegree» est petit dans la comparaison des degrés, cela sera expliqué plus tard.

ʻExpression () utilise le degré de priorité de l'opérateur pour contrôler l'association des jetons. ʻExpress () appellelead ()etbind ()comme décrit ci-dessus.

Parser.java


    public Token expression(int leftDegree) throws Exception {
        Token left = lead(next());
        int rightDegree = degree(token());
        while (leftDegree < rightDegree) {
            Token operator = next();
            left = bind(left, operator);
            rightDegree = degree(token());
        }
        return left;
    }

Prenons le mouvement de ʻexpression () `comme exemple de quelques listes de jetons.

Si la liste de jetons est uniquement ʻa`

Le premier appel à ʻexpression () appelle leftDegree avec 0. Pour ʻa seulement, un appel àlead ()retourne ʻa et left est déterminé par ʻa. Le prochain degree () retourne le degré de (eob) ʻadded pour faciliter la terminaison, et rightDegreeest0`. Si «leftDegree» est «0» et «rightDegree» est «0», «while» ne tient pas, et «left» «a» est renvoyé tel quel. En d'autres termes, nous avons pu analyser une liste de jetons contenant uniquement «a».

Si la liste de jetons est ʻa = 3`

Si ʻa = 3, l'appel à lead () retourne ʻa et left est déterminé par ʻa. Le prochain degree () retourne le degré de = ʻet rightDegree est 10. Comme dans le cas précédent, ʻexpression () tient while lorsque leftDegree est appelé avec 0. Ensuite, il appelle bind () avec ʻa et = comme arguments. Comme expliqué dans bind (), bind () appelle ʻexpression () pour analyser le jeton sur le côté droit de l'expression. Lorsque vous appelez ʻexpression () avecbind (), vous pouvez analyser jusqu'à ʻa =, donc le seul jeton qui reste dans la liste de jetons est 3. C'est la même situation que "lorsque la liste de jetons est seulement ʻa" expliquée plus tôt. Autrement dit, ʻexpression () appelée par bind () retourne 3 et ʻoperator.right est déterminé par 3. bind () returns=à l''expression ()de l'appelant, La «gauche» de «l'expression ()» de l'appelant est déterminée par «=». Ledegree ()sur la ligne suivant l'appelbind ()retourne le degré0 of (eob), donc exit while. Avec cela, ʻexpression () retourne le gauche déterminé comme étant=, et l'analyse est terminée. Cette explication est également l'explication lorsque «leftDegree» est petit dans la comparaison de degrés qui a été expliquée plus tard.

C'est la dernière explication de la pièce à analyser. block () appelle ʻexpression () jusqu'à ce que la liste de jetons devienne (eob) `et ajoute le résultat de l'analyse à la liste. Les résultats de l'analyse sont ajoutés à «blk» autant que le nombre d'expressions dans la liste de jetons.

Parser.java


    public List<Token> block() throws Exception {
        List<Token> blk = new ArrayList<Token>();
        while (!token().kind.equals("eob")) {
            blk.add(expression(0));
        }
        return blk;
    }

En utilisant l'implémentation ci-dessus, la chaîne de caractères qui est l'exemple de programme

a = 3 + 4 * 5

Est analysé et imprimé sur la sortie standard.

Parser.java


    public static void main(String[] args) throws Exception {
        String text = "a = 3 + 4 * 5";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        for (Token ast : blk) {
            System.out.println(ast.paren());
        }
        // --> (a = (3 + (4 * 5)))
    }
}

C'est tout pour la mise en œuvre. Merci beaucoup.

en conclusion

La source est disponible ici.

Calc https://github.com/quwahara/Calc/tree/article-2-parser/Calc/src/main/java

Il y a un article de suite.

** Implémenter un interpréteur simple en Java ** http://qiita.com/quwahara/items/30e93dfd2690913d66c0

Enfin, je vais vous donner un résumé des classes Parser.

Parser.java



import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Parser {

    private Map<String, Integer> degrees;
    private List<String> factorKinds;
    private List<String> binaryKinds;
    private List<String> rightAssocs;

    public Parser() {
        degrees = new HashMap<>();
        degrees.put("*", 60);
        degrees.put("/", 60);
        degrees.put("+", 50);
        degrees.put("-", 50);
        degrees.put("=", 10);
        factorKinds = Arrays.asList(new String[] { "digit", "variable" });
        binaryKinds = Arrays.asList(new String[] { "sign" });
        rightAssocs = Arrays.asList(new String[] { "=" });
    }

    private List<Token> tokens;
    private int i;
    
    public Parser init(List<Token> tokens) {
        i = 0;
        this.tokens = new ArrayList<Token>(tokens);
        Token eob = new Token();
        eob.kind = "eob";
        eob.value = "(eob)";
        this.tokens.add(eob);
        return this;
    }

    private Token token() throws Exception {
        if (tokens.size() <= i) {
            throw new Exception("No more token");
        }
        return tokens.get(i);
    }

    private Token next() throws Exception {
        Token t = token();
        ++i;
        return t;
    }

    private Token lead(Token token) throws Exception {
        if (factorKinds.contains(token.kind)) {
            return token;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

    private int degree(Token t) {
        if (degrees.containsKey(t.value)) {
            return degrees.get(t.value);
        } else {
            return 0;
        }
    }

    private Token bind(Token left, Token operator) throws Exception {
        if (binaryKinds.contains(operator.kind)) {
            operator.left = left;
            int leftDegree = degree(operator);
            if (rightAssocs.contains(operator.value)) {
                leftDegree -= 1;
            }
            operator.right = expression(leftDegree);
            return operator;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

    public Token expression(int leftDegree) throws Exception {
        Token left = lead(next());
        int rightDegree = degree(token());
        while (leftDegree < rightDegree) {
            Token operator = next();
            left = bind(left, operator);
            rightDegree = degree(token());
        }
        return left;
    }

    public List<Token> block() throws Exception {
        List<Token> blk = new ArrayList<Token>();
        while (!token().kind.equals("eob")) {
            blk.add(expression(0));
        }
        return blk;
    }

    public static void main(String[] args) throws Exception {
        String text = "a = 3 + 4 * 5";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        for (Token ast : blk) {
            System.out.println(ast.paren());
        }
        // --> (a = (3 + (4 * 5)))
    }
}

Recommended Posts

2 Implémentez une analyse syntaxique simple en Java
1 Implémentez une analyse de phrase simple en Java
Simple htmlspecialchars en Java
Implémentation de l'authentification en deux étapes en Java
Implémenter l'authentification de base en Java
Implémenter l'envoi d'e-mails en Java
Implémenter un tri rapide de type fonction en Java
Implémentez rm -rf en Java.
Implémenter la signature XML en Java
Implémenter un test piloté par table dans Java 14
Réception d'entrée très simple en Java
Implémenter une fonction de connexion simple dans Rails
Implémenter reCAPTCHA v3 dans Java / Spring
Implémenter la fonction PHP implode en Java
Un exemple simple de rappels en Java
Analyser l'analyse syntaxique de l'API COTOHA en Java
Essayez d'implémenter Yuma en Java
Comment implémenter le filtre de Kalman par Java
Implémenter l'autorisation API Gateway Lambda dans Java Lambda
Partition en Java
Essayez d'implémenter l'ajout n-aire en Java
Changements dans Java 11
Janken à Java
Implémenter quelque chose comme une pile en Java
Taux circonférentiel à Java
FizzBuzz en Java
Essayez d'utiliser l'analyse syntaxique de l'API COTOHA en Java
Lire JSON en Java
Implémentation de l'interpréteur par Java
Faites un blackjack avec Java
Application Janken en Java
Programmation par contraintes en Java
Mettez java8 dans centos7
NVL-ish guy en Java
Joindre des tableaux en Java
"Hello World" en Java
Commentaires dans la source Java
Fonctions Azure en Java
Formater XML en Java
Implémentation Boyer-Moore en Java
Hello World en Java
Utiliser OpenCV avec Java
Détermination de type en Java
Divers threads en java
Implémentation du tri de tas (en java)
API Zabbix en Java
Art ASCII à Java
Comparer des listes en Java
POST JSON en Java
Exprimer l'échec en Java
Implémenter CustomView dans le code
Créer JSON en Java
Manipulation de la date dans Java 8
Nouveautés de Java 8
Utiliser PreparedStatement en Java
Nouveautés de Java 9,10,11
Exécution parallèle en Java
Markdown implémenté dans Rails