Редактирование: Конструирование Компиляторов, Теоретический минимум (2012)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
- | ''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 | + | ''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].'' |
== Алфавит == | == Алфавит == | ||
Строка 7: | Строка 7: | ||
Грамматика <math>~G = (N,T,P,S)</math> - четверка множеств, где | Грамматика <math>~G = (N,T,P,S)</math> - четверка множеств, где | ||
* <math>~N</math> - алфавит нетерминальных символов | * <math>~N</math> - алфавит нетерминальных символов | ||
- | * <math>~T</math> - алфавит терминальных символов, <math>N \cap T = \ | + | * <math>~T</math> - алфавит терминальных символов, <math>N \cap T = \empty</math>; |
- | * <math>~P</math> - множество правил вида <math>\alpha \rarr \beta | + | * <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>S \in N</math> - начальный символ или аксиома грамматики | ||
Строка 159: | Строка 159: | ||
== Определение эквивалентных состояний ДКА == | == Определение эквивалентных состояний ДКА == | ||
- | Два состояния <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 | + | Два состояния <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>q_i</math> и <math>q_j</math> называются различимыми, если они не эквивалентны. | ||
== Определение контекстно-свободной грамматики без ε-правил == | == Определение контекстно-свободной грамматики без ε-правил == | ||
Строка 211: | Строка 210: | ||
# ''F'' ⊆ ''Q'' — множество заключительных состояний | # ''F'' ⊆ ''Q'' — множество заключительных состояний | ||
Кроме того, должны выполняться следующие условия: | Кроме того, должны выполняться следующие условия: | ||
- | # Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q'' ∈ ''Q'', ''a'' ∈ ''T'' ∪ {ε}, ''Z'' ∈ ''Г'' | + | # Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q'' ∈ ''Q'', ''a'' ∈ ''T'' ∪ {ε}, ''Z''<sub>0</sub> ∈ ''Г'' |
# Если ''D''(''q'', ε, ''Z'') ≠ ∅, то ''D''(''q'', ''a'', ''Z'') = ∅ для всех ''a'' ∈ ''T'' | # Если ''D''(''q'', ε, ''Z'') ≠ ∅, то ''D''(''q'', ''a'', ''Z'') = ∅ для всех ''a'' ∈ ''T'' | ||
Строка 236: | Строка 235: | ||
== Определение нормальной формы Хомского для КС-грамматики == | == Определение нормальной формы Хомского для КС-грамматики == | ||
- | + | говорят что КС-грамматика находится в нормальной форме Хомского если каждое правило имеет вид: | |
- | + | # Либо A → BC, A,B,C - нетерминалы | |
- | # Либо A → BC | + | # либо A → α, α - терминал |
- | # | + | # либо S → e, в таком случае S не встречается в правых частях правил |
- | # | + | |
== Определение правостороннего вывода в КС-грамматике == | == Определение правостороннего вывода в КС-грамматике == |