Участник:Shovkoplyas Grigory — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Просмотр таблицы маршрутизации)
 
(не показано 29 промежуточных версий 3 участников)
Строка 1: Строка 1:
'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.
 
 
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex> и слово <tex>w</tex>.<br/>
 
'''Выход:''' <tex>true</tex>, если <tex>w</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.
 
 
 
==Определения==
 
==Определения==
{{Определение
 
|definition =
 
Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
 
Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>.
 
}}
 
  
 
{{Определение
 
{{Определение
|definition =
+
|definition =  
'''<tex>j</tex>-м списком ситуаций''' <tex>I_j</tex> для входной цепочки <tex>w = a_1 a_2 ... a_n</tex>, где <tex>0 \leqslant j \leqslant n</tex>, называется множество ситуаций <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* a_{i+1} ... a_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i \rbrace</tex>. То есть <tex>\gamma \alpha </tex> выводит часть <tex>w</tex> c первого по <tex>j</tex>-й символ.
+
Таблица маршрутизации {{---}} таблица, состоящая из сетевых маршрутов и предназначенная для определения наилучшего пути передачи сетевого пакета.
}}
 
 
 
{{Лемма
 
|statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow w \in L(G)</tex>.
 
|proof = Поскольку <tex>S \Rightarrow^* \gamma S \delta</tex> (при <tex>\gamma = \delta = \varepsilon</tex>), из определения <tex>I_n</tex> получаем, что <tex>([S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* a_1 ... a_n = w)</tex>.
 
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|definition =
+
|definition =  
Последовательность списков ситуаций <tex>I_0, I_1, .., I_n</tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
+
Сетевой маршрут {{---}} запись таблицы маршрутизации, содержащая в себе адрес сети назначения (destination), маску сети назначения (netmask), шлюз (gateway), интерфейс (interface) и метрику (metric).
 
}}
 
}}
  
== Алгоритм Эрли ==
+
===Пример таблицы маршрутизации===
Чтобы воспользоваться леммой, необходимо найти <tex>D_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <tex>D_j</tex> используются <tex>D_0, \ldots, D_{j}</tex> (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).
+
{| border="1"
 
 
Алгоритм основывается на следующих трёх правилах:
 
# Если <tex>[A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}</tex> (где <tex>w_j</tex> — <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j</tex>.
 
# Если <tex>[ \rightarrow \eta \cdot , k] \in I_j</tex> и <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_{k}</tex>, то <tex>[A \rightarrow \alpha B \cdot \beta, i] \in I_j</tex>.
 
# Если <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j</tex> и <tex>(A \rightarrow \beta) \in P</tex>, то <tex>[A \rightarrow \cdot \beta, j] \in I_j</tex>.
 
 
 
=== Псевдокод ===
 
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
 
<font color=green> // Инициализация </font>
 
D[0] = {<tex>[S' \rightarrow \cdot S, 0]</tex>}
 
'''for''' i = 1 '''to''' len(w) - 1
 
  D[i] = <tex>\varnothing </tex>
 
<font color=green> // Основная часть </font>
 
'''for''' j = 0 '''to''' len(w) - 1
 
  scan(D, j)
 
  '''while''' D[j] изменяется
 
    complete(D, j)
 
    predict(D, j)
 
 
 
<font color=green> // Первое правило </font>
 
'''function''' scan(D, j)
 
  '''if''' j = 0
 
    '''return'''
 
  '''for''' <tex>[A \rightarrow \alpha \cdot a \beta, i]</tex> <tex>\in</tex> D[j - 1]
 
    '''if''' a = w[j - 1]
 
      D[j] <tex>\cup</tex>= {<tex>[A \rightarrow \alpha \cdot a \beta, i]</tex>}
 
<font color=green> // Второе правило </font>
 
'''function''' predict(D, j)
 
  '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, i]</tex> <tex>\in</tex> D[j]
 
    '''for''' <tex>[B \rightarrow \eta]</tex> <tex>\in</tex> P
 
      D[j] <tex>\cup</tex>= {<tex>[B \rightarrow \cdot \eta, j]</tex>}
 
<font color=green> // Третье правило </font>
 
'''function''' complete(D, j)
 
  '''for''' <tex>[B \rightarrow \eta \cdot, i]</tex> <tex>\in</tex> D[j]
 
    '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, k]</tex> <tex>\in</tex> D[i]
 
      D[j] <tex>\cup</tex>= {<tex>[A \rightarrow \alpha B \cdot \beta, k]</tex>}
 
 
 
==Корректность алгоритма==
 
{{Теорема
 
|statement = Приведенный алгоритм правильно строит все списки ситуаций.
 
|proof =
 
 
 
 
 
=====Алгоритм не добавит в список ситуацию, которая ему не принадлежит:=====
 
Докажем индукцией по исполнению алгоритма.<br/>
 
База (инициализация): <tex>\alpha = \varepsilon \Rightarrow^* \varepsilon </tex> и <tex>S' \Rightarrow^* \gamma S \delta </tex> при <tex>\gamma = \delta = \varepsilon </tex>.<br/>
 
Индукционный переход: пусть в <tex> I_{0},...,I_{j} </tex> нет лишних ситуаций. Пусть включаем <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая:
 
 
 
1. Включаем по правилу <tex>(1)</tex>.<br/>
 
Тогда <tex>\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>. По предположению <tex>\alpha' \Rightarrow^* a_{i+1}...a_{j-1} </tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' A \delta', \gamma' \Rightarrow^* a_1...a_{i} </tex>. Значит, <tex> \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j} </tex> и при <tex>\gamma = \gamma', \delta = \delta'</tex> <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_j</tex>.
 
 
 
2. Включаем по правилу <tex>(2)</tex>.<br/>
 
Тогда <tex>\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex> и <tex> [B \rightarrow \eta \cdot, k] \in I_{j} </tex>. По предположению, <tex>\alpha' \Rightarrow^* a_{i+1}...a_{k}, \eta \Rightarrow^* a_{k+1}...a_{j} </tex>, откуда <tex>\alpha = \alpha' B \Rightarrow^*a_{i+1}...a_{j} </tex>. Кроме того, существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{i} </tex>. Значит, при <tex>\gamma = \gamma', \delta = \delta'</tex> <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_j</tex>.
 
 
 
3. Включаем по правилу <tex>(3)</tex>.<br/>
 
Тогда <tex>\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \eta, k] \in I_{j}, A \Rightarrow \beta</tex>. По предположению <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}</tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S' \Rightarrow^* \gamma' B \delta', \gamma' \Rightarrow^* a_1...a_{k} </tex>. Значит, при <tex>\gamma = \gamma' \alpha', \delta = \eta \delta' </tex>  выполнено <tex> S' \Rightarrow^* \gamma A \delta</tex>, следовательно <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_j</tex>.
 
 
 
=====В каждый список попадут все ситуации, которые ему принадлежат:=====
 
Для всех наборов <tex>\tau = \langle \alpha, \beta, \gamma, \delta, A, i , j \rangle</tex> нужно доказать, что, если <tex> S' \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_{i}, (A \rightarrow \alpha \beta) \in P, \alpha \Rightarrow^* a_{i+1}...a_{j}</tex>, то алгоритм добавит <tex> [A \rightarrow \alpha \cdot \beta, i]</tex> в <tex> I_{j}</tex>.
 
 
 
''Рангом набора'' <tex> \tau </tex> называется <tex> \tau_{S'}(\tau) + 2(j + \tau_{\gamma}(\tau) + \tau_{\alpha}(\tau))</tex>, где <tex>\tau_{S'}(\tau)</tex> — длина кратчайшего вывода <tex>S' \Rightarrow^* \gamma A \delta </tex>, <tex>\tau_{\gamma}(\tau)</tex> — длина кратчайшего вывода <tex>\gamma \Rightarrow^* a_1...a_{i}</tex>, <tex>\tau_{\alpha}(\tau)</tex> — длина кратчайшего вывода <tex>\alpha \Rightarrow^* a_{i+1}...a_{j}</tex>.
 
 
 
Докажем утверждение индукцией по рангу набора.<br/>
 
База: если ранг <tex>\tau</tex> равен 0, то <tex>\tau_{S'} = \tau_{\gamma} = \tau_{\alpha} = j = i = 0</tex>. Значит, <tex>A = S'</tex>, <tex>\alpha = \gamma = \delta = \varepsilon </tex>, <tex>\beta = S </tex>. При инициализации такая ситуация <tex>[S' \rightarrow \cdot S, 0]</tex> будет добавлена в <tex>I_0</tex>.<br/>
 
Индукционный переход:
 
пусть ранг <tex>\tau</tex> равен <tex>r > 0</tex>, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора <tex>\tau</tex>. Для этого рассмотрим три случая:
 
 
 
1. <tex>\alpha</tex> оканчивается терминалом.<br/>
 
<tex>\alpha = \alpha' c</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>c = a_{j}</tex>. Рассмотрим набор <tex>\tau' = \langle \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \rangle </tex>. <tex>(A \rightarrow \alpha' a_{j} \beta) \in P</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 2</tex>, так как <tex>\tau_{S'}(\tau) = \tau_{S'}(\tau'), \tau_{\gamma}(\tau) = \tau_{\gamma}(\tau'), \tau_{\alpha}(\tau) = \tau_{\alpha}(\tau')</tex>. Значит, по предположению <tex>[A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>, и <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex> по правилу <tex>(1)</tex>.
 
 
 
2. <tex>\alpha</tex> оканчивается нетерминалом.<br/>
 
<tex>\alpha = \alpha' B</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>\mathcal {9} k</tex> такое, что <tex>\alpha' \Rightarrow^*a_{i+1}...a_{k}, B \Rightarrow^* a_{k+1}...a_{j}</tex>.<br/>
 
Рассмотрим набор <tex>\tau' = \langle \alpha', B \beta, \gamma, \delta, A, i, k \rangle</tex>, его ранг меньше <tex>r</tex>, следовательно <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex> по предположению.<br/>
 
Пусть <tex>B \Rightarrow \eta</tex> — первый шаг в кратчайшем выводе <tex>B \Rightarrow^* a_{k+1}...a_{j}</tex>. Рассмотрим набор <tex>\tau'' = \langle \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \rangle</tex>. <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta</tex>, следовательно <tex>\tau_{S'}(\tau'') \leqslant \tau_{S'}(\tau) + 1</tex>.<br> Пусть длина кратчайшего вывода <tex>\alpha' \Rightarrow^*a_{i+1}...a_{k}</tex> равна <tex>n_1</tex>, а длина кратчайшего вывода <tex> B \Rightarrow^* a_{k+1}...a_{j}</tex> равна <tex>n_2</tex>. Тогда <tex>\tau_{\alpha}(\tau) = n_1 + n_2</tex>. Так как <tex> B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}</tex>, то <tex>\tau_{\alpha}(\tau'') = n_2 - 1</tex>. Очевидно, что <tex>\tau_{\gamma}(\tau'') = \tau_{\gamma}(\tau) + n_1</tex>. Тогда ранг <tex>\tau''</tex> равен <tex>\tau_{S'}(\tau'') + 2(\tau_{\gamma}(\tau'') + \tau_{\alpha}(\tau'') + j) \leqslant \tau_{S'}(\tau) + 1 + 2(\tau_{\gamma}(\tau) + n_1 + n_2 - 1 + j)</tex> <tex>= \tau_{S'}(\tau) - 1 + 2(\tau_{\gamma}(\tau) + \tau_{\alpha}(\tau) + j) < r</tex>. Значит, по предположению для <tex>\tau''</tex>, <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex>. Из того, что <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex> и <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex>, по правилу <tex>(2)</tex> <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
 
 
 
3. <tex>\alpha = \varepsilon</tex>.<br/>
 
В этом случае <tex>i = j, \tau_{\alpha}(\tau) = 0, (A \rightarrow \beta) \in P</tex>.<br/>
 
<tex>\tau_{S'}(\tau) \neq 0</tex> т.к. иначе <tex> \gamma = \varepsilon</tex>, следовательно <tex> \tau_{\gamma}(\tau) = 0, i = 0 </tex>, откуда <tex> r = 0</tex>, но <tex>r > 0</tex>.
 
Т.к. <tex>\tau_{S'}(\tau) > 0</tex>, <tex> \exists B, \gamma', \gamma'', \delta', \delta'' : S' \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''</tex>, где <tex>(B \rightarrow \gamma'' A \delta'') \in P</tex>. Рассмотрим набор <tex>\tau' = \langle \gamma'', A \delta'', \gamma', \delta', B, k, j \rangle</tex>, где <tex>k</tex> такое, что <tex>\gamma' \Rightarrow^* a_1...a_{k}, \gamma'' \Rightarrow^* a_{k+1}...a_{j}</tex>.
 
Пусть длина кратчайшего вывода <tex>\gamma' \Rightarrow^*a_{1}...a_{k}</tex> равна <tex>n_1</tex>, а длина кратчайшего вывода <tex> \gamma'' \Rightarrow^* a_{k+1}...a_{j}</tex> равна <tex>n_2</tex>.<br/>
 
Найдём ранг <tex>\tau'</tex>. <tex>\tau_{S'}(\tau') = \tau_{S'}(\tau) - 1, \tau_{\gamma}(\tau') = n_1, \tau_{\alpha}(\tau') = n_2</tex>. <tex>\tau_{\alpha}(\tau) = 0, \tau_{\gamma}(\tau) = n_1 + n_2</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 1</tex>. Значит, по предположению <tex>[B \rightarrow \gamma'' \cdot A \delta'', k] \in I_{j}</tex>, следовательно по правилу <tex>(3)</tex> <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
 
}}
 
 
 
==Пример==
 
Построим список разбора для строки <tex>w = (a + a)</tex> в грамматике со следующими правилами:
 
* <tex>S \rightarrow T + S</tex>;
 
* <tex>S \rightarrow T </tex>;
 
* <tex>T \rightarrow F * T</tex>;
 
* <tex>T \rightarrow F</tex>;
 
* <tex>F \rightarrow ( S )</tex>;
 
* <tex>F \rightarrow a</tex>.
 
 
 
{|
 
|-
 
|
 
 
 
{| class="wikitable"
 
|-
 
!<tex>I_0</tex>
 
|-
 
|
 
{|
 
 
|-
 
|-
!Ситуация !! Из правила
+
!Destination||Netmask||Gateway||Interface||Metric
 
|-
 
|-
|<tex>[S' \rightarrow \cdot S, 0]</tex> || 0
+
|0.0.0.0||0.0.0.0||192.168.0.1||192.168.0.100||10
 
|-
 
|-
|<tex>[S \rightarrow \cdot T + S, 0]</tex> || 3
+
|127.0.0.0||255.0.0.0||127.0.0.1||127.0.0.1||1
 
|-
 
|-
|<tex>[S \rightarrow \cdot T, 0]</tex> || 3
+
|192.168.0.0||255.255.255.0||192.168.0.100||192.168.0.100||10
 
|-
 
|-
|<tex>[T \rightarrow \cdot F * T, 0]</tex> || 3
+
|192.168.0.100||255.255.255.255||127.0.0.1||127.0.0.1||10
 
|-
 
|-
|<tex>[T \rightarrow \cdot F, 0]</tex> || 3
+
|192.168.0.1||255.255.255.255||192.168.0.100||192.168.0.100||10
|-
 
|<tex>[F \rightarrow \cdot ( S ), 0]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot a, 0]</tex> || 3
 
|}
 
 
|}
 
|}
  
||
 
  
{| class="wikitable"
+
==Описание компонентов==
 +
{{Определение
 +
|definition =
 +
Адрес сети назначения (Destination) {{---}} собственно, адрес конечного узла пути передачи сетевого пакета.
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
Маска сети назначения (Netmask) {{---}} битовая маска, определяющая, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети.
 +
В двоичной записи всегда выглядит как множество единиц в начале и нулей в конце.
 +
}}
 +
 
 +
===Пример получения адреса сети===
 +
{| class="simple" border="1"
 
|-
 
|-
!<tex>I_1</tex>
+
! ||Двоичная запись||Десятичная запись
 
|-
 
|-
|
+
|IP-адрес||<tt>11000000 10101000 00000001 00000010</tt> ||192.168.1.2
{|
 
 
|-
 
|-
!Ситуация !! Из правила
+
|Маска||  <tt>11111111 11111111 11111110 00000000</tt> || 255.255.254.0
 
|-
 
|-
|<tex>[F \rightarrow ( \cdot S ), 0]</tex> || 1
+
|Адрес сети||     <tt>11000000 10101000 00000000 00000000</tt> ||192.168.0.0
|-
 
|<tex>[S \rightarrow \cdot T + S, 1]</tex> || 3
 
|-
 
|<tex>[S \rightarrow \cdot T, 1]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F * T, 1]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F, 1]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot ( S ), 1]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot a, 1]</tex> || 3
 
|}
 
 
|}
 
|}
  
||
+
Чтобы вычислить адрес сети, нужно применить логическое ''и'' к адресу и маске.
  
{| class="wikitable"
+
{{Определение
|-
+
|definition =  
!<tex>I_2</tex>
+
Шлюз (Gateaway) {{---}} адрес узла в сети, на который необходимо отправить пакет, следующий до указанного адреса назначения. Шлюзы бывают ''по умолчанию'', тогда значения адреса назначения и маски указываются как 0.0.0.0.
|-
+
}}
|
 
{|
 
|-
 
!Ситуация !! Из правила
 
|-
 
|<tex>[F \rightarrow a \cdot, 1]</tex> || 1
 
|-
 
|<tex>[T \rightarrow F \cdot * T, 1]</tex> || 2
 
|-
 
|<tex>[T \rightarrow F \cdot , 1]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot , 1]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot + S, 1]</tex> || 2
 
|-
 
|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2
 
|}
 
|}
 
  
|-
+
{{Определение
|
+
|definition =
 +
Интерфейс (Interface) указывает, какой локальный интерфейс отвечает за достижение шлюза. Например, шлюз 192.168.0.1 (интернет-маршрутизатор) может быть достижим через локальную сетевую карту, адрес которой 192.168.0.100.
 +
}}
  
{| class="wikitable"
+
{{Определение
|-
+
|definition =  
!<tex>I_3</tex>
+
Метрика (Metric) {{---}} числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние (необязательный параметр).
|-
+
}}
|
 
{|
 
|-
 
!Ситуация !! Из правила
 
|-
 
|<tex>[S \rightarrow T + \cdot S, 1]</tex> || 1
 
|-
 
|<tex>[S \rightarrow \cdot T + S, 3]</tex> || 3
 
|-
 
|<tex>[S \rightarrow \cdot T, 3]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F * T, 3]</tex> || 3
 
|-
 
|<tex>[T \rightarrow \cdot F, 3]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot ( S ), 3]</tex> || 3
 
|-
 
|<tex>[F \rightarrow \cdot a, 3]</tex> || 3
 
|}
 
|}
 
  
||
+
==Принцип действия==
 +
При отправке сетевого пакета, операционная система смотрит, по какому именно маршруту он должен быть отправлен, основываясь на таблице маршрутизации.
 +
Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя и имеют наименьшую метрику.
 +
Если ни один из маршрутов не подходит, пакет уничтожается, а его отправителю возвращается ICMP-сообщение ''No route to host''.
  
{| class="wikitable"
+
Внутри каждого пакета есть поле TTL (Time to live) при каждой пересылке значение уменьшается на единицу, и если оно становится нулем, то пакет выбрасывается.
|-
+
ICMP-сообщение в данном случае ''TTL expired in transit''.
!<tex>I_4</tex>
 
|-
 
|
 
{|
 
|-
 
!Ситуация !! Из правила
 
|-
 
|<tex>[F \rightarrow a \cdot , 3]</tex> || 1
 
|-
 
|<tex>[T \rightarrow F \cdot * T, 3]</tex> || 2
 
|-
 
|<tex>[T \rightarrow F \cdot , 3]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot + S, 3]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot , 3]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T + S \cdot , 1]</tex> || 2
 
|-
 
|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2
 
|}
 
|}
 
  
||
 
  
{| class="wikitable"
+
==Просмотр таблицы маршрутизации==
|-
+
Ниже приведены команды в разных операционных системах, с помощью которых можно посмотреть таблицу маршрутизации
!<tex>I_5</tex>
 
|-
 
|
 
{|
 
|-
 
!Ситуация !! Из правила
 
|-
 
|<tex>[F \rightarrow ( S )\cdot , 0]</tex> || 1
 
|-
 
|<tex>[T \rightarrow F \cdot * T, 0]</tex> || 2
 
|-
 
|<tex>[T \rightarrow F \cdot , 0]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot + S, 0]</tex> || 2
 
|-
 
|<tex>[S \rightarrow T \cdot , 0]</tex> || 2
 
|-
 
|<tex>[S' \rightarrow S \cdot , 0]</tex> || 2
 
|}
 
|}
 
  
|}
+
Windows: '''route print'''
  
Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5</tex>, то <tex>w \in L(G) </tex>.<br>
+
Linux:  '''route -n'''
  
 
==Источники информации==
 
==Источники информации==
 
*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
 
*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
 
* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.
 
* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Алгоритмы разбора]]

Текущая версия на 04:28, 2 января 2017

Определения[править]

Определение:
Таблица маршрутизации — таблица, состоящая из сетевых маршрутов и предназначенная для определения наилучшего пути передачи сетевого пакета.


Определение:
Сетевой маршрут — запись таблицы маршрутизации, содержащая в себе адрес сети назначения (destination), маску сети назначения (netmask), шлюз (gateway), интерфейс (interface) и метрику (metric).


Пример таблицы маршрутизации[править]

Destination Netmask Gateway Interface Metric
0.0.0.0 0.0.0.0 192.168.0.1 192.168.0.100 10
127.0.0.0 255.0.0.0 127.0.0.1 127.0.0.1 1
192.168.0.0 255.255.255.0 192.168.0.100 192.168.0.100 10
192.168.0.100 255.255.255.255 127.0.0.1 127.0.0.1 10
192.168.0.1 255.255.255.255 192.168.0.100 192.168.0.100 10


Описание компонентов[править]

Определение:
Адрес сети назначения (Destination) — собственно, адрес конечного узла пути передачи сетевого пакета.


Определение:
Маска сети назначения (Netmask) — битовая маска, определяющая, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. В двоичной записи всегда выглядит как множество единиц в начале и нулей в конце.


Пример получения адреса сети[править]

Двоичная запись Десятичная запись
IP-адрес 11000000 10101000 00000001 00000010 192.168.1.2
Маска 11111111 11111111 11111110 00000000 255.255.254.0
Адрес сети 11000000 10101000 00000000 00000000 192.168.0.0

Чтобы вычислить адрес сети, нужно применить логическое и к адресу и маске.


Определение:
Шлюз (Gateaway) — адрес узла в сети, на который необходимо отправить пакет, следующий до указанного адреса назначения. Шлюзы бывают по умолчанию, тогда значения адреса назначения и маски указываются как 0.0.0.0.


Определение:
Интерфейс (Interface) указывает, какой локальный интерфейс отвечает за достижение шлюза. Например, шлюз 192.168.0.1 (интернет-маршрутизатор) может быть достижим через локальную сетевую карту, адрес которой 192.168.0.100.


Определение:
Метрика (Metric) — числовой показатель, задающий предпочтительность маршрута. Чем меньше число, тем более предпочтителен маршрут. Интуитивно представляется как расстояние (необязательный параметр).


Принцип действия[править]

При отправке сетевого пакета, операционная система смотрит, по какому именно маршруту он должен быть отправлен, основываясь на таблице маршрутизации. Как правило, выбирается наиболее конкретный (т.е. с наиболее длинной сетевой маской) маршрут из тех, которые соответствуют адресу отправителя и имеют наименьшую метрику. Если ни один из маршрутов не подходит, пакет уничтожается, а его отправителю возвращается ICMP-сообщение No route to host.

Внутри каждого пакета есть поле TTL (Time to live) при каждой пересылке значение уменьшается на единицу, и если оно становится нулем, то пакет выбрасывается. ICMP-сообщение в данном случае TTL expired in transit.


Просмотр таблицы маршрутизации[править]

Ниже приведены команды в разных операционных системах, с помощью которых можно посмотреть таблицу маршрутизации

Windows: route print

Linux: route -n

Источники информации[править]

  • Алексей Сорокин — Алгоритм Эрли
  • Ахо А., Ульман Д.— Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. С. 358 — 364.