Biçimsel diller, Chomsky sınıflandırmasına göre 4 sınıfa ayırılır:
- Tip 3 Düzenli diller
- Tip 2 Bağlamdan bağımsız diller
- Tip 1 Bağlama duyarlı diller
- Tip 0 Özyinelemeli sayılabilir diller
Her sınıf, daha küçük sayılı sınıfların bir alt kümesidir. Tip 0 en genel sınıftır, Turing makina ve bilgisayar programıyla sayılanan her dilli kapsar.
Bu sınıflandırma (hiyerarşi), dillerin katarlarını türetten gramer ya da kabul eden makinaların hesaplama gücüne göre yapılmıştır.
Uygulama
Teorik bilişim bilimi bakımından önemli olan bu madde ``pratikte`` programlama dilleri kullanarak bilgisayar programları üretilmesini sağlayan derleyici ve yorumlayıcı yazılımlarının hazırlanmasında önemli bir rol oynar. ``Biçimsel dil kuramı``, sıfırdan bir programlama dili geliştirmek isteyen bir bilgisayar programcısının ilk öğrenmesi gereken konulardan biridir. Mesela alttaki Tip 2 grameri Java,C,C++ de kullanılan floating point sayılarından oluşan biçimsel dili tanımlar; bu dil 3.1415, ya da 1.40239846e-45f gibi sayıların yazılış şekillerini gösterir.FloatingPointLiteral:
Digits . [1] [2] [3]
. Digits [4] [5]
Digits ExponentPart [6]
Digits [7] FloatTypeSuffix
Digits:
Digit
Digits Digit
Digit:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
ExponentPart:
ExponentIndicator SignedInteger
ExponentIndicator: one of
e E
SignedInteger:
[8] Digits
Sign: one of
+ -
FloatTypeSuffix: one of
f F d D
