ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    LL (k)-граматики
         

     

    Інформатика, програмування
    LL (k) - граматики.

    Визначення LL (k)-граматик.
    Для початку припустимо, що G = ( N , E , P , S ) - однозначна граматика і w = a1, a2 ... an - ланцюжок з L ( G ). Тоді існує єдина послідовність левовиводімих ланцюжків b0, b1 .. bm, для якої S = b0, bi, pi Ю bi 1 при 0 <= i   Припустимо, що ми хочемо знайти цей лівий розбір, переглядаючи w один раз зліва направо. Можна спробувати зробити це, будуючи послідовність левовиводімих ланцюжків b0, b1 .. bm. Якщо bi = a1, a2 ... ajAB, то до даного моменту аналізу ми вже прочитали першими j вхідних символів і порівняли їх з першими j символами ланцюжка bi. Було б бажано визначити bi 1, знаючи тільки a1, a2 ... aj (частина вхідний ланцюжки, зчитану до даного моменту), кілька наступних вхідних символів (aj 1 aj +2 ... aj + k для деякого фіксованого k) і нетермінал A. Якщо ці три чинники однозначно визначають, яке правило треба застосувати для розгорнення нетермінала A, то ai +1 точно визначається за ai і k вхідним символам aj 1 aj +2 ... aj + k.
    Граматика, в якій кожен лівий висновок, має таку властивість, називається LL (k)-граматикою. Ми побачимо, що для кожної LL (k) - граматики можна побудувати детермінований лівий аналізатор, що працює лінійний час. Дамо кілька визначень:
    ОПР: Нехай a = xb така левовиводімая ланцюжок у граматиці G = ( N , E , P , S ), що xОE *, а b або починається нетерміналом, або порожній ланцюжок. Будемо називати x закінченою частиною ланцюжка a, а b - незакінченою частиною частиною. Кордон між x і b будемо називати кордоном.
    ПЗМ: Нехай x = abacAaB, тоді abac - закінчена частина ланцюжка x, AaB - незакінчена частину ланцюжка. Якщо x = abc, то abc - закінчена частина і е - незакінчена і кордоном служить кінець ланцюжка.
    Іншими словами ідею LL (k) - граматики можна пояснити так: якщо є вже розібрана частина ланцюжка, то на підставі цього і ще декількох нерозібраних символів ми можемо зробити висновок про те, яке правило неоюходімо застосувати. Таким чином граматика посуществу не залежить (не рахуючи k наступних символів) від того, що виводиться з незакінченою частини ланцюжка. У термінах дерев цей процес виглядає наступним чином: дерево виводу ланцюжка будується починаючи з кореня і детерміновано зверху вниз.
    Вводять функцію FIRST (x) - повертає перший k символів. Зазвичай приписують в якості індексів k і G - кількість символів і граматика відповідно, але їх можна опускати, якщо це не викличе непорозумінь.
    ОПР: KC-граматика G = ( N , E , P , < b> S ) називається LL (k)-граматикою для деякого фіксованого k, якщо з існування двох лівих висновків
    (1) S Юw Aa ` Ю wb` a ` Юwx
    S Юw Aa ` Ю wc` a ` Юwy
    для яких FIRST ( x ) = FIRST ( y ), випливає що b ` = c` .
    Інакше це визначення виражає те, що для наявної ланцюжка і знаючи наступні k символів можна застосувати не більше одного правила виводу. Граматика називається LL - граматикою, якщо вона LL (k) - граматика для деякого k.
    ПЗМ: Хай G складається з правил S ® aAS | b , A ® a | bSA . Інтуїтивно G є LL (1) - граматикою, тому що, якщо дан найлівіший нетермінал С у левовиводімой ланцюжку і наступний вхідний символ с , існує не більше одного правила, що застосовується до С і що приводить до термінальної ланцюжку, що починається символом с . Переходячи до визначення LL (1) - граматики, ми бачимо, що якщо S Ю wSa ` Ю wb` a ` Ю wx і S Ю wSa ` Ю wc` a ` Ю wy та ланцюжки x і y починаються одним і тим же символом, то має бути b ` = c` . В даному випадку якщо x і y починаються символом a , то у висновку брало участь правило S ® aAS і b ` = c` = aAS . Альтернатива S ® b тут неможлива. З іншого боку, якщо x і y починаються з b , то має застосовуватися правило S ® b і b ` = c` = b . Зауважимо, що випадок x = y = e тут неможливий, так як з S у граматиці G не виводиться e .
    Коли розглядаються два висновки S Ю wAa ` Ю wc` a ` Ю wy міркування аналогічно. Граматика G є прикладом так званої простої LL (1) - граматики (або розділеної граматики).
    ОПР: КС-граматика G = ( N , E , P , < b> S ) без e-правил називається простий LL (k) - граматикою (або розділеної граматикою), якщо для кожного A Про N всі його альтернативи починаються різними термінальними символами.

    Пророкує алгоритми розбору.
    Розбір для LL (k)-граматики дуже зручно здійснювати за допомогою так званого k-який пророкує алгоритму розбору. k-який пророкує алгоритм використовує вхідну стрічку, магазин і вихідну стрічку. Алгоритм намагається простежити висновок ланцюжка, збережені на його вхідний стрічці. При читанні аналізованої ланцюжка вхідна головка може "заглядати" вперед на чергові k символу. Ці символи називають аванцепочкой. Алгоритм має конфігурацію що представляється трійкою (x, Xa, n ), де
    x - невикористана частина вхідний ланцюжка
    Xa - ланцюжок у магазині і Х - верхній символ
    n - ланцюжок на вихідний стрічці
    Роботою k-який пророкує алгоритму керує керуюча таблиця, яка задає відповідність між безліччю
    ((верхній символ магазину) Х (аванцепочка))
    і безліччю
    ((права частина правила і його номер) | помилка | викид | допуск).
    Алгоритм є коректним для граматики, якщо для будь-якої ланцюжка з цієї граматики алгоритм дозволяє отримати впорядкований список правил для її розбору. Якщо роботою якогось алгоритму керує якась таблиця і цей алгоритм виявляється коректним для даної граматики, то таблицю називають коректною.
    ПЗМ:
    Нехай дана граматика з правилами:
    S ® aAS
    S ® b
    A ® a
    A ® bSA
    Для такої граматики буде побудована таблиця:

    аванцепочка
    a b e верхній S aAS, 1 b, 2 помилка символ A a, 3 bSA, 4 помилка магазину a викид помилка помилка b помилка викид помилка $ помилка помилка допуск За такої таблиці буде проведений аналіз:
    ( abbab , S $, e) | - ( abbab , aAS $, 1 )
    bbab , AS $, 1 )
    bbab , bSAS $, 14 )
    bab , SAS $, 14 )
    bab , bAS $, 142 )
    ab , AS $, 142 )
    ab , aS $, 1423 )
    b , S $, 1423 )
    b , b $, 14232 )
    e, $, 14232 )
    k-який пророкує алгоритм розбору КС-граматики G можна моделювати на детермінованому МП-перетворювачі з кінцевим маркером на вхідних стрічці. Так як вхідна головка МП-перетворювача може оглянути тільки один вхідний символ, аванцепочка повинна зберігатися в кінцевій пам'яті керуючого пристрою. Інші деталі моделювання очевидні.
    ТРМ: Хай А - k-який пророкує алгоритм розбору для КС-граматики G . Тоді існує такий детермінований МП-перетворювач, який дозволяє розібрати будь-яку ланцюжок з цієї граматики. Інакше кажучи можна промоделювати будь-який алгоритм на зазначеному перетворювачі.
    СЛВ: Хай А - k-який пророкує алгоритм розбору для КС-граматики G . Тоді для G існує детермінований лівий аналізатор.

    Наслідки визначення LL (k)-граматики.
    Покажемо що для кожної LL (k) граматики можна механічно побудувати коректний k-який пророкує алгоритм розбору. Так як ядром алгоритму є управляюча таблиця, треба показати, як будувати з граматики таку таблицю. Для цього виведемо деякі слідства визначення LL (k) - граматики.
    У визначенні LL (k) - граматики стверджується, що для даної що виводиться ланцюжка wA a ланцюжок w і безпосередньо наступні за нею k вхідних символів однозначно визначають, яку застосувати правило для розгорнення нетермінала A. Тому на перший погляд може здатися, що для визначення потрібного правила треба пам'ятати весь ланцюжок w. Однак це не так. Доведемо теорему, дуже важливу для розуміння LL (k)-граматик:
    ТРМ: КС-граматика G = ( N , E , P , < b> S ) є LL (k)-граматикою тоді і тільки тоді, коли для двох різних правил A ® b ` і A ® c ` з P перетин FIRST ( b` a `) ЗFIRST ( c` a `) пусто для всіх таких wA a` , що S ЮwA a `.
    ДКВ: Необхідність. Припустимо, що w, A, a `, b` і c ` задовольняють умовам теореми, а FIRST ( b` a ` ) ЗFIRST ( c `a` ) містить x. Тоді за визначенням FIRST для деяких y і z знайдуться висновки S ЮwA a ` Юw b` a ` Юwxy і S ЮwA a ` Юw c` a ` Юwxz. (Зауважимо, що тут ми використали той факт, що N не містить марних терміналів, як це передбачається для всіх розглянутих граматик.) Якщо | x | b ` c` , то G не LL (k) - граматика.
    Достатність. Припустимо, що G не LL (k) - граматика. Тоді знайдуться такі два висновки S ЮwA a ` Юw b` a ` Юwx і S ЮwA a ` Юw c` a ` Юwy, що ланцюжки x і y збігаються в першу k позиціях, але b` c ` . Тому A ® b ` і A ® c` - різні правила з P і кожне з множин FIRST ( b `a` ) та FIRST ( c `a` ) містить ланцюжок FIRST (x) збігається з FIRST (y). ЧТД .
    ПЗМ: Граматика G з правила S ® a S | a, не буде LL (1) - граматикою, тому що FIRST1 (a S ) = FIRST1 (a) = a. Це можна пояснити так - бачачи тільки перший символ ланцюжка ми не можемо визначити який правило необхідно застосувати (ліве або праве). З іншого боку ця граматика є LL2 (k) граматикою - що цілком очевидно.
    ОПР: Хай G = ( N , E , P , S ) - КС-граматика. Визначимо FOLLOWk ( b `) як множина термінальних символів, які можуть зустрічатися після нетемінала, що є аргументом функції.
    ТРМ: КС-граматика G = ( N , E , P , < b> S ) є LL (1)-граматикою тоді і тільки тоді, коли для двох різних правил A ® b ` і A ® c ` перетин FIRST1 ( b` FOLLOW1 (A)) ЗFIRST1 ( c ` FOLLOW1 (A )) пусто при всіх AО N . (Без ДКВ ).
    Теорему можна сформулювати так: по першому символу після нетермінала необхідно вибрати застосовне правило - отже ці символи різні і перетин порожньо. Ця теорема може застосовуватися до LL (k) - граматики, але не завжди виконуватися. Граматики для яких виконується теорема називаються сильними, таким чином всі LL (1) граматики - сильні. Необхідно також відмітити що кожна LL (k) - граматика однозначна, тому якщо є неоднозначна граматика - то вона не LL (k). Є нерозв'язна проблема розпізнавання, чи існує для даної КС-граматики G , що не є LL (k), еквівалентна їй LL (k) - граматика . Проте у ряді випадків таке перетворення можливо. Застосовується два способи:
    Перший спосіб - усунення лівої рекурсії.
    ПЗМ: Хай G - граматика S ® S a | b яка не є LL-граматикою. Замінимо правила на наступні:
    S ® b S `
    S ` ® a S` | e
    отримавши при цьому еквівалентну LL (1) - граматику.
    Інший спосіб - ліва факторизація.
    ПЗМ: Розглянемо LL (2) - граматику G з двома правилами S ® a S | a. У цих двох правилах "вліво винесемо за дужки" символ a, записав їх у вигляді S ® a ( S | e). Іншими словами, ми вважаємо що операція конкатенації дистрибутивність щодо операції вибору альтернативи (позначається вертикальною рискою). Замінимо ці правила на:
    S ® aA
    A ® S | e
    тим самим отримаємо еквівалентну LL (1)-граматику.


    Розбір для LL (1) - граматик.
    Ядром пророкує алгоритму є управляюча таблиця. У цьому і наступних розділах буде показано як побудувати коректну керуючу таблицю.
    алг 1: Керуюча таблиця для LL (1)-граматики.
    Вхід: LL (1) - граматика.
    Вихід: Коректна керуюча таблиця.
    Метод: Будемо вважати, що $-маркер дна магазину. Таблиця визначається наступним чином:
     Якщо A ® a ` - правило з P з номером i, то M [A, a] = ( a` , i) для всіх a № e, що належать FIRST1 ( a `). Якщо eОFIRST1 ( a `), то M [A, b] = ( a` , i) для всіх bОFOLLOW1 (A).
     M [a, a] = викид для всіх aОE.
     M [$, e] = допуск.
     У решті випадків M [X, a] = помилка для XОNІEІ ($) і aОEІ (e).
    ТРМ: Запропонований алгоритм будує коректну керуючу таблицю для LL (1) - граматики G .

    Розбір для LL (k) - граматик.
    Побудуємо керуючу таблицю для довільної граматики. Якщо граматика сильна, то можна застосувати попередній алгоритм з аванцепочкамі розширені до k символів. В іншому випадку виникає кілька проблем. У 1-м пророкує алгоритмі розбору в магазин містилися тільки символи з E І N і виявлялося, що для однозначного визначення чергового застосовуваного правила досить знати нетермінальний символ нагорі магазину і поточний вхідний символ . Для не сильних граматик цього може виявитися недостатньо.
    ПЗМ: Візьмемо граматику
    S ® aAaa | bAba
    A ® b | e
    Якщо дані нетермінал A і аванцепочка ba, то не відомо, яке з правил треба застосувати.
    Невизначеності такого роду однак можна дозволити, зв'язавши з кожним нетерміналом і частиною левовиводімой ланцюжка (яка може виявитися праворуч), спеціальний символ, званий LL (k) - таблицею. По даній аванцепочке LL (k) - таблиця буде однозначно визначати яке правило треба застосувати на черговому кроці виводу.
    ОПР: Хай E - деякий алфавіт. Якщо L 1 і L 2 - підмножини E , то покладемо L 1 Еk L 2 = (
    w | для деяких xО L 1 і yО L 2
    або w = xy, якщо | xy | Јk
    або w складається з першого k символів ланцюжка xy
    )
    ЛМА: Для будь-якої КС-граматики G = ( N , E , P , S ) і будь-яких a `, b` Про ( N І E ):
    FIRSTk ( a `b` ) = FIRSTk ( a `) Еk FIRSTk ( b` )
    ОПР: Хай G = ( N , E , P , S ) - КС-граматика. Для кожних AО N і LН E визначимо LL (k) - таблицю Ta, l, відповідну A і L, як функцію T (u) , значенням якої служить:
     = помилка, якщо в P немає такого правила A ® a `, що FIRSTk ( a` ) Еk L містить u;
     = (A ® a `, ), якщо A ® a` - єдине правило з P, для якого FIRSTk ( a `) Еk L містить u;
     не визначено, якщо в множині знайдуться два і більше правила (цю ситуацію називають конфліктом між правилами)
    На нормальною мовою це означає що виробляється значення помилка, якщо u взагалі не є ланцюжком граматики, повертається правило якщо воно існує і тільки одне і якщо кілька правил - то значення не визначається.
    алг 2: Побудова LL (k) - таблиць.
    Вхід: LL (k) - граматика G = ( N , E , P , S ).
    Вихід: Безліч TG LL (k) - таблиць, необхідних для побудови управляючої таблиці для G .
    Метод:
     Побудувати LL (k) - таблицю T0, відповідну S і (e).
     Покласти спочатку TG = (T0).
     Для кожної LL (k)-таблиці TОTG, що містить елемент T (u) = (A ® x0B1x1 ... Bmxm, ) включити в TG LL (k ) - таблицю T для 1ЈiЈm, якщо T ще не входить до TG.
     Повторювати крок 3 поки в TG можна включати нові таблиці.
    ПЗМ: Побудуємо відповідне безліч LL (2) - таблиць для граматики S ® aAaa | bAba і A ® b | e. Почнемо з TG = (TS, (e)). Так як TS, (e) (aa) = ( S ® aAaa, (aa)), то в TG треба включити TA, (aa). Аналогічно, так як T0 (bb) = ( S ® bAba, (ba)), то в TG потрібно так само включити. (Елементи LL (2) - таблиць TA, (aa) і TA, (ba), відмінні від значення помилка, наведено в таблиці нижче). Зараз TG = (TS, (e), TA, (aa), TA, (ba)), і алгоритм вже не може включити в TG нових таблиць, так що це три LL (2) -- таблиці утворюють безліч відповідне граматиці.
    TA, (aa) TA, (ba) u правило безлічі u правило безлічі ba A ® b -- ba A ® e -- aa A ® e -- aa A ® b -- Тепер дамо алгоритм, яким можна побудувати коректну керуючу таблицю за відповідним безлічі LL (k) - таблиць. Керований цією таблицею k-який пророкує алгоритм буде як магазинних символів вживати замість нетерміналов LL (k) - таблиці.
    алг 3: Побудова керуючої таблиці для LL (k) - граматики.
    Вхід: LL (k) - граматика і відповідне безліч TG LL (k) - таблиць.
    Вихід: Коректна керуюча таблиця M для G .
    Метод: M визначається на множині (TGІEІ ($)) ґE * k наступним чином:
     Якщо A ® x0B1x1 ... Bmxm - правило з P з номером i і TA, LОTG, то для всіх u, для яких TA, L (u) = (A ® x0B1x1 ... Bmxm, ) вважаємо M [TA, L, u] = (x0TB1, Y1 ... TBm, Ymxm, i).
     M [a, av] = викид для всіх vОE * (k-1).
     M [$, e] = допуск.
     У решті випадків M [X, u] = помилка
     TS, (e) - початкова таблиця.


    ПЗМ: Побудуємо керуючу таблицю для LL (2) - граматики
    S ® aAaa
    S ® bAba
     A ® b
     A ® e
    використовуючи відповідне їй безліч LL (2)-таблиць, знайдене в попередньому прикладі. Алгоритм повинен видати таблицю:
    aa ab a ba bb b e T0 aT1aa, 1 aT1aa, 1 bT2ba, 2 T1 e, 4 b, 3 T2 e, 4 b, 3 a викид викид викид b викид викид викид $ допуск * де T0 = TS, (e), T1 = TA, (aa) і T2 = TA, (ba). Мається на увазі, що в порожніх осередках - помилка. Допуск * знаходиться в останній колонці. Для вхідних ланцюжка bba 2-який пророкує алгоритм видасть таку послідовність тактів:
    (bba, T0 $, e) | - (bba, bT2ba $, 2)
     (ba, T2ba $, 2)
     (ba, ba $, 24)
     (a, a $, 24)
     (e, $, 24)
    ТРМ: Описаний алгоритм будує для LL (k) - граматики G = ( N , E , P , S ) Коректну таблицю, що керує роботою відповідного k-який пророкує алгоритму.
    ПЗМ: Розглянемо LL (2) - граматики G з правилами:
    S ® e
    S ® abA
     A ® S aa
     A ® b
    Побудуємо відповідні LL (2)-таблиці. Почнемо з T0 = TS, (e). Потім по T0 знайдемо T1 = TA, (e), далі T2 = TS, (aa) і T3 = TA, (aa):
    T0 T2 u правило безлічі u правило безлічі e S ® e -- aa S ® e -- ab S ® abA (e) ab S ® abA (aa) T1 T3 u правило безлічі u правило безлічі b A ® b -- aa A ® S aa (aa) aa A ® S aa (aa) ab A ® S aa (aa) ab A ® S aa (aa) ba A ® b --
    По цим таблицям побудуємо керуючу таблицю:
    aa ab a ba bb b e T0 abT1, 2 e, 1 T1 T2aa, 3 T2aa, 3 b, 4 T2 e, 1 abT3, 2 T3 T2aa, 3 T2aa, 3 b, 4 a викид викид викид b викид викид викид $ допуск
    Алгоритм побудований за таблицею розбере ланцюжок abaa наступним чином:
    (abaa, T0 $, e) | - (abaa, abT1 $, 2)
    | - (Baa, bT1 $, 2)
    | - (Aa, T1 $, 2)
    | - (Aa, T2aa $, 23)
    | - (Aa, aa $, +231)
    | - (A, a $, 231)
    | - (E, $, 231)
    ТРМ: Число кроків, які виконуються k-пророкує алгоритмом з керуючою таблицею, побудованої попереднім алгоритмом по LL (k) - граматики G, лінійно залежить від n, де n - довжина вхідної ланцюжка.

    Перевірка LL (k) - умови.
    По відношенню до довільної даній граматиці G виникає ряд природних питань:
     Чи є G LL (k) - граматикою для даного k?
     Чи існує таке k, що G - LL (k) - граматика?
      Так як для LL (1) ліві розбори будуються особливо просто, то якщо G не LL (1) - граматика, то чи існує еквівалентна їй LL (1) - граматика G ', для якої L ( G ) = L ( G' )?
    На жаль, тільки для першого питання є що відповідає на нього алгоритм. Можна показати, що другий і третій проблеми алгоритмічно нерозв'язних, але це доказ не наводиться. Наведемо алгоритм перевірки LL (k) - умови:
    алг 4: Перевірка LL (k) - умови.
    Вхід: КС-граматика G = ( N , E , P , S ) і ціле число k.
    Вихід: "Так" - якщо G - LL (k) - граматика і "Ні" в іншому випадку.
    Метод:
    Суть алгоритму зводиться до наступного: Для кожного нетермінала, що має дві або більше правила розкрутки обчислюється перетин перший k-символів всіх можливих ланцюжків розкрутки. Якщо це безліч пусто, то переходять до наступного терміналу, інакше закінчують зі значенням "Ні". Якщо все перетину порожні - закінчують зі значенням "Так". Для отримання перетину двох правил можна скористатися записом: (FIRSTk ( b `) ЕkL) З (FIRSTk ( c` ) ЕkL), де L = FIRSTk ( a `) та a` - ланцюжок символів після терміналу.

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status