Грамматика языка

предложений некоторого языка.

Правило (продукция) – это упорядоченная пара цепочек символов (α, β).
В правилах очень важен порядок цепочек, поэтому их чаще записывают в виде
α→β
читается как «α порождает β» или «β по определению есть α».

Грамматика языка программирования содержит правила двух типов:
правила, определяющие синтаксические конструкции языка легко поддаются формальному описанию;
правила, определяющие семантические ограничения языка обычно излагаются в неформальной форме.

Язык, заданный грамматикой G, обозначается как L(G).

S),
где: VT – множество терминальных символов;
VN – множество нетерминальных символов: VN∩VT=∅;
Р – множество правил (продукций) грамматики вида α→β, где α∈V+, β∈ V*;
S – целевой (начальный) символ грамматики S∈VN.

Определение грамматики языка

Множество V = VN∪VT называют полным алфавитом грамматики G.

Множество терминальных символов VT содержит символы,
которые входят в алфавит языка, порождаемого грамматикой
(символы этого множества встречаются только
в цепочках правых частей правил, если же встречаются
в левой части правила, то должны быть и в правой его части).

Множество нетерминальных символов VN содержит символы,
которые определяют слова, понятия, конструкции языка
(каждый символ этого множества может встречаться
в цепочках как левой, так и правой частей правил,
но должен хотя бы один раз быть в левой части
хотя бы одного правила).

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

Рекурсия в правилах грамматики выражается в том,
что один из нетерминальных символов определяется сам через себя.
Рекурсия может быть непосредственной (явной) –
тогда символ определяется сам через себя в одном правиле,
либо косвенной (неявной) – тогда символ определяется через цепочку правил.

правил грамматик предполагает, что:

если во множестве правил грамматики есть несколько правил, имеющих одинаковые левые части, вида:
α→β1, α→β2, … α→βn,
то эти правила объединяют вместе и записываются в следующем виде:
α→β1|β2|…βn|
(одной строке в такой записи соответствует сразу n правил);

нетерминальные символы берутся в угловые скобки: < >.

целых десятичных чисел со знаком задана:
G({0,l,2,3,4,5,6,7,8,9,-,+},{<число>,<чс>,<цифра>},P, <число>):
Р: <число> → <чс>| +<чс>| -<чс>
<чс> → <цифра>| <чс><цифра>
<цифра> → 0|1|2|3|4|5|6|7|8|9

Составляющие элементы грамматики G:

множество терминальных символов VT содержит двенадцать элементов: десять десятичных цифр и два знака;

множество нетерминальных символов VN содержит три элемента: символы <число>, <чс> и <цифра>;

множество правил P содержит 15 правил, которые записаны в три строки (то есть имеются только три различных левых части правил) рекурсия в 5 правиле,
4 правило позволяет избежать бесконечной рекурсии;

целевым символом грамматики является символ <число>.

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

G({0,l,2,3,4,5,6,7,8,9,-,+},{S,T,F},P,S):
Р: S → T| +T| -T
T → F| TF
F → 0|1|2|3|4|5|6|7|8|9

правил.

Языки классифицируются в соответствии с типами грамматик.

От того, к какому типу относится тот или иной язык программирования, зависит сложность распознавателя для этого языка

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

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