Редактирование: Конструирование Компиляторов, Теоретический минимум (2009)

== Алфавит ==

Алфавит - конечное множество символов

Грамматика <math>~G = (N,T,P,S)</math> - четверка множеств, где

* <math>~N</math> - алфавит нетерминальных символов

* <math>~T</math> - алфавит терминальных символов, <math>N \cap T = \empty</math>;

* <math>~P</math> - множество правил вида <math>\alpha \rarr \beta, \alpha \in ( N \cup T)^*N(N \cup T)^*, \beta \in (N \cup T)^*</math>

* <math>S \in N</math> - начальный символ или аксиома грамматики

Если на грамматику <math>~G = (N, T, P, S)</math> не накладываются никакие ограничения, то её называют грамматикой типа 0, или грамматикой без ограничений.

# Каждое правило грамматики, кроме <math>S \rarr \epsilon </math> , имеет вид <math>\alpha \rarr \beta, |\alpha| \le |\beta|</math>

# В том случае, когда <math>S \rarr \epsilon \in P</math>, символ <math>~S</math> не встречается в правых частях правил

== Грамматика типа 2 (Контекстно-свободная, КС) по Хомскому ==

Грамматика типа 2 (Контекстно-свободная, КС) - грамматика, где каждое правило <math>p \in P</math> имеет вид <math>A \rarr \alpha</math>, где <math> A \in N, \alpha \in (N \cup T)^*</math>

== Грамматика типа 3 (Праволинейная) по Хомскому ==

Грамматика типа 3 (Праволинейная) - грамматика, где <math> \forall p \in P </math> имеет вид либо <math> A \rarr xB </math>, либо <math> A \rarr x </math>, где <math> A,B \in N, x \in T^* </math>

 

* <math> \varnothing </math> — регулярное множество в алфавите T

* <math> ~\{a\} </math> — регулярное множество в алфавите T для каждого a &isin; T

* <math> ~\{\epsilon\} </math> — регулярное множество в алфавите T

* Если P и Q — регулярные множества в алфавите T, то регулярны множества

** <math>~P \cup Q</math> (объединение)

** <math>~PQ</math> (конкатенация, <math>\{ pq | p \in P, q \in Q\}</math>)

** <math>~P^*</math> (итерация: <math>P^* = \{\epsilon\} \cup P \cup PP \cup PPP \cup ...)</math>

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

Два состояния <math>q_i</math> и <math>q_j</math> называются эквивалентными (<math>q_i</math> ~ <math>q_j</math>), если <math>\forall z\in</math> T* верно, что <math>D(q_i, z)\in T \Leftrightarrow D(q_j, z)\in T</math>

'''Сентенциальная форма''' — цепочка над алфавитом <math> (T \cup N)^* </math>, выводимая из аксиомы грамматики

говорят что КС-грамматика находится в нормальной форме Хомского если каждое правило имеет вид:

Грамматика называется LR(1), если из условий

1. <math>S' =>_r uAw =>_r uvw</math>,

2. <math>S' =>_r zBx =>_r uvy</math>,

3. FIRST(w) = FIRST(y)

следует, что uAy = zBx (т.е. u = z, A = B и x = y).

Основа правой сентенциальной формы z - это правило вывода <math>A -> v</math> и позиция в z, в которой может быть найдена цепочка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если <math>S =>_r avb</math>, то <math>A -> v</math> в позиции, следующей за a - это основа цепочки <math>avb</math>. Подцепочка b справа от основы содержит только терминальные символы.