Język formalny

Elementy języka formalnego:

 Alfabet A = {a1, a2, …, an} - dowolny zbiór symboli, z których zestawiane są

słowa języka,

 Słowo - uporządkowany ciąg symboli alfabetu,

 Język A* - podzbiór zbioru możliwych słów nad alfabetem A,

 Gramatyka - zbiór reguł umożliwiających generowanie słów i zdań.

Przykład:

Alfabet: A={a, b}

Gramatyka: reguła R1 - a jest poprawne,

reguła R2 - Jeżeli  jest poprawne to ab jest poprawne.

Poprawne słowa:

a - na podstawie R1

aab - na podstawie R1 i R2

aaabb - na podstawie R1 i dwukrotnie stosowanej R2

Język A* = {aab, aaabb, a, b}.

Gramatyki bezkontekstowe

Gramatyka bezkontekstowa:

G = < T, N, P,  >

 T- zbiór symboli końcowych (terminal symbols ), z których budowane są słowa

generowane przez gramatykę G,

 N - zbiór symboli pomocniczych, nieterminalnych używanych przy określaniu

reguł opisujących konstruowanie słów poprawnych w sensie gramatyki G,

 P - Lista produkcji (list productions): zestaw reguł tzw. produkcji,

 ∈N: aksjomat języka, kategoria syntaktyczna (syntactic category), podaje z jakiej

konstrukcji można wyprowadzić wszystkie generowane przez gramatykę napisy.

Kategoria syntaktyczna

Gramatyka składa się z co najmniej jednej produkcji.

Każda produkcja składa się z trzech części:

 Części nagłówkowej, symbolu początkowego (head, start symbol), która jest

kategoria syntaktyczną,

 Metaznaku (metasymbol)

 Części zasadniczej (body).

Produkcje wchodzące w skład zbioru P są postaci:

x >u, x(należy)N, u(należy)(N(suma)T)*

Gramatyka wyrażenia arytmetycznego

Elementy składowe gramatyki:

 Zbiór T: T = {a, b, d, +, *, (, )}

 Zbiór N: N = {W, S, C}

Semantyka symboli: W - wyrażenie, S - składnik, C - czynnik.

 Kategoria syntaktyczna :  = W

 Lista produkcji:

P = { W>S; W>W+S; S>C; S>C*S;S>S*C; C>a; C>b; C>d;

C>W) }

Przykład: (a+b)*d

W

S

C*S

(W)*S

(W+S)*C

(S+S)*C

(C+C)*C

(a+c)*d

Sposoby opisu składni

Notacje:

 BNF (Backus-Naur Form)

 EBNF (Extended Backus-Naur Form)

 Diagramy syntaktyczne (Syntactic diagram)

Notacje: BNF, EBNF

Notacja BNF:

 Symbole terminalne,

 Symbole nieterminalne,

 Produkcje,

 Metasymbole

< > symbol pomocniczy,

::= symbol produkcji,

 symbol alternatywy,

( ) powtórzenie, { } - EBNF

Wyrażenie arytmetyczne:

<W> ::= <S> <W> + <S>  <S> + <W>

<S> ::= <C> <C> * <S>  <S> * <C>

<C> ::= (<W> )a  b 

Odwrotna Notacja Polska ONP

Beznawiasowe algebry Łukasiewicza

Gramatyka wyróżnia arytmetycznego w ONP:

Zbiór T: T = {a, b, d, +, *}

P: <W> ::= <Z> <Z> <O> | <Z>

<Z> ::= <X> <X> <O> | <X>

<X> ::= a | b | d

<O> ::= + | *

Przykład:

(a+b)*d ≡ ab + d*

---