Gramatyki Formalne cz I 1

TEORIA JĘZYKÓW I GRAMATYK FORMALNYCH CZĘŚĆ I

Mówiąc poprzednio o teorii kodów interesowaliśmy się przyporządkowaniem wiadomościom elementarnym wyrazów kodowych zbudowanych z symboli alfabetu. Rozważając problem dekodowalności zajmowaliśmy się sensem poszczególnych wyrazów. Teraz będzie nas interesować poprawność wyrazów.

Czym jest język, tak naturalny, jak i programowania? Jest to podzbiór zbioru wszystkich możliwych wyrazów, jakie można zbudować z liter przyjętego alfabetu. O poprawności wyrazów w danym języku decyduje gramatyka.

Próbowano zbudować matematyczne podstawy gramatyki języka naturalnego (angielskiego) — Noam Chomsky. To się nie powiodło ze względu na zbyt dużą komplikację i niekonsekwentną składnię języka naturalnego. Chomsky zbudował jednak podstawy lingwistyki matematycznej.

Czym jest gramatyka?

Formalną definicję podamy później.Na razie można przyjąć:

Gramatyka

generator pozwalający produkować napisy, które jak zgodnie z regułami języka są poprawnym zdaniami. Te, których się nie da wygenerować są odrzucane. Proces generowania i odrzucania odbywa się automatycznie.

Gramatykę

wykorzystujemy do konstrukcji translatora języków programowania, który tłumaczy program napisany przez człowieka na język komputera używając matematycznych definicji języków programowania.

Pierwszy krok przy tworzeniu gramatyki

tworzenie wykazu symboli do budowy zdań języka czyli alfabetu terminalnego.

Wygenerowane napisy zawierające choć jeden symbol spoza alfabetu terminalnego są dorzucane.

Symbolom terminalnym, z których buduje się zdania odpowiadają wyrazy języka naturalnego (nie zaś poszczególne litery).

Nie każdy napis zbudowany z poprawnych wyrazów jest poprawnym zdaniem — iak w języku naturalnym.

Gramatyka zawiera reguły pozwalające na poprawną strukturę zdań. Do budowy tych reguł używa się zbioru pomocniczych symboli czyli alfabetu nieterminalnego.

Symbole nieterminalne nie wchodzą w skład języka. Należą one do metajęzyka, czyli języka do opisu języka. W matematyce da się oddzielić iezyk reguł gramatyki od iezyka podlegającego opisowi. Tego nie da się zrobić w języku naturalnym, np. reguły gramatyki języka polskiego podaje się wjęzyku polskim.

Aksjomat

jeden z ważniejszych symboli metajęzykowych w matematycznym opisie gramatyki dotyczących poprayyności. Dla języków programowania ten aksjomat — to "prawidłowo zbudowana instrukcja".

Produkcja

reguły przekształcania symboli metajęzykowych w napisy zayyierające inne symbole metajęzyka lub wyrazy należące do języka.

Produkcja nie prowadzi nigdy poza język.

Dwie metody badania poprawności zdania w danym języku, czyli tego, że zdanie należy do języka:

1.    metoda generacyjna — wychodzimy od aksjomatu i stosując ciąg produkcji generujemy pożądane zdanie

2.    metoda redukcyjna — cofając się w ciągu produkcji można "zwinąć" zdanie do aksjomatu

Jeśli obie metody zawodzą — zdanie jest niepoprawne.