Интернет магазин китайских планшетных компьютеров

Компьютеры - Контекстно-свободная грамматика - Примеры

Примеры КС-грамматик и соответствующих им КС-языков:

Вложенные скобки

• Терминалы: '';
• нетерминал: S;
• продукции: S→, S→ε;
• начальный нетерминал — S.

Этой грамматикой задаётся язык вложенных скобок { | n≥0 }.

Язык Дика

Целые числа

• Терминалы: '+', '-', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9';
• нетерминалы: <число>, <число без знака>, <последовательность цифр>, <ненулевая цифра>, <цифра>;
• продукции:

<число> → 0
<число> → +<число без знака>
<число> → -<число без знака>
<число> → <число без знака>
<число без знака> → <ненулевая цифра>
<число без знака> → <ненулевая цифра><последовательность цифр>
<последовательность цифр> → <цифра><последовательность цифр>
<последовательность цифр> → <цифра>
<цифра> → 0
<цифра> → <ненулевая цифра>
<ненулевая цифра> → 1
<ненулевая цифра> → 2
<ненулевая цифра> → 3 
<ненулевая цифра> → 4 
<ненулевая цифра> → 5 
<ненулевая цифра> → 6 
<ненулевая цифра> → 7
<ненулевая цифра> → 8 
<ненулевая цифра> → 9 

• начальный нетерминал: <число>.

Этой грамматикой задаётся язык целых чисел.

Арифметическое выражение

• Терминалы: '+', '-', '*', '/', '', 'x'
• нетерминалы: <выражение>, <слагаемое>, <множитель>
• продукции:

<выражение> → <выражение> + <слагаемое>,
<выражение> → <выражение> - <слагаемое>,
<выражение> → <слагаемое>,
<слагаемое> → <слагаемое> * <множитель>,
<слагаемое> → <слагаемое> / <множитель>,
<слагаемое> → <множитель>,
<множитель> →,
<множитель> → x,

• начальный нетерминал: <выражение>.

Этой грамматикой задаётся арифметическое выражение, содержащее простейшие арифметические действие над переменной x. Если заменить терминал 'x' на нетерминал <число> из предыдущего примера, то получится грамматика, задающая арифметическое выражение, состоящее из операций сложения, вычитания, умножение и деления над целыми числами.