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




Скачать 100.77 Kb.
Дата02.08.2016
Размер100.77 Kb.

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


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

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

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

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

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


Формальные системы

Система

Краткое определение

Использование в трансляторах

Моделирующая способность

Конечный автомат

Алгоритм «без данных»

Цепочки, включающие выбор и повторение (лексика)

«Инстинктивное» поведение, распознавание последовательностей, неадаптивное поведение

Формальная грамматика

Конечный автомат со стековой памятью

Цепочки, включающие выбор, повторение, вложенность и приоритеты (синтаксис)

Распознавание вложенных последовательностей произвольной глубины

Сеть Петри

Система конечных автоматов

---

Поведение параллельных и независимых систем

Машина Тьюринга (программа)

Конечный автомат с неограниченной памятью

Формализуемые связи между символами цепочек (семантика)

Адаптивное поведение с элементами запоминания и обучения по заданной программе (правилам игры)

Неформальные системы

Программист

???

???

Разработка программ (правил игры)

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

Формальные грамматики и конечные автоматы


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

Автоматные модели и восходящее распознавание


Если интепретировать нетерминал в стеке как состояние автомата, то свертка по разным видам правил соответствует различным видам переходов в автомате:

  • правилу B::Ac в восходящем распознавателе соответствует элемент диаграммы «переход из состояния A в состояние B по символу с»;

  • правилу вида B::a соответствует переход из начального состояния в состояние B по символу a;

  • правилу вида B::Abc соответствует переход из состояния A в стостояние B при получении последовательности символов bc.

Нижеследующая формальная грамматика соответствует конечному автомату, имеющему состояния, соответствующие нетерминалам A,B,C и допустимые переходы, соответствующие ее правилам.
Z
:A# A:Aa B:Ab B:Bb C:Bc C:Cc B:Cb A:Ba A:a

Использовать автоматное представление в восходящих распознавателях приходится не только для целей описания лексики. В п.3.9 рассматривается способ предотвращения конфликтов типа «свертка-перенос», в котором для устранения «лишних» переносов правила формальной грамматики дробятся на части. Возникающие при этом промежуточные нетерминалы удобно представлять как состояния автомата, а ту часть грамматики, где применяется этот технологический прием, в виде соответствующей граф-схемы.

Автоматные модели и нисходящее распознавание


В нисходящем распознавании конечный автомат моделируется правилами вида B::aC, замена в стеке левой части на правую соответствует переходу из состояния B в состояние C при получении автоматов символа a. Нетерминал Z соответствует начальному состоянию автомата.
Z:aA A:aA A:bB B:bB B:cC C:cC C:bB B:aA A:#




Регулярные грамматики и лексический анализ


Самый простой класс грамматик, имеющий максимальные ограничения на вид правил, называется регулярными грамматиками, которые уже соответствуют более простым формальным системам – конечным автоматам (КА). В них допустимы только правила со следующей структурой правой части:

  • X :: Y - цепочка терминалов – нетерминал;

  • X :: - цепочка терминалов;

  • X :: - аннулирующее правило;

  • X :: Y - нетерминал.

Существуют следующие правила преобразования регулярной грамматики в диаграмму состояний-переходов КА:

  • нетерминал левой части соответствует исходному состоянию КА, помеченному соответствующим символом;

  • нетерминал правой части соответствует состоянию перехода, обозначенному соответствующим символом;

  • последовательность терминалов правой части соответствует последовательности входных символов, по которым производится переход из состояния, обозначенного нетерминалом левой части, в состояние, обозначенное нетерминалом правой через цепочку промежуточных состояний;

  • аннулирующее правило соответствует переходу в заключительное состояние по пустому символу (в КА для лексического анализа это соответствует неявному завершению лексемы при получении символа, не являющегося ее продолжением и возвращению его во входной поток);

  • правило с цепочкой терминальных символов соответствует переходу в заключительное состояние по последовательности символов этой цепочки через промежуточные состояния;

  • правило с единственным нетерминалом соответствует переходу из одного состояния в другое по пустому символу .

Полученный КА обладает двумя недостатками, не позволяющими реализовать на нем лексический анализатор:

  • он не является однозначным (детерминированным). Из одного состояния в нем бывают два (и более) перехода в различные состояния по одному и тому же символу (например, символ * в состоянии C). Аналогичные претензии можно предъявить к регулярной грамматике: она не является LL(1)-грамматикой, т.е. не допускает нисходящего разбора на основе анализа единственного текущего символа;

  • он содержит переходы по пустым символам .

Автоматные модели обладают высокой разрешимостью, указанные проблемы решаются соответствующими обобщенными алгоритмами, позволяющими устранить недетерминированность и «пустые» переходы путем формальных преобразований автомата.

На практике лексический анализ еще более автоматизирован. Имеются специальные средства описания лексики, так называемые регулярные выражения. Полная последовательность построения лексического анализатора состоит из следующих шагов:



  • преобразование (трансляция) описания лексики в виде регулярных выражений в регулярную грамматику;

  • преобразование регулярной грамматики в конечный автомат;

  • построение детерминированного конечного автомата из исходного;

  • устранение -переходов;

  • минимизация полученного автомата.

Граница лексики и синтаксиса


В принципе, лексика является частным случаем синтаксиса. Это подтверждается тем, что для описания лексики используются регулярные грамматики. На практике, лексический анализ отделен от синтаксического, и поэтому иногда возникают спорные вопросы, можно ли считать некоторую конструкцию лексической или же синтаксической. Например, является ли знаковая константа (предваренная знаком «+» или «-» ) лексической конструкцией?

Формально, мы можем определить лексемы трех видов: знаки операций «+» и «-», беззнаковые и знаковые константы, различая их по принципу максимального совпадения.Но тогда выражение вида abc-1245 будет распознано как две лексемы – идентификатор и знаковая константа, что с точки зрения синтаксиса является ошибочным. Правильным решением будет унарных операций вида +G и G описание в качестве синтаксических единиц в выражениях, где под G можно понимать синтаксические единицы различного уровня – от выражений в целом до отдельных термов, в зависимости от того, в каком контексте допустима соответствующая операция.

Другим принципиальным ограничением лексики является отсутствие вложенности фрагментов, составляющих лексему. Точнее, автомат может отслеживать вложенность на ограниченное количество уровней, причем каждый уровень должен определяться отдельной системой состояний.

Формальная и содержательная сторона синтаксического анализа


Фаза синтаксического анализа, несмотря на свою формализацию, имеет еще и содержательную сторону. С формальной позиции синтаксический разбор заключается в ответе на вопрос, является ли входное предложение языка правильным в заданной грамматике. Но реальным результатом является синтаксическое дерево, которое отражается структуру анализируемой программы: из каких синтаксических единиц она состоит и в какой взаимосвязи они находятся. Вызов связанных с его обходом семантических процедур задает «смысл» этой структуры и является продолжением процесса трансляции.

В связи с этим интересен вопрос эквивалентности формальных грамматик. Эта проблема алгоритмически неразрешима, что означает невозможность определить формальными методами, распознают ли две грамматики один и тот же синтаксис, либо нет. Обратная сторона вопроса: один и тот же синтаксис может быть задан различными грамматиками и для одной и той же программы они построят различные синтаксические деревья. В то же время с точки зрения семантики «смысл» программы должен быть всегда одним и тем же, независимо от особенностей трансляции.

В самом широком смысле формальная грамматика является языком программирования синтаксиса и, как любой язык программирования, она не отвечает на два вопроса: как написать программу под заданные требования и какой содержательный смысл имеет написанная программа. Применительно к синтаксическому анализу это звучит так:


  • разработка формальной грамматики под требуемый синтаксис является неформализуемой задачей и решается с использованием набора технологических приемов;

  • семантический анализ, основанный на интерпретации структуры синтаксического дерева, также является неформализуемой задачей. В каждой грамматике он делается на основе особенных свойств создаваемых ею деревьев.

Граница синтаксиса и семантики


Будучи основанным на более универсальной формальной системе, семантический анализ позволяет «брать на себя» функции синтаксического анализатора. Особенно это эффективно, если синтаксис может варьироваться в зависимости от контекста (окружения). Рассмотрим характерный пример.

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



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

  • создается один набор правил, а уровень вложенности является семантической характеристикой, которая определяет, допустимость применения правил для варьируемого синтаксиса на данном уровне вложенности.

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

  • имена типов данных отсутствует в синтаксисе как таковые. Соответственно, они не распознаются лексическим анализатором как ключевые слова, а в формальной грамматике им соответствуют идентификаторы. Этот способ сильно ограничивает синтаксический контроль;

  • имена производных типов данных по мере их определения включаются в таблицы лексического анализатора и правила формальной грамматики в виде допустимых ключевых слов. Это позволяет сделать синтаксический анализ более жестким и отлавливать недопустимые имена типов уже на этом уровне. Кроме того, в Си++ этот способ хорошо согласуется с идеей переопределения операций.



© Теория языков программирования и методы трансляции .



База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница