Интерпретаторы и компиляторы. Part 2.

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

Поговорим немного о синтаксических конструкциях.

Программа, которую мы пишем, реализует какой-то определённый алгоритм. Для того чтобы наш код заработал без затруднений, необходимо, чтобы все строки символов нашей программы были однозначно определены и имели нужный эффект. Это задача отводится языку. Язык может состоять из конечного и бесконечного числа строк. Если с первым всё ясно – достаточно перечислить все строки и описать их, то задача по обработке второго языка уже сложнее.  Нас, конечно же, интересует второй вариант – язык с бесконечным количеством строк.

А как же определить такие языки? Например, можно это сделать так:

{p^q | q>0}

Что же нам даёт эта замысловатая надпись? Это сокращённая запись языка с бесконечным количеством символов, в котором возможны следующие строки:

p

pp

ppp

и так далее.

Думаю, принцип должен быть понятен.

Таким образом, мы можем создавать довольно сложные вещи, например:

{p^qmⁿl^k | q,n,k > 0}

Тогда строки нашего языка могут быть уже более разнообразными:

pml

ppmll

ну и многое другое.

Если посмотреть на приведённые выше языки, то можно увидеть, что их можно определить, через регулярные выражения.

К примеру, следующее выражение:

p*

формирует строки:

(пустая строка, будем её обозначать: e)

p

pp и т.д.

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

pp*

Следующий элемент регулярного выражения, который мы рассмотрим – это символ ‘|’ – или. С помощью такого инструмента мы можем строить ещё более сложные языки, вот один из них:

(p | m*)

Это означает, что строка может состоять из одного элемента p или нуль или более элементов m. Посмотрим на них:

p

m

mm

mmm.

Отметим следующее: если L и K – регулярные выражения, то для них справедливы следующие выражения:

LK (K следует за L)

L|K (L или K)

L* (нуль или более элементов L)

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

a (a | d)*

Это всё конечно хорошо, но у регулярных выражений есть один недостаток, в них невозможно указать равенство, например в таком языке:

{aⁿbⁿ | n>0}

количество элементов a равно количеству элементов b.

Для того, чтобы этого недостаток устранить, мы воспользуемся таким методом как продукция, выглядит это так:

S → aSb

S →  ab

→ читается, как “может иметь вид”

В следующий раз рассмотрим грамматики и иерархию Хомского.