Лекции.Орг


Поиск:




Определение неоднозначности грамматики и языка




Этапы жизненного цикла программного продукта

· Анализ: цель – определение требований к будущему программному продукту

· Проектирование: результат – архитектура системного программного продукта (алгоритмы + декомпозиция, функции + интерфейс)

· Реализация: кодирование + тестирование + отладка

· Сопровождение: эволюция программного продукта при его эксплуатации

Состав и схема функционирования классической системы программирования

Транслятор – программа, кот позволяет писать программу на языке высокого уровня и обеспечивает ее выполнение (позволяет писать не в машинных кодах)

Компилятор - программа, которая осуществляет перевод исходной программы на ЯП в объектную программу (одна из разновидностей транслятора)

Интерпретатор – так же 1 из разновидностей трансляторов, выход – результат обработки исходных данных

Схема:

Редактор текстов -> (исходная программа на некотором языке программирования) -> компилятор (+макрогенератор) -> (объектная программа – машинно-ориентированное представление программы, где есть информация в машинном коде + инф о внешних связях + таблицы констант…) -> редактор связей –> (исполняемый модуль – программа в машинных кодах как единое целое, относительно некоторого условного начального адреса)

Типы трансляторов, особенности интерпретаторов и компиляторов

Схема работы «чистого» компилятора: (исходная программа на ЯП) -> ЛА + СА + КУ + генерация кода -> (объектный модуль)

Схема работы чистого интерпретатора: (исх. программа на ЯП + входные данные) -> интерпретатор -> (результат работы исх. программы на водных данных)

Смешанная стратегия: (исх. программа на ЯП) -> ЛА + СА + КУ -> (промежуточное представление программы + вх. данные) -> интерпретатор промежуточного представления -> результат работы исх. программы на входных данных

Общая схема работы компилятора

Фаза анализа: (исходная программа на ЯП) -> лексический анализатор -> (последовательность лексем) -> синтаксический анализатор -> (промежуточное представление) -> семантический анализатор

Фаза синтеза: подготовка к генерации -> генерация кода -> (объектный модуль)

Определение порождающей грамматики

Порождающая грамматика – это четверка (VT, VN, P, S), где

VT – алфавит терминальных символов (терминалов)

VN – алфавит нетерминальных символов (нетерминалов, не пересекающийся с VT)

P – конечное подмножество множества (VN U VN)+ X (VT U VN)*; элемент (a, b) называется правилом вывода и записывается в виде a -> b; в а есть хотя бы один нетерминал

S – начальный символ (цель) грамматики, S из VN

Определение языка, порождаемого грамматикой

Язык, порождаемый грамматикой G = (VT. VN, P, S), L(G) – это множество цепочек {a} из VT: каждая a выводима из S.

7. Определение эквивалентности грамматик
Грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Грамматики G1 и G2 почти эквивалентны, если языки, ими порождаемые, отличаются на более чем на эпсилон.

Определение типов грамматики и языков по Хомскому

Тип 0: на правила 0 не накладывается никаких ограничений, кроме огр. по определению(в а есть хотя бы 1 нетерминал)

Тип 1: а) неукорачивающие грамматики: |a| <= |b|; a из +, b из *

b) КЗ a -> b: a = w1 A w2; b = w1 B w2; w1, w2 из *

Тип 2: a) КС a -> b: a – отдельный нетерминал, b – непустая цепочка

b) УКС: a -> b: a – нетерминал, b – любая цепочка

Тип 3: a) праволинейные: A -> tB || A -> t, A, B из VN, t из VT

b) леволинейные: A -> Bt|| A -> t, …

Соотношения между типами грамматик

· Любая регулярная грамматика = КС

· Любая КС = КЗ, неукорачивающая

· Любая КЗ, любая неукорачивающая = типа 0

· Любая регулярная = УКС

· Любая КС = УКС

· УКС с эпсилон не явл. типа 1.

Соотношения между типами языков

Язык типа К, если его можно описать грамматикой типа К и нельзя грамматикой типа К + 1

· Любой регулярный язык = КС язык, но КС-языки не явл. регулярными

· Любой КС = язык типа 1, но есть типа 1 не КС

· Любой язык типа 1 = язык типа 0

Определение неоднозначности грамматики и языка

Дерево вывода: помеченное упорядоченное дерево, явл. деревом разбора в грамматике G = (VT, VN, P, S), если:

· Корень дерева помечен S, листья – символы из VT, либо эпсилон (для укорачивающих грамматик), все вершины – VN

· Если вершины помечены A из VN и пометки при непосредственных потомках, выписанные слева направо, образуют цепочку a1, …, an, где ai из (VT U VN), то A -> a1…an из P – правило вывода грамматики

· Если вершины помечены A из VN и при непосредственных потомках, помеченных эпсилон, то этот потомок единственный.

Грамматика G является неоднозначной, если существует w из L(G), для которой существует более одного дерева вывода.





Поделиться с друзьями:


Дата добавления: 2016-10-30; Мы поможем в написании ваших работ!; просмотров: 372 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Человек, которым вам суждено стать – это только тот человек, которым вы сами решите стать. © Ральф Уолдо Эмерсон
==> читать все изречения...

818 - | 780 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.007 с.