68832

Загальна форма означення мови

Лекция

Информатика, кибернетика и программирование

Задати синтаксис це означає задати алфавіт та множину форм усіх речень мови семантика визначає смислове значення усіх цих речень. Існує декілька формальних засобів опису синтаксису мови. Оскільки синтаксис мови пов’язаний з множиною речень рядків символів необхідно домовитись про позначення...

Украинкский

2014-09-26

123.5 KB

2 чел.

Лекція 2

Загальна форма означення мови

Означення мови складається з завдання її синтаксису та семантики. Задати синтаксис - це означає задати алфавіт та множину форм усіх речень мови, семантика визначає смислове значення усіх цих речень. Існує декілька формальних засобів опису синтаксису мови. Один з них (БНФ) розглядався у попередній лекції. Формальні засоби означення семантики ґрунтуються на введенні властивостей (атрибутів) символів граматики і правил обчислення значень цих атрибутів. Оскільки синтаксис мови пов'язаний з множиною речень (рядків символів), необхідно домовитись про позначення таких множин та означити операції на них.

Регулярні множини та регулярні вирази

Нехай   = {a1, a2, … , an} – множина символів, яку назвемо алфавітом.

Означення 2.1. Мовою над алфавітом  називається множина рядків (ланцюжків або послідовностей) символів, що належать  .

Наприклад, коли   = {a, b, с}, то L1 = {aa, bc, abc} є мова, а L2 = {ab, abb, aac} - інша мова. Мова може мати і нескінчену кількість рядків, хоча алфавіт містить тільки скінчену кількість символів. Надалі будемо вважати, що рядок символів - це синонім речення мови.

Означення 2.2. Конкатенацією (зчепленням або добутком) мов L1 та L2 називається мова L1L2, що задовольняє умові 

L1L2 = {xy | x  L1 & y  L2}.

Наприклад, якщо L1 = {a, b}, L2 = {c, d}, то L1L2 = {ac, ad, bc, bd}. Для позначення конкатенації однакових мов будемо застосовувати символ степеня. Наприклад, L1L1 = L12 = {aa, ab, ba, bb}. Будемо вважати, що

L0 = ,

де   - пустий рядок, або рядок, що не містить жодного символу.

Означення 2.3. Об’єднанням мов  L1  та  L2  називається мова  L1  L2, що містить усі рядки, які належать хоча б до однієї з мов L1 чи L2 

L1        L2 = {x | x     L1  або  x     L 2}.

Означення 2.4. Ітерацією мови L називається мова L*, що задовольняє умові 

L* =           Ln.

Позитивна ітерація мови  L+:

L+ =            Ln.

 

Регулярна множина над алфавітом означається рекурсивно таким чином

(1) пуста множина рядків   - регулярна множина над  ;

(2) {} - регулярна множина над  ;

(3) {x} - регулярна множина над ,  x  ;

(4) якщо P та Q регулярні множини над , то  P    Q, PQ, P+, Q+ - регулярні множини над  .

Регулярний вираз - це запис, що позначає регулярну множину. Наприклад, PQ - це регулярний вираз, що позначає конкатенацію регулярних множин P та Q. У регулярних виразах операцію об’єднання позначають символом «+», використовують дужки «(» та «)» для зміни порядку операцій, пусту множину  рядків позначають як 0, а множину {} - як 1.

Означення 2.5. Регулярною алгеброю називається множина рядків символів скінченого алфавіту, на якій визначені три операції: об’єднання, конкатенація та ітерація, що задовольняють аксіомам:

  1.  A + B = B + A; 2) A + (B + С) = (A + B) + С; 3) A + A = A; 4) A + 0 = A;

5) A(BС) = (AB)С; 6) A1 = A = 1A; 7) A0 = 0 = 0A; 8) A(B + С) = AB + AC;

9) (A + B)С = AB + BС; 10) 0* = 1; 11) A* = A + A*; 12) (A*)* = A*.

Регулярні вирази дають змогу описувати мови, але не будь-які. Тому для опису мови будемо користуватися також виразами, що не належать до класу регулярних. Наприклад, мову L, що містить усі рядки, у яких послідовність символів b ніколи не передує послідовності символів a, можна означити так

L = {ambn | m, n   0}

Означення граматики

Тепер повернемося до граматики парних чисел, розглянутої у минулій лекції. По-перше, її можна використати для визначення, чи є подана послідовність цифр (літер) парним числом. Наприклад, перевіримо послідовність 138. Літера 1 є за формулою (1) ненульовою цифрою і тому за формулою (4) - початком. Літера 3 - цифра (формула(1)), отже, 13 - початок (формула (4)). Нарешті, 8 - парна цифра (формула (3)), і з формули (5) випливає, що 138 - парне число.

По-друге, подану БНФ можна використати для написання (або, кажуть, породження) довільного парного числа. Наприклад, для того щоб одержати парне число, згідно з формулою (5) треба взяти парну цифру або початок, після якого записується парна цифра. Зупинимося на другому варіанті та одержимо послідовність 

<початок><парна цифра>.

Можна взяти одну з п’яти цифр, вказаних у формулі (3), і тоді одержати, наприклад,

<початок> 6.

Цифра 6 ніде у лівій частині формул не зустрічається. Тому за формулою (4) перетворюємо метасимвол <початок>, наприклад, так

<початок><цифра> 6.

Знову застосувавши формулу (4), можемо одержати

<ненульова цифра><цифра> 6.

Подальше послідовне застосування формул (2) та (1) дає, наприклад, парне число 106.

 Показуючи можливість переходу від лівої частини формули до правої символом «    » та використовуючи великі латинські букви для позначення власно метасимволів: A - <парне число>, B - <початок>, С - <парна цифра>, D -<цифра>, Е - <ненульова цифра>, - одержимо опис граматики парних чисел у формі 

A C|BC

B  E|BD

C   012141618

D   0|E

E   1|2|3|4|5|6|7|8|9.

З означення БНФ випливає, що від поданої форми можна перейти до еквівалентної, що не містить символів « | ». Наприклад, формулу для А можна перетворити у дві формули

А      С

А      ВС.

Одержана форма граматики називається набором правил, що породжує мову, або набором продукцій. Кожна формула - це правило. Характерною особливістю такого набора правил є можливість отримання будь-якого речення мови з одного символа (у розглянутому прикладі А). Але у цьому нема нічого дивного, тому що цей символ і уводився для позначення довільного речення даної мови.

Розглянемо граматику мови

L = {0 n1n |  n  0},

що містить усі послідовності, складені з однакової кількості нулів та одиниць таким чином, що спочатку записуються нулі, а потім - одиниці. Продукції цієї граматики мають вигляд 

1. S      0S1

2. S      .

Для того, щоб одержати деяке речення треба до символу S застосувати декілька разів правило 1, а потім - правило 2. Зрозуміло, що застосування правила 2 зупиняє процес. Наприклад,

S  0S1  00S11 000S111 000111.

Послідовність вказаних кроків називається виводом рядка 000111, а кожне застосування продукції - кроком виводу або підстановкою. Виявляється, що найбільш істотні властивості формальних мов залежать від вигляду продукцій. Для того, щоб перейти до розгляду цієї залежності, уведемо означення граматики.

Означення 2.6. Граматикою G називається алгебраїчна структура, що являє собою упорядковану четвірку (N, T , P, S), де

а) N та T - непусті скінчені алфавіти відповідно нетермінальних та термінальних символів такі, що N  T = ; об’єднання цих алфавітів будемо позначати символом  V  і називати словником граматики G: V = N  T;

б) P - скінчена множина продукцій вигляду

                 ,                                                                             

де       V* N V*,    V*, і тому  P  V* N V* x V*;

в) S  N  і називається початковим символом, джерелом або аксіомою.

Якщо      P, і ,   V*, то кажуть, що рядки    та    задовольняють відношенню безпосередньої виводимості, і записують це так

    

Транзитивне замикання цього відношення позначають символом +, а рефлексивно-транзитивне - *. Якщо для рядків та має місце   + , то кажуть, що    нетривіально виводиться з  .

Приклади формальних граматик

 Розглянемо граматику G1 мови L1, що описується виразом

L1 = {a m b n | m, n  0}.

Ця граматика має вигляд

G1 = ({S, A, B}, {a, b}, P1, S}).

Елементами P1 є правила

1. S  AB

2. A  aA

3. A  

4. B  bB

5. B  

Вивід рядка aaabb:

 S  AB  aAB  aaAB  aaaAB  aaaB  aaabB  aaabbB  aaabb.

Кожний рядок, що утворюється на черговому кроці виводу, називається сентенціальною формою. Речення мови - це сентенціальна форма, що містить тільки термінали. Надалі для позначення терміналів будемо застосовувати рядкові букви, а нетерміналів - великі.

Часто речення мови можна породжувати за допомогою різних граматик. Дві граматики Gi та Gj, що породжують одну і ту ж саму мову, тобто L(Gi) = L(Gj), називають еквівалентними. Наприклад, розглянутій вище граматиці G1 еквівалентна граматика G2 = ({S, Y}, {a, b}, P2, S), де P2:

1. S  aS             5. Y  b

2. S  a              6. Y  bY

3. S  b              7. S  

4. S  bY

При створенні компілятора одна з еквівалентних граматик може виявитись зручнішою за іншу.

У розглянутих вище прикладах ліві частини правил складалися з одного нетерміналу. Але означення граматики цього зовсім не потребує. Як приклад граматики, що містить правила, у лівій частині яких знаходиться більше одного символа, розглянемо граматику G3 для породження мови L3:

L3 = {ak | k = 2n  &  n  0}.

G3 = ({S, M, Q, R}, {a}, P3, S),

де P3:

1. S  QMQ                4. RQ  MMQ

2. QM  QR                 5. M  a

3. RM  MMR             6. Q  .

Послідовне виконання правил 2, 3 (можливо багаторазове) та 4 призводить до подвоєння символів M. Причому, почавши виконувати таку послідовність кроків виводу, не можна зупинитися у довільний момент, тому що сентенціальна форма буде містити символ R. А у цьому випадку перейти до рядка, що містить тільки термінали, за допомогою правил 5 та 6 нема можливості. Тому мова, що визначається граматикою G3, дійсно містить тільки рядки s, довжина яких дорівнює цілому невід’ємному степеню 2. Це позначається так | s | = 2k , k    0.

Приклад виводу:

S  QMQ  QRQ  QMMQ  QRMQ  QMMRQ  QMMMMQ + aaaa.

Класифікація Хомського

Аналізуючи властивості мов, що визначаються різними граматиками, американський вчений Хомський запропонував відрізняти граматики залежно від вигляду продукцій. Класифікація Хомського має ієрархічний характер, тобто кожний наступний клас граматик є підкласом (підмножиною) попереднього.

Якщо на продукції граматики не накладаються ніякі обмеження, то така граматика називається граматикою Хомського типу 0.

Граматика G = (N, T, P, S) називається граматикою Хомського типу 1 або контекстно-залежною граматикою (КЗГ), якщо усі елементи P мають вигляд 

  ,

де   = 1A2,   =  12,  1, 2  V*, A  N,    V+.

У цьому означенні рядки  1  та  2  можна розглядати як контекст (оточення), у якому символ A може бути замінений на  . Звідси походить назва граматики.  

Якщо усі елементи P мають вигляд

A  ,

де  A  N,    V+,

то граматику називають граматикою Хомського типу 2.

Нарешті, якщо P складається тільки з продукцій виду

 A  ,

де  A  N та   {T  TN} (тобто права частина є або термінал, або термінал, за яким прямує один нетермінал), то кажуть, що G - це граматика Хомського типу 3.

Якщо припустити, що граматики Хомського типу 2 та 3 можуть містити -продукцію вигляду 

S  ,

де   - пустий рядок, то утворюються відповідно контекстно-вільна та регулярна граматики.

Ієрархія граматик природним чином переноситься на ієрархію мов. Наприклад, якщо мову можна генерувати за допомогою граматики типу 2, то її називають мовою типу 2.

Характерна властивість контекстно-залежної мови

Теорема 2.1. Мова L є контекстно-залежною тоді і тільки тоді, коли вона породжується граматикою, усі продукції якої

  

задовольняють умові

1   |  |       |  | .          

 Доведення. Якщо L контекстно-залежна мова, то існує контекстно-залежна граматика G = (N, T, P, S), що породжує її (L = L(G)), і всі продукції G мають вигляд 

1A2  12,

де  A  N,     V+,  1, 2  V*.

Тоді можна записати

| 1 A 2 | = | 1 | + | A | + | 2 | = | 1 | + 1 + | 2 |  1,

| 12 | = | 1 | + |  | + | 2 |  | 1 | + 1 + | 2 | = | 1 A 2 | ,

і тому

1 | 1 A 2 |  | 1 2 |.

Цим доведено необхідність.

Тепер доведемо достатність. Нехай G = (N, T, P, S)- граматика, усі продукції якої

  

задовольняють умові

1 |  | |  |.

Побудуємо граматику R, еквівалентну граматиці G, з продукціями вигляду 

1A2  12 

Продукції G мають вигляд

1) A  1n;

2)  1m  1k ,   де  m  k,  і   A  N,  i, i  V.

В усіх продукціях замінимо кожний елемент ai  T новим нетерміналом Ai і включимо продукцію  Ai     ai  у  R. Продукції типу 1) також включимо в R, оскільки вони мають правильну форму, а кожну продукцію типу 2), що має вигляд 

W1Wn   Y1Yq,  n  q,

перетворимо в n + q нових продукцій:

W1 … Wn  X1W2 … Wn,

X1W2 … Wn  X1 X2W3 … Wn,

…………….

                                    X1… X n-2Wn-1Wn  X1 … X n-1Wn ,

                                             X1… X n-1Wn  X1 … X n-1Xn X n+1Xq,

                                                    X1… X q  Y1X2 … Xq ,

                                               Y1 X2… X q   Y1Y2X3 … Xq ,

…………….

                                             Y1 … Yq-1 X q  Y1 … Yq .

Усі ці продукції мають вигляд      1A2  12,  і R еквівалентна G.


 

А также другие работы, которые могут Вас заинтересовать

76492. Имущественные права несовершеннолетнего ребенка 21 KB
  Создание условий жизни необходимых для развития ребенка обеспечивается главным образом родителями несущими основную финансовую ответственность за его достойное содержание. Статья 60 СК наделяет ребенка следующими имущественными правами: а правом на получение содержания от своих родителей и других членов семьи то есть совершеннолетних трудоспособных братьев и сестер дедушки бабушки; б правом собственности на полученные им доходы имущество полученное им в дар или в порядке наследования и на любое другое имущество приобретенное на...
76493. Споры о воспитании детей 16.87 KB
  Существует два вида споров о воспитании детей: споры о месте жительства несовершеннолетнего ребенка при раздельном проживании родителей; споры об участии отдельно проживающего родителя в воспитании ребенка. 66 Семейного Кодекса Российской Федерации родители при их раздельном проживании могут решить вопрос о месте проживания ребенка соглашением письменным договором в котором сами определяют с кем из родителей будут жить несовершеннолетние дети кто и в каких размерах будет выплачивать средства на их содержание Однако такое соглашение не...
76494. Права и обязанности родителей 19.17 KB
  Большинство прав родителей корреспондируются с правами ребенка однако последние шире по объему. Втретьих при осуществлении родительских прав и обязанностей должен соблюдаться приоритет интересов ребенка п. Это положение имеет принципиальное значение поскольку нередки жизненные ситуации когда интересы родителя противоречат интересам ребенка. Например родители не оказывают должного внимания духовному развитию ребенка ссылаясь на нехватку времени.
76495. Осуществление и защита родительских прав 14.01 KB
  Способы воспитания детей должны исключать пренебрежительное жестокое грубое унижающее человеческое достоинство обращение оскорбление или эксплуатацию детей. Родители осуществляющие родительские права в ущерб правам и интересам детей несут ответственность в установленном законом порядке. Все вопросы касающиеся воспитания и образования детей решаются родителями по их взаимному согласию исходя из интересов детей и с учетом мнения детей.
76496. Осуществление прав отдельно проживающим родителем 16.2 KB
  66 СК родитель проживающий отдельно от ребенка имеет право на общение с ребенком участие в его воспитании и решение вопросов получения ребенком образования что согласуется с установленным в Кодексе принципом равных родительских прав и обязанностей п. В результате ущемляются законные права и интересы как одного из родителей так и ребенка. 66 СК установлено что родитель с которым проживает ребенок не должен препятствовать общению ребенка с другим родителем если такое общение не причиняет вред физическому и психическому здоровью...
76497. Меры государственной помощи семьям, имеющим детей 17.04 KB
  Основные виды государственных пособий гражданам имеющим детей в связи с их рождением и воспитанием перечислены в Федеральном законе от 19. При этом более подробные нормы об условиях назначения детских пособий и порядке их выплаты содержатся в Приказе Минздравсоцразвития России от 23 декабря 2009 г. N 1012н Об утверждении Порядка и условий назначения и выплаты государственных пособий гражданам имеющим детей. В указанных правовых актах перечислены следующие виды пособий: 1 пособие по беременности и родам; 2 единовременное пособие...
76498. Защита прав несовершеннолетних детей 19.12 KB
  56 Семейного Кодекса РФ говорит о том что ребенок имеет право на защиту своих прав и право на защиту от злоупотреблений со стороны родителей. Защита прав и законных интересов осуществляется родителями а в случаях предусмотренных Семейным кодексом в частности когда органом опеки и попечительства установлено что между интересами родителей и детей имеются противоречия родители лишены родительских прав граждане чья дееспособность ограничена вследствие злоупотребления алкоголем органом Опеки и попечительства прокурором судом. При...
76499. Лишение родительских прав: основания, порядок 16.41 KB
  Уклонение родителей от выполнения своих обязанностей по воспитанию детей может выражаться в отсутствии заботы об их нравственном и физическом развитии обучении подготовке к общественно полезному труду; – отказываются без уважительных причин взять своего ребенка из родильного дома отделения либо из иного лечебного учреждения воспитательного учреждения учреждения социальной защиты населения или из других аналогичных учреждений; – злоупотребляют своими родительскими правами т. использование этих прав в ущерб интересам детей например...
76500. Правовые последствия лишения родительских прав 16.64 KB
  71 СК следует что родители лишенные родительских прав утрачивают вопервых все права основанные на факте родства с ребенком в отношении которого они лишены родительских прав причем речь идет не только о тех правах которые они имели до достижения детьми совершеннолетия но и других вытекающих как из семейных так и иных правоотношений. Вовторых родители лишенные родительских прав утрачивают право на льготы и государственные пособия установленные для граждан имеющих детей. Так лишение родительских прав влечет утрату для...