Рис.3.7

3.4. Выведите детерминированный автомат, принимающий регулярное

выражение из упражнения 3.3. 3.5.Приведите грамматику типа 3, соответствующую конечному автомату,

представленному на рис. 3.7, где А есть начальное состояние, а С-

последнее. Как бы вы описали этот язык? 3.6. Напишите процедуру распознавания строк языка, принимаемого автоматом

из упражнения 3.5.

3.7.Число с фиксированной точкой определяется как возможный знак, за которым следует

строка, состоящая из нуля или большего числа цифр, с последующей точкой и следую

щей за нею строкой из нуля или более цифр; содержит она по крайней мере одну

цифру (до или после точки). Напишите процедуру распознавания такого числа.

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

платформ и следующего за ними вагона с охраной. Напишите процедуру распознавания товарного поезда.

3.9.Предложите структуры данных, применимые для реализации таблицы констант.

3.10.Предложите вместо взаимно рекурсивных процедур другой вариант для обращения с двумя видами лексического анализа, требуемого при использовании Алгола 68 (т. е.внутри и вне форматов).

Глава 4

КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И СИНТАКСИЧЕСКИЙ АНАЛИЗ СВЕРХУ ВНИЗ

В предыдущей главе мы рассмотрели проблему распознавания языков типа 3 и показали, что конечный автомат можно применять для распознавания любого языка этого типа. Далее мы определили, что во избежание возврата всегда можно воспользоваться детерминированным автоматом. Грамматики

типа 3 удобны для генерирования символов, которые создаются во время лексического анализа, но они не очень подходят для описания способов объединения этих символов в предложения типичных языков программирования. Например, как уже отмечалось в гл. 2, согласование скобок нельзя специфицировать с помощью грамматики типа 3. Контекстно-свободные грамматики, хотя и не могут специфицировать все свойства типичных языков программирования, являются более универсальными и поэтому более пригодными в качестве основы для фазы синтаксического анализа (разбора) компиляции.

Здесь мы изучим свойства контекстно-свободных грамматик и их связь с теорией автоматов, а также приведем методы синтаксического анализа сверху вниз. Методы синтаксического анализа снизу вверх описываются в гл. 5.

4.1. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ

Контекстно-свободные грамматики традиционно служат основой для синтаксического анализа компиляции. Когда какой-либо язык программирования нельзя генерировать с помощью контекстно-свободной грамматики, всегда можно найти такую контекстно-свободную грамматику, которая генерирует супермножество языка, т. е. язык, включающий в себя заданный язык программирования. Применение этой грамматики для синтаксического анализа означает, что ряд ограничений в реальном языке (например, обязательное объявление всех идентификаторов в программе) не будет проверяться анализатором. Однако в компиляторе нетрудно предусмотреть другие действия по выполнению необходимых проверок в исходной программе (например, за счет применения таблицы символов).

Из определения контекстно-свободной грамматики, приведенного в гл. 2, ясно, что класс контекстно-свободных грамматик более мощный (т. е. может генерировать больше языков), чем класс регулярных грамматик, но менее мощный, чем класс контекстно-зависимых грамматик. Язык

{bnn>=0}

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

S->aSb

S->e

С другой стороны, язык

{anbncnn>=0}

является контекстно-зависимым, а не контекстно-свободным. Контекстно-свободные грамматики имеют ряд характеристик, для которых справедливы следующие положения. Доказательства большинства из них можно найти в [27].

1 . Каноническая форма

а) Каждая контекстно-свободная грамматика эквивалентна (т. е. генерирует тот же язык) грамматике в нормальной форме Хамского, т. е. со всеми порождающими правилами вида

A->BC A->C

при обычных условиях, касающихся терминалов и нетерминалов.

б) Каждая контекстно-свободная грамматика эквивалентна грамматике в нормальной форме Грейбаха, т. е. со всеми порождающими правилами вида

А->bа

где а - строка нетерминалов (возможно, пустая). 2. Самовложение

Самовложение определяется следующим образом. Если в грамматике G есть нетерминал А, для которого

A=>*GаlAа2

(здесь а1 и а2 являются непустыми строками терминалов и/или нетерминалов), то о такой грамматике говорят, что она содержит самовложение. Например, две приведенные ниже грамматики содержат самовложение:

1) G1 = ({S}, {a, b}, Р, S),

где элементы Р:

S->aSb S->e

2) G2=({S,A}, {begin, end, [,] },P,S),

где элементы Р:

S->begin A end

S->e

A->[S]

В последнем случае об А и S говорят, что они проявляют свойство самовложения. Теоретически любая контекстно-свободная грамматика, не содержащая самовложения, эквивалентна регулярной грамматике или (иначе) генерирует регулярный язык. Дело также в том, что регулярная грамматика не может содержать самовложения. Именно самовложение позволяет эффективно различать контекстно-свободные (нерегулярные) и регулярные языки. Как видно из второго примера, согласование скобок и т. п. требует самовложения, поэтому его нельзя специфицировать посредством регулярной грамматики.

3. Лемма подкачки

Для любого контекстно-свободного языка L существует такая константа k, что любое предложение языка z, длина которого превышает k, можно записать в виде

z=uvwxy, где vwx<=k

v и х не являются пустой строкой, а строка

uVwxy (для i>=0)