Необходимостта от установяване на официални езици, свързани с някои недостатъци на естествен език, които се появиха в използването му в теорията на алгоритмите. Помислете за някои от тях:
1. зависимост от начините на конструиране на изречения (синтаксис) от тяхното значение (семантика). Например, трябва да използвате изречението "-лекарят на пациента", или "-лекарят на пациента", според един лекар, принадлежащи към съответния етаж;
2. семантична многозначност на предложенията. Например, изречението: "Дръжте парите си в банката", може да включва съхраняване на пари в една финансова институция или по някакъв капацитет;
3. семантични неточност предложения. Така например, по предложение на "Вчера беше топло време", че е невъзможно да се определи температурата на въздуха, тъй като по различно време на годината, топло време може да съответства на различни температури;
4. Наличието на парадокси, обсъждани в предходния параграф.
Официално език, удобен за теорията на алгоритмите, не трябва да има тези недостатъци. В този случай, за да се опише формално език (езикът - обект) ще използва различен език (мета-език), например, естествено руски език.
Правила за изграждане на думи от буквите на думи и изречения от формален език ще се нарича официално граматика. За описание на синтаксиса на езика, използван официално предложено от американския лингвист и математик Чомски стандартен формуляр, който може да се изрази като:
където X - азбука на терминалните символи на официална език;
Y - спомагателен азбука на nonterminal символи;
R - крайно множество от правила, синтаксис;
S - начална вторичен символ от множество не-терминални символи (терминал символ - най-маловажния елемент на формален език).
Всяка от синтактичен правило R представлява заместване → В, където А и В - някои думи, получени от символите X и Y. азбуки предложения формален език започне да получава, ако е приложимо към nonterminal символ S пермутация на Такова заместване R., ляво част от които съответства на nonterminal символ на S, трябва да бъде в Р. Ако резултатът съдържа само терминални символи, това означава, че езикът на предложението е било получено. Ако присъстват в получените символи nonterminal верига, тогава да започне отново прилага към веригата на един от заместителите R, където всяка от тях. Ако получената низ има множество случаи на А, след съответното заместване позволява замяна на всеки от тези случаи на А в Б.
Да разгледаме пример за официална граматика, в която X =, = Y и замествания на системата има формата:
Тази граматика генерира формален език, който съдържа двоични числа, които се четат от ляво на дясно, както и от дясно на ляво. Например, прилагането на пермутации 3, 4, 1 ще доведе до производството на броя 01010; пермутации 4, 3, 3, 2 - вземане номер 1,001,001 и т.н.
Нормално Форма Бакъс-Naur.
Нормално Бакъс-Naur Форма (БНФ) - е друг начин да се опише формално език.
За описание на официална език с помощта на BPF ще използва правилата на синтаксиса (производство), който ще използвате следните символи:
1. = - е знака, който се отделя от лявата страна на продукта, който е не-терминал символ на дясната ръка, която не е празна, ограничен верига на терминални и не-терминални символи. Символ. = Чете по дефиниция, или могат да се състоят от;
2. | - сепаратор, който е поставен между различните форми на същите nonterminal понятия. Символ или чете;
3. <> - Ъглови скоби са използвани, за да се разграничат nonterminal, т.е. такова нещо, което не може да се намери в предложенията описва на езика и се използва, за да опише тези предложения.
Да разгледаме примери описват десетични цифри от типа число и константи използвайки BPF.
Фактът, че един е число, изразено с помощта на BNF, както следва:
В този случай, ъглови скоби <> използва за идентифициране на не-терминал символ, който не може да се случи в изречението описва формално език и е предназначена да опише синтактични правила. Символ 1 може да се случи в изречение описва формално език и е терминал символ.
С цел да се покаже, че не-терминал символ <цифра> може да е 0 или 1, можете да използвате следните правила синтаксис:
По този начин, можем да пишем правило, за да опише номерата на десетичните:
<цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.
тип константи число може да се дефинира рекурсивно, както следва:
- <константа>:: =<цифра>;
- <константа>:: =<константа> <цифра>;
- <цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.
Първото правило гласи: <константа> Тя може да се състои от <цифры>. Второто правило гласи: <константа> Тя може да се състои от други <константы>, последвано от <цифра>.
Тези правила синтактични формират граматиката на езика <констант>. Предложения на този език са последователности на крайни символи, които могат да бъдат получени от nonterminal <константа>. Вземем примера на получаване на постоянна 673 от употребата на синтактичните правила, написани с помощта на BNF:
- Ние използваме второто правило: nonterminal <константа> се заменя с верига <константа> <цифра>;
- Ние използваме третото правило: nonterminal <цифра> се заменя с терминал символ 3;
- Ние използваме второто правило отново и да получите <константа> <цифра>3;
- Ние използваме третото правило, а ние получаваме <константа> 73;
- Ние използваме първото правило: nonterminal <константа> се заменя със nonterminal <цифра>, Резултатът е верига <цифра> 73;
- Ние използваме третото правило и да получите 673.
БНФ и неговите модификации в момента са стандартните начини за описване на синтаксиса на езиците за програмиране.
Свързани статии