Построение FIRST и FOLLOW — различия между версиями
Shersh (обсуждение | вклад) (→Конструирование FOLLOW для арифметических выражений) |
Shersh (обсуждение | вклад) (→Псевдокод) |
||
Строка 28: | Строка 28: | ||
'''for''' <tex>( A \to \alpha \in P )</tex> | '''for''' <tex>( A \to \alpha \in P )</tex> | ||
<tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex> | <tex> \mathrm{FIRST}[A]\ \cup =\ \mathrm{FIRST}(\alpha) </tex> | ||
− | + | '''if''' <tex> \mathrm{FIRST}[A] </tex> изменился | |
+ | changed = ''true'' | ||
</code> | </code> | ||
{{Утверждение | {{Утверждение |
Версия 13:53, 29 июня 2014
Для данной LL(1)-грамматики оказывается возможным построить нисходящий рекурсивный парсер, который по слову сможет построить его дерево разбора в грамматике или сказать, что слово не принадлежит языку грамматики. Более того, становится возможной даже автоматическая генерация парсеров для таких грамматик[1].
Чтобы написать парсер для LL(1)-грамматики, необходимо построить множества и , после чего по ним можно составить таблицу синтаксического анализатора.
Содержание
Построение FIRST
Для построения
воспользуемся несколькими леммами, которые следуют прямо из определения. Пусть — цепочки из терминалов и нетерминалов, — символ из алфавита.Лемма (1): |
Данная лемма означает, что в множество
правила , где — произвольный терминал или нетерминал, — нужно добавить , если для всех верно, что .Лемма (2): |
Псевдокод
Алгоритм строит для каждого терминала грамматики бесполезных символов. Изначально каждое правило отображается в пустое множество.
function constructFIRST(): forchanged = true while changed changed = false for if изменился changed = true
Утверждение: |
Приведённый алгоритм правильно строит множество для данной грамматики. |
Алгоритм на каждом шаге использует леммы, чтобы построить списки для каждого нетерминала. Поэтому он добавит только те терминалы, которые на самом деле лежат в .
Покажем, что алгоритм найдёт все символы из множества .Предположим, что в грамматике возможен вывод , и алгоритм не включил в . Докажем индукцией по числу шагов , что этого не может быть.Пусть за шагов алгоритм добавит символы в множество для каждого нетерминала , если . База индукции для числа шагов верна, если считать, что для всех терминалов нам известны . Если алгоритм корректно отрабатывает на -ом шаге, то он правильно отработает их на -ом шаге, потому что
Для леммам, следовательно, переход доказан. К тому же, алгоритм завершится за конечное число шагов, так как в алгоритм правильно построил по предположению индукции, а для он правильно построит по для каждого нетерминала не может добавиться больше символов, чем есть в алфавите. |
Построение FOLLOW
Сформулируем похожие утверждения для построения
.Лемма (3): |
Для каждого правила верно, что |
Лемма (4): |
Для каждого правила вида или верно, что |
Псевдокод
Реализация построения лемм. Для алгоритма сначала требуется выполнить построение для грамматики.
function constructFOLLOW(): for// в стартовый терминал помещается символ конца строки changed = true while changed changed = false for for if changed = true if изменился
Корректность данного алгоритма доказывается точно так же, как и корректность алгоритма конструирования
.Пример
Рассмотрим, как будут строиться множества
и на примере грамматики арифметических выражений. Ограничимся только операциями сложения, умножения и наличием скобок. Числа будем обозначать одной буквой для простоты. Интуитивная грамматики для арифметических выражений выглядит следующим образом:
Однако данная грамматика содержит левую рекурсию, правое ветвление и является неоднозначной. Чтобы избавиться от данных проблем неявно, можно придумать более удачную грамматику для рассматриваемого языка. Например, она может иметь следующий вид:
Данная грамматика содержит только правое ветвление, от которого можно избавиться левой факторизацией, после чего грамматика пример вид:
А затем для простоты анализирования раскрыть нетерминалы
и в правилах для и .
Конструирование FIRST для арифметических выражений
Рассмотрим, как будет выглядеть множество
после очередной итераций цикла .После 1ой итерации:
Правило | FIRST |
---|---|
После 2ой итерации:
Правило | FIRST |
---|---|
После 3eй итерации:
Правило | FIRST |
---|---|
Далее никаких изменений происходить не будет, и на этом алгоритм завершит свою работу.
Конструирование FOLLOW для арифметических выражений
Теперь рассмотрим построение таблицы
после каждой итераций цикла . Стартовым нетерминалом будет , поэтому в него добавим сразу .До цикла while:
Правило | FOLLOW |
---|---|
После 1ой итерации:
Правило | FOLLOW |
---|---|
После 2ой итерации:
Правило | FOLLOW |
---|---|
После 3ей итерации:
Правило | FOLLOW |
---|---|
На этом построение множества
для грамматики закончится.Итоговая таблица
Правило | FIRST | FOLLOW |
---|---|---|
См. также
Примечания
Источники информации
- Wikipedia — LL parser
- СitForum — Синтаксический анализ
- Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. ISBN 5-8459-0189-8