Formale Grammatik: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Die Seite wurde neu angelegt: „Nicht alle Wörter, die aus den Symbolen eines Alphabets gebildet werden können, sind auch in der Sprache enhalten. Zum Beispiel können aus dem Alphabet für römische Zahlen auch Wörter wie <math>\textrm{MIMIMI}</math> gebildet werden, die keine gültigen römischen Zahlen darstellen. Denn zu einer Sprache gehören auch '''Regeln''' zur Bildung der Wörter. Diese Regeln fasst man zu einer Grammatik zusammen. === Beispiel === <sy…“)
 
Keine Bearbeitungszusammenfassung
Zeile 1: Zeile 1:
Nicht alle Wörter, die aus den Symbolen eines Alphabets gebildet werden können, sind auch in der Sprache enhalten. Zum Beispiel können aus dem Alphabet für römische Zahlen auch Wörter wie <math>\textrm{MIMIMI}</math> gebildet werden, die keine gültigen römischen Zahlen darstellen. Denn zu einer Sprache gehören auch '''Regeln''' zur Bildung der Wörter. Diese Regeln fasst man zu einer [[Formale Grammatik|Grammatik]] zusammen.
Eine [[formale Grammatik]] ist ein mathematisches Werkzeug, um [[formale Sprache]]n zu beschreiben.
 
Eine Grammatik besteht aus einer Reihe von Regeln, nach denen sich die Wörter der Sprache '''ableiten''' lassen.
Zusätzlich zu den Symbolen des Alphabets der Sprache, die hier '''Terminalsymbole''' genannt werden, werden hier noch so genannte '''Nicht-Terminalsymbole''' eingeführt. Wenn alle Nicht-Terminalsymbole nach den Regeln der Grammatik zu den Terminalsymbolen eines Wortes abgeleitet werden können, entspricht dieses Wort den Regeln der Grammatik und gehört damit zu der dazugehörigen Sprache. Jede Regel entspricht der Form <code>X ::= Y</code>, lies: "X kann zu Y abgeleitet werden". <code>X</code> muss dabei ein Nichtterminalsymbol sein<ref>Wir beschränken uns hier der Einfachheit halber auf so genannte ''kontextfreie Grammatiken''. Andere Grammatiken gestatten mehr Freiheiten für <code>X</code>.</ref>, <code>Y</code> darf beliebig viele Nicht- und Terminalsymbole enthalten.


=== Beispiel ===
=== Beispiel ===
Zeile 11: Zeile 14:


# Eine <code><RoemischeZahl></code> besteht aus einer <code><Tausender></code>-, einer <code><Hunderter></code>-, einer <code><Zehner></code>- und einer <code><Einer></code>-Stelle ''in dieser Reihenfolge''.
# Eine <code><RoemischeZahl></code> besteht aus einer <code><Tausender></code>-, einer <code><Hunderter></code>-, einer <code><Zehner></code>- und einer <code><Einer></code>-Stelle ''in dieser Reihenfolge''.
# Die <code><Tausender></code>-Stelle ist ''entweder'' leer – dafür steht das <code>ε</code> – ''oder'' besteht aus einem <code>M</code>, gefolgt von noch mehr <code><Tausender></code>n, die aber auch leer sein dürfen. Der senkrechte Strich <code>|</code> trennt zwei Alternativen.
# Die <code><Tausender></code>-Stelle ist ''entweder'' leer – dafür steht das <code>ε</code> – ''oder'' besteht aus einem <code>M</code>, gefolgt von noch mehr <code><Tausender></code>n, die aber auch leer sein dürfen. Der senkrechte Strich <code>|</code> steht für das ''oder''.
# Die <code><Hunderter></code>-Stelle ist entweder ein <code>C</code>, ein <code>CC</code>, ... ein <code>CM</code> oder leer.
# Die <code><Hunderter></code>-Stelle ist entweder ein <code>C</code>, ein <code>CC</code>, ... ein <code>CM</code> oder leer.
# Die <code><Zehner></code> und die <code><Einer></code> funktionieren genau wie die Hunderter.
# Die <code><Zehner></code> und die <code><Einer></code> funktionieren genau wie die Hunderter.
Zeile 22: Zeile 25:
|-
|-
|<code><Symbol></code>
|<code><Symbol></code>
|Dies nennt man ''Nichtterminalsymbol'', dieses muss noch weiter durch die Anwendung von Regeln abgeleitet werden, bis irgendwann ein Wort entstanden ist, das keine Nichtterminalsymbole mehr enthält.
|Nichtterminalsymbole setzt man in spitze Klammern.
|-
|-
|<code>Sekt&nbsp;<nowiki>|</nowiki>&nbsp;Selters</code>
|<code>Sekt&nbsp;<nowiki>|</nowiki>&nbsp;Selters</code>

Version vom 7. September 2023, 07:14 Uhr

Eine formale Grammatik ist ein mathematisches Werkzeug, um formale Sprachen zu beschreiben.

Eine Grammatik besteht aus einer Reihe von Regeln, nach denen sich die Wörter der Sprache ableiten lassen. Zusätzlich zu den Symbolen des Alphabets der Sprache, die hier Terminalsymbole genannt werden, werden hier noch so genannte Nicht-Terminalsymbole eingeführt. Wenn alle Nicht-Terminalsymbole nach den Regeln der Grammatik zu den Terminalsymbolen eines Wortes abgeleitet werden können, entspricht dieses Wort den Regeln der Grammatik und gehört damit zu der dazugehörigen Sprache. Jede Regel entspricht der Form X ::= Y, lies: "X kann zu Y abgeleitet werden". X muss dabei ein Nichtterminalsymbol sein[1], Y darf beliebig viele Nicht- und Terminalsymbole enthalten.

Beispiel

<RoemischeZahl> ::= <Tausender> <Hunderter> <Zehner> <Einer>
<Tausender>     ::= M <Tausender> | ε
<Hunderter>     ::= C | CC | CCC | CD | D | DC | DCC | DCCC | CM | ε
<Zehner>        ::= X | XX | XXX | XL | L | LX | LXX | LXXX | XC | ε
<Einer>         ::= I | II | III | IV | V | VI | VII | VIII | IX | ε

Diese Regeln bedeuten Folgendes:

  1. Eine <RoemischeZahl> besteht aus einer <Tausender>-, einer <Hunderter>-, einer <Zehner>- und einer <Einer>-Stelle in dieser Reihenfolge.
  2. Die <Tausender>-Stelle ist entweder leer – dafür steht das ε – oder besteht aus einem M, gefolgt von noch mehr <Tausender>n, die aber auch leer sein dürfen. Der senkrechte Strich | steht für das oder.
  3. Die <Hunderter>-Stelle ist entweder ein C, ein CC, ... ein CM oder leer.
  4. Die <Zehner> und die <Einer> funktionieren genau wie die Hunderter.

Syntax

Syntaxelement Erläuterung
<Symbol> Nichtterminalsymbole setzt man in spitze Klammern.
Sekt | Selters Der senkrechte Strich trennt zwei Optionen, von denen nur eine gewählt werden kann.
ε ε steht für das leere Symbol, das Nichts.
<A> ::= ??? Ersetze <A> durch ???

Ableitung von Wörtern aus den Regeln

Durch wiederholte Anwendung der Regeln einer Grammatik kann aus einem Nichtterminalsymbol ein vollständiges Wort abgeleitet werden, das keine Nichtterminalsymbole mehr enthält, z.B. aus dem Nichtterminalsymbol <RoemischeZahl> das Wort MMXXIII.

Ableitungsschritt von... ... nach... Angewandte Regel
<RoemischeZahl> → <Tausender><Hunderter><Zehner><Einer> <RoemischeZahl> ::= <T><H><Z><E>
<Tausender><Hunderter><Zehner><Einer> → M<Tausender><Hunderter><Zehner><Einer> <Tausender> ::= M<Tausender>
M<Tausender><Hunderter><Zehner><Einer> → MM<Tausender><Hunderter><Zehner><Einer> <Tausender> ::= M<Tausender>
MM<Tausender><Hunderter><Zehner><Einer> → MM<Hunderter><Zehner><Einer> <Tausender> ::= ε
MM<Hunderter><Zehner><Einer> → MM<Zehner><Einer> <Hunderter> ::= ε
MM<Zehner><Einer> → MMXX<Einer> <Zehner> ::= XX
MMXX<Einer> → MMXXIII <Einer> ::= III

Die Reihenfolge dieser Ableitungsschritte ist nicht fest, man hätte auch zuerst die <Einer> zu III ableiten können.

Zur Visualisierung der Ableitung zeichnet man Ableitungsbäume:

Die letztendlich abgeleiteten Terminalsymbole stehen dann unten in den Blättern des Baumes.

Zum Weiterlesen

  1. ↑ Wir beschränken uns hier der Einfachheit halber auf so genannte kontextfreie Grammatiken. Andere Grammatiken gestatten mehr Freiheiten für X.
Abgerufen von „https://wiki.kah.gs/index.php?title=Formale_Grammatik&oldid=3194“