Формальные грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Исправлены тире)
(Арифметические выражения: тире)
Строка 47: Строка 47:
 
===Арифметические выражения===
 
===Арифметические выражения===
 
<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )\}</tex>
 
<tex>\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )\}</tex>
# <tex>S \rightarrow S O S</tex> - два выражения, соединенные действием
+
# <tex>S \rightarrow S O S</tex> два выражения, соединенные действием
# <tex>S \rightarrow (S) </tex> - выражение, взятое в скобки
+
# <tex>S \rightarrow (S) </tex> выражение, взятое в скобки
# <tex>S \rightarrow 0</tex> - ноль
+
# <tex>S \rightarrow 0</tex> ноль
# <tex>S \rightarrow DN</tex> - число, у которого первая цифра не ноль
+
# <tex>S \rightarrow DN</tex> число, у которого первая цифра не ноль
# <tex>O \rightarrow + | - | * | /</tex> - действие
+
# <tex>O \rightarrow + | - | * | /</tex> действие
# <tex>D \rightarrow 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</tex> - цифра, не являющаяся нулем
+
# <tex>D \rightarrow 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</tex> цифра, не являющаяся нулем
# <tex>N \rightarrow NN | \epsilon</tex> - любая последовательность из цифр, возможно пустая
+
# <tex>N \rightarrow NN | \epsilon</tex> любая последовательность из цифр, возможно пустая
# <tex>N \rightarrow 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</tex> - любая цифра
+
# <tex>N \rightarrow 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</tex> любая цифра
  
 
Вывод строки <tex>2+2*2</tex>: <tex>S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2</tex>
 
Вывод строки <tex>2+2*2</tex>: <tex>S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2</tex>
  
 
Левосторонний вывод для такой же строки: <tex>S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow  2+2*S \rightarrow  2+2*2</tex>
 
Левосторонний вывод для такой же строки: <tex>S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow  2+2*S \rightarrow  2+2*2</tex>

Версия 05:09, 10 ноября 2011

Определение:
Нетерминал — элемент, представляющий некоторую сущность языка (например часть формулы) и не имеющий конкретного значения.


Определение:
Формальная грамматика — способ описания формального языка, представляющий собой четверку [math]\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle[/math], где [math]\Sigma[/math] - алфавит, [math]N[/math] - набор нетерминалов, [math]S[/math] - начальный символ грамматики, [math]P[/math] - набор правил вывода [math]\alpha\rightarrow \beta[/math]


Определение:
Терминал — элемент фалфавита [math]\Sigma[/math]


Определение:
[math]\alpha \Rightarrow \beta[/math] ([math]\beta[/math] выводится из [math]\alpha[/math] за один шаг):
  1. [math]\alpha=\alpha_1\alpha_2\alpha_3[/math]
  2. [math]\beta=\beta_1\beta_2\beta_3[/math]
  3. [math]\alpha_1=\beta1[/math], [math]\alpha_3=\beta3[/math], [math]\alpha_2\rightarrow\beta2 \in P[/math]


Определение:
[math]\alpha \Rightarrow^* \beta[/math] ([math]\beta[/math] выводится из [math]\alpha[/math] за ноль или более шагов):
[math]\exists \gamma_1, \gamma_2,...,\gamma_n : \alpha \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow ... \Rightarrow \gamma_n \Rightarrow \beta[/math]


Определение:
Язык грамматики — все последовательности терминалов, которые можно получить из начального символа по правилам вывода. [math]L(\Gamma) = \{\omega|S \Rightarrow^{*}\omega, \omega \in \Sigma^{*}\}[/math]


Примеры грамматик

Правильные скобочные последовательности

[math]\Sigma = \{(, )\}[/math]

  1. [math]S \rightarrow (S)[/math]
  2. [math]S \rightarrow SS[/math]
  3. [math]S \rightarrow \epsilon[/math]

Вывод строки [math](()())[/math]: [math]S\rightarrow(S)\rightarrow(SS)\rightarrow((S)S)\rightarrow((S)(S))\rightarrow(()(S))\rightarrow(()())[/math]

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

[math]\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, *, /, -, (, )\}[/math]

  1. [math]S \rightarrow S O S[/math] — два выражения, соединенные действием
  2. [math]S \rightarrow (S) [/math] — выражение, взятое в скобки
  3. [math]S \rightarrow 0[/math] — ноль
  4. [math]S \rightarrow DN[/math] — число, у которого первая цифра не ноль
  5. [math]O \rightarrow + | - | * | /[/math] — действие
  6. [math]D \rightarrow 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9[/math] — цифра, не являющаяся нулем
  7. [math]N \rightarrow NN | \epsilon[/math] — любая последовательность из цифр, возможно пустая
  8. [math]N \rightarrow 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9[/math] — любая цифра

Вывод строки [math]2+2*2[/math]: [math]S \rightarrow SOS \rightarrow SOSOS \rightarrow 2OSOS \rightarrow 2O2OS \rightarrow 2O2O2 \rightarrow 2+2O2 \rightarrow 2+2*2[/math]

Левосторонний вывод для такой же строки: [math]S \rightarrow SOS \rightarrow 2OS \rightarrow 2+S \rightarrow 2+SOS \rightarrow 2+2OS \rightarrow 2+2*S \rightarrow 2+2*2[/math]