LR(1)-разбор — различия между версиями
Xottab (обсуждение | вклад) (Новая страница: «{{В разработке}}») |
|||
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
| + | ===Отличия от SLR-разбора=== | ||
| + | <wikitex> | ||
| + | Основным отличием LR(1)-разбора от SLR-разбора является использование предпросмотра(англ. lookahead) символов. | ||
| + | |||
| + | Приведём пример, ситуации, в которой SLR-разбор не справится с задачей: | ||
| + | |||
| + | Рассмотрим грамматику вида: | ||
| + | $ | ||
| + | S \to L=R | R \\ | ||
| + | L \to *R | id \\ | ||
| + | R \to L | ||
| + | $ | ||
| + | |||
| + | Покажем её канонический LR(0) - набор: | ||
| + | {| style="background-color:#CCC;margin:0.5px" | ||
| + | !style="background-color:#EEE"| $I_0$ | ||
| + | !style="background-color:#EEE"| $I_1$ | ||
| + | !style="background-color:#EEE"| $I_2$ | ||
| + | !style="background-color:#EEE"| $I_3$ | ||
| + | !style="background-color:#EEE"| $I_4$ | ||
| + | !style="background-color:#EEE"| $I_5$ | ||
| + | !style="background-color:#EEE"| $I_6$ | ||
| + | !style="background-color:#EEE"| $I_7$ | ||
| + | !style="background-color:#EEE"| $I_8$ | ||
| + | !style="background-color:#EEE"| $I_9$ | ||
| + | |- | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ $S' \to \cdot S$ $S \to \cdot L = R$ $S \to \cdot R$ $L \to \cdot * R$ $L \to \cdot id$ $R \to \cdot L$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |style="background-color:#FFF;padding:2px 30px"| $A \to B$ | ||
| + | |} | ||
| + | </wikitex> | ||
Версия 18:36, 15 июня 2015
Эта статья находится в разработке!
Отличия от SLR-разбора
<wikitex> Основным отличием LR(1)-разбора от SLR-разбора является использование предпросмотра(англ. lookahead) символов.
Приведём пример, ситуации, в которой SLR-разбор не справится с задачей:
Рассмотрим грамматику вида: $ S \to L=R | R \\ L \to *R | id \\ R \to L $
Покажем её канонический LR(0) - набор:
| $I_0$ | $I_1$ | $I_2$ | $I_3$ | $I_4$ | $I_5$ | $I_6$ | $I_7$ | $I_8$ | $I_9$ |
|---|---|---|---|---|---|---|---|---|---|
| $A \to B$ $S' \to \cdot S$ $S \to \cdot L = R$ $S \to \cdot R$ $L \to \cdot * R$ $L \to \cdot id$ $R \to \cdot L$ | $A \to B$ | $A \to B$ | $A \to B$ | $A \to B$ | $A \to B$ | $A \to B$ | $A \to B$ | $A \to B$ | $A \to B$ |
</wikitex>
