Podstawowe pojęcia lingwistyki matematycznej.

• Składnia. Wyprowadzenie zdań języka.
• Notacje typu Infix oraz Postfix
• Drzewa składniowe

Składnia. Wyprowadzenie zdań języka.

Opis języków naturalnych oraz prostszych modeli, czyli języków bezkontekstowych, a zarówno wyrażeń arytmetycznych, dokonuje się za pomocą wzajemnej rekursji, z zastosowaniem symboli wyróżnionych oraz zmiennych (kategorii syntaktycznych). Reguły wiążące ze sobą zmienne zwane są produkcjami. Na podstawie tych reguł tworzone są zdania, czyli łańcuchy, należące do języka.

Lingwistyka matematyczna ma do czynienia z regułami typu:

<zdanie> -> <fraza 1><fraza 2>,

<fraza rzeczownikowa> -> <rzeczownik>,

<rzeczownik> -> statek,

gdzie zmienne są ujęte w nawiasy kątowe, a symbole wyróżnione (np. końcowe) są reprezentowane za pomocą słów nie ujętych w nawiasy. Np., reguła <rzeczownik> -> "statek" oznacza, ze łańcuch składający się z pojedynczego słowa końcowego "statek", należy do kategorii syntaktycznej <rzeczownik>; symbol "->" oznacza "może być złożonym z" lub "należy do".

Wyprowadzenie zdań języka wykonuje się na podstawie tych reguł i opisuje się za pomocą symbolu "=>". Oznacza to zastępowanie zmiennej prawą stroną produkcji dla tej zmiennej. Poniższa tabela zawiera zbiór produkcji pewnej gramatyki, oraz zdania, wyprowadzone za pomocą tych produkcji.

Przykład wyprowadzeń zdań języka

Informatyka stosuje notację zwaneą notacją Backusa-Naura (Backus-Naur Form - BNF), będącej notacją gramatyki bezkontekstowej. Takie użycie gramatyk bezkontekstowych uprościło definicje języków programowania oraz konstrukcje kompilatorów. Notacja BNF stosuje pojecie "przypisanie :=", powodujące zamianę wartości zmiennej. Np., zbiór reguł z powyższego przykładu w postaci BNF wygląda następująco:

<wyraz> := <wyraz> + <wyraz>,

<wyraz> := <wyraz> * <wyraz>,

<wyraz> := (<wyraz>),

<wyraz> := e

Notacje typu Infix oraz Postfix

Gramatyki, opisujące wyrażenia arytmetyczne, powinny pracować z formami rekurencyjnymi (nawiasowymi).

Przykład drzewa składni dla zdań arytmetycznych

3 + (4 * 5)	(3 + 4) * 5
String: + 3 * 4 5	String: * + 3 4 5

Ciągi (string) otrzymane z tych drzew, są notacjami typu Operator Prefix Notation, gdzie operator pisze się przed operandem.

Definicja:

Notacja typu Operator Prefix Notation jest ciągiem, gdzie operator pisze się przed operandem.

Dla zapisu zdania bez nawiasów przez logika J.Łukasiewicza została zaproponowana notacja, zwana Notacją Polską(Polish notation). Ta forma zapisu jest stosowana dla opracowania wzorów matematycznych w translatorach.

Definicja:

Notacja typu Postfix czyli Notacja Polska(Polish Notation) jest ciągiem, gdzie nie stosuje się nawiasów i operator pisze przed (Polish Notation) lub po operandzie Odwrotna Polska Notacja(Inverse Polish Notation).

Przykład: Podane zdanie arytmetyczne wyprowadzone jest z użyciem notacji Polish Notation oraz Inverse Polish Notation

Przykład Notacji polskiej

Drzewa składniowe

Drzewa składniowe - Syntax (Production) trees - stosowane są w teorii języków kontekstowo niezależnych jako modele formalne procesu produkowania zdań języka Każde drzewo składniowe odpowiada zdaniu z obliczenia zdań (Sentence or Propositional Calculus).

Reguła budowania drzewa: Every non-terminal sprouts branches leading to every character in the right side of the production that replaces it.

Przykład: Podana jest gramatyka kontekstowo-niezalezna z regułami: S -> AA, A -> AAA, A -> bA, A -> Ab, A -> a. Zbudować drzewo składniowe dla wyprowadzenia słowa: bbaaaab.

Przykład drzewa składni dla gramatyki kontekstowo-niezależnej

Reguła	Drzewo
S -> AA
A -> bA, A -> AAA
A -> bA, A -> a, A -> a, A -> Ab,
A -> a, A -> a