Язык высокого уровня (исходный) описывается в терминах некоторой грамматики Эта грамматика определяет синтаксис допустимых предложений языка [5, б].
Грамматика - это четверка G = ( N, Е, Р, S ), где N - конечное множество не терминальных символов; Σ - непересекающееся с N конечное множество терминальных символов; Р - конечное подмножество множества (ТÈΣ)*N(NÈΣ)*x(NÈΣ)* (элемент множества Р (a,b) называется правилом (α→β)); S - выделенный символ из N, называемый начальным (исходным) символом.
Язык, порождаемый грамматикой G (обозначение L(G)) - множество терминальных цепочек, порождаемых грамматикой G.
Грамматика G называется:
1) праволинейной, если каждое правило из Р имеет видA→xB или A→x, где А, BÎN, xÎΣ;
2) контекстно-свободной (КС), если каждое правило из Р имеет вид А→α, где АÎN, αÎ(N È Σ)*;
3) контекстно-зависимой (неукорачивающей), если каждое правило из Р имеет вид α→β, где │α│≤│ β │.
Грамматика, не удовлетворяющая ни одному из указанных ограничений называется грамматикой общего вида (без ограничений).
Пусть Σ - входной алфавит и Δ - выходной алфавит. Переводом с языка L1ÍΣ* на язык L2ÍΔ* назовем отношение T из Σ* в Δ*, для которого l1 - область определения, L2 - множество значений.
Схемой синтаксически-управляемого (СУ) перевода (трансляции) называется пятерка
Т=( N, Σ, Δ, R, S ),
где N - конечное множество нетерминальных символов; S - конечный входной алфавит; Δ - конечный выходной алфавит; R - конечное множество правил вида A→α,β, где αÎ(NÈΣ)*, βÎ(NÈΔ)* и вхождения нетерминалов в цепочку β образуют перестановку вхождения нетерминалов в цепочку α, S - начальный символ, выделенный нетерминал из N.
Переводом, определяемым схемой Т (обозначение τ(T)) называется множество пар
{ (х, у) | (s, s) Þ* (х, у), хÎΣ* и yÎΔ* },
где Þ* рефлексивно-транзитивное замыкание.
Если Т=( N, Σ, Δ, R, S ) - СУ-схема, то τ(Т) называется синтаксически-управляемым переводом.
Грамматика Gi=( N, Σ, R, S ), где Р={ A→α| A→α, βÎR } называется входной грамматикой СУ-схемы Т.
Грамматика G0=( N, Δ, P', S ), где Р={ A→b | A→α, βÎR } называется выходной грамматикой СУ-схемы Т.
Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка
Р=(Q, Σ, Г, Δ, δ, q0, z0, F),
где Q - конечное множество состояний; Σ - конечный входной алфавит; Г - конечный алфавит магазинных символов; Δ - конечный выходной алфавит; δ - отображение множества Q x(ΣÈ{е}) х Г в множество конечных подмножеств Q х Г* х Δ*; q0 - начальное состояние; z0ÎГ - символ, находящийся в магазине в начальный момент; FÍQ - множество заключительных состояний.
Конфигурация преобразователя Р - четверка (q, х, α, у), где y - выходная цепочка, выданная вплоть до настоящего момента; цепочка у - выход для х, если (q0, х, z0, е) Þ* (q, е, α, у), qÎF, aÎГ*.
Переводом (преобразованием) определяемым МП-преобразователем (t(p)) называется множество {(х, у) | (q0, х, z0,e) Þ*(q, е, α, у), q из F, α из Г*}.
Лемма 1. Пусть Т=( N, Σ, Δ, R, S ) - простая СУ-схема. Существует такой МП-преобразователь Р, что τe(P) = τ(T).
Лемма 2. Пусть Р=(Q, Σ, Г, Δ, δ, q0, z0, F) -МП-преобразователь. Существует такая простая СУ-схема, чтоτ(T)=τe(P).
Упрощенная модель компилятора может быть представлена как совокупность моделей лексического анализатора, синтаксического анализатора и генератора команд. Построенная модель должна адекватно отражать процесс компиляции, должна быть удобной и простой в работе, кроме того, она должна носить конструктивный характер, т.е. допускать не только фиксацию свойств, но и исследование зависимостей характеристик от параметров компилятора.
Компилятор можно задать как множество пар (х, у), где х - программа в исходном языке, у - программа в том языке, на который нужно перевести х. Множество пар (х, у) называется переводом. Если х - цепочка в алфавите Σ, а у - цепочка в алфавите Δ, то перевод - это отображение множества Σ* в Δ*, где Σ*(Δ*) обозначает множество, содержащее все цепочки в алфавите Σ(Δ), включая e (пустой символ).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.