LL(k)-грамматики, множества FIRST и FOLLOW — различия между версиями
Shersh (обсуждение | вклад) (→FIRST и FOLLOW) |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 6 участников) | |||
Строка 10: | Строка 10: | ||
* <tex> S \Rightarrow^* p A \beta \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi </tex> | * <tex> S \Rightarrow^* p A \beta \Rightarrow p \alpha' \beta \Rightarrow^* p y \xi </tex> | ||
где <tex> p </tex> и <tex> y </tex> {{---}} цепочки из терминалов, уже разобранная часть слова <tex> w </tex>, <tex> A </tex> {{---}} нетерминал грамматики, в которой есть правила <tex> A \to \alpha </tex> и <tex> A \to \alpha' </tex>, причём <tex> \alpha, \alpha', \beta, \eta, \xi </tex> {{---}} последовательности из терминалов и нетерминалов.<br> | где <tex> p </tex> и <tex> y </tex> {{---}} цепочки из терминалов, уже разобранная часть слова <tex> w </tex>, <tex> A </tex> {{---}} нетерминал грамматики, в которой есть правила <tex> A \to \alpha </tex> и <tex> A \to \alpha' </tex>, причём <tex> \alpha, \alpha', \beta, \eta, \xi </tex> {{---}} последовательности из терминалов и нетерминалов.<br> | ||
− | + | Если из выполнения условий, что <tex> |y| = k </tex> или <tex> |y| < k, \eta = \xi = \varepsilon </tex>, следует равенство <tex> \alpha = \alpha' </tex>, то <tex> \Gamma </tex> называется '''LL(k)-грамматикой'''. | |
}} | }} | ||
LL(1)-грамматика является частным случаем. Её определение почти такое же, только вместо строки <tex> y </tex> один символ <tex> c \in \Sigma \cup \{\varepsilon\} </tex>. | LL(1)-грамматика является частным случаем. Её определение почти такое же, только вместо строки <tex> y </tex> один символ <tex> c \in \Sigma \cup \{\varepsilon\} </tex>. | ||
Строка 17: | Строка 17: | ||
== FIRST и FOLLOW == | == FIRST и FOLLOW == | ||
− | Ключевую роль в построении парсеров для LL(1)-грамматик | + | Ключевую роль в построении парсеров для LL(1)-грамматик играют множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex>. |
Пусть <tex> c </tex> {{---}} символ из алфавита <tex> \Sigma </tex>, <tex> \alpha,\ \beta </tex> {{---}} строки из нетерминалов и терминалов (возможно пустые), <tex> S,\ A </tex> {{---}} нетерминалы грамматики (начальный и произвольный соответственно), <tex> \$ </tex> {{---}} символ окончания слова. Тогда определим <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> следующим образом: | Пусть <tex> c </tex> {{---}} символ из алфавита <tex> \Sigma </tex>, <tex> \alpha,\ \beta </tex> {{---}} строки из нетерминалов и терминалов (возможно пустые), <tex> S,\ A </tex> {{---}} нетерминалы грамматики (начальный и произвольный соответственно), <tex> \$ </tex> {{---}} символ окончания слова. Тогда определим <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> следующим образом: | ||
Строка 23: | Строка 23: | ||
|id=deffirst | |id=deffirst | ||
|definition= | |definition= | ||
− | <tex> \mathrm{FIRST}( | + | <tex> \mathrm{FIRST}(A) = \{c \mid A \Rightarrow^* c \beta \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \} </tex> |
}} | }} | ||
{{Определение | {{Определение | ||
Строка 30: | Строка 30: | ||
<tex> \mathrm{FOLLOW}(A) = \{c \mid S \Rightarrow^* \alpha A c \beta \} \cup \{ \$ \ \mathrm{if}\ S \Rightarrow^* \alpha A \} </tex> | <tex> \mathrm{FOLLOW}(A) = \{c \mid S \Rightarrow^* \alpha A c \beta \} \cup \{ \$ \ \mathrm{if}\ S \Rightarrow^* \alpha A \} </tex> | ||
}} | }} | ||
− | Другими словами, <tex> \mathrm{FIRST}( | + | Другими словами, <tex> \mathrm{FIRST}(A) </tex> {{---}} все символы (терминалы), с которых могут начинаться всевозможные выводы из <tex> \alpha </tex>, а <tex> \mathrm{FOLLOW}(A) </tex> {{---}} всевозможные символы, которые встречаются после нетерминала <tex> A </tex> во всех [[Удаление бесполезных символов из грамматики | небесполезных]] правилах грамматики. |
+ | |||
+ | '''Замечание:''' более общим случаем множества <tex> \mathrm{FIRST} </tex> является множество <tex> \mathrm{FIRST}_k </tex>, однако в данном конспекте оно не используется. | ||
+ | {{Определение | ||
+ | |id=deffirstk | ||
+ | |definition= | ||
+ | <tex> \mathrm{FIRST}_k(A) = \{w \mid A \Rightarrow^* w \beta,\ |w| \leqslant k \} \cup \{ \varepsilon\ \mathrm{if}\ A \Rightarrow^* \varepsilon \} </tex> | ||
+ | }} | ||
=== Примеры === | === Примеры === | ||
Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей. | Множества <tex> \mathrm{FIRST} </tex> и <tex> \mathrm{FOLLOW} </tex> могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей. | ||
Строка 42: | Строка 49: | ||
!style="background-color:#EEE"| FOLLOW | !style="background-color:#EEE"| FOLLOW | ||
|- | |- | ||
− | |style="background-color:#FFF;padding:2px 30px"| A | + | |style="background-color:#FFF;padding:2px 30px"| <tex>A</tex> |
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex> | |style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex> | ||
|style="background-color:#FFF;padding:2px 40px"| <tex>\{\ ),\ \$\ \} </tex> | |style="background-color:#FFF;padding:2px 40px"| <tex>\{\ ),\ \$\ \} </tex> | ||
|- | |- | ||
− | |style="background-color:#FFF;padding:2px 30px"| B | + | |style="background-color:#FFF;padding:2px 30px"| <tex>B</tex> |
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex> | |style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ \varepsilon\ \} </tex> | ||
|style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ ),\ \$\ \} </tex> | |style="background-color:#FFF;padding:2px 30px"| <tex>\{\ (,\ ),\ \$\ \} </tex> | ||
Строка 70: | Строка 77: | ||
<tex> \Rightarrow </tex> | <tex> \Rightarrow </tex> | ||
− | Предположим, что есть два различных правила <tex> A \to \alpha </tex> и <tex> A \to \beta </tex> таких, что <tex> c \in \mathrm{FIRST}( | + | Предположим, что есть два различных правила <tex> A \to \alpha </tex> и <tex> A \to \beta </tex> таких, что <tex> c \in \mathrm{FIRST}(A) \cap \mathrm{FIRST}(\beta) </tex>. Тогда: |
* <tex> S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma </tex> | * <tex> S \Rightarrow^* p A \gamma \Rightarrow p \alpha \gamma \Rightarrow^* p c \alpha' \gamma </tex> | ||
* <tex> S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma </tex> | * <tex> S \Rightarrow^* p A \gamma \Rightarrow p \beta \gamma \Rightarrow^* p c \beta' \gamma </tex> | ||
Строка 103: | Строка 110: | ||
<tex> A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m </tex> | <tex> A \to \alpha \beta_1 \mid \ldots \mid \alpha \beta_n \mid \gamma_1 \mid \ldots \mid \gamma_m </tex> | ||
− | Причём <tex> \alpha \ne \varepsilon </tex>, а наибольший общий префикс <tex> \alpha </tex> и <tex> \gamma_i | + | Причём <tex> \alpha \ne \varepsilon </tex>, а наибольший общий префикс <tex> \alpha </tex> и <tex> \gamma_i\ (1 \leqslant i \leqslant m</tex>) равен <tex> \varepsilon </tex>. Тогда изменим грамматику следующим образом, введя новый нетерминал <tex> A' </tex>: |
<tex> A \to \alpha A' \mid \gamma_1 \mid \ldots \mid \gamma_m </tex> | <tex> A \to \alpha A' \mid \gamma_1 \mid \ldots \mid \gamma_m </tex> | ||
Строка 109: | Строка 116: | ||
<tex> A' \to \beta_1 \mid \ldots \mid \beta_n </tex> | <tex> A' \to \beta_1 \mid \ldots \mid \beta_n </tex> | ||
− | Алгоритм завершится, когда в грамматике не будет правого ветвления. Он | + | Алгоритм завершится, когда в грамматике не будет правого ветвления. Он отработает конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным. |
− | '''Замечание:''' отсутствие левой рекурсии и правого ветвления в грамматике не является | + | '''Замечание:''' отсутствие левой рекурсии и правого ветвления в грамматике не является достаточным условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой. |
== См. также == | == См. также == |
Текущая версия на 19:35, 4 сентября 2022
Наибольший интерес в построении синтаксических анализаторов (парсеров) представляют LL(1)-грамматики, так как для них возможно построение нисходящих парсеров без возврата, то есть без корректировки выбранных правил в грамматике. LL(1)-грамматики являются подмножеством КС-грамматик. Однако для достаточно большого количества формальных языков можно построить LL(1)-грамматику, например, для языка арифметических выражений и даже для некоторых языков программирования, в частности можно и для языка Java.
LL(k)-грамматика
Дадим теперь формально определение LL(k)-грамматики.
Определение: |
Пусть где | — КС-грамматика. Рассмотрим два произвольных левосторонних вывода слова в этой грамматике:
LL(1)-грамматика является частным случаем. Её определение почти такое же, только вместо строки
один символ .Неформально это означает, что, посмотрев на очередной символ после уже выведенной части слова, можно однозначно определить, какое правило из грамматики выбрать.
FIRST и FOLLOW
Ключевую роль в построении парсеров для LL(1)-грамматик играют множества
и .Пусть
— символ из алфавита , — строки из нетерминалов и терминалов (возможно пустые), — нетерминалы грамматики (начальный и произвольный соответственно), — символ окончания слова. Тогда определим и следующим образом:Определение: |
Определение: |
Другими словами, небесполезных правилах грамматики.
— все символы (терминалы), с которых могут начинаться всевозможные выводы из , а — всевозможные символы, которые встречаются после нетерминала во всехЗамечание: более общим случаем множества
является множество , однако в данном конспекте оно не используется.Определение: |
Примеры
Множества
и могут отличаться даже для одной грамматики, если она задана разными правилами. Рассмотрим пример двух различных грамматик для языка правильных скобочных последовательностей.Правило | FIRST | FOLLOW |
---|---|---|
Теорема о связи LL(1)-грамматики с множествами FIRST и FOLLOW
Далее будет показано, как множества
и связаны с понятием LL(1)-грамматики.Теорема: |
Доказательство: |
Предположим, что данная грамматика не будет LL(1)-грамматикой. Значит, у какого-то слова существует два различных левосторонних вывода.Но это противоречит тому, что .Аналогично проверятся второе условие. Если, например, , то , и
Предположим, что есть два различных правила и таких, что . Тогда:Последний переход можно совершить, так как определения следует, что . Это противоречит предположению, что и — различные правила. Второе условие проверяется аналогичным образом. лежит в пересечении множеств двух правил вывода. Так как грамматика является LL(1)-грамматикой, то из |
Следствия
Сформулируем несколько важных cледствий из теоремы.
Левая рекурсия
Утверждение (1): |
Грамматика cодержит левую рекурсию не является LL(1)-грамматикой. |
Если грамматика содержит левую рекурсию, значит, в ней существует какой-то нетерминал Тогда понятно, что с правилами , где — строка из терминалов и нетерминалов, не начинающаяся с . , и это противоречит первому условию теоремы. |
Чтобы избавиться от левой рекурсии, можно воспользоваться алгоритмом устранения левой рекурсии.
Левая факторизация
Утверждение (2): |
Грамматика cодержит правое ветвление не является LL(1)-грамматикой. |
Наличие в грамматике правого ветвления означает, что существует правило Очевидно, что . . Поэтому грамматика не будет LL(1)-грамматикой по первому условию теоремы. |
Алгоритм устранения правого ветвленения
Чтобы избавиться от правого ветвления, нужно воспользоваться алгоритмом левой факторизации. Его суть заключается в следующем: для каждого нетерминала
ищем самый длинный префикс, общий для двух или более правил вывода из . Важно, чтобы как можно больше строк имело общий префикс, и можно было вынести части правил после общего префикса в отдельный нетерминал. Более формально, рассмотрим правила
Причём
, а наибольший общий префикс и ) равен . Тогда изменим грамматику следующим образом, введя новый нетерминал :
Алгоритм завершится, когда в грамматике не будет правого ветвления. Он отработает конечное число шагов, так как каждый раз длина правой части правил уменьшается ходя бы на единицу, а тривиальные префиксы мы не рассматриваем. К тому же, алгоритм не меняет язык грамматики, следовательно, является корректным.
Замечание: отсутствие левой рекурсии и правого ветвления в грамматике не является достаточным условием того, что она будет LL(1)-грамматикой. После их устранения грамматика всё ещё может остаться не LL(1)-грамматикой.
См. также
Источники информации
- Wikipedia — LL grammar
- LL(k)-грамматики и трансляция
- Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. ISBN 5-8459-0189-8