9988995987

18 Wstęp

przez nie. W tym samym okresie Panini, za pomocą 3959 reguł podał wysoce usystematyzowany, opis gramatyki Sanskrytu znany jako Ashtadhy-ayi („Osiem rozdziałów”). W swoim upisie używając m.in. metareguł, transformacji i rekursji spowodował, że gramatyka ta uważana jest za pierwszy system formalny. Występująca obecnie w powszechnym użyciu notacja BNF (Backus-Naur Form) opisu gramatyk bezkontekstowych wykorzystywana jako formalny sposób opisu gramatyki języków programowania, zbioru instrukcji czy protokołów jest do tego stopnia podobna do gramatyki Paniniego, że bywa nazywana też Panini-Backus form ([10]).

Notacja BNF jest zestawem reguł produkcji następującej postaci

<symbol nieterminalny> ::= <wyrazenie zawierające symbole>

Znaczenie użytych symboli jest następujące

•    < - lewy ogranicznik symbolu,

•    > - prawy ogranicznik symbolu,

•    : : = - jest zdefiniowane jako,

•    wyrażenie zawierające symbole składa się z symboli nietermi-nalnych i symboli terminalnych (czyli takich, które nigdy nie pojawiają się po lewej stronie reguł), rozdzielonych ewentualnie znakiem alternatywy: |.

Dla przykładu, używając notacji BNF, określimy liczby całkowite przy pomocy następujących reguł

•    <znak minus>::= -

Przykład wartości: -

•    <zero>::= 0 Przykład wartości: 0

•    <cyfra niezerowa>::=1|2|3|4|5|6|7|8|9

Przykład wartości: 1, 2, 3

•    <ciąg cyfr> ::= <cyfra> I <cyfra><ciąg cyfr>

Przykład wartości: 0, 1, 01, 001, 23, 45, 99, 10023, 000001

•    cliczba całkowita dodatnia>::= <cyfra niezerowa> I <cyfra niezerowa><ciąg cyfr>

Przykład wartości: 1, 2, 34, 56, 406, 556066

©2009 by P. Fulmański, Uniwersytet Łódzki. Wersja z dnia: 9 stycznia 2010