Могу ли я преобразовать любую грамматику в грамматику приоритета оператора?

Question

Какую грамматику можно реализовать с помощью анализа приоритета оператора?

Answer 1

Если вы спрашиваете, можете ли вы изменить операторный приоритет языка с помощью грамматики, тогда ответ: да, конечно.

Если вы спрашиваете, можете ли вы проанализировать «типичную» контекстно-свободную грамматику, используя метод синтаксического разбора оператора сверху вниз, то ответ - нет. НО вы можете смешать их. Хорошая статья, посвященная анализу Pratt, которая должна дать вам некоторую информацию о применении этого к анализатору рекурсивного спуска: http://effbot.org/zone/simple-top-down-parsing.htm

Answer 2

Это отличный вопрос, на который я отвечаю: да. Это выглядит как проблема с двойной звездой (# 4.21) в четвертой главе «Хопкрофт и Ульман» текст по вычислимости и формальным языкам. Ответ (обобщенное доказательство по конструкции) также предоставляется. Очень кратко, он предполагает предварительное преобразование в сокращенный GNF, из которого окончательный Строительство выполняется для удаления смежных нетерминалов. Не самый эффективная конструкция, но она работает (если вы можете следовать аналогичному режиму для преобразования в CNF и GNF ранее). Надеюсь, это поможет!