igor писал(а):
Вечерком отпишусь (постараюсь).
Выполняю обещанное.
Итак, разбираем упражнение 4.2 из книги Вирта.
Множество абстрактных терминальных символов:{id, string, "=", ".", "|", "(", ")", "[", "]", "{", "}"}
Множество нетерминальных символов:{syntax, production, expression, term, factor}
FIRST(production) = {id}
FOLLOW(production) = {id, string, "=", ".", "|", "(", ")", "[", "]", "{", "}"}
FIRST(expression) = {id, string, "(", "[", "{"}
FOLLOW(expression) = {id, string, "|", "(", ")", "[", "]", "{", "}"}
FIRST(term) = FIRST(expression)
FOLLOW(term) = FOLLOW(expression)
FIRST(factor) = FIRST(term)
FOLLOW(factor) = FOLLOW(term)
Ну, а теперь множество моих комментариев: 1. Так как в правых частях продукций есть нетерминалы, то этот синтаксис относится уже к классу контекстно-свободных языков, а не регулярных. Здесь мы несколько отошли от темы топика, но я думаю, что это не страшно, можно продолжить обсуждение в этой теме (на усмотрение модераторов).
2. Раз мы перешли к рассмотрению
абстрактных терминальных символов, то забудьте про
letter,
digit и прочую лексику. Терминальные символы (абстрактные или элементарные) рассматриваются как неделимые. На всякий случай перечитайте страницу 30, где Вирт говорит о двух этапах определения синтаксиса.
3. Никаких нарушений условий детерминированности в примере 4.2 я не обнаружил. Да, множество FIRST для приведённых нетерминалов пересекаются. Ну и что? Никакого криминала в этом нет.
Попробую последний пункт пояснить. Рассмотрим для определённости нетерминалы
production и
factor. И тот, и другой может начинаться с терминала
id. Но в приведённом синтаксисе нигде не встречается конструкция вида
K = term0 | term1, в которой
production и
factor выступали бы в роли
term0 и
term1, соответственно. То же самое можно сказать про конструкцию вида
K = fac0 fac1 и про любую пару нетерминалов.
А теперь я жду объяснений. В чём был прикол?
Я серьёзно. Может я смотрю на всё это уже замыленными глазами и не вижу очевидное.
Прошу тогда помочь мне увидеть это нарушение условия детерминированности.
PS: Я пошёл дальше, и нарисовал на листочке графы автоматов, соответствующих этому синтаксису. Если кому то интересно, то я мог бы их оцифровать и выложить.