Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    — Сам записывает клиентов и напоминает им о визите;
    — Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    — Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом

    • Синтаксический анализ для T-грам- матик


    ⇐ ПредыдущаяСтр 18 из 23Следующая ⇒




    Обычно код генерируется из некоторого промежуточного языка с довольно жесткой структурой. В частности, для каждой операции известна ее размерность, то есть число операндов, большее или равное 0. Операции задаются терминальными символами, и наоборот - будем считать все терминальные символы знаками операций. Назовем грамматики, удовлетворяющие этим ограничениям, T -грам- матиками. Правая часть каждой продукции в Т -грамматике есть правильное префиксное выражение, которое может быть задано следующим определением:

    1. Операция размерности 0 является правильным префиксным выражением;

    2. Нетерминал является правильным префиксным выражением;

    3. Префиксное выражение, начинающееся со знака операции размерности n > 0, является правильным, если после знака операции следует n правильных префиксных выражений;

    4. Ничто другое не является правильным префиксным выражением

    Образцы, соответствующие машинным командам, задаются правилами грамматики (вообще говоря, неоднозначной). Генератор кода анализирует входное префиксное выражение и строит одновременно все возможные деревья разбора. После окончания разбора выбирается дерево с наименьшей стоимостью. Затем по этому единственному оптимальному дереву генерируется код.

    Для T -грамматик все цепочки, выводимые из любого нетерминала A, являются префиксными выражениями с фиксированной арностью операций. Длины всех выражений из входной цепочки a1... an можно предварительно вычислить (под длиной выражения имеется ввиду длина подстроки, начинающейся с символа кода операции и заканчивающейся последним символом, входящим в выражение для этой операции). Поэтому можно проверить, сопоставимо ли некоторое правило с подцепочкой ai::: ak входной цепочки a1... an, проходя слева-направо по ai... ak. В процессе прохода по цепочке предварительно вычисленные длины префиксных выражений используются для того, чтобы перейти от одного терминала к следующему терминалу, пропуская подцепочки, соответствующие нетерминалам правой части правила.

    Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
    Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
    Что умеет делать SeoHammer
    — Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
    — Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
    — Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
    — SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
    SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.
    Зарегистрироваться и Начать продвижение

    Цепные правила не зависят от операций, следовательно, их необходимо проверять отдельно. Применение одного цепного правила может зависеть от применения другого цепного правила. Следовательно, применение цепных правил необходимо проверять до тех пор, пока нельзя применить ни одно из цепных правил. Мы предполагаем, что в грамматике нет циклов в применении цепных правил. Построение всех вариантов анализа для T-грамматики дано ниже в алгоритме 9.5. Тип Titem в алгоритме 9.5 ниже служит для описания ситуаций (то есть правил вывода и позиции внутри правила). Тип Tterminal - это тип терминального символа грамматики, тип Tproduction - тип для правила вывода.

    Tterminal a[n]; setofTproduction r[n]; int l[n]; // l[i] - длина a[i]-выраженияTitem h; // используется при поиске правил, // сопоставимых с текущей подцепочкой // Предварительные вычисленияДля каждой позиции i вычислить длину a[i]-выражения l[i]; // Распознавание входной цепочки for (int i=n-1; i> =0; i--){ for (каждого правила A -> a[i] y из P){ j=i+1; if (l[i]> 1) // Первый терминал a[i] уже успешно // сопоставлен {h=[A-> a[i].y]; do // найти a[i]y, сопоставимое // с a[i]..a[i+l[i]-1] {Пусть h==[A-> u.Xv]; if (X in T) if (X==a[j]) j=j+1; else break; else // X in N if (имеется X-> w in r[j]) j=j+l[j]; else break; h=[A-> uX.v]; //перейти к следующему символу } while (j! =i+l[i]); } // l[i]> 1 if (j==i+l[i]) r[i]=r[i] + { (A-> a[i]y) }} // for по правилам A -> a[i] y// Сопоставить цепные правилаwhile (существует правило C-> A из P такое, что имеется некоторый элемент (A-> w) в r[i] и нет элемента (C-> A) в r[i]) r[i]=r[i] + { (C-> A) }; } // for по i

    Листинг 9.5.

    Проверить, принадлежит ли (S-> w) множеству r[0]; Множества r[i] имеют размер O(|P|). Можно показать, что алгоритм имеет временную и емкостную сложность O(n). Рассмотрим вновь пример рис. 9.24. В префиксной записи приведенный фрагмент программы записывается следующим образом:

    = + a x + @ + + b y @ + i z 5

    На рис. 9.27 приведен результат работы алгоритма. Правила вычисления стоимости приведены в следующем разделе. Все возможные выводы входной цепочки (включая оптимальный) можно построить, используя таблицу l длин префиксных выражений и таблицу r применимых правил. Операция Длина Правила (стоимость)

    Пусть G - это T -грамматика. Для каждой цепочки z из L(G) можно построить абстрактное синтаксическое дерево соответствующего выражения (рис. 9.24). Мы можем переписать алгоритм так, чтобы он принимал на входе абстрактное синтаксическое дерево выражения, а не цепочку. Этот вариант алгоритма приведен ниже. В этом алгоритме дерево выражения обходится сверху вниз и в нем ищутся поддеревья, сопоставимые с правыми частями правил из G. Обход дерева осуществляется процедурой PARSE. После обхода поддерева данной вершины в ней применяется процедура MATCHED, которая пытается найти все образцы, сопоставимые поддереву данной вершины. Для этого каждое правило-образец разбивается на компоненты в соответствии с встречающимися в нем операциями. Дерево обходится справа налево только для того, чтобы иметь соответствие с порядком вычисления в алгоритме 9.5. Очевидно, что можно обходить дерево вывода и слева направо.

    Структура данных, представляющая вершину дерева, имеет следующую форму:

    Сервис онлайн-записи на собственном Telegram-боте
    Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
    — Разгрузит мастера, специалиста или компанию;
    — Позволит гибко управлять расписанием и загрузкой;
    — Разошлет оповещения о новых услугах или акциях;
    — Позволит принять оплату на карту/кошелек/счет;
    — Позволит записываться на групповые и персональные посещения;
    — Поможет получить от клиента отзывы о визите к вам;
    — Включает в себя сервис чаевых.

    Для новых пользователей первый месяц бесплатно.
    Зарегистрироваться в сервисе
    struct Tnode { Tterminal op; Tnode * son[MaxArity]; setofTproduction RULEs; };

    В комментариях указаны соответствующие фрагменты алгоритма 9.5.

    Tnode * root; bool MATCHED(Tnode * n, Titem h) { bool matching; пусть h==Xv, v== v" 1 v" 2... v" m, m=Arity(X); if (X in T)// сопоставление правила if (m==0) // if l[i]==1 if (X==n-> op) //if X==a[j] return(true); else return(false); else // if l[i]> 1 if (X==n-> op) //if X==a[j] {matching=true; for (i=1; i< =m; i++) //j=j+l[j] matching=matching & & // while (j==i+l[i]) MATCHED(n-> son[i-1], v" i); return(matching); //h=[A-> uX.v] } else return(false); else // X in N поиск подвывода if (в n^.RULEs имеется правило с левой частью X) return(true); else return(false); }void PARSE(Tnode * n) { for (i=Arity(n-> op); i> =1; i--) // for (i=n; i> =1; i--) PARSE(n-> son[i-1]); n-> RULEs=EMPTY; for (каждого правила A-> bu из P такого, что b==n-> op) if (MATCHED(n, bu)) // if (j==i+l[i]) n-> RULEs=n-> RULEs+{(A-> bu)}; // Сопоставление цепных правил while (существует правило C-> A из P такое, что некоторый элемент (A-> w) в n-> RULEs и нет элемента (C-> A) в n-> RULEs) n-> RULEs=n-> RULEs+{(C-> A)}; }Основная программа//Предварительные вычисленияПостроить дерево выражения для входной цепочки z; root = указатель дерева выражения; //Распознать входную цепочкуPARSE(root); Проверить, входит ли во множество root-> RULEsправило с левой частью S;

    Листинг 9.6.

    Выходом алгоритма является дерево выражения для z, вершинам которого сопоставлены применимые правила. С помощью такого дерева можно построить все выводы для исходного префиксного выражения.


    ⇐ Предыдущая13141516171819202122Следующая ⇒




    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.