68833

Особливості класифікації формальних мов

Лекция

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

Наприклад контекстновільна граматика G1 розглянута у попередній лекції нерегулярна а мова L1 що нею генерується регулярна тому що її можна одержати за допомогою регулярної граматики G2. Граматики типу 3 а також регулярні граматики мають істотні переваги перед іншими типами граматик тому...

Украинкский

2014-09-26

117 KB

1 чел.

Лекція 3

Особливості класифікації формальних мов

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

    Багато  так  званих  "локальних"  засобів   (конструкцій)   мов програмування можуть бути описані граматикою типу  3.  Серед  них  - константи, службові слова, ідентифікатори. Наприклад,  ідентифікатор визначається правилами  

ID  буква

ID  буква ЗАЛИШОК

ЗАЛИШОК буква

ЗАЛИШОК цифра

ЗАЛИШОК буква ЗАЛИШОК

ЗАЛИШОК  цифра ЗАЛИШОК .

    Граматики типу 3, а також  регулярні  граматики  мають  істотні переваги перед іншими типами граматик тому, що для них існують алгоритми, що розв’язують такі задачі: 

    1) для поданих граматики  G  та рядка    термінальних символів встановити,  чи  належить     до   мови   L(G),   що   генерується граматикою  G;

    2) для поданих двох граматик  G1   та  G2   встановити,  чи  вони еквівалентні.

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

1) при читанні зліва направо кількість зустрінутих  закриваючих дужок не перебільшує кількості зустрінутих відкриваючих;

2) кожний рядок  містить  однакову  кількість  відкриваючих  та закриваючих дужок.

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

((( )))

(( )( )) .

Рядок

( ))(( )

не належить мові дужок, тому що не виконується властивість 1).

З теорії  [1]  відомо,  що  мова  дужок  нерегулярна.  Але  усі правильні рядки дужок можна породити за допомогою контекстно-вільної граматики:

S (S)

S SS 

S  .

    У  більшості  мов  програмування  є   декілька   видів   дужок, наприклад,

(   ) ,   [    ],  begin   end .

Обмеження на використання декількох видів дужок також можна означити за допомогою контекстно-вільної граматики. Цей тип граматик  одержав найбільше застосування на етапі синтаксичного аналізу.

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

x :=  y

допустиме  тільки,  якщо   x   та    y    мають   відповідні   типи. Контекстно-вільна граматика не дозволяє описати це обмеження, і тому необхідно використовувати граматики іншого типу.

Чим більш універсальний клас  граматики,  що  використовується, тим більше конструкцій типових мов програмування  можна  описати.  З іншого боку, чим вище рівень універсальності граматики, тим  складніша  програма, що застосовує цю граматику для аналізу рядків символів.

Застосування формальної теорії мов при розробці мов програмування

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

Повідомлення про  Алгол 60  з’явилося  однією  з  перших  спроб формального означення мови. Більшу частину синтаксису  було  описано за допомогою контекстно-вільної граматики,  а  решту  синтаксису  та семантику - англійською  мовою.  У  першому  повідомленні  містилось багато  неоднозначностей,  і  навіть  переглянуте  повідомлення   не виявилося вільним від них.

Подальший розвиток методи формального означення мов програмування отримали  у  повідомленні  про  Алгол  W,  у якому у формальну частину означення синтаксису було включено інформацію  про тип.

Істотне просування у розвитку методів, що розглядаються, одержано у  переглянутому повідомленні про Алгол 68,  де для означення  усього синтаксису   мови застосовано дворівневу граматику. Ця граматика ще називається W-граматикою  на  честь  її винахідника    ванВейнгаардена.   Ідея   застосування   дворівневої граматики полягає в тому,  що одна  граматика  використовується  для генерації нескінченої кількості правил другої. Правила ж останньої генерують речення  Алголу 68. Дворівневі  граматики  застосовуються також для опису семантики мов програмування.

Крім дворівневих граматик  для  опису  мов  програмування, що містять  контекстно-залежні конструкції, використовують атрибутні, аффіксні та інші граматики [2, 3].

Дерево виводу

Контекстно-вільна   мова   (КВ-мова) означається як множина термінальних  рядків,  які  можна вивести з початкового символу. Виводу кожного рядка символів КВ-мови можна поставити у відповідність дерево виводу.  Це  робиться  шляхом інтерпретації  кожної  підстановки  кроком  побудови дерева. При цьому кожному символу, що використовується  при  виводі, ставлять у відповідність вершину, і з вершини  a  проводиться  дуга  у вершину  b, коли черговий крок виводу полягає у  заміні  символу   a  на символи, серед яких є символ  b.

Розглянемо  приклад  побудови  дерева  виводу.   Нехай   подано граматику 

1. S aABc                   4. A Ab

2. S                            5. B bB

3. A  cSB                      6. B   a.

Візьмемо, наприклад, рядок  acabac, його вивід  можна  виконати так

S aABc aAbBc acSBbBc acSabBc acabBc acabac.

                1        4              3                   6                2                      6

Цифри під нетерміналами показують, який символ замінюється,  та  яке правило застосовується.  Першій  підстановці  відповідає  дерево  на рис. 3.1,а, другій - 3.1,б і т.д., останній - 3.1,е.

а

б

в

г

д

е

Рис.3.1. Побудова дерева виводу.

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

Побудованому дереву відповідає і інший вивід

S aABc aAbBc acSBbBc acBbBc acabBc acabac.

                 1        4              3                2                   6                     6

У цьому  виводі  кожна  підстановка  замінює  найлівіший  нетермінал сентенціальної   форми.   Такий   вивід   називається   лівим   (або лівостороннім).

Для кожного дерева існує тільки один лівий вивід та тільки один правий (коли замінюється найправіший нетермінал).  Відношення  лівої та правої безпосередньої виводимості рядка    з    позначаються відповідно    L   та     R .   Для позначення замикань цих відношень використовують відповідно символи  *L та   *R.

Очевидно, відношення   L та R  дозволяють  за  лівою  та  правою частинами визначити застосовану підстановку.

Неоднозначні граматики

Рядку мови може відповідати більш  ніж  одне  дерево,  оскільки рядок може мати  різні  виводи,  що  породжують  неоднакові  дерева. Наприклад, для рядка  acabac  існує інше дерево (рис.3.2).

Рис.3.2. Дерево виводу рядка  acabac.              

Цьому дереву відповідає, наприклад, вивід

S aABc aAbBc acSBbBc acSabBc  

acabBc acabac.

Коли граматика дозволяє генерувати деякий  рядок  за  допомогою виводів, яким відповідають різні дерева,  таку  граматику  називають неоднозначною.

  Розглянемо ще один приклад неоднозначної граматики

                             E  EtE

                             E  x.

Для  рядка   xtxtx   одержуємо  два  різних  дерева  (рис.3.3),   що відповідають лівим виводам:

           а) E  EtE  EtEtE  xtEtE  xtxtE  xtxtx;

           б) E  EtE  xtE  xtEtE  xtxtE  xtxtx.

Якщо інтерпретувати символ  t  як бінарну операцію, а  x  -  як операнд, то  можна  вважати,  що  структура  дерева  відображає послідовність обчислення виразу  xtxtx: (xtx)tx  -  дерево   а), xt(xtx)  -  дерево  б). У разі, коли   t   -  додавання,  результати обох обчислень співпадають:

(x1  + x2) + x3  = x1  + (x2  + x3),

а коли  t  є віднімання  - ні:

а

( x1  - x2) - x3  x1  - ( x2  - x3 ) .

б

Рис.3.3. Дерева двох виводів рядка  xtxtx.

За поданою неоднозначною граматикою для  КВ-мови  можна  (але  не завжди) знайти однозначну для тієї ж мови. Для мови з прикладу існує багато однозначних граматик, у тому числі дві такі:   

E Etx

E x

та

E xtE

E x

Згідно з першою граматикою спочатку виконується найлівіша операція (таку операцію називають лівоасоційованою, а згідно з другоюнайправіша (правоасоційована операція).

Наведений  приклад   показує, що  у  компіляторах треба використовувати однозначні граматики. Але встановлення, чи  належить подана граматика до класу однозначних, може  виявитись  дуже  складною проблемою, тому що теоретично доведено [1],  що  ця  задача  не  має алгоритмічного розв’язку. Крім того, треба мати на увазі,  що  деякі мови принципово не можуть описуватись однозначною граматикою.

Проблема граматичного розбору

Задача  розбору  полягає  у  пошуку  послідовності  продукцій, що ведуть від початкового символа до  поданого  рядка.  Коли пошук послідовності починають  з  початкового  символа  і  йдуть  до вхідного рядка, метод розбору  називають  низхідним.  У  разі,  коли пошук ведеться у напрямку від вхідного рядка до початкового символа, метод розбору - висхідний. Існують і комбіновані методи.

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

Розглянемо приклад повернення у виводі. Нехай подано граматику з правилами:

S A

S B

A xA | y

B xB | z.

і треба проаналізувати (або встановити, чи існує вивід) рядок xxxz. Якщо спочатку застосовується послідовність правил:

S A xA xxA xxxA,

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

S B xB xxB xxxB xxxz,

Основна прикладна задача теорії синтаксичного аналізу - це розробка детермінованих методів.


 

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

34081. Право государственной и муниципальной собственности на землю 36 KB
  Право государственной и муниципальной собственности на землю. Особенность субъектов государственной собственности в том что они обладают правом территориального верховенства. В соответствии с ГК в государственной собственности находятся все земли за исключением земель находящихся в муниципальной или частной собственности презумпция государственной собственности на землю. Порядок разграничения государственной собственности на землю определяется Земельным кодексом Законом â€œО введении в действие Земельного кодекса†Закона “О...
34082. Право частной собственности на земельные участки: общая характеристика, субъекты права собственности 31.5 KB
  Право частной собственности на земельные участки: общая характеристика субъекты права собственности. Частная собственность на земельные участки. Исключения: иностранцы лица без гражданства а также российские юридические лица в уставном складочном которых доля иностранцев и лиц без гражданства более 50 могут использовать земли сельскохозяйственного назначения только на праве аренды ФЗ â€œОб обороте земель сельскохозяйственного назначенияâ€; земельные участки расположенные на территории ЗАТО могут приобретать российские...
34083. Содержание права частной собственности на землю. Объект права частной собственности 30 KB
  Содержание права частной собственности на землю. Объект права частной собственности. Право собственности является наиболее обширным по объему правом на вещь. Римские юристы не оставили точного определения права собственности но упоминали об основных правомочиях собственника.
34084. Разграничение государственной собственности на землю 27.5 KB
  Разграничение государственной собственности на землю. 214 ГК РФ государственная собственность имущество принадлежащее на праве собственности Российской Федерации федеральная собственность и имущество принадлежащее на праве собственности субъектам Российской Федерации собственностьсубъектов Российской Федерации. Таким образом субъектами права государственной собственности являются Российская Федерация республики края области города федерального значения автономная область автономные округа.Поскольку объектами любых прав...
34085. Понятие и общая характеристика приватизации земель в Российской Федерации 25 KB
  Приватизация земельных участков может осуществляться одновременно с приватизацией расположенных на нем объектов недвижимости на основании положений Земельного кодекса РФ ФЗ от 21 декабря 2001 г. 3 ФЗ О введении в действие Земельного кодекса Российской Федерации. Приватизация земельных участков может производиться путем продажи их на аукционе или конкурсе продажи посредством публичного предложения или без объявления цены путем внесения земельного участка в качестве вклада в уставный капитал открытого акционерного общества. Цена выкупа...
34086. Пожизненное наследуемое владение земельным участком 24.5 KB
  Право пожизненного наследуемого владения. предоставление земельных участков на праве пожизненного земельного владения не допускается. Основаниями возникновения права пожизненного наследуемого владения являются: принятие наследства в состав которого входит пожизненное наследуемое владение на земельный участок. договор куплипродажи или иная сделка об отчуждении здания строения сооружения расположенные на земельном участке принадлежавшем бывшему собственнику зданий строений сооружений на праве пожизненного наследуемого владения;...
34087. Постоянное (бессрочное) пользование земельным участком 27.5 KB
  Юридические лица могут быть разделены на 3 группы по отношению к этому праву: юридические лица которым и после введения в действие Земельного Кодекса предоставляются земельный участки на данном праве и которые могут использовать земельные участки на праве постоянного бессрочного пользования органы государственной власти органы местного самоуправления государственные и муниципальные учреждения казенные предприятия центры исторического наследия президентов России прекративших исполнение своих полномочий; юридические лица...
34088. Основания возникновения и изменения прав на земельные участки 59 KB
  По договору кули продажи одна сторона продавец обязуется пережать другой стороне покупателю земельный участок за плату. договор дарения: По договору дарения одна сторона даритель безвозмездно передает или обязуется передать земельный участок другой стороне одаряемому в собственность. договор ренты: По договору ренты одна сторона получатель ренты передаёт другой стороне плательщику ренты земельный участок в собственность а плательщик ренты обязуется периодически выплачивать ренту. Рента обременяет земельный участок поэтому...
34089. Основания прекращения прав на земельные участки 38.5 KB
  Основания добровольного прекращения: ликвидация юридического лица; смерть гражданина и отсутствие соответствующих наследников; отчуждение земельного участка другим лицам в порядке установленном гражданским законодательством; добровольный отказ от прав на земельный участок. Процедура различна для собственников и лиц не являющихся собственниками Собственник земельного участка может отказаться от своего права путем подачи заявления в орган осуществляющий государственную регистрацию прав на недвижимое имущество и сделок с ним....