О границах лексики, синтаксиса и семантики
4.3. О границах лексики, синтаксиса и семантики
http://ermak.cs.nstu.ru/trans/Trans431.htm
http://ermak.cs.nstu.ru/trans/Trans432.htm
http://ermak.cs.nstu.ru/trans/Trans433.htm
Напомним, что каждая фаза анализа программы имеет свою формальную систему представления (по сути, программирования):
лексический анализ - конечные автоматы;
синтаксический анализ - формальные грамматики;
семантический анализ - уникальная внутренняя модель данных, создаваемая компьютерной программой (по формальной сути - формальная система, эквивалентная машине Тьюринга).
Любой формальный аппарат имеет определенные границы применимости, выше которых «ему не дано подняться» в силу его собственной структуры и сложности.
То есть определенные идеи в такой формальной системе просто не представимы.
Это свойство системы можно назвать моделирующей способностью.
С другой стороны, для каждой формальной системы существуют проблемы, которые разрешимы в них в общем виде: для любой такой системы существует формальный метод (алгоритм) их решения.
Это свойство называется разрешимостью.
(*) Очевидно, чем больше моделирующая способность системы, тем меньше в ней разрешимых проблем, то есть тем меньше она может быть подвержена автоматизации и программной реализации.
Конечные автоматы обладают в этом ряду самой низкой моделирующей способностью и самой высокой разрешимостью.
Формальные грамматики занимают в этом ряду промежуточное положение: они позволяют описывать достаточно сложные явления, но, в то же время, имеют возможности для алгоритмического разрешения возникающих в них проблем.
---
(мой комментарий в комментах)
http://ermak.cs.nstu.ru/trans/Trans431.htm
http://ermak.cs.nstu.ru/trans/Trans432.htm
http://ermak.cs.nstu.ru/trans/Trans433.htm
Напомним, что каждая фаза анализа программы имеет свою формальную систему представления (по сути, программирования):
лексический анализ - конечные автоматы;
синтаксический анализ - формальные грамматики;
семантический анализ - уникальная внутренняя модель данных, создаваемая компьютерной программой (по формальной сути - формальная система, эквивалентная машине Тьюринга).
Любой формальный аппарат имеет определенные границы применимости, выше которых «ему не дано подняться» в силу его собственной структуры и сложности.
То есть определенные идеи в такой формальной системе просто не представимы.
Это свойство системы можно назвать моделирующей способностью.
С другой стороны, для каждой формальной системы существуют проблемы, которые разрешимы в них в общем виде: для любой такой системы существует формальный метод (алгоритм) их решения.
Это свойство называется разрешимостью.
(*) Очевидно, чем больше моделирующая способность системы, тем меньше в ней разрешимых проблем, то есть тем меньше она может быть подвержена автоматизации и программной реализации.
Конечные автоматы обладают в этом ряду самой низкой моделирующей способностью и самой высокой разрешимостью.
Формальные грамматики занимают в этом ряду промежуточное положение: они позволяют описывать достаточно сложные явления, но, в то же время, имеют возможности для алгоритмического разрешения возникающих в них проблем.
---
(мой комментарий в комментах)