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,

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


 

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

37939. Изучение свойств ферромагнетиков и явления магнитного гистерезиса для железа 202.5 KB
  Изучение магнитных свойств вещества. Расчет и построение кривой намагничивания, снятие петли гистерезиса и определение тепловых потерь на перемагничивание ферромагнетиков. Вычисление коэрцитивной силы и остаточной намагниченности изучаемого образца железа.
37940. ОПРЕДЕЛЕНИЕ УСКОРЕНИЯ СВОБОДНОГО ПАДЕНИЯ С ПОМОЩЬЮ ФИЗИЧЕСКОГО И МАТЕМАТИЧЕСКОГО МАЯТНИКОВ 166.5 KB
  Определение ускорения свободного падения с помощью математического маятника. Определение ускорения свободного падения с помощью оборотного маятника.Определение ускорения свободного падения с помощью математического маятника.Определение ускорения свободного падения с помощью оборотного маятника.
37941. ИЗУЧЕНИЕ КОЛЕБАНИЙ ПРУЖИННОГО МАЯТНИКА 168.5 KB
  11 Изучение свободных незатухающих колебаний пружинного маятника.11 Изучение затухающих колебаний пружинного маятника12 5. Изучение вынужденных колебаний пружинного маятника.14 ЛАБОРАТОРНАЯ РАБОТА № 10 ИЗУЧЕНИЕ КОЛЕБАНИЙ ПРУЖИННОГО МАЯТНИКА Цель работы Изучение свободных незатухающих свободных затухающих и вынужденных колебаний пружинного маятника.
37942. Изучение собственных колебаний струны 137 KB
  Колебания струны5 3.10 Лабораторная работа № 11 а Изучение собственных колебаний струны 1. Цель работы Изучение собственных колебаний струны. Колебания струны В закрепленной с обоих концов натянутой струне при возбуждении поперечных колебаний устанавливаются стоячие волны причем в местах закрепления струны должны располагаться узлы.
37943. Определение ускорения силы тяжести при свободном падении тела 374 KB
  Центростремительное ускорение соответствующее движению Земли по орбите годичное вращение гораздо меньше чем центростремительное ускорение связанное с суточным вращением Земли. Поэтому с достаточной точностью можно считать что система отсчета связанная с Землей вращается относительно инерциальных систем с постоянной угловой скоростью суточного t = 86400 с вращения Земли . Если не учитывать вращение Земли то тело лежащее на ее поверхности следует рассматривать как покоящееся сумма действующих на это тело сил равнялось бы тогда...
37944. Изучение закона сохранения энергии с помощью маятника Максвелла 188 KB
  12 Лабораторная работа № 13 Изучение закона сохранения энергии с помощью маятника Максвелла 1. Цель работы Изучение закона сохранения энергии на примере движения маятника Максвелла. Диск маятника представляет собой непосредственно сам диск и сменные кольца которые закрепляются на диске. При освобождении маятника диск начинает движение: поступательное вниз и вращательное вокруг своей оси симметрии.
37945. НАКЛОННЫЙ МАЯТНИК 252 KB
  Изучение силы трения качения. Определение коэффициента трения качения. Со стороны поверхности на тело действует сила трения FТР. Тело скользит по поверхности со скоростью на него действует сила трения совершающая отрицательную работу вследствие чего полная механическая энергия системы уменьшается т.
37946. Изучение закона сохранения момента импульса с помощью гироскопа и определение скорости его прецессии 695 KB
  12 Лабораторная работа № 15 Изучение закона сохранения момента импульса с помощью гироскопа и определение скорости его прецессии 1. Цель работы Изучение гироскопического эффекта и закона сохранения момента импульса с помощью гироскопа. Определение скорости прецессии гироскопа измерение угловой скорости вращения маховика гироскопа и момента инерции гироскопа. Справедливость этого закона можно проверить с помощью гироскопа.
37947. Определение коэффициента Пуассона воздуха методом адиабати 445 KB
  1 Определение коэффициента Пуассона воздуха методом адиабатического расширения: Методические указания к лабораторной работе № 16 по курсу общей физики Уфимск. В работе определяется коэффициент Пуассона воздуха методом адиабатического расширения основанным на измерении давления газа в сосуде после последовательно происходящих процессов его адиабатического расширения и изохорного нагревания.8] Список литературы ЛАБОРАТОРНАЯ РАБОТА № 16 ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПУАССОНА ВОЗДУХА МЕТОДОМ АДИАБАТИЧЕСКОГО РАСШИРЕНИЯ 1. Цель работы Определение...