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.
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.
(4 * 5)(3 + (4 * 5))(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.
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.
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.
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.
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 ʻ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.
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