Разработка компиляторов
Детерминированные МП-автоматы
МП-автоматы обладают одним существенным недостатком - они недетерминированны по своей природе. На практике нам хотелось бы иметь дело с детерминированными автоматами, в которых в каждой конфигурации возможно не более одного такта:
Определение. МП-автомат называется детерминированным, если для каждых и верно одно из следующих утверждений:
- содержит не более одного элемента для каждого и
- для всех и содержит не более одного элемента
К сожалению, детерминированные МП-автоматы описывают только подмножество всего класса КС-языков - это подмножество называется детерминированными КС-языками. Этот класс языков называют также LR(k)-грамматиками, так как они могут быть однозначно разобраны путем просмотра цепочки слева направо с заглядыванием вперед не более, чем на k символов.
Детерминированные КС-языки, как и весь класс КС-языков, позволяют проверить пустоту определяемого ими языка или принадлежность заданной цепочки языку. Однако, детерминированные КС-языки не обладают некоторыми важными теоретико-множественными свойствами, например, детерминированные КС-языки не замкнуты относительно пересечения, дополнения или объединения (общий класс КС-языков также не замкнут относительно пересечения и дополнения, но замкнут относительно объединения).
Тем не менее, с точки зрения методов компиляции, класс LR(k)-грамматик чрезвычайно важен, так как на нем и некоторых его разновидностях основаны большинство современных средств синтаксического разбора. Мы рассмотрим LR(k)-грамматики в отдельной лекции.
