XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 109
Текст из файла (страница 109)
Тем самым возникает идея определить „смысл" через отображение множества „синтаксических объектов" — деревьев выводов фраз языка в некоторое „предметное множество", множество „семантических объектов". Здесь мы ограничимся крайне элементарным введением в формальное описание семантики КС-языков и опишем некоторый простейший „кирпичик" формальной семантики языков программирования.
Начнем с формального определения фразы КС-языка. Определение 8.16. Пусть С = (т', У, В, Р) — КС-грамматика. Терминальную цепочку х называют фразой лэыиа Ь(С), если А 1-' х для некоторого нетерминала А Н Ф. Пусть Т(х) — дерево вывода фразы х с корневым нетерминалом А. Возьмем в Т(х) некоторое поддерево с корневым нетерминалом В. Выводимую из этого вхождения В терминальную цепочку называют аодфраэой фразы х. Если вершина дерева Т(х), соответствующая данному вхождению В, имеет глубину 1 (или, что равносильно, уровень, на единицу меньший уровня корня А), то данная подфраза называется нодфраэой первого рровил фразы х.
Рассмотрим в качестве примера следующую грамматику арифметических выражений: Ехрт -+ А1от ~(Ехрт + Ехрти(Ехрт * Ехрт), А1отп — ~а1)...~а . Предполагается, что вместо вхождения нетерминала АФотп может быть подставлен любой символ некоторого алфавита У = = (а1, ..., а„) (атом в арифметическом выражении может быть либо переменным, либо константой). Нарисуем дерево вывода выражения (а+ (Ь*(с+ (д* (е+ д))))), где а, Ь, с, д, е, д — некоторые атомы из У (рис. 8.39).
695 Д.8.2. Семаитииа форма»алых ивыиов Это выражение в качестве подфраз первого уровня имеет цепочки а и (Ь* (с+ (И* (е+ д)))). Вторая фраза имеет подфразы первого уровня Ь и (с+ (ав (с+д))) И А»о»а А ив»» Множество всех фраз язые о ка о обозначим через РН(й), Рис. 8.39 а множество всех деревьев вывода фраз Ь вЂ” через ТРН(Ь).
Для однозначного языка Ь эти множества эквивалентны. Определение 8.16. Семанп»ическал функция языка Ь есть отображение БЕМ(й) ТРН(Ц -~ )()(Ь) множества всех деревьев вывода фраз а в некоторое множество ЩЬ), называемое универсумом (предметной областью, семан- тической областью, областью интерпретации) языка Ь. Замечание 8.14.
Ради общности следовало бы определить семантическую функцию как частичное отображение, но мы не будем этого делать, вводя для „бессмысленных" фраз специальный „неопределенный" элемент в универсум („нуль» предметной области, „неопределенный смысл"). Заметим также, что и т.д. Заметим, что фраза а, выводимая из самого левого узла Ехрг глубины 1 имеет в качестве подфразы первого уровня ту же цепочку а, т.е. подфрзза первого уровня может совпадать с самой исходной фразой. (Ехуи' + Ехр») А»о»а (Ехрт ° Ехре) а Аамв (Ехрт + Ехрт) Ь А»» <Ехр ° Е р,) и Аь»»в (Етр» + Ехр») 696 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ для однозначного языка семантическая функция может быть определена как отображение из множества фраз языка.
ф Способы определения семантической функции могут быть различными. Нас будет интересовать важный частный случай, когда значение семантической функции на некоторой фразе (под фразой здесь и далее понимается дерево ее вывода, причем разные деревья для одной и той же цепочки рассматриваются как разные фразы) определяется однозначно через значение этой функции на подфраэах первого уровня. Более формально: представим фразу х синтаксически как „соединение" своих подфраз первого уровня: х = р(у11" аут) =и191" итвутииь+1, (8.28) где и1, ..., и~в+т — некоторые терминальные цепочки.
Например, для определенного вьпне языка арифметических выражений фраза, дерево вывода которой изображено на рис. 8.39 раскладывается следующим образом: (а+ (Ь*(с+ (Нт (е+д))))) = и1аиг(Ь*(с+ (Н*(е+д))))из, где и1 есть цепочка (,иэ — цепочка +, а из — цепочка ). Таким образом, любая фраза представляется, вообще говоря, не как простое соединение своих подфраз первого уровня, а как соединение с „прослойками" в виде определенных терминальных цепочек. Операцию у в (8.28), задающую такие прослойки, называют часто конкатпенарноа операцией. Эта операция определяется грамматикой языка.
Тогда предполагается, что если фраза х представлена в виде (8.28), то определено отображнение ф: ЩЬ)~в -+ У(Х,) (т.е. некоторая операция на предметной области), такое, что БЕМ(й)(х) =ф(БЕМ(й)(ут),...,ЯЕМ(Ц(у, )). (8.29) Это ограничение, накладываемое на семантическую функцию, назовем принципом еомоморфной интперпретпации. Д.8.2. Семантика формавьнык ввмков 697 Примем теперь некоторые соглашения об обозначениях. Семантическую функцию языка Ь будем обозначать ~ Ць, опуская индекс, указывающий на язык, если зто не ведет к недоразумению.
Тогда равенство (8.29) можно переписать в виде Подобные определения семантики фразы через семантику ее подфраз первого уровня называют семантическими правилами языка. Семантические правила соответствуют синтаксическим правилам — правилам исходной КС-грамматики. Так, для приведенной выше грамматики арифметических выражений, полагая Б = Й, можно записать следующие семантические правила: $Ехрт~)= $ЕхртД+ ~Ехрт~ (для синтаксического правила Ехрт -+ (Ехрт+ Ехрт) ), т.е.
здесь конкатенарной операции д, такой, что р(и,е) = (и+ о) для любых двух фраз и и и, сопоставляется обычное арифметическое сложение; ~Ехрт~ = ~Ехрт~ в~Ехрт~ (для синтаксического правила Ехрт -~ (Ехрт* Ехрт) ) операция на универсуме — арифметическое умножение; КЕМ 3 = КАйопъ) (для синтаксического правила Ехрт -~ А1отп); ЙАт 3 = йо;2 (для синтаксического правила АФотп — > а;, 1 = 1, и ). Строго говоря, в первых двух правилах мы должны различать три разных вхождения одного и того же нетерминала Ехрт, так как они соответствуют разным деревьям.
698 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Семантическая функция лзыка арифметических выражений будет определена, если мы зададим значение этой функции на атомах: это естественно ассоциируется с хорошо знакомой процедурой вычисления значения арифметического выражении при подстановке вместо входящих в него переменных конкретных числовых значений (при этом не исключается, что атом может быть константой — обозначением конкретного числа; в таком случае само синтаксическое правило задает сразу значение семантической функции на данном атоме). Так, для приведенного вьппе выражения, полагая $а)) = 1, ЦЬ)) = 2, ~(сД = 3, ЦдД = 4, ~(е)) = 5, $д]$ = 6, получим значение всего выражения, равное 95.
Таким образом, в этом конкретном случае семантика фразы есть числовое значение представленного данной фразой арифметического выражения. Мы рассмотрели в качестве универсума множество вещественных чисел и получили одну семантику. Задав универсум как-нибудь иначе (например, как множество комплексных чисел или множество функций некоторого класса), получим совсем другую семантику. Длл одного и того же синтаксиса, следовательно, могут быть определены различные семантики (семантические функции). Разобранный вьппе на примере языка арифметических выражений подход к определению семантики называют иногда энсшенснональным подходом. Суть его состоит в том, что лвно определветсл универсум как множество „внелзыковых" объектов (экстенсионалов) и каждой языковой фразе сопоставляется некоторый экстенсионал.
Длл разобранного выше примера экстенсионал — это вещественное число. Слово „внеязыковых" взлто в кавычки потому, что универсум сам может быть некоторым азыком (выступзющим тогда по отношению к исходному лзыку как метаязык). Не исключено даже, что метаязык совпадает с самим определяемым лзыком — примером могут служить всевозможные толковые словари.
Существует и другой подход к определению семантики, называемый ннгпенснональным, одной из разновидностей кото- Д.В.2. Семавтяяа форматьвых лтьтков 699 рого является ансиоматвинесний метод определения семантпини языка. Аксиоматический метод предполагает рассмотрение исходного, „объектного" языка, семантика которого определяется, как формальной тпеории (или формальнотЪ системы). Не давая строгого определения формальной теории в его общности, поясним его суть и рассмотрим пример.
Формальнал теория задается как некоторый язык, цепочки которого называются в этом случае ртпвержденилми (или предложениями). В этом языке определяется подъязык так называемых доказуемых утверждений: задается некоторое начальное множество утверждений, которые считаются априори доказанными (множество аксиом таеории), и задается некоторое множество правил вывода, применяя которые к некоторым утверждениям (в частности, уже доказанным), можно получать новые утверждения. Если мы применяем правило вывода к доказанному утверждению, то получаем новое доказанное утверждение. Утверждение, которое таким образом может быть выведено иэ аксиом, называют пгеоремот2 данной теории.
Утверждение считается имеющим смысл, если оно есть либо аксиома, либо теорема данной теории. В отличие от экстенсионального подхода при интенсиональном подходе априори не определяется никакой универсум, и при таком подходе к определению семантики „иметь смысл" означает „быть теоремой или аксиомой данной теории". Вернемся к рассмотренному вьппе языку арифметических выражений. Зададим его в виде формальной теории следующего вида: 1) аксиома — любой атом а1, ..., а„; 2) правила вывода: ет, ег =~ (ет + ег), (1) ет, ег ~ (ет * ег), (2) т.е. если ет и ег доказаны, то доказано утверждение (ет + ег) и утверждение (ет я ег).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
