Liczby całkowite
Zacznijmy od zdefiniowania liczb całkowitych. Po pierwsze określmy, co będziemy chcieli nazywać liczbami całkowitymi. Przyjmijmy, że poprawnymi liczbami są wszystkie skończone ciągi cyfr dziesiętnych poprzedzone pojedynczym znakiem \( + \) lub \( - \). Dopuścimy zatem jako poprawne napisy \( 123,-22,00,+013 \), ale jako niepoprawne uznamy np. napisy \( ++12,-+0,2+3,XVI,+,\varepsilon \). Oto propozycja gramatyki:
G=\( \langle \{ \)S,Z,C,L\( \} \),\( \{ \)-,+,0,1,2,3,4,5,6,7,8,9\( \} \),\( \{ \)
\(C::=0|1|2|3|4|5|6|7|8|9,S::=L|ZL,Z::=+|-,L::=C|LC, \} \),S\( \rangle \)
W ten sposób napisana gramatyka daje jednoznaczne wyprowadzenie każdej liczby całkowitej, zgodnej z naszymi założeniami. Zauważmy, że na samym początku wyprowadzania decydujemy, czy liczba ma być ze znakiem, czy bez – o tym decyduje wybór \( L \) lub \( ZL \) spośród dwóch wariantów, które daje nam symbol \( S \). Z symbolu pomocniczego \( L \) możemy wygenerować dowolny niepusty ciąg cyfr, a z symbolu \( Z \) znak. Przykładowe wyprowadzenie liczby -120 wygląda następująco:
\begin{Rysunek}[rys3-120] \end{Rysunek}