Алфавиты, цепочки и языки. Основные понятия и определения

БАЗОВЫЕ ПОНЯТИЯ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ И ГРАММАТИК

Контрольные вопросы

1. Какое место занимают трансляторы в структуре системного программного обеспечения? Что такое трансляция, компиляция, транслятор, компилятор, интерпретатор?

2. Что понимается под синтаксисом, семантикой, лексикой языка программирования? Поясните суть этих понятий на примере языка С.

3. Из каких процессов состоит компиляция? Расскажите об общей структуре компилятора.

4. В чем состоит сущность, назначение и взаимосвязь этапов лексического и синтаксического анализа?

5. Почему в большинстве современных компиляторов лексический анализ выделяется в отдельную фазу?

6. Постройте самостоятельно общую схему работы интерпретатора. В чем ее отличие от общей схемы работы компилятора, приведенной на рис.1.1?

7. Постройте самостоятельно общую схему работы компилятора с языка Ассемблера. Какие особенности присущи данному компилятору? Какие фазы компиляции в нем могут объединяться или отсутствовать?

8. Назовите основные факторы, влияющие на количество проходов компилятора в процессе трансляции исходного текста программы. В чем заключается это влияние?

9. Почему в глобальной сети Интернет используются в основном языки программирования, предусматривающие интерпретацию исходной программы?

10. Чем обусловлено построение компиляторов с языка Ассемблера по двухпроходной схеме?

11. В чем заключается суть метода синтаксически-ориентированной трансляции?

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

Алфавит (или словарь) - это конечное множество символов.

Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.

Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита. Синонимы цепочки – предложение, строка или слово.

Цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ e.

Более формально цепочка символов в алфавите V определяется следующим образом:

1) e - цепочка в алфавите V;

2) если a - цепочка в алфавите V и a - символ этого алфавита,

то aa - цепочка в алфавите V;

3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Если a и b - цепочки, то цепочка ab называется конкатенацией (илисцеплением) цепочек a и b.

Например, если a = ab и b = cd, то ab = abcd.

Для любой цепочки a всегда ae = ea = a.

Обращением (илиреверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке.

Обращение цепочки a будем обозначать a^R.

Например, если a = abcdef, то a^R = fedcba.

Для пустой цепочки: e = e^R.

Длина цепочки- это число составляющих ее символов.

Например, если a = abcdefg, то длина a равна 7.

Длину цепочки a будем обозначать | a |. Длина e равна 0.

n-ой степенью цепочки a(будем обозначать aⁿ) называется конкатенация n цепочек a.

a⁰ = e; aⁿ = aa^n-1 = a^n-1a.

Язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.