Языки, грамматики, Бэкусовские нормальные формы (БНФ)

Введём несколько определений. Пусть задано некоторое непустое, конечное множество знаков А={a1, ...an}, которое мы назовём алфавитом

Любую конечную последовательность букв (которые могут и повторяться), выбираемых из алфавита А назовём словом (цепочкой) в А.

Множество всех слов в алфавите А, включая и пустое слово, которое мы обозначим через ε, будем обозначать через A*. 

Очевидно, A* не пусто и  бесконечно (мы ведь не ограничиваем возможную длину слов!). Но, являясь бесконечным, A* - перечислимое (или, как говорят в математике, счётное) множество.

Действительно, если A={a,b}, то элементы A* можно перечислить, упорядочив их по длине и (внутри одной и той же длины) лексикографически т.е , по алфавиту.  При этом, конечно, мы считаем лексикографический порядок  заранее определённым и на  А. Итак, получим:

0. Слова длины 0: ε

1. Слова длины 1: a, b

2. Слова длины 2: aa, ab, ba, bb

. . .

Далее, языком  над  алфавитом A называется любое множество L ≤ A* (здесь '≤'  для множеств означает отношение нестрогого включения, т.е.  утверждения о том, что L есть подмножество A*, возможно, с A* совпадающее).

Язык может быть конечным (т.е. содержащим конечное множество слов) и бесконечным (содержащим бесконечное множество слов).

Строго определить конечный язык можно простым перечислением всех составляющих его слов. Так, если A={0,1}, то примером  конечного языка над A будет L1={011, 1111, 1, 010101}, состоящий из четырёх слов.

При этом понятно, что бесконечный язык таким способом  задать в принципе не получится. Но можно поступить иначе.  Определять слова языка не фактическим их перечеслением, т.е. "показом", а заданием строгих грамматических правил, которым должна удовлетворять структура всех этих слов и только их.

Придумав такие правила для некоторого, возможно неформально (т.е. словесно) описанного целевого языка,  мы, тем самым,  для этого языка  построим грамматику, теперь уже строго определив  заданный язык.

Рассмотрим,  например, множество всех чётных натуральных чисел (к которому мы отнесём и ноль), представленных в двоичной системе счисления. Очевидно,  оно бесконечно и, в традиционной записи, состоит из завершающихся цифрой 0 последовательностей двоичных цифр (например, 110, 010110, 00, 0, 11111100 и т.д.).

Это определение вполне понятно человеку, но при этом неформально, не точно, не строго  и поэтому мало приспособлено для построения систем компьютерного представления и обработки таких множеств.

Для строгого определения элементов выше указанного множества, попробуем задать их структуру верхнего уровня, например так:  

‹двоичное_чётное›  - это  ‹двоичное›, к которому справа приписан ‹ноль›

Введя специальное обозначение "::="  для 1-й связки (слова "это") и просто опустив 2-ю связку (фразу "к которому справа приписан..."),  то же самое мы можем записать короче:

‹двоичное_чётное›  ::= ‹двоичное‹ноль›         [1]

Здесь четко видно, что составной объект, имеющий обозначение ‹двоичное_чётное› как слово, распадается на два объекта следующего (ещё не окончательного!) уровня: ‹двоичное›  и ‹ноль›.

Теперь, дальнейшая детализация структуры исходного объекта, будет состоять из независимого выявления структуры объектов ‹двоичное›  и ‹ноль›.

Второй из этих двух объектов проще, с него и начнём. Пользуясь уже введёнными нами обозначениями, запишем:

‹ноль› ::= 0           [2]

Здесь просто записано, что под термином (понятием) ‹ноль› понимается слово 0.

При этом ‹ноль› и любое другое обозначение в угловых скобках (т.е. конструкция вида < ... > ) называется нетерминальным (т.е. не окончательным, требующим дальнейшей детализации) символом. В то же время, 0 в правой части формулы [2], как и любая другая конструкция, не обрамлённая угловыми скобками, называется терминальным (окончательным) символом, который являясь неделимым (атомарным), непосредственно входит в состав слова, принадлежащего определяемому языку.

Теперь займёмся нетерминальным символом ‹двоичное›, который может быть определён (детализован) так:

‹двоичное› ::= <двоичная_цифра> | <двоичная_цифра> <двоичное>,         [3]

где знак "|" обозначает связку "или".

Формула [3] - это по существу сокращённая запись двух правил:

‹двоичное› ::= <двоичная_цифра>       [4]

‹двоичное› ::= <двоичная_цифра> <двоичное>      [5]

Правило [3], как и пара правил [4,5] определяют структуру объекта ‹двоичное› следующим образом:  <двоичное> - это либо <двоичная_цифра>, либо <двоичная_цифра>, к которой справа приписан объект, так же представляющий собой  <двоичное>.

Входящее в это определение правило [5] представляет собой пример так называемого рекурсивного правила, когда для определения понятия (<двоичное>), оно же, это понятие, и используется. Важно понимать,  что "порочного круга" в данном случае, при этом, не возникает, т.к. структура объекта, соответствующего понятию <двоичное> в правой части правила [5] в некотором смысле проще, чем структура объекта, соответствующего тому же  понятию в левой части (<двоичное> в правой части, как слово, попросту короче, чем в левой).

Последний  факт позволяет, при повторных (упрощающих) применениях рекурсивного правила к некоторому заданному слову, в конце концов достигать атомарного уровня построения этого слова, разрывая тем самым рекурсивную цепочку определений. В нашем примере "точкой" выхода из рекурсии, или, как говорят, базой рекурсии, служит правило [4].

Вернёмся к примеру. Теперь, единственно недоопределённым элементом наших построений остаётся понятие <двоичная_цифра>, которое уточняется до терминального уровня так:

<двоичная_цифра> ::= 0 | 1

Собрав воедино выше приведённые определения, получим следующее формальное описание языка, представляющего множество всех объектов, рассматриваемых нами как <двоичное_чётное>:

‹двоичное_чётное›  ::= ‹двоичное‹ноль›

‹двоичное› ::= <двоичная_цифра> | <двоичная_цифра> <двоичное>

‹ноль› ::= 0

<двоичная_цифра> ::= 0 | 1

Выше приведённая система обозначений, позволяет совершенно точно, на уровне алфавита, лексики и синтаксиса  описывать грамматику языков некоторого обширного класса (класса, так называемых, КС-языков) и называется системой Бэкусовских Нормальных Форм (БНФ), или метаязыком Бэкуса-Наура.

Практический интерес к БНФ обусловлен тем, что большая часть современных языков программирования является именно КС-языками (или языками, близкими к ним), а значит, допускает возможность строгих их (языков) БНФ-определений.

Точный смысл таких определений состоит в следующем. Пусть <L> - нетерминальный символ, дающий общее наименование всем словам некоторого, определяемого в БНФ языка L (тогда в БНФ-правилах, определяющих L  обязательно присутствует правило вида " <L> ::= ... " ) и пусть  w - некоторое слово, факт принадлежности которого языку L необходимо выяснить. Тогда, w принадлежит L тогда и только тогда, когда:

  1. w содержит только терминальные символы определяющей язык L  БНФ-системы правил;
  2. w может быть получено из <L> в результате некоторой последовательности применения правил данной БНФ-системы.

Например, имея ввиду выше приведённое БНФ- определённие языка "двоичное_чётное", легко убедиться (убедитесь самостоятельно!), что слово 101 никак не может быть получено из "начального" нетерминального символа  ‹двоичное_чётное›, а 1010 - может. Следовательно, 101 - не принадлежит, а 1010 - принадлежит рассматриваемому языку.

Содержательный практический пример применения метаязыка БНФ  для описания сильно упрощённой версии Паскаля дан в комментариях, здесь.



4.833335
Your rating: Нет Average: 4.8 (12 votes)

Комментарии

Задача 1

  1. <один>::=1
  2. <ноль>::=0
  3. <палиндром>::=<один>|<ноль>
  4. <палиндром>::=<ноль>|<один>
  5. <палиндром>::=<один><палиндром><один>|<ноль><палиндром><ноль>
  6. <палиндром>::=<ноль><палиндром><ноль>|<один><палиндром><один>

Белый Александр

Разве не очевидно, что союз "или" ("|") коммутативен. Т.е. сказать "A или B" то же самое, что сказать "B или A" ?

Тогда

Тогда так?

  1. <один>::=1
  2. <ноль>::=0
  3. <палиндром>::=<один>|<ноль>
  4. <палиндром>::=<один><палиндром><один>|<ноль><палиндром><ноль>

Вообще не пойму задачу со скобками, уже и примеры готовых решений смотрел, все равно не понимаю что к чему((

Ну или наоборот, сначала если

Ну или наоборот, сначала если бы 0 был, а потом 1

задача 1

<ноль>::=0
<единица>::=1
<палиндром>::=<ноль>|<единица>
<палиндром>::=<ноль><палиндром><ноль>|<единица><палиндром>

ВОт так или я ошибаюсь

вроде правильно

вроде правильно, а что такое палиндром и зачем мы его пишем

Валерия,

палиндром, это слово - перевёртыш, которое слева направо читается так же, как справа налево
Пример палиндрома:

  1. 1001
  2. aba
  3. 1
  4. a

Палиндром

Валерия, написано же, невнимательно читала:) Палиндром – это число, слово или фраза, одинаково читающиеся в обоих направленияx.Иногда палиндромом неформально называют любой симметричный относительно своей середины набор символов.

а все поняла

а все поняла

Николай

В теги добавь, а то удалят пост. И еще в самом конце еще раз <единица> пропиши ))

спасибо

спасибо

К задаче 1 о палиндромах.

Ещё можно так сказать:
Палиндром - это слово, которое симметрично относительно своей середины.

Например ПОП. В двухбуквенном алфавите {0,1}, палиндром, например, 001011 110100 (пробел вставлен для наглядности).

Ясно, что даже в двухбуквенном алфавите палиндромов бесконечно много, длина-то не ограничена. Как же описать их все.
Ответ очевиден - задать общую структуру этих слов, что мы и делаем на БНФ.

Действительно, весь бесконечный класс палиндромов в алфавите R={a,b}, например, задаётся так:

  1. <пал>::=    // вариант самого короткого  (ПУСТОГО!) палиндрома
  2. <пал>::= a   // вариант однобуквенного палиндрома
  3. <пал>::= b   // и ещё один вариант однобуквенного палиндрома (других однобуквенных палиндромов нет!)
  4. <пал>::=a<пал>a  //рекурсивное правило, позволяющее удлинять палиндром
  5. <пал>::=b<пал>b //и ещё одна возможность удлинения

Итак, построить любой палиндром теперь можно начав с одного из правил 1-3, т.е. с пустого или однобуквенного палиндрома и далее при необходимости удлиняя конструкцию применением правил 4 и 5. Если начинаем с правила 1, то получаем только палиндромы с чётным числом букв, а если начнём с правила 2 - с нечётным.

Показать например, что abbba правильно построенное слово языка палиндромов (т.е. палиндром) можно построив его вывод по выше указанным правилам. Вот этот вывод:

<пал> (4)=> a<пал>a (5)=> ab<пал>ba (3)=> abbba

Так мы из понятия (нетерминального символа) <пал> вывели слово abbba, состоящее только из терминалов. Следовательно abbba, - это пал (т.е. палиндром).

Заметьте, что обозначение вида F (i)=> G у нас означает "из cлова F выводится слово G по правилу с номером i ".

x-10sinx+(sqr(sqr(x)-sqr(sqr(x)*x))

program;
var
x:real;
y:rea;
begin
write('введ dite x');
readln(x);
y:=x-10*sin(x)+abs(sqr(sqr(x)-sqr(sqr(x))*x));
writeln('выраж=', y:3:1);
end.

что у меня не правильно

что у меня не правильно почему то не запускается? y:= вот там курсив

Асхад.

Не знаю что именно вы хотели делать с помощью этой программы, но если хотели считать чему будет равен у, то так

  1.  Program z1;
  2.  Var x,y:real;
  3.  begin
  4.  writeln('введите значение x');
  5.  readln(x); // ввод x
  6.  y:=x-10*sin(x)+(sqr(sqr(x)-sqr(x))*x); // здесь главное не запутаться в скобках
  7.  writeln('y=',y ); // выводим значение y
  8.  end.

и оформляйте код программы заключая в теги < pre> и < / pre> только без пробелов

спасибо теперь выводит

спасибо теперь выводит

Сорри.

небольшая ошибка в оформлении, вот так надо

  1.  Program z1;
  2.  Var x,y:real;
  3.  begin
  4.       writeln('введите значение x');
  5.       readln(x);
  6.       y:=abs(x-10*sin(x)+(sqr(sqr(x)-sqr(x))*x));
  7.       writeln('y=',y );
  8.  end.

Рита,

Можно проще:
выражение (sqr(sqr(x)-sqr(x))*x) тождественно равно 0 при любом x

  1. Program z1;
  2.  Var x,y:real;
  3. begin
  4.  write('x= ');
  5.  readln(x);
  6.  y:=abs(x-10*sin(x));
  7.  writeln('y= ',y );
  8. end.

Спасибо, Никита:)

Действительно проще:) Жаль сама не догадалась

Поправки Риты

Поправки Риты верны и существенны. Хотя мне не ясно, откуда взялась странная задача,
которую решает Асхад.
Асхад! Решения будут удаляться без объяснений, если:
1. Не приведено условие задачи.
2. Неправильно оформлен код (см. замечание Риты)

Задача

Дано число вида abcd. Нужно получить 4-х значное число badc.

  1. program One;
  2.   var a, a1, a2, a3, a4: integer;
  3. begin
  4.     write ('ввод а')
  5.     readln (a);
  6.     a1:=a div 1000;
  7.     a2:=a mod 1000;
  8.     a2:=a2 div 100;
  9.     a3:=a mod 100;
  10.     a3:=a3 div 100;
  11.     a4:=a mod 10;
  12.     writeln;
  13.     a4:=a4*1000;
  14.     a3:=a3*100;
  15.     a2:=a2*10;
  16.     a:=a2+a1+a4+a3;
  17.     writeln (a);
  18.     readln;
  19. end.

Что-то не выходит, посмотрите, пожалуйста, что у меня не так...

Александр,

строка 4: пропущен знак ;
главная ошибка находится в строке 10: если от двузначного числа отбросить последние две цифры , что останется ???
И зачем так всё усложнять( строки 6-12) ?

можно же проще:

  1. program exmpl;
  2.  var a,b,c,d:integer;
  3. begin
  4.  write('abcd= ');
  5.  readln(a);//ввод числа
  6.  d:=a mod 10;//последняя цифра исходного числа
  7.  c:=(a div 10)mod 10;//предпоследняя цифра исходного числа
  8.  b:=(a div 100) mod 10;// вторая цифра исходного числа
  9.  a:=a div 1000;// первая цифра исходного числа
  10.  b:=b*1000+a*100+d*10+c;// формирование числа
  11.  write('badc= ',b);// вывод результата
  12. end.

Никита

Спасибо большое, всё понятно и оказывается очень даже просто))

Единичный бит

Подскажите пожалуйста. Например в числе 21 четыре единичных бита, (в двоичной 10101 ) тут же всего три единички. Как подсчитывать единичные биты?

Денис

А от куда в числе 21 может взяться 4 единичных бита ? Их же там 3 !

Единичный бит

А например в числе 3468 сколько единичных битов? 110110001100

Денис

В числе 3468 содержится 6 единичных битов

Двоичная система

Здравствуйте, подскажите пожалуйста, как из двоичного кода получить десятичное число...Нас в школе учили только переводить числа из десятичной системы счисления в двоичную, а на оборот нет и мне не совсем на лекции стало понятно как это делается!

Александр,

Пусть дано двоичное число a=anan-1...a1

степени:n-1, n-2,...,1,0

 индекс:   n, n-1,...,2,1

n-1,n-2,...0     соответствие степеней и  

anan-1...a1       индексов      an cоответствует степень n-1, ..., a1 соответствует степень 0

(anan-1...a1)2= (an*2(n-1)+an-1*2(n-2)+...+a2*21+a1*20)10

Например, a=1101;    ( число разрядов, n=4)

(1101)2=(1*23+1*22+0*21+1*20)10=1310

Таким образом 11012=1310

Правило перевода в 2-ичную с.с.

Правило простое.

Чтобы перевести число A из 10-ной c.c. в 2-чную нужно разложить его по убывающим степеням числа 2 и выписать в том же порядке коэффициенты при этих степенях.

Например, A=25.
Находим наибольшую степень двух в этом числе - это 16. Она в число входит с коэффициентом 1. Следующая по убыванию степень 8. Она тоже входит в оставшуюся за вычетом 16-ти часть числа (т.е. в число 9) с коэффициентом 1. Следующие по убыванию степени - 4 и 2 не входят (а значит "входят" с коэффициентами 0) и, наконец, 1 с снова входит.
Получили в итоге разложение по убывающим степеням двойки: 25=1*16 + 1*8 + 0*4 + 0*2 +1*1.
Выписав коэффициенты этого разложения, получим ответ: 11001

На практике и для программной реализации удобно разлагать число последовательным его делением на 2 по следующему алгоритму:

Делим заданное A нацело на 2. Получаем остаток - R1 и частное - Q1. Берём теперь Q1 в качестве A;
Делим заданное A нацело на 2. Получаем остаток - R2 и частное - Q2. Берём теперь Q2 в качестве A;
Делим заданное A нацело на 2. Получаем остаток - R3 и частное - Q3. Берём теперь Q3 в качестве A;
...
Процесс продолжаем пока не окажется, что при очередных полученных Rn и Qn частное Qn стало нулём.
Тогда остатки выписанные в обратном порядке: Rn ... R2R1 и будут представлять искомую запись.

Покажем это на нашем примере A=25 в виде Паскаль-программы:

  1. program DecTo2;
  2.   var A,r1,r2,r3,r4,r5: Byte;
  3.        B: LongInt;
  4. Begin
  5.   A:=25;
  6.   r1:=A mod 2;  //1
  7.   A:=A div 2;    //12
  8.   r2:=A mod 2;  //0
  9.   A:=A div 2;     //6
  10.   r3:=A mod 2;   //0
  11.   A:=A div 2;      //3
  12.   r4:=A mod 2;    //1
  13.   A:=A div 2;      //1
  14.   r5:=A mod 2;    //1
  15.   A:=A div 2;      //0
  16.   Writeln(r5,r4,r3,r2,r1); //выводим в ОБРАТНОМ порядке
  17.  
  18. //Для вывода (показа на дисплее), можно было собрать цифры в одно ДЕСЯТИЧНОЕ(!) число...
  19.    B:=r5*10000+ r4*1000+r3*100+r2*10+r1;
  20.    Writeln(B) // ... которое и вывести
  21.    //Это большое число, потому LongInt !

Cпасибо, вроде понял, сейчас

Cпасибо, вроде понял, сейчас потренируюсь!

Задачи на БНФ.

Не знаю, актуально ли уже сейчас мое решение. Я немного потренировалась образовывать БНФ.
Задача 1. определить в БНФ для палиндромов (симметричных) чисел в двоичной системе счисления, при алфавите В={0;1}

  1. <симм>::= <ноль><симм><ноль> | <ед><симм><ед> //при слове, содержащем более 1 символа
  2. <симм>::= <ноль> | <ед>  //при слове длиной в 1 символ
  3. <ноль>::= 0
  4. <ед>::= 1

Описать в БНФ множество всех правильных скобочных записей, при алфавите А={(,)}
  1. <пр_ск_з>::= () | <пр_ск_з><пр_ск_з> | (<пр_ск_з>)

пр_ск_з - "правильная скобочная запись"

У Вас всё правильно, Аминат.

У Вас всё правильно, Аминат.

Ошибка?

"Далее, языком над алфавитом A называется любое множество L ≤ A "
Разве не (L≤A*) должно быть?

Да, Вы правы, Амир. Исправил.

Да, Вы правы, Амир. Исправил.

Решетников Максим аватар

ПСЗ

правильной скобочной записью (ПСЗ) назовем слово, которое получитсяели в обычном алг выражении, содержащим только '()' стереть все знаки, кроме '()'

  1. <psz>::=()|<psz><psz>|(<psz>)