Ни один праволинейный язык не является существенно неоднозначным
 Скачать 2.83 Mb.
|
|
Ни один праволинейный язык не является существенно … неоднозначным Базисом простых операция явл: Переменная х Конечного числа функции конечного символа данных функции следования x=x+1x=x+1 … Константа 0 Рекурсивная функция Пусть L, L1, L2 – языки над алфавитом ∑, тогда опер. L1 и L2 – это: Сцепление L1 и L2 Разность L1 и L2 Усеченная итерация L Итерация L Грамматика называется LR (0)-грамматикой, если каждое состояние сё LR(0)-автомата, содержащее пункт вида ..., состоит из единственного пункта: B  A B  A Граф зависимостей по данным DDG (DDG) - зависимости по данным между узлами -инструкциями представляются в виде .. направленных дуг узлов вершин циклов Грамматика называется леволинейной, если все продукции имеют вид: А  A  А  A Натуральными числами принято называть ... только неотрицательные целые числа все целые числа как вещественные, так и целые числа все числа, как отрицательные, так и положительные В простейшем случае фазы лексического и синтаксического анализа могут выполняться компилятором … Перпендикулярно Последовательно Смешанно Параллельно Грамматика S  T, U праволинейная. Грамматика S S bS, S aaaT, S aabaT, S abaaT, S aabbaT, S ababaT,S abbaaT, T aT, T bT, T праволинейнаяГрамматика G=(VT,VN,P,S) называется… грамматикой, если каждое правило из Р имеет вид а В, где а 712: (VT  VN)+, B  (VT 746, VN)+ и  <=  Праволинейной Неукорачивающей Укорачивающей Свободной Для доказательства нерегулярности языка удобно использовать … леммы о разрастании Свойства схему накачке Огдена выражения Пусть L - регулярный язык над алфавитом  , поскольку регулярный язык является автоматным, то найдётся автомат А, допускающий язык L, пусть n - размер автомата, следовательно n ... условию леммыудовлетворяет Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из… отношений предшествования Пяти Четырех Трех Двух Компилятор GNU C использует уасс для построения … анализатора Заданного Аналитического Синтаксического Лексического LL(k)-грамматиками называются грамматики, допускающие ... построение левого разбора (left) при чтении анализируемой цепочки слева (left) направо, подсматривая вперед не более чем на k символов детерминированное Число шагов (переносов и свёрток) LR(0)- анализатора,… зависит от длинны выходной цепочки Линейно Каждое правило в… - грамматике иммет вид A a, где А VN и ( ) * a VN VTКС СК SK KS Лемма Огдена и лемма о разрастании для KC-языков полезны при доказательстве утверждений о том, что некоторые языки не являются … Функциональными Порождающими Контекстно-зависимыми Контекстно-свободными Если в описании подпрограммы рекурсивный вызов о каждой из возможных ветвей различения случаев встречается не более одного раза, то рекурсия называется простой или … Линейной Не является примитивно-рекурсивной операцией …, т.к она не всюду определена Вычитания Язык, порождаемый контекстно-свободной грамматикой, называется … языком Контекстно свободным Естественным обобщением конечного автомата явл… (finite-state transducer), позволяющий на каждом такте отправить несколько символов в дополнительный «выходной» поток Конечный преобразователь Строки матрицы … помечаются первыми (левыми) символами, столбцами – вторыми (правыми) символами отношений предшествования Предшествования Не всякая разделенная грамматика с … правилами относится к классу слабо разделенных грамматик Аннулирующими Грамматику типа 2 по Хомскому можно определить как: Укорачивающую контекстно-свободную Праволинейную Контекстно-свободную Леволинейную Недетерминированный конечный автомат - обобщение ... автомата, в котором переход в данной конфигурации может быть определён не единственным образом: строкового детерминированного условного ограниченного Класс множеств, принимаемых HKA без выхода, совпадает с классом множеств, принимаемых ДКА без… Входа Эквивалентности Сохранения Выхода Теорию вычислимости разрабатывал … Тьюринг Гёдель В работах, связанных с формальными языками и грамматиками, используется модель ..., состоящая из входной ленты, устройства управления и вспомогательной ленты, называемой магазином или стеком. магазинного автомата Слово, не содержащее ни одного символа (то есть, последовательность длинны 0), называется … словом и обозначается  пустым Если направление не важно (например, при соединении элементов электрической цепи), то граф является … Неориентированным Двоичное дерево состоит из узлов, каждый из которых хранит свое значение, а также две ссылки – на … и … поддерево Правое левое Язык L является регулярным тогда и только тогда, когда он является …. Автоматным Класс регулярных языков … относительно объединения, пересечения, разности, дополнения, конкантенации и итерации («»звездочки»Клини) Замкнут Слово w допускается … конечным автоматом, если оно принадлежит языку, задаваемому меткой некоторого успешного пути Обратным Всевозможным Обобщённым Упрощенным Для решения задач рекурсивными методами разрабатывают этапы, образующие рекурсивную триаду: Декомпозиция Параметризация База рекурсии Композиция Область памяти, предназначенная для хранениявсех промежуточных значений локальных перемнных при каждом следующем рекурсивном обращении, образует … Рекурсивное дерево Рекурсивный стек Рекурсивный массив Нерекурсивный стек Регуляные языки ненулевого уровня определяется … соотношением: Ri+1=RiU  L1L2,L*1|L1,L2 Ri} Ri+1=RiU L1L2,L*1|L1,L2 Ri}Прецедентным Рекурсивным Рекуррентным Регулярным Язык B = {1 n 2 | n >= 0} не является … Регулярным Класс регулярных языков замкнут относительно операции объединения, пересечения, дополнения, сцепления и итерации, т.е. если L1 и L2 - регулярные языки, то языки L1 L2, L1  L2, L1, L1 L2, L1 * также будут ...регулярными Автомат А называется … , если в нем нет эквивалентных (неразличимых) состояний. Неприведенным Приведенным Замкнутым Бесконечным Операции суперпозиции и примитивной рекурсии сохраняют: Всюду определённость функций Неопределенность функций Произведение функций Индуктивность вычислимости функций Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты Х могут быть реализованы как поля … в записях, представляющих узлы Х Символов Строк Данных Атрибутов Грамматика G=(VT,VN,P,S) называется …, если каждое правило из Р имеет вид A tВ либо A t, где а 712; B VN, t VTправолинейной На рисунке изображен … автомат  Абстрактный Мили Произвольный Мура Детерминированный конечный автомат (Q,  называется полным, если для каждого состояния p Q и для каждого символа a найдется такое состояние q 712; Q; что (p, a, q)  В … - атрибутивных грамматиках атрибуты не наследуются K L S D Конечный автомат (Q, называется детерминированным, если:Для каждого перехода (p, х, q) выполняется равенство  =0Для каждого перехода (p, х, q) выполняется равенство =1Множество I содержит ровно один элемент для любого символа a и для любого состояния p Q существуют не более одного состояния q 712; Q со свойством (p, a, q) Множество L(A)={a|  языком Символ Х  называется …, если X w  для некоторой терминальной цепочки wпорождающим Язык L  * называется регулярным, если существует регулярное выражение а алфавита  такое, что …L = M(a) L = L(a+c-2q) L(c) = A(m) L = L(a) Регулярное выражение над алфавитом ={c1,c2,…ck} – способ … языка над регулярного Пусть G = (N, T, S, P) – праволинейная грамматика, тогда L(G) - … язык Автоматный Прямая рекурсия предусматривает непосредственное обращение рекурсивной функции себе, но с иным набором … данных Входных Синтаксический LL анализатор (LL parser) – в информатике нисходящий … анализатор для некоторого подмножества контекстно-свободных грамматик, известных как LL-грамматики Синтаксических Терминальный Лексический Первичный уасс основан на … - атрибутивном подходе S L K D Для более удобного представления регулярных языков можно использовать регулярные … Строки символы выражения записи Над языками можно производить операции: Совмещения объединения разности пересечения Если язык А является …, то для некоторого числа p верно, что любая строка s ∈ A, содержащая не менее p символов, может быть разделена на три части: s = xyz. регулярным ,,,,,,,,, xyiz ∈ A для всех i ≥ 0 |y| > 0 |xy| ≤ p К способам конечного описания формального языка относят. порождающие грамматики. автоматы. регулярные выражения. Классы Каждый автоматный язык … Имеет в себе полный детерм. Конеч. автомат Равен значению, большему 1 Распознается полным детерм. Конеч. Автоматом игнорируется полным детерм. Конеч. Автоматом Конечные автоматы можно изображать в виде … Массива данных Диаграмм состояний Двумерного массива данных Трехмерного массива данных Якоря в регулярных выражениях указывают на … или … чего-либо (в алфавитном порядке) Конец начало Если к обобщенному конечному автомату добавить переход с меткой …, то множество допускаемых этим автоматом слов не изменится. 6 0 1 2 Если L * , то L называется … над алфавитом ;подмножество множества Задача определения того, является ли произвольная атрибутная грамматика чистой многопроходной в обоих направлениях, зависит экспоненцально от размера атрибутной … Грамматики При обработке парсером SLR грамматика SLR преобразуется в таблицысинтаксического анализа без конфликтов shift/reduce или reduce/reduce для любой комбинации состояния парсера LR(0) и ожидаемого символа … lookahead По любой KC-грамматике можно построить МП-автомат, задающий тот же язык, что и ... грамматика Исходная промежуточная вторичная конечная Язык L автоматный тогда и только тогда, когда существует леволинейная грамматика G такая, что … L = L(G) G=G(L) L=L(L) G=L(G) Пусть G = (N, T, S, P) – праволинейная грамматика. Тогда L(G) – … язык Автоматный Функциональная схема автомата …  Пятого рода Мили Третьего рода Мура Примитивно-рекурсивной функции являются всюду … Определенными Если при преобразовании грамматики G в управляющую таблицувосходящего синтаксического акцептора не возникает ни одногоконфликта типа сдвиг/свертка или свертка/свертка даже без использования множеств последователей нетерминальных символов для расстановки знаков операций свертки, то G называется … -грамматикой. LR(0) LR(2) LR(1) LR(-1) Пусть L , L1, L2 – языки над алфавитом ∑, тогда опер. L1 L2 – это …Пересечение L1 и L2 Итерация L Усеченная итерация L Разность L1 и L2 Алгоритм собственно разбора (исполнения анализатора по входному потоку) одинаков и у LALR(1), и у SLR(1) и шире, чем у … LR(100) LR(1) LR(-1) LR(0) Если L1 и L2-два регулярных языка, то их пересечение L1 ∩ L2 будет … Противоположной равной различной регулярным Если L1 и L2 являются двумя обычными языками, то их конкатенация L1.L2 будет регулярной Максимальная степень всех узлов есть … дерева Степень Если граф зависимостей не имеет циклических зависимостей, он образует направленный … граф, и порядок оценки может быть найден с помощью топологической сортировки Ациклический Язык, допускаемый ( распознаваемый, определяемый ) автоматом M. (обозначаетсяL ( M ) ) – это множество всех …, допускаемых автоматом M Цепочек Дуги, являющиеся петлями в графе …  1, 2 C, a, d, e A, c D, e Класс автоматных языков замкнут относительно: Объединения Деления Итерации Конкатенации Для автомата Мура таблица выходов не строится, т.к. от выходной сигнал не зависит от входного. Для автомата Мура строится совмещенная таблица переходов и выходов В работах, связанных с формальными языками и грамматиками, используется модель …, состоящая из входной ленты, устройства управления и вспомогательной ленты, называемой магазином или стеком магазинного автомата Если удалось получить LL(1)-грамматику, то для построенияанализатора можно использовать метод рекурсивного спуска без возвратов Примитивно рекурсивными называют функции, которые можно получить с помощью операций подстановки и рекурсии из базисных функций Функция вычислима, если существует такой алгоритм, то есть пошаговая процедура «от простого к сложному», которая по входному набору переменных вычисляет значение функции, если этот входной набор принадлежит к области определения функции Дуги, инцидентны вершине 3 в графе …  A,e,f D,e,f D,b,f A,c Множество языков называют классом Грамматика G называется …, если каждое правило из P имеет вид А  или А , где, А, B , x  леволинейной, праволинейной или автоматной Регулярные выражения используются для обозначения регулярных языков Если L – автоматный язык в алфавите Σ, тогда существует праволинейная грамматика G = (N, T, S, P) такая, что L = L(G) |