Методические указания (1114907), страница 5
Текст из файла (страница 5)
α2=*Е β2=i
Е = β1E’/ β2E’
E’= α1E’/ α2E’/ε
E→ (E)E’
E → iE’
E’ → +EE’
E’ → *EE’
E’ → ε
-
E→TE’
-
E’ → +TE’
-
E’ → ε
-
T →FT’
-
T’ → *FT’
-
T’ → ε
-
F → (E)
-
F → d
-
Определим значение функций FIRST и FOLLOW для разработанной грамматики.
FIRST FOLLOW
E={id, ( } E={$, ) }
E’={+, ε } E’ = {$, ) }
T = {id, ( } T = {+, $, ) }
T’ = {*, ε } T’ = {+, $, ) }
F = {id, ( } F = {*, $, ), + }
-
Построим таблицу предиктивного анализатора. “Synch” указывает синхронизирующие токены, полученные из множества FOLLOW соответствующего терминала.
| id | + | * | ( | ) | $ | |
| E | E → TE’ | E →TE’ | Synch | Synch | ||
| E’ | E’ → +TE’ | E’ → ε | E’ → ε | |||
| T | T →FT’ | Synch | T → FT’ | Synch | Synch | |
| T’ | T’ → ε | T’ →FT’ | T’ → ε | T’ → ε | ||
| F | F → id | Synch | Synch | F → (E) | Synch | Synch |
-
Проверим правильность построения на трех примерах.
Правильный: id*(id+id)$
| $E $E’T $E’T’F $E’T’id $E’T’ $E’T’F* $E’T’F $E’T’)E( $E’T’)E $E’T’)E’T $E’T’)E’T’F $E’T’)E’T’id $E’T’)E’T’ $E’T’)E’ $E’T’)E’T+ $E’T’)E’T $E’T’)E’T’F $E’T’)E’T’id $E’T’) $E’T’ $E’ $ | id*(id+id)$ id*(id+id)$ id*(id+id)$ id*(id+id)$ *(id+id)$ *(id+id)$ (id+id)$ (id+id)$ id+id)$ id+id)$ id+id)$ id+id)$ +id)$ +id)$ id)$ id)$ id)$ )$ )$ $ $ $ |
Строка разложена
Неправильный: )id*+id$
| $E $E $E’T $E’T’F $E’T’id $E’T’ $E’T’F* $E’T’F $E’T’ $E’ $E’T+ $E’T $E’T’F $E’T’id $E’T’ $E’ $ | )id*+id$ Id*+id$ Id*+id$ Id*+id$ Id*+id$ *+id$ *+id$ +id$ +id$ +id$ +id$ id$ id$ id$ $ $ $ | Ошибка, пропускаем «)» Id € FIRST(E) Ошибка, М[F,+] = Synch F снимаем со стека |
Разложили строку с обработкой ошибок
Неправильный: id+(*id)$
| $E $E’T $E’T’F $E’T’id $E’T’ $E’ $E’T+ $E’T $E’T’F $E’T’)E( $E’T’)E $E’T’)E $E’T’)E’T $E’T’)E’T’F $E’T’)E’T’ $E’T’) $E’T’ $E’ $ | id+(*id)$ id+(*id)$ id+(*id)$ id+(*id)$ +(*id)$ +(*id)$ +(*id)$ (*id)$ (*id)$ (*id)$ *id)$ Id)$ Id)$ Id)$ )$ )$ $ $ $ | Ошибка, пропускаем «*» Id € FIRST(E) |
Разложили строку с обработкой ошибки
Задача «Построение КЗ-грамматики»
Теоретическая часть
Контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики.
Определение: Контекстно-зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 1 по иерархии Хомского), у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами. Для грамматики G(VT,VN,P,S), V=VT∪VN все правила имеют вид:
-
αAβ→αγβ, где α, β∈V*, γ∈V+, A∈VN. Такие грамматики относят к контекстно-зависимым.
-
α→β, где α, β∈V+, |α|≤|β|. Такие грамматики относят к неукорачивающим.
Эти классы грамматик эквивалентны. Могут использоваться при анализе текстов на естественных языках, однако при построении компиляторов практически не используются в силу своей сложности. Для контекстно-зависимых грамматик доказано утверждение: по некоторому алгоритму за конечное число шагов можно установить, принадлежит цепочка терминальных символов данному языку или нет.
Определение: НС-грамматикой (или грамматикой непосредственно-составляющих) называется грамматика, правила которой имеют вид aAb ® agb, где A О N, a, b О V*, g О V +. Цепочки a и b задают контекст, в котором A можно заменять на g.
Т е о р е м а. Контекстно-зависимые языки рекурсивны.
Доказательство. Пусть задана неукорачивающая грамматика G и произвольная цепочка a О T +. Чтобы проверить, принадлежит ли a языку L(G), достаточно построить множество всех цепочек из V +, не превосходящих по длине a, и построить из этих цепочек последовательности, в которых цепочки не повторяются, упорядочены по длине (каждая следующая не короче предыдущей) и первая цепочка всегда S, а последняя - a. Таких последовательностей конечное множество. Остаётся проверить каждую из них, не является ли она выводом в G. Такая проверка завершается за конечное число шагов. Если вывод найден, то a О L(G), в противном случае - нет.
Отсюда следует, что любой рекурсивно перечислимый, но нерекурсивный язык (например, множество программ самоприменимых машин Тьюринга) является языком типа 0, но не языком типа 1.
Контекстно-зависимые грамматики содержат важный подкласс НС-грамматик.
Ниже перечислены некоторые свойства контекстно-зависимых грамматик:
-
Все цепочки, последовательно выводимые из начального символа, имеют длину не меньшую, чем предыдущая, поскольку каждое правило должно оставлять длину цепочки неизменной или увеличивать ее1.
-
Контекстно-зависимые грамматики генерируют цепочки, для хранения которых требуется фиксированный объем памяти. Например, такие грамматики способны распознавать цепочки вида anbncn, что не может сделать контекстно-свободная грамматика.
-
Контекстно-зависимые грамматики обычно слишком сложны, чтобы быть практически полезными для моделирования языков программирования.
Контекстно-зависимые грамматики позволяют определять языковые структуры, не охваченные контекстно-независимыми грамматиками, но их практическое применение при создании анализаторов сопряжено с некоторыми сложностями следующего характера.
-
При использовании контекстно-зависимых грамматик резко возрастает количество правил и нетерминальных символов. Представьте себе сложность контекстно-зависимой грамматики, необходимой для описания форм числа (единственного и множественного) и лица (первого, второго и третьего), а также всех остальных форм соглашений, принятых в английском языке.
-
В контекстно-зависимых грамматиках размывается структура фраз языка, столь ясно представимая с помощью контекстно-независимых правил.
-
При попытке описать более сложные соглашения и обеспечить семантическую согласованность самой грамматики теряются многие преимущества разделения синтаксического и семантического компонентов языка.
-
Контекстно-зависимые грамматики не решают проблемы построения семантического представления значения текста. Анализатор, который просто принимает или отвергает предложение, никому не нужен. Он должен возвращать эффективное представление семантического значения предложений.
Пример КЗ-грамматики:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
