Il y a une analyse de phrase dans le processus d'implémentation du compilateur. Je voudrais implémenter une version très primitive de cette analyse de phrase en Java.
J'ai été inspiré par le Computer Study Group qui s'est tenu le 28 janvier 2017. Bien que ce soit loin du contenu avancé de la présentation de cette session d'étude et que je n'ai pas de telles connaissances, J'ai pensé que ce serait amusant s'il y avait un article sur l'implémentation du compilateur Hello, World!.
Avant de mettre en œuvre, confirmons d'abord ce que vous voulez faire. L'analyse de phrase décompose une chaîne programmée en ce qu'on appelle une phrase ou un jeton. Regardons un exemple. Il existe une chaîne programmée qui affecte le résultat de l'ajout à une variable.
ans1 = 10 + 20
Le but de l'analyse des phrases est de décomposer cette chaîne de caractères en cinq parties: «an1», «=», «10», «+» et «20».
La chaîne décomposée est appelée une phrase ou un jeton.
De plus, chacun de ces cinq jetons est une unité significative.
La signification est intuitive, mais «an1» est une variable, «=» et «+» sont des opérateurs, et «10» et «20» sont des nombres.
C'est aussi le but de l'analyse des phrases de donner une telle signification aux jetons.
Dans l'implémentation, "la chaîne de caractères est ʻans1 et la signification est variable", "la chaîne de caractères est = ʻet la signification est opérateur", etc.
Il est plus pratique de mettre ensemble la chaîne de caractères et la signification.
Par conséquent, dans l'implémentation, la chaîne de caractères et la signification sont combinées dans un objet jeton.
Pour résumer à nouveau ce que je veux faire avec l'analyse de phrases,
"Je veux décomposer la chaîne de caractères programmée en une chaîne de caractères et un jeton qui représente la signification."
Maintenant que je sais ce que je veux faire, je réfléchis à comment le faire. Pour démonter, contraignez le jeton et utilisez-le. Les restrictions sont les suivantes.
Considérez cette contrainte sur les noms de variables, les opérateurs et les nombres. Déterminez la contrainte pour le premier caractère.
Il montre également la restriction qu'il n'y a pas de duplication dans le premier caractère.
Utilisons cette contrainte pour la décomposer en jetons. Regardons à nouveau l'exemple précédent.
ans1 = 10 + 20
Tracez la chaîne de caractères dans l'exemple de programme caractère par caractère dans l'ordre à partir de la gauche.
Tracez dans l'ordre «a» → «n» → «s» → «1» ... jusqu'au dernier «0».
Lorsque vous tracez le premier ʻa ici, ʻa est un alphabet, donc
En raison de contraintes, «a» est déterminé comme étant le premier caractère du nom de la variable.
Puisque le nom de la variable a été défini, le n → s → 1 suivant est également tracé dans l'ordre comme une chaîne de chaînes de nom de variable.
Le caractère après «1» ne fait pas partie du nom de la variable, il peut donc être décomposé en jetons sous la forme d'une chaîne de caractères correspondant au nom de la variable.
Je vais continuer à tracer.
L'espace avant = n'est lié à aucun jeton, alors sautez-le simplement.
Et je rencontre =. Ceci est également déterminé comme un opérateur à partir de la contrainte, et le jeton d'opérateur peut être décomposé.
Pour résumer comment décomposer, créez une contrainte de jeton, tracez la chaîne de caractères dans le programme et décomposez-la en jetons avec la signification qui répond à la contrainte du premier caractère pour la fin.
Passez à la mise en œuvre.
La première est la classe qui représente le jeton.
Il existe deux variables de champ dans la classe: un kind qui représente la signification et une valeur qui contient la chaîne.
C'est une classe qui effectue une analyse de phrase et décompose la chaîne de caractères du programme en ce jeton.
Implémentation de toString () pour vérifier le contenu.
Token.java
public class Token {
public String kind;
public String value;
@Override
public String toString() {
return kind + " \"" + value + "\"";
}
}
Regardons une classe qui effectue une analyse de phrase. Jetons un coup d'œil partiel. C'est le début du processus. Un champ de texte contient la chaîne de programmation. Et il y a un i-field qui sert d'index pour tracer cette chaîne. Initialisez-les avec la méthode init.
Lexer.java
import java.util.ArrayList;
import java.util.List;
public class Lexer {
private String text;
private int i;
public Lexer init(String text) {
i = 0;
this.text = text;
return this;
}
C'est la partie du mécanisme qui trace la chaîne de caractères.
«Est EOT» signifie qu'il n'y a plus de caractères à tracer.
c () est une chaîne programmatique, qui est le caractère au point d'intérêt lors du traçage.
next () renvoie le caractère d'intérêt et avance la position d'intérêt à la suivante.
Lexer.java
private boolean isEOT() {
return text.length() <= i;
}
private char c() throws Exception {
if (isEOT()) {
throw new Exception("No more character");
}
return text.charAt(i);
}
private char next() throws Exception {
char c = c();
++i;
return c;
}
Je vais expliquer dans l'ordre la partie qui utilise le mécanisme de traçage de la chaîne de caractères.
skipSpace () saute les caractères qui ne sont pas liés aux jetons, tels que les espaces.
Peu importe le nombre d'espaces au début ou à la fin de la chaîne du programme ou au milieu de l'expression, c'est OK.
Lexer.java
private void skipSpace() throws Exception {
while (!isEOT() && Character.isWhitespace(c())) {
next();
}
}
C'est la partie qui détermine la contrainte du premier caractère. Dans l'ordre, il est déterminé s'il s'agit du premier caractère de l'opérateur, du numéro et du nom de la variable.
Lexer.java
private boolean isSignStart(char c) {
return c == '=' || c == '+' || c == '-' || c == '*' || c == '/';
}
private boolean isDigitStart(char c) throws Exception {
return Character.isDigit(c);
}
private boolean isVariableStart(char c) throws Exception {
return Character.isAlphabetic(c);
}
C'est la partie qui se décompose en jetons.
Dans l'ordre, il se décompose en jetons d'opérateurs, de nombres et de noms de variables.
La position d'intérêt ʻi dans la chaîne programmée est par next () `
Si vous pouvez le décomposer en jetons, vous pouvez probablement continuer.
Lexer.java
private Token sign() throws Exception {
Token t = new Token();
t.kind = "sign";
t.value = Character.toString(next());
return t;
}
private Token digit() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && Character.isDigit(c())) {
b.append(next());
}
Token t = new Token();
t.kind = "digit";
t.value = b.toString();
return t;
}
private Token variable() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && (Character.isAlphabetic(c()) || Character.isDigit(c()))) {
b.append(next());
}
Token t = new Token();
t.kind = "variable";
t.value = b.toString();
return t;
}
En utilisant la partie qui juge la contrainte du premier caractère ci-dessus et la partie qui se décompose en jetons, Renvoie le premier jeton trouvé à partir de la position d'intérêt. D'abord l'espace est sauté, Le personnage à la position d'intérêt détermine le jeton et le décompose en jetons.
Lexer.java
public Token nextToken() throws Exception {
skipSpace();
if (isEOT()) {
return null;
} else if (isSignStart(c())) {
return sign();
} else if (isDigitStart(c())) {
return digit();
} else if (isVariableStart(c())) {
return variable();
} else {
throw new Exception("Not a character for tokens");
}
}
Utilisez le nextToken () ci-dessus pour décomposer toutes les chaînes de programmation en jetons.
Lexer.java
public List<Token> tokenize() throws Exception {
List<Token> tokens = new ArrayList<>();
Token t = nextToken();
while (t != null) {
tokens.add(t);
t = nextToken();
}
return tokens;
}
En utilisant l'implémentation ci-dessus, la chaîne de caractères qui est l'exemple de programme
ans1 = 10 + 20
Est analysé lexicalement et imprimé sur la sortie standard.
Lexer.java
public static void main(String[] args) throws Exception {
String text = " ans1 = 10 + 20 ";
List<Token> tokens = new Lexer().init(text).tokenize();
for (Token token : tokens) {
System.out.println(token.toString());
}
// --> variable "ans1"
// --> sign "="
// --> digit "10"
// --> sign "+"
// --> digit "20"
}
}
C'est tout pour la mise en œuvre. Merci beaucoup.
La source est disponible ici.
Calc https://github.com/quwahara/Calc/tree/lexer/Calc/src/main/java
Il y a un article de suite.
** Implémenter une analyse syntaxique simple en Java ** http://qiita.com/quwahara/items/9bf468ff4286b28d2a24
Juste au cas où, je vais vous donner un résumé de «class Lexer».
Lexer.java
import java.util.ArrayList;
import java.util.List;
public class Lexer {
private String text;
private int i;
public Lexer init(String text) {
i = 0;
this.text = text;
return this;
}
private boolean isEOT() {
return text.length() <= i;
}
private char c() throws Exception {
if (isEOT()) {
throw new Exception("No more character");
}
return text.charAt(i);
}
private char next() throws Exception {
char c = c();
++i;
return c;
}
private void skipSpace() throws Exception {
while (!isEOT() && Character.isWhitespace(c())) {
next();
}
}
private boolean isSignStart(char c) {
return c == '=' || c == '+' || c == '-' || c == '*' || c == '/';
}
private boolean isDigitStart(char c) throws Exception {
return Character.isDigit(c);
}
private boolean isVariableStart(char c) throws Exception {
return Character.isAlphabetic(c);
}
private Token sign() throws Exception {
Token t = new Token();
t.kind = "sign";
t.value = Character.toString(next());
return t;
}
private Token digit() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && Character.isDigit(c())) {
b.append(next());
}
Token t = new Token();
t.kind = "digit";
t.value = b.toString();
return t;
}
private Token variable() throws Exception {
StringBuilder b = new StringBuilder();
b.append(next());
while (!isEOT() && (Character.isAlphabetic(c()) || Character.isDigit(c()))) {
b.append(next());
}
Token t = new Token();
t.kind = "variable";
t.value = b.toString();
return t;
}
public Token nextToken() throws Exception {
skipSpace();
if (isEOT()) {
return null;
} else if (isSignStart(c())) {
return sign();
} else if (isDigitStart(c())) {
return digit();
} else if (isVariableStart(c())) {
return variable();
} else {
throw new Exception("Not a character for tokens");
}
}
public List<Token> tokenize() throws Exception {
List<Token> tokens = new ArrayList<>();
Token t = nextToken();
while (t != null) {
tokens.add(t);
t = nextToken();
}
return tokens;
}
public static void main(String[] args) throws Exception {
String text = " ans1 = 10 + 20 ";
List<Token> tokens = new Lexer().init(text).tokenize();
for (Token token : tokens) {
System.out.println(token.toString());
}
// --> variable ,"ans1"
// --> sign "="
// --> digit "10"
// --> sign "+"
// --> digit "20"
}
}
Recommended Posts