Регулярное выражение генерирует регулярное множество. Например, регулярное выражение (а Ь)с генерирует регулярное множество {ас, bc}. Ясно, что регулярное множество можно генерировать с помощью не только одного регулярного выражения (хотя бы потому, что «» является коммутативной). Мы обычно не делаем различия между регулярным выражением и генерируемым им множеством.

Другие свойства регулярных множеств:

1. Существует алгоритм, определяющий принадлежность строки заданному регулярному множеству (специфицированному регулярным выражением).

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

Эти свойства весьма полезны с точки зрения разработчика компилятора.

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

1. При чтении слева направо число встреченных закрывающих скобок никогда не превышает число встреченных открывающих скобок.

2. В каждой строке содержится одинаковое число открывающих и закрывающих скобок.

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

<{( ))) О О (О) (О о (О ()))

а приводимые ниже

нет:

0) (О «о 0)

- правило 1,

- правило 2.

Не существует способа выражения этого языка в виде регулярного выражения (см. [45], с. 72) или его генерирования с помощью грамматики типа 3.

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

S{S)

В большинстве: языков программирования имеются пары скобок, которые необходимо согласовывать, например

О, [], begin «nd. if fl, do od

и, конечно, каждой открывающей скобке должна соответствовать закрывающая скобка. Так,

begin ()«id

представляет собой правильную структуру скобок, а

begin (end)

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

.Х: = У

может быть допустимым, если объявлено, что Х и У имеют соответствующие типы. Если X и У были описаны как

int X;char Y

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

Таким образом, оказывается, что чем более универсален класс используемой грамматики, тем больше, средств типичных языков программирования мы можем описать. Однако, чем универсальнее грамматика, тем сложнее должна быть машина (или программа), которая применяется для распознавания строк соответствующего языка. В гл. 3 мы увидим, что с грамматикой типа 3 ассоциируется класс распознавателей, известный как конечный автомат или машина с конечным числом состояний, между которыми происходит передача управления по мере считывания символов строки, причем строка принимается или нет в зависимости от того, какого состояния машина достигает в итоге. Для языка, генерируемого с помощью контекстно-свободной грамматики, необходим (вообще) автомат магазинного типа, т. е. конечный автомат плюс стек, а для контекстно-зависимых языков - линейный автомат с ограничениями, т.е. машина Тьюринга с конечным объемом ленты. Наконец, языку типа 0 требуется машина Тьюринга в качестве распознавателя.

Полное описание этих машин, а также доказательства эквивалентности различных классов языков и соответствующих им автоматов приведены в [27].

2.3. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

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

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

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

2. Разработчикам компиляторов требуется точное определение языка, который они реализуют, и предпочтительно в легко реализуемой форме.

Эти две причины представляются противоречивыми. Первая подразумевает, что определение должно быть удобочитаемым и что программисту, знакомому с ним, будет нетрудно получить ответ относительно языка. Согласно второй причине определение должно иметь такой вид, чтобы на его основе можно было легко и при наименьшем вмешательстве человека построить (по крайней мере) анализатор. В гл. 4 мы увидим, что наиболее естественные (и удобочитаемые) грамматики не всегда позволяют автоматически построить анализатор. В частности, некоторые методы разбора, как правило, требуют преобразования грамматики перед ее использованием для построения синтаксического анализатора.

Сообщение об Алголе 60 явилось одной из первых попыток формального определения языка. Большая часть синтаксиса была описана с помощью контекстно-свободной грамматики, а остальная его часть и семантика - на английском языке. В первом сообщении содержалось много неоднозначностей, и даже пересмотренное сообщение [46] оказалось несвободным от них [33].

Дальнейшая разработка методов формального определения представлена сообщением об Алголе W [8], в котором сделана попытка включить в формальную часть синтаксиса некоторую информацию о типе. В пересмотренном сообщении об Алголе 68 [55] для определения всего синтаксиса языка использовалась двухуровневая грамматика (W-грамматика, названная в честь ее изобретателя грамматикой А. ван Вейнгаардена). Идея применения двухуровневой грамматики заключается в том, что, как и правила обычной грамматики, обеспечивающие конечный способ описания языка, который состоит из бесконечного числа строк, в сообщении об Алголе 68 (здесь и далее под Алголом/68 и сообщением об Алголе 68 мы подразумеваем пересмотренный Алгол 68 и пересмотренное сообщение об Алголе 68 соответственно) вторая грамматика применяется для генерирования бесконечного числа правил, которые в свою очередь генерируют предложения Алгола 68. Другими словами, хотя Алгол 68 нельзя генерировать посредством контекстно-свободной грамматики, которая по определению может иметь только конечное множество правил, расширение (простое?) грамматики, разрешающее ей иметь бесконечное множество правил, служит достаточным обобщением, что позволяет специфицировать эту грамматику, генерирующую Алгол 68. В действительности с помощью такой грамматики можно генерировать любой язык типа 0. Это значит, что мы имеем дело с довольно мощной концепцией. Имея в виду тип распознавателя, который требуется языкам типа 0, эту концепцию можно считать даже слишком мощной для определения языков программирования, контекстно-зависимые средства которых носят довольно простой характер.

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

Здесь «:» употребляется вместо «-»->, а «,»- для разделения символов (терминалов или нетерминалов) в правой части гиперправила. В конце каждого правила ставится точка. Присваивание, получатель и источник имеют свой вид, и в соответствии с правилами W-грамматик слова, написанные заглавными буквами, должны согласованно замещаться при применении гиперправила. Гиперправило (в целом) представляет собой «скелет» бесконечного числа порождающих правил языка. Фактические порождающие правила грамматики получают путем согласованной подстановки метапонятий в