О границах лексики, синтаксиса и семантики

Теперь, когда мы разобрались в деталях процесса трансляции, можно со знанием дела провести границы между различными фазами трансляции и дать сравнительную оценку применяемым в них формальным системам. Напомним, что каждая фаза анализа программы имеет свою формальную систему представления (по сути, программирования):

· лексический анализ – конечные автоматы;

· синтаксический анализ – формальные грамматики;

· семантический анализ – уникальная внутренняя модель данных, создаваемая компьютерной программой (по формальной сути – формальная система, эквивалентная машине Тьюринга).

Любой формальный аппарат имеет определенные границы применимости, выше которых «ему не дано подняться» в силу его собственной структуры и сложности. То есть определенные идеи в такой формальной системе просто не представимы.Это свойство системы можно назвать моделирующей способностью. С другой стороны, для каждой формальной системы существуют проблемы, которые разрешимы в них в общем виде: для любой такой системы существует формальный метод (алгоритм) их решения. Это свойство называется разрешимостью. Очевидно, чем больше моделирующая способность системы, тем меньше в ней разрешимых проблем, то есть тем меньше она может быть подвержена автоматизации и программной реализации. Конечные автоматы обладают в этом ряду самой низкой моделирующей способностью и самой высокой разрешимостью. Формальные грамматики занимают в этом ряду промежуточное положение: они позволяют описывать достаточно сложные явления, но, в то же время, имеют возможности для алгоритмического разрешения возникающих в них проблем.

Легко заметить, что каждый следующий этап анализа программы базируется на более сложной формальной модели (с большей моделирующей способностью и меньшей разрешимостью). Отсюда следует, что любая фаза анализа может быть реализована средствами последующего уровня и является ее частным случаем. Рассмотрим этот тезис подробнее.