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

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

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

• точным (или формальным);

• лаконичным.

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

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

{xⁿ | n>0}

Здесь знак "|" можно прочесть как "где", n — целое, а умножение следует понимать как конкатенацию.

Другой пример языка.

{ xⁿ yⁿ | n>0}

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

ху

хххууу

ххххххххуууууууу

С другой стороны, определение

{ x^m yⁿ | m, n > 0}

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

{ x^m yⁿ | m, n ≥ 0}

тогда строки

ххх (нуль элементов у)

и

ууууууу (нуль элементов х)

также представляют возможные строки языка. При таком определении языка ему также принадлежит элемент e.

Этот элемент — пустая строка, не содержащая ни знаков х, ни знаков у. Как будет показано далее, пустые строки играют важную роль в определении языков программирования.

Регулярные выражения

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

x ^*y^*

Здесь символ "*" обозначает, что предшествующий ему элемент, употребляется нуль или большее число раз. Если в каждой строке языка должно находиться минимум по одному элементу х и у, то язык можно определить следующим образом - хх^*уу^*

Возможна альтернативная запись х⁺y⁺

Здесь плюс означает одно или большее число вхождений предшествующего элемента. Кроме того, в регулярных выражениях можно использовать символ "|" (в данном контексте читается как "или"). Таким образом, выражение х* | у^* представляет определение языка, строки которого состоят из нуля или большего количества элементов x или из нуля или большего количества элементов у. Выражение (а | b)^* представляет язык, строки которого состоят из нуля или большего числа элементов а или b (другими словами, строка состоит из нуля или большего числа знаков, каждый из которых может быть а или b). В последнем выражении скобки употребляются для того, чтобы показать более высокий приоритет знака | над знаком *. Принято, что знак * имеет более высокий приоритет, чем |, поэтому язык a | b^*

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

(aab | ab)^*

Этот язык будет включать в себя следующие строки.

e

aababaab

ababab

aabaabaabab

Регулярное выражение (ааа | ab)*

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

Дата добавления: 2015-07-07