Verwenden Sie Javascript, um eine lexikalische Analyse von vier arithmetischen Compilern zu schreiben

In unserem Juniorjahr gibt es einen Kurs namens „Compilation Principles“, in dem wir aufgefordert werden, selbst einen einfachen Compiler zu schreiben. Natürlich verwende ich js Ich werde die Gnade nicht sehr gebrauchen. Das hat nichts mit der Sprache zu tun, ich verwende nur gerne js und es werden nicht viele js-Funktionen darin verwendet.

Außerdem ist der Code etwas schlecht, also beschweren Sie sich nicht.

Lassen Sie mich zunächst meinen gesamten Prozess erläutern

1. Der erste Schritt ist die lexikalische Analyse: Sie müssen einen regulären Ausdruck schreiben und dann die Wörter und Zahlen darin einfügen. Schneiden Sie sie alle aus.

2. Grammatikregeln erstellen Hier wähle ich LL(1)-Grammatik. Entwerfen Sie hier Ihre eigene Grammatik.

3. Zwischencode erstellen. Hier habe ich einen Syntaxbaum verwendet.

4. Schreiben Sie ein Konvertierungsprogramm und welche Art von grammatikalischem Satz welcher Art von Programm entspricht.

Lexikalische Analyse:

1. Geben Sie einen regulären Ausdruck ein und konvertieren Sie den regulären Ausdruck in nfa->dfa-> ;dfa minimiert. Gehen Sie für diesen Teil zum NetEase Cloud Classroom-Compiler, der Java verwendet. Folgen Sie einfach dem obigen Video für den vorherigen NFA-Teil.

2. Holen Sie sich die Tabelle, die DFA minimiert. Für jeden regulären Ausdruck wird lediglich diese Tabelle benötigt. Daher können Sie die Tabelle nach der Bestimmung des regulären Ausdrucks direkt speichern, ohne sie jedes Mal neu generieren zu müssen.

3. Dann brauchen Sie eine Menge regulärer Ausdrücke
   

1. Nummer eins

2. Ein Symbol

3. Ein Schlüsselwort

4. Ein Variablenname

5. „irgendetwas " (dies kann zur Fehlerbehandlung verwendet werden. Wenn es nicht 1-4 oben ist, können Sie 5 zum Empfangen und Ausschließen verwenden)

    var id_ = new build_rule();
    id_.build_from_str(id__str, 3);    //这个变量id__str就是那个已经生成字符串保存起来的dfa最小化的表
    //数字3就是id对应的名字，到时候用来判断来生成类型码的

    var key_word = new build_rule();
    key_word.build_from_str(key_word_str, 1);    //和上面一样

    var ops = new build_rule("{op}{op}*", 1);    //这个使用正则生成的规则的，需要经过nfa---dfa---最小化这几步的转化
    //1符号和关键字统称的类型


    var num = new build_rule("{float}", 4);    //同上

    var anything = new build_rule();
    anything.build_from_str(anything_str);
    anything.rule_name = 5;    //这个就是用来处理错误的，识别5这个类型时候就会出错，也可以记录这个出错让程序一直扫描到后面再输出错误

    //按照自己定义的规定的顺序进行添加规则，到时候就会按照这个顺序进行查找
    var qing = qingai(code);
    qing.add_rules(key_word);
    qing.add_rules(id_);
    qing.add_rules(ops);
    qing.add_rules(num);
    qing.add_rules(anything);
    qing.action();

1. Alle regulären Ausdrücke sind in Ordnung. Es hängt von Ihrer eigenen Vereinbarung ab. Die Reihenfolge lautet beispielsweise:
   Variablenname——–>Schlüsselwort————>Andere
   Wenn in diesem Fall "var" erkannt wird, wird var als Variablenname betrachtet, denn wenn var nicht als Schlüsselwort definiert ist, kann es als zulässiger Variablenname verwendet werden.
   Die Reihenfolge muss also selbst festgelegt werden.

2. Nachdem mehrere reguläre Ausdrücke und deren Reihenfolge erstellt wurden, beginnt die Arbeit.

3. Der Quellcode wird von Anfang an gescannt und der Hauptzeiger zeigt auf den Anfang
   

1. Der Zeiger zeigt zum Anfang

2. Beginnen Sie mit der ersten Regel

3. Gemäß den DFA-Automatenregeln, also der Tabelle, wenn Sie auf ein Zeichen stoßen , springe zu dieser Zeile

4. Wenn du nach dem Lesen der nächsten Zeile immer noch springen kannst, springe zu einer anderen Zeile. Wenn es nicht springen kann, prüfen Sie, ob diese Zeile eine Endmarkierung hat. Wenn ja, beenden Sie sie reibungslos, ohne nach der nächsten Regel zu suchen. Fügen Sie dann die Länge der gefundenen Zeichenfolge zum Hauptzeiger hinzu und notieren Sie die Informationen dieser Zeichenfolge Zeile, diese Spalte, welcher Typ. Wenn nicht, finden Sie die nächste Regel.

5. Weil es eine Regel gibt, dass alles ist , um sicherzustellen, dass jeder Attribute finden kann.

6. Es wird immer noch einige geben, die nicht gefunden werden, weil Leerzeichen und Zeilenumbrüche vorhanden sind. Sie müssen sie am Ende überprüfen und herausfiltern.

4. Dann können Sie basierend auf dem Quellcode, den Sie geschrieben haben

a=7464;b=7465;a=b+7464*2;

, eine solche Tabelle erhalten 8. Der folgende Typcode ist der Typcode, der verwendet werden muss, um diese Art von Zeichenfolge in der Grammatik auszudrücken. Später wird die Grammatikseite anhand des Typcodes feststellen, ob das eingegebene Satzsymbol nicht der angegebenen Grammatik entspricht. Da unterschiedliche Schlüsselwörter und Symbole unterschiedliche Bedeutungen haben, sind die Typcodes von Schlüsselwörtern und Symbolen unterschiedlich. Meine Variablennamen werden durch d dargestellt

Zusammenfassungsschritte

1. Geben Sie den regulären Ausdruck ein

2. Ersetzen Sie die Makrodefinition des regulären Ausdrucks durch normale Zeichen

3. Schneiden Sie den regulären Ausdruck aus

4. Übergeben Sie den gesamten Schnittausdruck an den NFA-Automaten, um das NFA-Diagramm zu erstellen

5. Setzen Sie den Kopfknoten des NFA-Diagramms ein. Geben Sie den DFA-Automaten ein, um die DFA-Tabelle zu erstellen

6. und führen Sie eine DFA-Minimierung für die NFA-Tabelle durch, um die DFA-minimierte Tabelle zu erhalten

7. Damit ist eine Zeichenfolge abgeschlossen. Die Konstruktion des entsprechenden Suchautomaten

8. wiederholt 1-7, bis alle regulären Ausdrücke konvertiert sind. Danach müssen Sie nur noch alle minimierten Tabellen speichern und diese Tabelle jedes Mal laden. Es ist nicht erforderlich, jedes Mal NFA, DFA oder ähnliches zu generieren.

9. Fügen Sie die Regeln der Reihe nach in den Scanner ein (eigentlich ist es nur eine While-Schleife, die alle Zeichen im Quellprogramm schreibt) und beginnen Sie mit dem Scannen.

10. Token-Tabelle abrufen

11. Ende

Verwandte Artikel:

Algorithmen und Beispiele zum Parsen von vier arithmetischen Ausdrücken in JavaScript

Analyse des JavaScript-Vorkompilierungsprinzips

Das obige ist der detaillierte Inhalt vonVerwenden Sie Javascript, um eine lexikalische Analyse von vier arithmetischen Compilern zu schreiben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!