Theoretische Informatik: Grammatiken prüfen

Hallo,

Bisschen Code, um einen String auf Grammatikkonformität zu prüfen:

[autoit]

; Startsymbol X
; Regel 1: X -> ( X A X ) X
; Regel 2: X -> epsilon

[/autoit][autoit][/autoit][autoit]

; prüfe Input
Global $input = InputBox("Wort?", "Bitte zu prüfendes Wort eingeben:", "(A(A)(A(A)))")
If $input == "" Then $input = "(A(A(A)(A)))"

[/autoit][autoit][/autoit][autoit]

Global $pointer = 1

[/autoit][autoit][/autoit][autoit]

; Startsymbol aufrufen
ConsoleWrite(StringFormat("Prüfe Wort '%s'", $input) & @CRLF)
X()
; prüfen, ob alles gefressen
if $pointer <= StringLen($input) Then error()
MsgBox(0, "ERFOLG", StringFormat("Das Wort '%s' ist in der Sprache.", $input))

[/autoit][autoit][/autoit][autoit]

; Funktion, die alle Regeln mit rechter Seite = X umsetzt
Func X()
; Regel 1
If StringMid($input, $pointer, 1) = "(" Then
match("(")
X()
match("A")
X()
match(")")
X()
Else
; Regel 2
match("") ; oder einfach nichts, denn match() macht hier nichts Interessantes
EndIf
EndFunc ;==>X

[/autoit][autoit][/autoit][autoit]

Func match($string)
ConsoleWrite(StringFormat("Matche '%s', Pointer ist %d", $string, $pointer) & @CRLF)
; Eingabe schon zuende?
If $pointer > StringLen($input) + 1 Then error()
; aktuelle(s) Zeichen prüfen
ConsoleWrite("Gucke auf Zeichen " & StringMid($input, $pointer, StringLen($string)) & @CRLF)
if StringMid($input, $pointer, StringLen($string)) == $string Then
; Pointer vorschieben
$pointer += StringLen($string)
Else
; FEHLER
error()
EndIf
EndFunc

[/autoit][autoit][/autoit][autoit]

Func error()
MsgBox(0, "FEHLER", StringFormat("Das Wort '%s' ist nicht in der Sprache.\nFehler an Stelle %d, Zeichen %s.", $input, $pointer, StringMid($input, $pointer, 1)))
Exit
EndFunc ;==>error

[/autoit]

Johannes

Brauchen kann das wohl niemand außer dem Nutzer, der mich danach gefragt hat, wie man sowas macht ;).

Mehr Informationen zum Thema gibt es z.B. hier. Man hat einen Satz von Regeln (die Grammatik), mit denen man Wörter erzeugen kann. Die umgekehrte Frage soll dieses Skript beantworten: Gegeben ein Wort w, gehört das zu dieser Grammatik, kann man es also mit den Regeln erzeugen?
Der Algorithmus von oben kann das für eine Teilmenge von Grammatiken erledigen, ist aber auch nicht auf Flexibilität ausgelegt, die Regeln sind hartkodiert. Wer darauf aufbauen möchte, ist herzlich dazu eingeladen :).