Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Грамматика языка
Содержание
- 1. Грамматика языка
- 2. Методы построения трансляторовТема № 4Грамматика языка
- 3. Грамматика языка Определение грамматики языка Грамматика –
- 4. Грамматика языка Формально грамматика G определяется как
- 5. Грамматика языка Запись правил грамматик в форме
- 6. Грамматика языка Запись правил грамматик в форме
- 7. Грамматика языка Классификация грамматик и языковФормальные грамматики
- 8. Грамматика языка Классификация грамматик (по Хомскому)
- 9. Грамматика языка Классификация грамматик (по Хомскому)
- 10. Грамматика языка Классификация грамматик (по Хомскому)
- 11. Грамматика языка Классификация грамматик (по Хомскому)
- 12. Грамматика языка Классификация языков
- 13. Грамматика языка Классификация языков
- 14. Грамматика языка Классификация языков
- 15. Грамматика языка Классификация языков
- 16. Скачать презентанцию
Методы построения трансляторовТема № 4Грамматика языка
Слайды и текст этой презентации
Слайд 1курс лекций по дисциплине
Методы построения трансляторов
Преподаватель: к.т.н., доцент Карамзина А.Г.
ГОСУДАРСТВЕННОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
Грамматика языка
Слайд 3Грамматика языка
Определение грамматики языка
Грамматика – это описание способа
построения предложений некоторого языка.
Правило (продукция) – это упорядоченная пара цепочек
символов (α, β). В правилах очень важен порядок цепочек, поэтому их чаще записывают в виде
α→β
читается как «α порождает β» или «β по определению есть α».
Грамматика языка программирования содержит правила двух типов:
правила, определяющие синтаксические конструкции языка легко поддаются формальному описанию;
правила, определяющие семантические ограничения языка обычно излагаются в неформальной форме.
Язык, заданный грамматикой G, обозначается как L(G).
Слайд 4Грамматика языка
Формально грамматика G определяется как четверка:
G(VT, VN, P, S),
где: VT – множество терминальных символов;
VN – множество нетерминальных символов: VN∩VT=∅;
Р – множество правил (продукций) грамматики вида α→β, где α∈V+, β∈ V*;
S – целевой (начальный) символ грамматики S∈VN.
Определение грамматики языка
Множество V = VN∪VT называют полным алфавитом грамматики G.
Множество терминальных символов VT содержит символы,
которые входят в алфавит языка, порождаемого грамматикой
(символы этого множества встречаются только
в цепочках правых частей правил, если же встречаются
в левой части правила, то должны быть и в правой его части).
Множество нетерминальных символов VN содержит символы,
которые определяют слова, понятия, конструкции языка
(каждый символ этого множества может встречаться
в цепочках как левой, так и правой частей правил,
но должен хотя бы один раз быть в левой части
хотя бы одного правила).
Особенность формальных грамматик в том, что они позволяют определить бесконечное множество цепочек языка с помощью конечного набора правил за счет рекурсивных правил.
Рекурсия в правилах грамматики выражается в том,
что один из нетерминальных символов определяется сам через себя.
Рекурсия может быть непосредственной (явной) –
тогда символ определяется сам через себя в одном правиле,
либо косвенной (неявной) – тогда символ определяется через цепочку правил.
Слайд 5Грамматика языка
Запись правил грамматик в форме Бэкуса-Наура
Данная форма
записи правил грамматик предполагает, что:
если во множестве правил
грамматики есть несколько правил, имеющих одинаковые левые части, вида: α→β1, α→β2, … α→βn,
то эти правила объединяют вместе и записываются в следующем виде:
α→β1|β2|…βn|
(одной строке в такой записи соответствует сразу n правил);
нетерминальные символы берутся в угловые скобки: < >.
Слайд 6Грамматика языка
Запись правил грамматик в форме Бэкуса-Наура
Пример: грамматика
для целых десятичных чисел со знаком задана:
G({0,l,2,3,4,5,6,7,8,9,-,+},{,,},P, ):
Р: →
<чс>| +<чс>| -<чс><чс> → <цифра>| <чс><цифра>
<цифра> → 0|1|2|3|4|5|6|7|8|9
Составляющие элементы грамматики G:
множество терминальных символов VT содержит двенадцать элементов: десять десятичных цифр и два знака;
множество нетерминальных символов VN содержит три элемента: символы <число>, <чс> и <цифра>;
множество правил P содержит 15 правил, которые записаны в три строки (то есть имеются только три различных левых части правил) рекурсия в 5 правиле,
4 правило позволяет избежать бесконечной рекурсии;
целевым символом грамматики является символ <число>.
Названия нетерминальных символов
не обязаны быть осмысленными,
это сделано просто для удобства понимания
правил грамматики человеком.
Набор же терминальных символов всегда
строго соответствует алфавиту языка,
определяемого грамматикой.
G({0,l,2,3,4,5,6,7,8,9,-,+},{S,T,F},P,S):
Р: S → T| +T| -T
T → F| TF
F → 0|1|2|3|4|5|6|7|8|9
Слайд 7Грамматика языка
Классификация грамматик и языков
Формальные грамматики классифицируются по структуре
их правил.
Языки классифицируются в соответствии с типами грамматик.
От
того, к какому типу относится тот или иной язык программирования, зависит сложность распознавателя для этого языкачем сложнее язык, тем выше вычислительные затраты компилятора
на анализ цепочек исходной программы,
тем сложнее компилятор и его структура.
Для некоторых типов языков в принципе
невозможно построить компилятор,
который анализировал бы исходные тексты
на этих языках за приемлемое время
на основе ограниченных вычислительных ресурсов
(именно поэтому до сих пор невозможно
создавать программы на естественных языках).
