Введение в теорию формальных языков и грамматик

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

 

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

Любой язык программирования (алгоритмический язык) можно понимать как множество цепочек символов, задаваемое некоторым множеством правил. Множество цепочек символов, построенных по определенным правилам, образует формальный язык. Формальная грамматика включает набор грамматических правил, с помощью которых можно порождать и анализировать цепочки формального языка [3].

 

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

< предложение>, < сказуемое >, < подлежащее >, < дополнение >,

< прилагательное>, < существительное >, < точка >

Пусть имеем словарь, состоящий из 5 символов:

{ Дом, Дуб, Заслоняет, Старый, .}

Считаем, что в грамматике имеются определенные правила, содержащие информацию о том, как из этих символов можно строить предложения языка. Рассмотрим первое из таких правил.

1. <предложение>: ® <подлежащее> <сказуемое>

<дополнение> .

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

2. <подлежащее>: ® <прилагательное> <существительное >

3. <дополнение>: ® <прилагательное><существительное >

4. <сказуемое>: ® ЗАСЛОНЯЕТ

5. <прилагательное>: ® СТАРЫЙ

6. <cуществительное >: ® ДОМ

7. <cуществительное >: ® ДУБ

Применим предложенные правила для порождения (вывода )

предложения СТАРЫЙ ДУБ ЗАСЛОНЯЕТ СТАРЫЙ ДОМ.

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

 

<предложение>: ® <подлежащее> <сказуемое> <дополнение>.

(Применили 1правило).

 

<предложение>: ® <прилагательное> <существительное >

<сказуемое> < дополнение >.

(Применили 2 правило ).

 

<предложение>: ® СТАРЫЙ <существительное >

<сказуемое> < дополнение >.

(Применили 5 правило ).

<предложение>: ® СТАРЫЙ ДУБ <сказуемое> < дополнение >.(Применили 7 правило).

 

<предложение>: ® СТАРЫЙ ДУБ ЗАСЛОНЯЕТ < дополнение >.(Применили 4 правило).

 

<предложение>: ® СТАРЫЙ ДУБ ЗАСЛОНЯЕТ <прилагательное> <существительное >.

(Применили 3 правило).

 

<предложение>: ® СТАРЫЙ ДУБ ЗАСЛОНЯЕТ СТАРЫЙ <существительное >.

(Применили 5 правило)

 

<предложение>: ® СТАРЫЙ ДУБ ЗАСЛОНЯЕТ СТАРЫЙ ДОМ.(Применили 6 правило).

 

С помощью рассмотренной грамматики можно вывести и другие предложения. Например,

СТАРЫЙ ДОМ ЗАСЛОНЯЕТ СТАРЫЙ ДОМ.

СТАРЫЙ ДОМ ЗАСЛОНЯЕТ СТАРЫЙ ДУБ.

СТАРЫЙ ДУБ ЗАСЛОНЯЕТ СТАРЫЙ ДУБ.

 

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

Рассмотрим процедуру вывода (порождения) языка грамматикой на примере дерева. Дерево показывает, какие правила применялись к различным промежуточным элементам.

 

<предложение>

 

<подлежащее> <сказуемое> <дополнение> .

 

<прилагат.> <сущест. 1> < прилагат.> <cущест. 2>