Während der Compiler-Implementierung findet eine Phrasenanalyse statt. Ich möchte eine sehr primitive Version dieser Phrasenanalyse in Java implementieren.
Ich wurde von der Computer Study Group inspiriert, die am 28. Januar 2017 stattfand. Obwohl es weit vom fortgeschrittenen Inhalt der Präsentation dieser Studiensitzung entfernt ist und ich nicht über solche Kenntnisse verfüge, Ich dachte, es würde Spaß machen, wenn es einen Artikel über die Compiler-Implementierung gäbe. Hallo, Welt!
Lassen Sie uns vor der Implementierung zunächst bestätigen, was Sie tun möchten. Das Parsen von Phrasen unterteilt eine programmierte Zeichenfolge in sogenannte Phrasen oder Token. Schauen wir uns ein Beispiel an. Es gibt eine programmierte Zeichenfolge, die das Ergebnis der Addition zu einer Variablen zuweist.
ans1 = 10 + 20
Der Zweck der Phrasenanalyse besteht darin, diese Zeichenfolge in fünf Teile zu zerlegen: "ans1", "=", "10", "+" und "20". Die zerlegte Zeichenfolge wird als Phrase oder Token bezeichnet. Darüber hinaus ist jeder dieser fünf Token eine sinnvolle Einheit. Die Bedeutung ist intuitiv, aber "ans1" ist eine Variable, "=" und "+" sind Operatoren und "10" und "20" sind Zahlen. Es ist auch der Zweck der Phrasenanalyse, Token eine solche Bedeutung zu geben. In der Implementierung ist "Zeichenkette ist" ans1 "und Bedeutung ist variabel", "Zeichenkette ist" = "und Bedeutung ist Operator" usw. Es ist bequemer, die Zeichenkette und die Bedeutung zusammenzufügen. Daher werden in der Implementierung die Zeichenfolge und die Bedeutung zu einem Token-Objekt kombiniert. Um zusammenzufassen, was ich mit der Phrasenanalyse noch einmal machen möchte: "Ich möchte die programmierte Zeichenfolge in eine Zeichenfolge und ein Token zerlegen, die die Bedeutung darstellen."
Jetzt, wo ich weiß, was ich tun möchte, denke ich darüber nach, wie ich es tun soll. Zum Zerlegen beschränken Sie den Token und verwenden ihn. Die Einschränkungen sind wie folgt.
Berücksichtigen Sie diese Einschränkung für Variablennamen, Operatoren und Zahlen. Bestimmen Sie die Einschränkung für das erste Zeichen.
Es zeigt auch die Einschränkung, dass das erste Zeichen keine Duplizierung enthält.
Verwenden wir diese Einschränkung, um sie in Token aufzuteilen. Schauen wir uns noch einmal das vorherige Beispiel an.
ans1 = 10 + 20
Verfolgen Sie die Zeichenfolge im Beispielprogramm zeichenweise in der Reihenfolge von links.
Verfolgen Sie in der Reihenfolge von "a" → "n" → "s" → "1" ... bis zur letzten "0".
Wenn Sie hier das erste "a" verfolgen, ist "a" ein Alphabet
Aufgrund von Einschränkungen wird "a" als erstes Zeichen des Variablennamens bestimmt.
Da der Variablenname festgelegt wurde, wird das folgende n → s → 1 ebenfalls in der Reihenfolge als Zeichenfolge von Variablennamenzeichenfolgen verfolgt.
Das Zeichen nach "1" wird nicht Teil des Variablennamens, daher kann es als Zeichenfolge, die dem Variablennamen entspricht, in Token zerlegt werden.
Ich werde weiter verfolgen.
Das Leerzeichen vor = bezieht sich nicht auf ein Token. Überspringen Sie es einfach.
Und ich treffe =. Dies wird auch als Operator aus der Einschränkung bestimmt, und das Operatortoken kann zerlegt werden.
Um zusammenzufassen, wie zerlegt werden soll, erstellen Sie eine Token-Einschränkung, verfolgen Sie die Zeichenfolge im Programm und zerlegen Sie sie in Token mit der Bedeutung, die die Einschränkung des ersten Zeichens bis zum Ende erfüllt.
Fahren Sie mit der Implementierung fort.
Erstens ist die Klasse, die das Token darstellt.
Die Klasse enthält zwei Feldvariablen: eine Art, die die Bedeutung darstellt, und einen Wert, der die Zeichenfolge enthält.
Es ist eine Klasse, die eine Phrasenanalyse durchführt und die Programmzeichenfolge in dieses Token zerlegt.
Ich habe toString () implementiert, um den Inhalt zu überprüfen.
Token.java
public class Token {
public String kind;
public String value;
@Override
public String toString() {
return kind + " \"" + value + "\"";
}
}
Schauen wir uns eine Klasse an, die eine Phrasenanalyse durchführt. Werfen wir einen Teilblick. Dies ist der Beginn des Prozesses. Es gibt ein Textfeld, das die programmatische Zeichenfolge enthält. Und es gibt ein i-Feld, das als Index für die Verfolgung dieser Zeichenfolge dient. Initialisieren Sie sie mit der init-Methode.
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;
}
Dies ist der Teil des Mechanismus, der die Zeichenfolge verfolgt.
isEOT bedeutet, dass keine Zeichen mehr zu verfolgen sind.
c () ist eine programmierte Zeichenfolge, bei der es sich um das Zeichen handelt, das sich beim Verfolgen am interessierenden Punkt befindet.
next () gibt den interessierenden Charakter zurück und rückt die interessierende Position zur nächsten vor.
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;
}
Ich werde in der Reihenfolge den Teil erklären, der den Mechanismus zum Verfolgen der Zeichenkette verwendet.
skipSpace () überspringt Zeichen, die nicht mit Token zusammenhängen, z. B. Leerzeichen.
Unabhängig davon, wie viele Leerzeichen sich am Anfang oder Ende der Programmzeichenfolge oder in der Mitte des Ausdrucks befinden, ist dies in Ordnung.
Lexer.java
private void skipSpace() throws Exception {
while (!isEOT() && Character.isWhitespace(c())) {
next();
}
}
Dies ist der Teil, der die Einschränkung des ersten Zeichens bestimmt. In der Reihenfolge wird festgelegt, ob es sich um das erste Zeichen des Operators, der Nummer und des Variablennamens handelt.
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);
}
Dies ist der Teil, der in Token zerfällt. In der Reihenfolge zerlegt es sich in Token von Operatoren, Zahlen und Variablennamen. Die interessierende Position "i" in der programmierten Zeichenfolge ist "next ()" Wenn Sie es in Token zerlegen können, können Sie wahrscheinlich fortfahren.
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;
}
Verwenden Sie den Teil, der die Einschränkung des ersten Zeichens oben beurteilt, und den Teil, der sich in Token zerlegt. Gibt den ersten Token zurück, der von der interessierenden Position gefunden wurde. Zuerst wird der Platz übersprungen, Das Zeichen an der interessierenden Position bestimmt den Token und zerlegt ihn in Token.
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");
}
}
Verwenden Sie das obige nextToken (), um alle programmatischen Zeichenfolgen in Token zu zerlegen.
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;
}
Unter Verwendung der obigen Implementierung die Zeichenfolge, die das Beispielprogramm ist
ans1 = 10 + 20
Wird lexikalisch analysiert und auf Standardausgabe gedruckt.
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"
}
}
Das ist alles für die Implementierung. Vielen Dank.
Die Quelle finden Sie hier.
Calc https://github.com/quwahara/Calc/tree/lexer/Calc/src/main/java
Es gibt einen Folgeartikel.
** Implementieren Sie eine einfache Syntaxanalyse in Java ** http://qiita.com/quwahara/items/9bf468ff4286b28d2a24
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