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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Просмотр таблицы маршрутизации)
 
(не показано 37 промежуточных версий 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>I_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <tex>I_j</tex> используются <tex>I_0, \ldots, I_{j}</tex> (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).
+
{| border="1"
 
 
Алгоритм основывается на следующих трёх правилах:
 
# Если <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex> (где <tex>a_j</tex> — <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i] \in I_j</tex>.
 
# Если <tex>[B \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>.
 
 
 
<tex>I_0</tex> = <tex>\lbrace [S' \rightarrow \cdot S, 0] \rbrace</tex> # Правило (0) — инициализация
 
useful_loop(0)
 
 
for j = 1..n
 
    for <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex>
 
        <tex>I_j</tex> &cup;= <tex>\{ [A \rightarrow \alpha a_{j} \cdot \beta, i] \}</tex> # Правило (1)
 
    useful_loop(j)
 
 
 
function useful_loop(j):
 
    do
 
        for <tex>[B \rightarrow \eta \cdot , k] \in I_j</tex>
 
            for <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_{k}</tex>
 
                <tex>I_j</tex> &cup;= <tex>\lbrace [A \rightarrow \alpha B \cdot \beta, i] \rbrace</tex> # Правило (2)
 
           
 
        for <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j</tex>
 
            for <tex>\beta : (A \rightarrow \beta) \in P</tex>
 
                <tex>I_j</tex> &cup;= <tex>\lbrace [A \rightarrow \cdot \beta, j] \rbrace</tex> # Правило (3)
 
    while на данной итерации какое-то множество изменилось
 
 
 
==Корректность алгоритма==
 
{{Теорема
 
|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
{|
 
 
|-
 
|-
!Ситуация !! Из правила
+
|0.0.0.0||0.0.0.0||192.168.0.1||192.168.0.100||10
 
|-
 
|-
|<tex>[S' \rightarrow \cdot S, 0]</tex> || 0
+
|127.0.0.0||255.0.0.0||127.0.0.1||127.0.0.1||1
 
|-
 
|-
|<tex>[S \rightarrow \cdot T + S, 0]</tex> || 3
+
|192.168.0.0||255.255.255.0||192.168.0.100||192.168.0.100||10
 
|-
 
|-
|<tex>[S \rightarrow \cdot 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 * T, 0]</tex> || 3
+
|192.168.0.1||255.255.255.255||192.168.0.100||192.168.0.100||10
|-
 
|<tex>[T \rightarrow \cdot F, 0]</tex> || 3
 
|-
 
|<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'''
  
 
==Источники информации==
 
==Источники информации==
* Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---}} The Art of Computer Programming. Vol. 3. Sorting and Searching.
 
*[http://en.wikipedia.org/wiki/Interpolation_search Wikipedia {{---}} Interpolation search]
 
 
*[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.