Welche Beziehung besteht zwischen Programmiersprachen, regulären Ausdrücken und formalen Sprachen?

Ich habe mich im Internet nach einer Antwort auf diese Frage umgesehen und es scheint, als ob jeder außer mir die Antwort implizit kennt. Vermutlich liegt das daran, dass die einzigen Menschen, die sich darum kümmern, diejenigen sind, die eine Hochschulausbildung zu diesem Thema absolviert haben. Andererseits wurde ich für einen Highschool-Auftrag in die Enge getrieben.

Meine Frage ist, wie genau sich Programmiersprachen auf formale Sprachen beziehen. Überall, wo ich lese, wird etwas in der Art gesagt, dass "formale Sprachen zur Definition der Grammatik von Programmiersprachen verwendet werden".

Nach dem, was ich sammeln konnte, ist eine formale Sprache eine Reihe von Produktionsregeln, die für einen bestimmten Satz von Symbolen (das Alphabet der Sprache) gelten. Diese Produktionsregeln definieren eine Reihe von Transformationen, wie z.

b -> a

aaa->c

Dies kann so angewendet werden, dass:

abab->aaaa aaaa-> ca

Nur als Randnotiz, wenn wir das Alphabet unserer formalen Sprache als {a, b, c} definieren, dann sind a und b keine Terminals und c ist terminal, da es nicht transformiert werden kann (bitte korrigieren Sie mich, wenn ich falsch liege Das).

Wie um alles in der Welt trifft dies auf Programmiersprachen zu? Oft wird auch angegeben, dass Regex verwendet wird, um eine Sprache in ihrer Textform zu analysieren, um sicherzustellen, dass die Grammatik korrekt ist. Das macht Sinn. Dann wird angegeben, dass reguläre Ausdrücke durch formale Sprachen definiert sind. Regex gibt wahr oder falsch zurück (zumindest nach meiner Erfahrung), je nachdem, ob die Automaten mit endlichen Zuständen, die den regulären Ausdruck darstellen, den Zielpunkt erreichen. Soweit ich sehen kann, hat das nichts mit Transformationen zu tun *.

Für die Kompilierung des Programms selbst würde eine formale Sprache wahrscheinlich Code in Code auf einer niedrigeren Ebene umwandeln und schließlich über ein komplexes Regelwerk zur Assemblierung gelangen, das die Hardware dann verstehen könnte.

Das ist also alles aus meiner verwirrten Sicht. Wahrscheinlich stimmt vieles nicht, was ich gesagt habe, und deshalb bitte ich um Hilfe.

* Es sei denn, Sie betrachten etwas (a|b)*b*c->trueals Produktionsregel. In diesem Fall erfordert die Regel endliche Zustandsautomaten (dh Regex). Das macht keinen Sinn, wie wir gerade gesagt haben

Wer Ihnen gesagt hat, dass reguläre Ausdrücke zum Parsen von Code verwendet werden, hat Desinformation verbreitet. Klassisch (ich weiß nicht, inwieweit dies in modernen Compilern zutrifft) besteht das Parsen von Code - die Umwandlung von Code von Text in einen Syntaxbaum - aus zwei Schritten:

1. Lexikalische Analyse: Verarbeitet den Rohtext in Blöcke wie Schlüsselwörter , numerische Konstanten , Zeichenfolgen , Bezeichner usw. Dies wird klassisch mit einer Art Finite-State-Maschine implementiert, die einem deterministischen Finite-Automaten (DFA) ähnelt.

2. Parser: Wird nach einer lexikalischen Analyse ausgeführt und konvertiert den Rohtext in einen kommentierten Syntaxbaum. Die Grammatik von Programmiersprachen ist (in erster Näherung) kontextfrei (tatsächlich benötigt man eine noch strengere Teilmenge), und dies ermöglicht es bestimmten effizienten Algorithmen, den lexifizierten Code in einen Syntaxbaum zu zerlegen. Dies ähnelt dem Problem, zu erkennen, ob eine bestimmte Zeichenfolge zu einer kontextfreien Grammatik gehört, mit dem Unterschied, dass wir den Beweis auch in Form eines Syntaxbaums benötigen.

Grammatiken für Programmiersprachen werden als kontextfreie Grammatiken geschrieben, und diese Darstellung wird von Parsergeneratoren verwendet, um schnelle Parser für sie zu erstellen. Ein einfaches Beispiel hätte eine nicht-terminale Anweisung und dann Regeln der Form Anweisung IF-Anweisung, wobei IF-Anweisung → if-Bedingung dann BLOCK enden oder dergleichen (wobei BLOCK → STATEMENT | BLOCK; STATEMENT zum Beispiel). In der Regel werden diese Grammatiken in Backus-Naur-Form (BNF) angegeben.$\to$$\to$$\to$

Die tatsächlichen Spezifikationen von Programmiersprachen sind nicht kontextfrei. Beispielsweise kann eine Variable nicht angezeigt werden, wenn sie nicht in vielen Sprachen deklariert wurde, und Sprachen mit strenger Typisierung ermöglichen es möglicherweise nicht, einer Zeichenfolgenvariablen eine Ganzzahl zuzuweisen. Die Aufgabe des Parsers besteht lediglich darin, den Rohcode in ein Formular zu konvertieren, das einfacher zu verarbeiten ist.

Ich sollte erwähnen, dass es andere Ansätze gibt, wie zum Beispiel das Parsen rekursiver Abstammung, bei denen kein Syntaxanalysebaum generiert wird, der Code jedoch beim Parsen verarbeitet wird. Obwohl es nicht die Mühe macht, den Baum zu generieren, arbeitet er im Übrigen auf derselben Ebene wie oben beschrieben.

Das sind einige schwere Sachen für einen Highschool-Auftrag.

Die Antwort von Yuval Filmus ist wirklich gut, daher ist dies eher eine ergänzende Antwort, um einige der von ihm angesprochenen Punkte zu verdeutlichen.

Eine formale Sprache ist eine mathematische Konstruktion. Ihre Verwendung für Programmiersprachen ist nur eine von vielen möglichen Verwendungen. Tatsächlich leistete der Linguist Noam Chomsky bedeutende Beiträge zur frühen Theorie der formalen Sprachen. Er erfand die Chomsky-HierarchieFormale Sprachen werden auch in der Linguistik angewendet, um die Syntax natürlicher Sprachen wie Englisch zu beschreiben. Stellen Sie sich das wie die reellen Zahlen vor: Wir können die reellen Zahlen verwenden, um sowohl konkrete Dinge wie die Entfernung von Los Angeles nach New York als auch abstrakte Dinge wie das Verhältnis des Umfangs eines Kreises zum Durchmesser zu beschreiben. Obwohl diese beiden Dinge unabhängig von den reellen Zahlen existieren, sind die reellen Zahlen ein hilfreiches System, um sie zu beschreiben. Formale Sprachen sind ein hilfreiches System zur Beschreibung von Englisch und Python, da beide ein ähnlich strukturiertes Format haben.

$a + b + c = d$$a + b = d - c$$a$$b$$c$ als Dollarbeträge zum Beispiel, und dann hat die Gleichung Bedeutung.

Klassischerweise wird eine Programmiersprache zwei Grammatiken haben: eine lexikalische Grammatik und eine syntaktische Grammatik. Die lexikalische Grammatik behandelt Zeichen wie Buchstaben, Semikolons, Klammern und Klammern. Es ist normalerweise eine reguläre Grammatik, daher kann sie mit regulären Ausdrücken oder einem DFA oder NFA ausgedrückt werden. (Es gibt Beweise in der formalen Sprachtheorie, die zeigen, dass die drei gleichwertig sind - das heißt, sie akzeptieren dieselben Sprachen.) Die Lexing-Phase des Compilers oder Interpreters ist eine Art Mini-Interpreter für die reguläre Sprachgrammatik. Es liest die Regeln der Grammatik und fasst nach diesen Regeln einzelne Zeichen zu Token zusammen. Wenn die Sprache eine hat zum Beispiel ifAussage , dass sieht mehr oder weniger wie C ist, die Lexer könnten die Zeichen Klumpen iund fin den einzelnen TokenIFOPEN_PARENSuchen Sie dann nach einer öffnenden Klammer und geben Sie ein Token aus. Behandeln Sie dann alles, was in Klammern steht, und suchen Sie dann die schließende Klammer und geben Sie ein aus CLOSE_PAREN. Wenn der Lexer die Erstellung von Token abgeschlossen hat, übergibt er sie dem Parser, der feststellt, ob die Token tatsächlich gültige Anweisungen der Programmiersprache bilden. Wenn Sie also ip a == bin Python schreiben , gibt der Lexer sein Bestes, um zu erraten, was für ein Token es ipist (wahrscheinlich wird es von den meisten Lexern als Bezeichner verwendet), und gibt es an den Parser weiter, der sich beschwert, weil Sie kein Token haben können Kennung an dieser Position.

$a \rightarrow b$

Schauen wir uns die Grammatikregeln für Pythons ifAussage an. Das ist die Regel:

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

Diese Regel sagt uns, wie der Parser herausfindet, ob eine vom Lexer gesendete Zeichenfolge eine if-Anweisung ist. Jedes Wort in einfachen Anführungszeichen muss einfach so im Quellcode erscheinen, damit der Parser nach dem einfachen Wort sucht if. Der Parser versucht dann, einige Token der Regel zuzuordnen für test:

test: or_test ['if' or_test 'else' test] | lambdef

testwird in Bezug auf andere Regeln in der Grammatik definiert. Beachten Sie, wie sich testauch in seiner Definition einschließt; Das nennt man eine rekursive Definition. Es ist die große Stärke von kontextfreien Sprachen, die reguläre Sprachen nicht haben, und es ermöglicht die Definition von verschachtelten Schleifen für die Syntax von Programmiersprachen.

Wenn der Parser es schafft, einige Token zuzuordnen test, versucht er, einen Doppelpunkt zuzuordnen. Wenn dies erfolgreich ist, wird versucht, weitere Token anhand der Regel für abzugleichen suite. Der Abschnitt ('elif' test ':' suite)*bedeutet, dass wir eine beliebige Anzahl von Wiederholungen des wörtlichen Textes haben können elif, gefolgt von etwas, das übereinstimmt test, gefolgt von einem Doppelpunkt, gefolgt von etwas, das übereinstimmt suite. Wir können auch null Wiederholungen haben; Das Sternchen am Ende bedeutet "Null oder so viele wie wir wollen".

Ganz am Ende ist ['else' ':' suite]. Dieser Teil ist in eckigen Klammern eingeschlossen. das heißt, wir können null oder eins haben, aber nicht mehr. Um dies abzugleichen, muss der Parser mit dem Literaltext else, einem Doppelpunkt und dann mit einem übereinstimmen suite. Hier ist die Regel für ein suite:

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

Es ist im Grunde ein Block in C-ähnlichen Sprachen. Da Python verwendet Zeilenumbrüche und Einzüge zu Gemeinheiten, die Lexer - Ausgänge NEWLINE, INDENTund DEDENTToken den Parser zu sagen , wo eine neue Linie begonnen, wo der Code eingerückt gestartet, und wo sie auf der äußeren Ebene des Einzugs zurückgeführt .

Wenn einer dieser Übereinstimmungsversuche fehlschlägt, kennzeichnet der Parser einen Fehler und stoppt. Wenn das Parsen des gesamten Programms erfolgreich ist, hat der Parser normalerweise einen Analysebaum wie Yuval in seiner Antwort erstellt und möglicherweise eine Symboltabelle und andere Datenstrukturen, in denen semantische Informationen gespeichert sind. Wenn die Sprache statisch ist, durchsucht der Compiler den Analysebaum nach Tippfehlern. Außerdem wird der Analysebaum durchsucht, um Code auf niedriger Ebene (Assemblersprache, Java-Bytecode, .Net Intermediate Language oder ähnliches) zu generieren, der tatsächlich ausgeführt wird.

Als Übung würde ich empfehlen, die Grammatik einer Ihnen vertrauten Programmiersprache (wieder Python , Java und hier C # , Javascript , C ) zu nehmen und zu versuchen, etwas Einfaches wie vielleicht x = a + b;oder von Hand zu analysieren if (True): print("Yay!"). Wenn Sie nach etwas Einfacherem suchen, gibt es auch eine nette Grammatik für JSON , die im Grunde nur die Syntax für Objektliterale in Javascript (wie {'a': 1, 'b': 2}) abdeckt . Viel Glück, das ist hirnrissig, aber es stellt sich als sehr interessant heraus, wenn Sie sich nicht in einer verrückten Frist befinden.

In einer Nussschale

Programmiersprachen bestehen aus einer Syntax, die das Programm als Zeichenfolge darstellt, und einer Semantik, die die beabsichtigte Bedeutung des Programms darstellt.

Formale Sprachen sind Syntax ohne Bedeutung. Es ist dazu gedacht, die Struktur von formal definierten Stringsets zu untersuchen, ohne diesen Strings üblicherweise eine Bedeutung beizumessen.

Reguläre Ausdrücke und andere Formalismen (z. B. kontextfreie Grammatiken) werden verwendet, um formale Sprachen zu definieren, die als syntaktischer Bestandteil der Programmierung und natürlicher Sprachen verwendet werden, dh um Sätze strukturiert darzustellen. Andere Mechanismen werden verwendet, um diese Struktur mit der Semantik der Programmiersprachen in Beziehung zu setzen.

Vieles wird hier erheblich vereinfacht, insbesondere in Bezug auf die natürliche Sprache.

Mit viel mehr Details

Um Ihre Frage zu beantworten, sollten wir von vorne beginnen. Eine Sprache im üblichen Sinne ist informell ein Mittel, um Informationen oder Ideen zu vermitteln. In einer Sprache unterscheidet man normalerweise zwischen Syntax und Semantik. Über Semantik möchten Sie sprechen / schreiben. die Informationen, die Sie vermitteln möchten. Syntax ist das Mittel, mit dem Sie es übermitteln, dh eine herkömmliche Darstellung, die zwischen Personen und nun auch zwischen Personen und Geräten oder zwischen Geräten (Computern) ausgetauscht werden kann.

In der Regel verwenden Sie das Wort dog, um die Idee eines Hundes zu vermitteln. Das Wort dogbesteht aus drei Buchstaben oder einem ähnlichen Laut und soll eine Art Tier darstellen. Die Schlüsselidee ist, dass Kommunikation durch Repräsentation dessen erfolgt, was kommuniziert werden soll. Repräsentationsstrukturen werden üblicherweise als Syntax bezeichnet, während das, was dargestellt wird, als Semantik bezeichnet wird. Dies gilt mehr oder weniger für natürliche Sprache sowie für Programmiersprachen.

Wörter sind syntaktische Einheiten, die mehr oder weniger elementare semantische Konzepte darstellen. Diese elementaren Konzepte müssen jedoch auf verschiedene Weise zusammengesetzt werden, um eine komplexere Bedeutung zu erhalten. Wir schreiben the dog, um zu vermitteln, dass wir einen bestimmten Hund meinen, und the dog bites the catum eine komplexere Idee zu vermitteln. Die Art und Weise, wie die Wörter organisiert sind, muss jedoch durch Regeln festgelegt werden, damit wir erkennen können, welche der beiden Gruppen sich tatsächlich beißen.

Wir haben also Regeln wie diese sentence -> subject verb complement, die zu Sätzen passen und uns mitteilen sollen, wie die mit jedem Teil verbundenen Ideen artikuliert sind. Diese Regeln sind syntaktische Regeln, da sie uns mitteilen, wie die Darstellung unserer Botschaft zu organisieren ist. Das subjectkann selbst durch eine Regel definiert werden subject -> article nounund so weiter.

$2x+1=23$$x$$1$$23$

equation -> expression "=" expression  
expression -> expression "+" expression 
expression -> number

Die Struktur der Programmiersprachen ist dieselbe. Programmiersprachen sind semantisch darauf spezialisiert, durchzuführende Berechnungen auszudrücken, anstatt zu lösende Probleme, Beweise für Theoreme oder freundschaftliche Beziehungen zwischen Tieren auszudrücken. Aber das ist der Hauptunterschied.

In der Syntax verwendete Darstellungen sind normalerweise Zeichenfolgen oder Töne für gesprochene Sprachen. Die Semantik gehört normalerweise zum abstrakten Bereich oder möglicherweise zur Realität, ist aber in unseren Denkprozessen oder im Verhaltensbereich von Geräten immer noch abstrahiert. Bei der Kommunikation wird die Information / Idee in eine Syntax kodiert, die vom Empfänger gesendet und dekodiert wird. Das Ergebnis wird dann vom Empfänger wie auch immer interpretiert.

Was wir also von der Sprache sehen, ist hauptsächlich die Syntax und ihre Struktur. Das obige Beispiel ist nur eine der gebräuchlichsten Methoden, um syntaktische Zeichenfolgen und ihre strukturelle Organisation zu definieren. Da sind andere. Für eine bestimmte Sprache können einige Zeichenfolgen einer Struktur zugewiesen werden und sollen zur Sprache gehören, während andere dies nicht tun.

Gleiches gilt für Worte. Einige Buchstabenfolgen (oder Lautfolgen) sind legitime Wörter, andere nicht.

Formale Sprachen sind nur Syntax ohne Semantik. Sie definieren mit einer Reihe von Regeln, welche Sequenzen unter Verwendung der Grundelemente eines Alphabets erstellt werden können. Was die Regeln sind, kann sehr unterschiedlich sein, manchmal komplex. Formale Sprachen werden jedoch für viele mathematische Zwecke jenseits der sprachlichen Kommunikation verwendet, sei es für natürliche oder für Programmiersprachen. Der Regelsatz, der die Zeichenfolgen in einer Sprache definiert, wird als Grammatik bezeichnet. Es gibt aber auch viele andere Möglichkeiten, Sprachen zu definieren.

In der Praxis ist eine Sprache in zwei Ebenen strukturiert. Die lexikalische Ebene definiert Wörter, die aus einem Buchstaben bestehen. Die syntaktische Ebene definiert Sätze oder Programme, die aus einem Alphabet von Wörtern (oder genauer aus Wortfamilien) aufgebaut sind, so dass es ein endliches Alphabet bleibt. Dies ist notwendigerweise etwas vereinfacht.

Die Struktur von Wörtern ist in den meisten Sprachen (Programmierung oder natürlich) ziemlich einfach, so dass sie normalerweise mit der einfachsten Formsprache definiert werden: den regulären Sprachen. Sie können mit regulären Ausdrücken (regexp) definiert werden und sind mit programmierten Geräten, so genannten Finite-State-Automaten, relativ einfach zu identifizieren. Bei Programmiersprachen sind Beispiele für ein Wort ein Bezeichner, eine Ganzzahl, eine Zeichenfolge, eine reelle Zahl, ein reserviertes Wort wie if oder repeat, ein Interpunktionssymbol oder eine offene Klammer. Beispiele für Wortfamilien sind Bezeichner, Zeichenfolge und Ganzzahl.

Die syntaktische Ebene wird normalerweise durch einen etwas komplexeren Typ formaler Sprache definiert: die kontextfreien Sprachen, bei denen die Wörter als Alphabet verwendet werden. Die Regeln, die wir oben gesehen haben, sind kontextfreie Regeln für die natürliche Sprache. Bei Programmiersprachen können Regeln sein:

statement -> assignment
statement -> loop
loop ->  "while" expression "do" statement
assignment -> "identifier" "=" expression
expression -> "identifier"
expression -> "integer"
expression -> expression "operator" expression

Mit solchen Regeln können Sie schreiben:

while aaa /= bbb do aaa = aaa + bbb / 6 Das ist eine Aussage.

Die Art und Weise, wie es erstellt wurde, kann durch eine Baumstruktur dargestellt werden, die als Analysebaum oder Syntaxbaum bezeichnet wird (hier nicht vollständig):

                          statement
                              |
            _______________  loop _______________
           /      /                 \            \
      "while" expression           "do"       statement
       __________|_________                       |
      /          |         \                  assignment
 expression "operator" expression          _______|_______
     |           |          |             /       |       \
"identifier"   "/="   "identifier" "identifier"  "="   expression
     |                      |            |                 |
    aaa                    bbb          aaa             ... ...

Die auf der linken Seite einer Regel erscheinenden Namen werden als Nichtterminals bezeichnet, während die Wörter auch als Terminals bezeichnet werden, da sie im Alphabet für die Sprache (über der lexikalischen Ebene) stehen. Nicht-Terminal stellen die verschiedenen syntaktischen Strukturen dar, die zum Erstellen eines Programms verwendet werden können.

Solche Regeln werden als kontextfrei bezeichnet, da ein Nicht-Terminal unabhängig vom Kontext, in dem es vorkommt, beliebig durch eine der entsprechenden Regeln ersetzt werden kann. Die Regeln, die die Sprache definieren, werden als kontextfreie Grammatik bezeichnet.

Tatsächlich gibt es Einschränkungen, wenn Bezeichner zuerst deklariert werden müssen oder wenn ein Ausdruck Typeinschränkungen erfüllen muss. Eine solche Einschränkung kann jedoch als semantisch und nicht als syntaktisch angesehen werden. Tatsächlich ordnen einige Fachleute sie in die sogenannte statische Semantik ein .

Wenn ein Satz oder ein Programm gegeben ist, wird die Bedeutung dieses Satzes extrahiert, indem die vom Analysebaum für diesen Satz gegebene Struktur analysiert wird. Daher ist es sehr wichtig, Algorithmen, sogenannte Parser, zu entwickeln, die die einem Programm entsprechende Baumstruktur wiederherstellen können, wenn sie dem Programm gegeben werden.

Dem Parser geht der lexikalische Analysator voraus, der Wörter erkennt und die Familie bestimmt, zu der sie gehören. Dann wird die Folge von Wörtern oder lexikalischen Elementen an den Parser übergeben, der die zugrunde liegende Baumstruktur abruft. Aus dieser Struktur kann der Compiler dann bestimmen, wie Code generiert werden soll, was der semantische Teil der Programmverarbeitung auf der Compilerseite ist.

Der Parser eines Compilers kann tatsächlich eine dem Analysebaum entsprechende Datenstruktur erstellen und an die späteren Phasen des Kompilierungsprozesses übergeben, muss dies aber nicht. Das Ausführen des Parsing-Algorithmus läuft darauf hinaus, eine Berechnungsstrategie zu entwickeln, um den im Programmtext enthaltenen Syntaxbaum zu untersuchen. Dieser Syntax- / Analysebaum kann dabei je nach Kompilierungsstrategie (Anzahl der Stufen) erläutert werden oder auch nicht. Was jedoch notwendig ist, ist, dass es letztendlich mindestens eine Bottom-up-Untersuchung des Analysebaums gibt, ob explizit oder implizit in der Berechnungsstruktur belassen.

Der Grund dafür ist intuitiv, dass eine standardmäßige formale Methode zur Definition der einer syntaktischen Baumstruktur zugeordneten Semantik ein sogenannter Homomorphismus ist. Fürchte dich nicht vor dem großen Wort. Die Idee ist nur zu berücksichtigen, dass die Bedeutung des Ganzen sich aus der Bedeutung der Teile auf der Grundlage des Operators zusammensetzt, der sie verbindet

Zum Beispiel kann der Satz the dog bites the catmit der Regel analysiert werden sentence -> subject verb complement. Die Bedeutung der drei Teilbäume zu wissen subject, verbund complementdie Regel , dass sie komponiert uns sagt , dass das Thema der Aktion tut, und dass die Katze ist derjenige, der gebissen wird.

Dies ist nur eine intuitive Erklärung, die jedoch formalisiert werden kann. Die Semantik wird aus den Bestandteilen aufwärts konstruiert. Das verbirgt aber viel Komplexität.

Die interne Arbeitsweise eines Compilers kann in mehrere Stufen unterteilt werden. Der eigentliche Compiler arbeitet möglicherweise stufenweise mit Zwischendarstellungen. Es kann auch einige Stufen zusammenführen. Dies hängt von der verwendeten Technologie und der Komplexität der Kompilierung der jeweiligen Sprache ab.

Es gibt signifikante Unterschiede. Ich würde sagen, das Wichtigste unter ihnen ist, dass beim Parsen von echten Programmiersprachen der Umgang mit Syntaxfehlern im Vordergrund steht. Bei einer formalen Sprache würde man einfach sagen, dass es nicht in der Sprache ist, aber ein Compiler, der sagt, dass dies nicht sehr nützlich ist - er sollte Ihnen sagen, was falsch ist, und wenn es ein kleiner Fehler war, analysieren Sie im Idealfall weiter, damit es geht Weitere Fehler melden. Viel Forschung (und Implementierungsaufwand) steckt dahinter. Eigentlich interessiert Sie das Richtig / Falsch-Ergebnis nicht einmal so sehr, Sie möchten lediglich die Struktur der Eingabe analysieren. Formale Sprachen werden dort als Werkzeug verwendet, und es gibt viele Überschneidungen, aber Sie lösen wirklich ein anderes Problem.

Außerdem wurde in den meisten Sprachen festgelegt, bestimmte Dinge in der Grammatik nicht zu erzwingen , z. B. das von Ihnen erwähnte Beispiel "Eine Variable kann nicht angezeigt werden, wenn sie nicht deklariert wurde". Dies ist normalerweise eine Sache, die vom Parser vollständig ignoriert und dann in einer separaten Analyse (semantische Analyse) erfasst wird, die sich mit solchen Dingen befasst und von Überlegungen wie der Kontextfreiheit nicht beeinflusst wird. Aber nicht immer - um beispielsweise C zu analysieren, wird häufig der Lexer-Hack verwendet, und C ++ ist ein berühmtes Beispiel für eine Sprache, die nicht analysiert werden kann, ohne gleichzeitig ernsthafte semantische Analysen durchzuführen (das Parsen von C ++ ist unentscheidbar, da Templates vollständig sind ). In einfacheren Sprachen ist es jedoch in der Regel uneinheitlich. Auf diese Weise ist es einfacher.

Eine formale Sprache ist eine Reihe von Wörtern - wobei ein Wort eine Folge von Symbolen aus einem Alphabet ist.

Dies bedeutet, dass Ihre Kopplung der Produktionsregeln und der formalen Sprache zu stark ist. Es ist nicht richtig, dass die formale Sprache die Produktionsregeln sind. Vielmehr definieren die Produktionsregeln die Formensprache. Die formale Sprache sind die Wörter, die von der Produktionsregel erzeugt werden können. (Dies setzt voraus, dass die formale Sprache von der Art ist, die durch Produktionsregeln definiert werden kann, z. B. können reguläre Sprachen durch eine kontextfreie Grammatik definiert werden.)

Die reguläre Sprache, die dem Ausdruck entspricht, (a|b)*c*dwird also durch die Produktionsregeln definiert.

S->ACd
A->
A->aA
A->bA
C->
C->cC

Die Wörter, die diese Produktionsregeln aus dem Startsymbol S erzeugen, sind genau die Zeichenfolgen, die der reguläre Ausdruck akzeptiert.

Es gibt eine andere Beziehung zwischen regulären Ausdrücken und Programmiersprachen, die mit Semantik zu tun hat. Die grundlegenden Kontrollkonstrukte einer imperativen Sprache sind sequentielle Komposition (mache A und dann B), Wahl (mache A oder B) und Wiederholung (mache A immer wieder).

Die gleichen drei Möglichkeiten zum Kombinieren von Verhalten finden sich in regulären Ausdrücken. Werfen Sie Unterprogrammaufrufe ein und Sie haben eine Analogie zu EBNF.

Es besteht also eine große Ähnlichkeit zwischen der Algebra regulärer Ausdrücke und der Algebra von Befehlen. Dies wird ausführlich von Dijkstra in "Die Vereinigung der drei Kalküle" untersucht. Es ist auch die Basis von Milners CCS, die eine Antwort auf die Frage liefert: Was ist, wenn wir Parallelität hinzufügen?