Разработка компиляторов
Свойства контекстно-свободных грамматик
Весь процесс синтаксическо анализа можно упрощенно рассматривать как определение принадлежности входной цепочки заданной контекстно-свободной грамматике (в дальнейшем, мы будем использовать сокрещение "КС-грамматика"). Однако надо оговориться, что такая формулировка сильно упрощена, так как процесс вывода цепочки по грамматике нетривиален и к тому же усложняется тем фактом, что далеко не все свойства языков программирования могут быть описаны КС-грамматиками.
Кроме того, КС-грамматики зачастую страдают от проблемы неоднозначности. Грамматика называется неоднозначной (ambiguous grammar) , если существует, по крайней мере, одна выводимая в этой грамматике цепочка, для которой существует более одного вывода. Например, можно рассмотреть язык G0, описывающий простые арифметические выражения со сложением и умножением, и задаваемый КС-грамматикой следующим набором правил: . Эта грамматика неоднозначна, так как в ней существует два различных вывода для выражения вида a+a+a или a*a+a (левосторонний и правосторонний вывод).
В данном случае проблему неоднозначности можно решить путем преобразования грамматики к эквивалентной грамматике . Но и у этой грамматики есть серьезный недостаток: операции + и * имеют один и тот же приоритет, и потому выражение a+a*a будет трактоваться как (a+a)*a . Для того, чтобы получить правильный приоритет операций, необходимо продолжить преобразование грамматик и перейти к следующему набору правил: . Более подробно проблемы, связанные с неоднозначными грамматиками, будут рассмотрены в лекции 8.
