Тестирование софта - статьи


Предварительные сведения


В этом разделе мы приводим некоторые сведения из теории синтаксического анализа. Более подробное изложение приведенных фактов можно найти в известной книге А. Ахо, Р. Сети и Д. Ульмана (см. [5]).

Грамматика формального языка задается четверкой G = (T,N,P,S), где

  • T – множество терминальных символов или токенов;
  • N – множество нетерминальных символов;
  • P – список правил грамматики;
  • S – стартовый символ грамматики.
Множество предложений формального языка, задаваемого грамматикой G, будем обозначать
G.

Дадим несколько определений.

Расширением грамматики G (или просто расширенной грамматикой) называется грамматика G' = (T,N',P',S'), где S' – новый нетерминальный символ, а к множеству правил добавлено правило S' > S.

Сентенциальной формой будем называть последовательность грамматических символов – нетерминалов и токенов. Далее, греческими буквами из начала алфавита (?, ?, ?, ?, ...) мы будем обозначать какие-либо сентенциальные формы. Пустую сентенциальную форму будем обозначать через ?.

Правосентенциальной формой называется сентенциальная форма, для которой существует правый вывод из стартового правила.

Пример. Рассмотрим следующую грамматику:

S > AB

A > cd

B > eCf

C > Ae

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

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

Пример. Пусть грамматика та же, что и в предыдущем примере. Форма AeCf, как мы уже заметили, является правосентенциальной. В ней есть две подпоследовательности символов Ae и eCf, которые могут быть свернуты в нетерминалы C и B соответственно. Однако основой является только последовательность eCf, так как сентенциальная форма CCf невыводима из стартового символа.


Начало  Назад  Вперед