Während der Compiler-Implementierung wird eine Syntaxanalyse durchgeführt. Fortsetzung von Implementierung einer einfachen Phrasenanalyse in Java Ich möchte eine sehr primitive Syntaxanalyse in Java implementieren.
Bestätigen Sie, was Sie in der Implementierung tun möchten. Angenommen, die Zeichenfolge im Programm ist eine Operation mit vier Regeln. Bei der syntaktischen Analyse wird die Reihenfolge analysiert, in der die vier Regeln berechnet werden. Betrachten Sie die folgende Formel als Beispiel.
a = 3 + 4 * 5
Wie Sie auf einen Blick sehen können, wird es aus dem Teil in Klammern in der folgenden Reihenfolge berechnet.
(4 * 5)(3 + (4 * 5))(a = (3 + (4 * 5)))Die Syntaxanalyse verwendet diese Reihenfolge. Im eigentlichen Programm gibt es Funktionsdefinitionen und Aufrufe. Der Einfachheit halber möchten wir zunächst die vier Regeln und Zuordnungen zu Variablen analysieren können.
Ich verstehe, dass ich bestellen möchte. Überlegen Sie, wie Sie den geordneten Status in der Implementierung ausdrücken können. Beginnen wir mit einem Teil der Beispielformel "4 * 5". In Vorheriger Artikel wurde der Ausdruck in Token zerlegt. Wenn "4 * 5" in Token zerlegt wird, wird es zu "4", "" und "5". Um den Status von "4 * 5" auszudrücken, fügen Sie hier eine Feldvariable hinzu, damit Sie sehen können, dass links ein "4" -Token und rechts ein "5" -Token für das "" -Token vorhanden sind. Ich werde dir geben. Insbesondere werde ich der Implementierung der Token-Klasse im vorherigen Artikel "left" und "right" hinzufügen.
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();
}
}
}
Jetzt können Sie den Zustand von "4 * 5" ausdrücken, indem Sie dem "linken" des "" Tokens den "4" -Token und dem "rechten" den "5" -Token geben. Als nächstes wird der Zustand von "3 + (4 * 5)" ausgedrückt. Auf die gleiche Weise soll das "+" Token "links" das "3" -Token und das "rechte" das "" -Token haben. Hier hat der "*" - Token die "4" - und "5" -Token in der "vorherigen" und "rechten" in der vorherigen Erklärung. Mit anderen Worten, es ist "4 * 5". Zusammenfassend gibt es "+" Token, "3" Token in "links", "4 * 5" Token in "rechts" und der Zustand von "3 + (4 * 5)" kann ausgedrückt werden. In einem anderen Fall habe ich der Token-Klasse auch paren () hinzugefügt, das den Status in Klammern darstellt, um den Inhalt zu überprüfen.
Als nächstes betrachten wir, wie diese Bestellung durchgeführt wird.
Im Beispielausdruck werden drei Operatoren angezeigt. Es gibt drei: =, + und *.
Es sind diese Operatoren, die die Grundlage der Bestellung bilden.
In der Reihenfolge, in der ich bestätigt habe, was ich in der Syntaxanalyse tun wollte, war "" die Nummer 1, "+" die Nummer 2 und "=" die Nummer 3.
Hier wird der numerische Wert des Grads des ersten Kommens dem Operator zugewiesen, der in dieser Reihenfolge an erster Stelle steht.
Weisen Sie "60" zu "", "50" zu "+" und "10" zu "=" zu.
Basierend auf diesem Grad setzen wir Klammern an die erste Stelle mit der größten Anzahl.
Da "*" "60" ist und der Grad der größte ist, wird er zuerst in Klammern gesetzt.
= Ist 10, was der kleinste Grad ist, daher wird es am Ende in Klammern gesetzt.
Fahren Sie mit der Implementierung fort. Schauen wir uns einige der Klassen an, die Syntaxanalyse durchführen.
Der erste definiert, wie es in Bezug auf die Bedeutung des Tokens funktioniert.
"Grad" definiert den Grad der Operatorreihenfolge.
factorKinds definiert Art von Token am linken und rechten Ende eines Ausdrucks, z. B. a Token und 3 Token.
binaryKinds definiert die Art des Tokens, das in der Mitte des Ausdrucks steht, z. B. das=Token oder das+Token.
rightAssocs ist eine Bestellung von = Token, die einer besonderen Behandlung bedarf und die Definition dafür ist.
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[] { "=" });
}
Dies ist der Initialisierungsteil vor der nachfolgenden Syntaxanalyse. Sie erhalten eine Liste der vom Lexikon zerlegten Token. Analysieren Sie diese Token-Liste. Da es bequem ist, die Beendigung in der Analyse zu behandeln, fügen Sie das "eob" -Token, das die Beendigung darstellt, am Ende der Token-Liste hinzu. Setzen Sie außerdem den Index "i" auf 0, um von Anfang bis Ende auf die Token-Liste zu verweisen.
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;
}
Es ist eine Funktion, der Reihe nach auf die Token-Liste zu verweisen.
token () ist das Token, das Sie derzeit in der Token-Liste anzeigen.
next () gibt das interessierende Token zurück und rückt die interessierende Position zum nächsten vor.
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;
}
Ich werde auf die Erklärung des zu analysierenden Teils eingehen.
lead () analysiert die Token am linken und rechten Ende des Ausdrucks, z. B. a und 3, und gibt diesen Token zurück.
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.");
}
}
grad () gibt den Prioritätsgrad des Tokens zurück.
bind () weist den Operator-Token die linken und rechten Token zu und gibt die zugewiesenen Operator-Token zurück.
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.");
}
}
Schauen wir uns bind () genauer an.
bind () nimmt das Token links vom Ausdruck und das Operator-Token des Ausdrucks als Argumente.
bind () weist dem Operator-Token operator.left zuerst das Token links zu.
Das Token, das "operator.right" zugewiesen ist, weist den Rückgabewert zu, der "expression ()" aufgerufen hat.
Lassen Sie uns erklären, welche Art von Token expression () zurückgibt.
Übergeben Sie beim Aufruf von expression () die Priorität des Operator-Tokens als Argument.
Der übergebene Grad wird in expression () mit dem Grad des Operators verglichen, der in der Token-Liste folgt.
Wenn mehr oder weniger übergeben, gibt expression () das Token vor dem folgenden Operator-Token zurück.
Betrachten Sie in der folgenden Formel beispielsweise, wenn "bind ()" als Argument verwendet wird, "left" "6" und "operator" + "ist.
6 + 7 - 8
expression () wird mit einem Grad von + `` 50 aufgerufen und mit dem Grad 50 des nachfolgenden - verglichen.
Da der Grad derselbe ist, wird das Token "7" vor dem "-" zurückgegeben.
Dann kehrt es zu "bind ()" zurück und "7" wird "operator.right" zugewiesen.
Jetzt gibt bind () das``` zurück, das 6 + 7 zugeordnet ist.
Wenn leftDegree im Gradvergleich klein ist, wird dies später erklärt.
expression () verwendet die Priorität des Operators, um die Tokenzuordnung zu steuern.
Express () Aufrufelead ()und bind () wurden zuvor erläutert.
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;
}
Nehmen wir die Bewegung von expression () als Beispiel für einige Token-Listen.
Beim ersten Aufruf von "expression ()" wird "leftDegree" mit "0" aufgerufen. Wenn nur "a", wird ein Aufruf von "lead ()" a "und" left "durch" a "bestimmt. Der nächste "Grad ()" gibt den Grad von "(eob)" zurück, der hinzugefügt wurde, um das Beenden zu erleichtern, und "rightDegree" ist "0". Wenn "leftDegree" "0" und "rightDegree" "0" ist, gilt "while" nicht und "a" von "left" wird so zurückgegeben, wie es ist. Mit anderen Worten, die Token-Liste von nur "a" könnte analysiert werden.
Wenn "a = 3" ist, wird der Aufruf von "lead ()" a "und" left "durch" a "bestimmt.
Der nächste "Grad ()" gibt den Grad von "=" zurück und "rightDegree" ist "10".
Wie im vorherigen Fall gilt expression () while, wenn leftDegree mit 0aufgerufen wird. Dann ruft esbind () mit a und = als Argumenten auf. Wie in bind ()erläutert, ruftbind () expression (`` auf, um das Token auf der rechten Seite des Ausdrucks zu analysieren.
Wenn Sie "expression ()" mit "bind ()" aufrufen, können Sie bis zu "a =" analysieren. Das einzige Token, das in der Token-Liste verbleibt, ist "3".
Dies ist die gleiche Situation wie "wenn die Token-Liste nur" a "ist", wie zuvor erläutert.
Das heißt, der von bind () aufgerufene Ausdruck () gibt 3 zurück, und operator.right wird durch 3 bestimmt.
bind () return=zum Ausdruck des Aufrufers (), Das "Links" des Ausdrucks () des Aufrufers wird durch "=" bestimmt. Das "grad ()" in der Zeile nach dem "bind ()" - Aufruf gibt den Grad "0" von "(eob)" zurück, also beenden Sie "while". Nun gibt expression () left zurück, was als=festgelegt wird, und die Analyse ist abgeschlossen.
Diese Erklärung ist auch die Erklärung, wenn "leftDegree" in dem später erläuterten Gradvergleich klein ist.
Dies ist die endgültige Erklärung des zu analysierenden Teils.
block () ruftexpression ()auf, bis die Token-Liste (eob) wird, und fügt das Analyseergebnis der Liste hinzu.
Analyseergebnisse werden zu "blk" hinzugefügt, so viele wie die Anzahl der Ausdrücke in der Token-Liste.
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;
}
Unter Verwendung der obigen Implementierung die Zeichenfolge, die das Beispielprogramm ist
a = 3 + 4 * 5
Wird analysiert und auf Standardausgabe gedruckt.
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)))
}
}
Das ist alles für die Implementierung. Vielen Dank.
Die Quelle finden Sie hier.
Calc https://github.com/quwahara/Calc/tree/article-2-parser/Calc/src/main/java
Es gibt einen Folgeartikel.
** Implementieren Sie einen einfachen Interpreter in Java ** http://qiita.com/quwahara/items/30e93dfd2690913d66c0
Abschließend werde ich Ihnen eine Zusammenfassung der Parser-Klassen geben.
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