|
|
| (не показано 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> ∪= <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> ∪= <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> ∪= <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. |
| | + | |
| | + | [[Категория: Теория формальных языков]] |
| | + | [[Категория: Контекстно-свободные грамматики]] |
| | + | [[Категория: Алгоритмы разбора]] |
