|
88 (< где и метка правила подстановки, пустой (конечный) терминал. С целью оценки применимости предложенного способа синтаксического анализа для решения рассматриваемой задачи проведена оценка показателей его временной (^С")) и емкостной (£(")) сложности. В общем случае, временная сложность предложенного способа синтаксического анализа представлена следующим образом О(„) = с, +с2 -(£лг,)2 +с3 +с4 (3) i i J где ci и С2 _ коэффициенты, характеризующие максимальное число G(n) шагов, выполняемых при генерации и анализе вариантов в грамматиках '• схемы ОП МГ; коэффициент, определяющий максимальное число шагов при анализе одного элемента, входящего в конкретную грамматику ОП МГ; 3 коэффициент, определяющий максимальное число шагов при повторных обращениях к одной из грамматик, которая уже была использована при попытке анализа конкретного варианта стратегии (программы); —число грамматик соответствующих уровней ОП МГ. Такой способ имеет в общем случае кубическую вычислительную сложность, так как коэффициенты , не зависят от длины цепочки. Для = *Q>,)2 +С2 + С3 i Jоднозначных грамматик, т.е сложность |
183 но-средняя, для рассматриваемых случаев временная (Оср(п)) и емкостная (Е(л)) сложность. В общем случае для рассматриваемых методов и алгоритмов с учетом выф шеприведенных особенностей ГС временная сложность может быть представлена следующим образом: С(«) = с, *Q>,)2 +с2 + С}, i J где С, коэффициент, характеризующий максимальное число шагов, выполняемых при генерации и анализе вариантов на i-й страте схемы ГС; С2 коэффициент, определяющий максимальное число шагов при анализе одного элемента, входящего в конкретную подсистему j-й страты ГС; S С3 коэффициент, определяющий максимальное число шагов при поФ вторных обращениях к одной из грамматик, которая уже была использована при попытке анализа конкретного варианта; N„Nj максимальное число грамматик соответствующих страт. Данный алгоритм имеет в общем случае квадратичную вычислительную сложность, так как коэффициенты С,, С2, С3 не зависят от длины цепочки. |