Существуют 2 способа определения языка грамматики:
1. Построение последовательности правил вывода (порождение) от стартового символа и предложению языка
2. Построение дерева разбора
## Порождение
Основная идея порождения состоит в том, что любая продукция рассматривается как переписывающие правила, в которой нетерминал из левой части заменяется строкой из правой части продукции
#### Пример 1
$G (N, T, P, S)$  
$N = [E]$  
$T = [+, *, (, ), -]$  
$S = E$  
$E → E + E / E * E / (E) / -E / id$  
$E → -E$ - $E$ порождает $-E$  
$E → (E)$ - $E$ порождает $(E)$  
$E ⇒ -E ⇒ -(E) ⇒ -(id)$ - порождение строки $-(id)$ из стартового символа грамматики $E$  

Строка терминальных символов, полученная в результате вывода (порождения) из стартового символа грамматики $E$ в результате последовательности замен, называется **предложением языка**  
**Сентенциальная форма грамматики** - любая цепочка символов, полученная из стартового символа грамматики. Сентенциальная форма, которая содержит только терминальные символы, является предложением языка  
Таким образом, на каждом шаге порождения делается 2 выбора:
1. Выбирается заменяемый нетерминал **(ТОЛЬКО ОДИН!)**
2. Выбирается альтернатива (продукция) для этого нетерминала  
#### Пример 2
$G (N, T, P, S)$  
$E → E + E / E * E / (E) / -E / id$  
$w = -(id+id)$  
2 варианта порождения:
1) $E ⇒ -E ⇒ -(E) ⇒ -(E+E) ⇒ -(id+E) ⇒ -(id+id)$ - левостороннее порождение
2) $E ⇒ -E ⇒ -(E) ⇒ -(E+E) ⇒ -(E+id) ⇒ -(id+id)$ - правостороннее порождение  

**Левостороннее порождение** - на каждом шаге порождения заменяется крайний левый нетерминал  
**Правостороннее порождение** - на каждом шаге порождения заменяется крайний правый нетерминал  
На каждом шаге заменяется **ТОЛЬКО ОДИН** нетерминальный символ  
Используется **ТОЛЬКО ОДНО** порождение в течение всего вывода. Нельзя использовать то левое, то правое  
## Дерево вывода
**Дерево вывода (разбора)** можно рассматривать как графическое представление порождения, из которого удалена информация о порядке замещения  
**Дерево разбора** - это конечный неориентированный граф, обладающий следующими свойствами:
1. У него одна вершина - корень дерева - соответствует стартовому символу грамматики
2. Каждый внутренний узел дерева помечается некоторым нетерминалом $A$. Например, из нетерминала $A$ выводится продукция $XYZ$
3. Дочерние узлы помечаются слева направо символами из правой части продукции для $A$  
![Дерево вывода](05_01.%20Дерево%20вывода.png)  
Дерево разбора для правостороннего порождения будет такое же, потому что оно игнорирует порядок замен при порождении
#### Пример 3
Предложение языка может иметь не одно дерево разбора, и даже не одно левое и одно правое дерево разбора.  
$G (N, T, P, S)$  
$E → E + E / E * E / (E) / -E / id$  
$w = id + id * id$  
1. $E ⇒ E+E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id$  
![Первое дерево разбора](05_02.%20Первое%20дерево%20разбора.png)  
Данное дерево разбора отражает обычный приоритет операций сложения и умножения.  
2. $E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id$  
![Второе дерево разбора](05_03.%20Второе%20дерево%20разбора.png)  
Грамматика, которая дает более одного дерева разбора для некоторого предложения языка, называется **неоднозначной**.  
Контекстно-свободная грамматика (КС-грамматика) называется **однозначной**, если для некоторой цепочки существует только одно дерево разбора.  
Однозначность/неоднозначность - это свойство грамматики, а не языка.  
Однозначные грамматики обеспечивают однозначную семантическую интерпретацию программы.