Диссертация (1150733), страница 4
Текст из файла (страница 4)
Код наэтом языке — внешний код.В случае, когда известно, что значение строкового выражения должно являться кодом на некотором языке, говорят о встроенных языках (также называемыхвстроенными строковыми языками или string-embedded languages [31]). Например, для листинга 4 внешним языком является C#. Про переменную sExec,основываясь на строках 3–7, можно сделать предположение, что она должна содержать выражение на SQL.
Таким образом, в данном примере присутствуетSQL, встроенный в C#, и динамически формируемый SQL-запрос. Отметим, чтовыражение на строке 9 является статическим, а строковое выражение на строке1710 является динамически формируемым, но не является кодом на некотором языке программирования. Обработка таких выражений в общем случае называетсяанализом строк (string analysis [52]).123456public void Example(string tbl, bool cond){string sExec ="SELECT sOrderDescription, cderitInfo, @sMagicKey FROM ts."+ tbl;+ (cond ? "WHERE fld = 1 " : "WHERE fld = 2 ");7db.Execute(sExec);89Console.WriteLine("Success. Table: " + tbl);1011}Листинг 4: Пример кода метода на языке программирования C#, содержащегодинамически формируемые строковые выраженияОдним из распространённых способов классификации грамматик являетсяиерархия по Хомскому [53].
Рассмотрим её более подробно, так как различиямежду классами играют важную роль в решении задач данной работы.– Грамматика типа 0. Любая грамматика является грамматикой типа 0. Навид правил грамматик этого типа не накладывается никаких дополнительных ограничений. Класс языков типа 0 совпадает с классом рекурсивноперечислимых языков.– Грамматикой типа 1 будем называть неукорачивающую грамматику.Грамматика = ⟨, , , ⟩ называется неукорачивающей, если праваячасть каждого правила из не короче левой части: для любого правила → ∈ выполняется неравенство || ≤ ||. В виде исключения внеукорачивающей грамматике допускается наличие правила → , приусловии, что не встречается в правых частях правил.
Тип 1 также можно определить с помощью контекстно-зависимых грамматик. Грамматика = ⟨, , , ⟩ называется контекстно-зависимой (КЗ), если каждое правило из имеет вид → , где = 1 2 , = 1 2 , ∈ , ∈( ∪ )+ , 1 , 2 ∈ ( ∪ )* . В виде исключения в КЗ-грамматике допускается наличие правила с пустой правой частью → при условии, что не18встречается в правых частях правил. Цепочку 1 называют левым контекстом, цепочку 2 — правым контекстом.
Язык, порождаемый контекстнозависимой грамматикой, называется контекстно-зависимым языком.– Грамматикой типа 2 будем называть контекстно-свободную грамматику.Грамматика = ⟨, , , ⟩ называется контекстно-свободной (КС), есликаждое правило из имеет вид → , ∈ , ∈ ( ∪ )* . Заметим,что в КС-грамматиках допускаются правила с пустыми правыми частями.
Язык, порождаемый контекстно-свободной грамматикой, называетсяконтекстно-свободным языком.– Грамматикой типа 3 является регулярная грамматика, определение которой приведено ниже.Грамматика = ⟨, , , ⟩ называется праволинейной, если каждое правило из имеет вид → , либо → , где , ∈ , ∈ *. Грамматика = ⟨, , , ⟩ называется леволинейной, если каждое правило из имеет вид → , либо → , где , ∈ , ∈ *.При фиксированном языке два следующих утверждения эквивалентны:– существует праволинейная грамматика 1 , такая что = (1 );– существует леволинейная грамматика 2 , такая что = (2 ).Из этого следует, что праволинейные и леволинейные грамматики определяют один и тот же класс языков, который будем называть классом регулярных языков.
Право- и леволинейные грамматики будем называть регулярнымиграмматиками.Существуют различные способы описания языков. Если язык конечен, то егоможно описать простым перечислением входящих в него цепочек. Однако формальный язык может быть бесконечным, и в этом случае требуются механизмы,позволяющие конечным образом представлять бесконечное множество цепочек.Можно выделить два основных подхода для такого представления:– механизм распознавания, когда описывается процедура, проверяющая принадлежность цепочки описываемому языку;19– механизм порождения (генерации), когда задаётся механизм, способныйпостроить все цепочки описываемого языка.Основной способ реализации механизма порождения — использование грамматик, которые описывают правила построения цепочек некоторого языка.
Вместе с этим можно явным образом описать процедуру-генератор цепочек языка, что также будет являться описанием языка. Например, программа на любомязыке программирования, генерирующая некоторый текст, является описаниемязыка. В данной работе будут рассматриваться именно такие программы.1.2Конечные автоматы и преобразователиОдним из способов задания регулярных языков является описание соответствующего конечного автомата, который может быть использован и как генератор, и как распознаватель.О ПРЕДЕЛЕНИЕ 15. Конечный автомат (Finite State Automata, [54]) — это пятёрка = ⟨,Σ,∆,, ⟩, где:– Σ — конечный алфавит;– — конечное множество состояний;– — множество начальных состояний, ⊆ ;– — множество заключительных или допускающих состояний, ⊆ ;– ∆ ⊆ × Σ* × ; если ⟨, , ⟩ ∈ ∆, то ⟨, , ⟩ называется переходом(transition) из в , а слово — меткой (label) этого перехода; в общемслучае автомат является недетерминированным (НКА), то есть позволяющим несколько переходов с одинаковым начальным состоянием и одинаковой меткой.О ПРЕДЕЛЕНИЕ 16.
Конечный автомат ⟨, Σ, ∆, , ⟩ называется детерминированным (deterministic, ДКА), если– множество содержит ровно один элемент;20– для каждого перехода ⟨, , ⟩ ∈ ∆ выполняется равенство || = 1;– для любого символа ∈ Σ и для любого состояния ∈ существует неболее одного состояния ∈ со свойством ⟨, , ⟩ ∈ ∆.О ПРЕДЕЛЕНИЕ 17. Конечный автомат с -переходами — это конечный автомат, в котором есть возможность совершать переходы по .О ПРЕДЕЛЕНИЕ 18.
-НКА — это НКА, где : × (Σ ∪ {}) → 2 .О ПРЕДЕЛЕНИЕ 19. Язык, распознаваемый конечным автоматом , — это язык( ), состоящий из всех допускаемых данным автоматом цепочек. Также говорят, что автомат описывает или задаёт некоторый язык ( ).Класс регулярных языков эквивалентен классу конечных автоматов в томсмысле, что для любого регулярного языка 1 можно построить детерминированный конечный автомат , такой ( ) = 1 . При этом множество языков,допускаемых автоматами с -переходами, совпадает с множеством языков, допускаемых детерминированными конечными автоматами.
Также будет удобноотождествлять регулярный язык и регулярное множество.Конечные автоматы можно изображать в виде диаграмм переходов (transitiondiagram). На диаграмме каждому состоянию соответствует вершина графа, а переходу — дуга. Дуга из в , помеченная словом , означает, что ⟨, , ⟩ является переходом данного конечного автомата. Вершины, соответствующие начальным и конечным состояниям, отмечаются отдельно: конечные состояния изображаются как двойной круг, начальные отмечаются отдельной входной дугой,не имеющей стартовой вершины. Также в данной работе будет использоватьсяследующая цветовая нотация: конечные вершины обозначены красным цветом,начальные — зелёным. Таким образом, автомат представим в виде графа и в данной работе к конечным автоматам будет применяться терминология из теорииграфов.В рамках рассматриваемой предметной области конечные автоматы широко применяются для приближения множества возможных значений динамически генерируемой программы [30, 31, 55]: в результате анализа программыгенератора строится конечный автомат, описывающий регулярное множество ,21являющееся приближением множества генерируемых программ .
При решении многих задач необходимо, чтобы было приближением сверху, то естьвыполнялось включение ⊇ . Например, при поиске ошибок это позволитоценивать полноту анализа: если алгоритм не выявил некорректных цепочек в, то их точно нет и в . Однако возможны ложные срабатывания: алгоритмобнаружил некорректную цепочку ∈ , но ̸∈ , ∈ ∖ . Для того, чтобы минимизировать количество промахов, необходимо уменьшать ∖ , то естьстроить как можно более точное приближение.
В работе [55] предлагается алгоритм построения такого приближения. Он будет использоваться в данной работе.О ПРЕДЕЛЕНИЕ 20. Конечный преобразователь (Finite State Transducer, [56]) —это конечный автомат, который может возвращать конечное число символовдля каждого входного символа. Конечный преобразователь может быть заданследующей шестёркой элементов: ⟨, Σ, ∆, 0 , , ⟩, где:– — множество состояний;– Σ — входной алфавит;– ∆ — выходной алфавит;– 0 ∈ — начальное состояние;– ⊆ — набор конечных состояний;– ⊆ × (Σ ∪ {}) × (∆ ∪ {}) × — набор переходов.Конечные преобразователи находят широкое применение в области обработки естественного языка (Natural Language Processing [57]). Кроме этого, они используются и при проведении лексического анализа, который является переводом входной цепочки из одного языка в другой: из языка над алфавитом символов в язык над алфавитом терминалов.
Большинство генераторов лексическиханализаторов строят по описанию лексики языка соответствующий конечныйпреобразователь.Важной операцией над конечными преобразователями является операциякомпозиции. Композиция конечных преобразователей — это два последовательно взаимодействующих конечных преобразователя, работающих следующим образом: выход первого конечного преобразователя подаётся на вход второму, что22позволяет описывать цепочки трансформаций. Ниже дано формальное определение операции композиция над конечными преобразователями, допускающиеналичие -переходов.О ПРЕДЕЛЕНИЕ 21.
Композицией двух конечных преобразователей1 = ⟨1 , Σ1 , ∆1 , 01 , 1 , 1 ⟩ и 2 = ⟨2 , Σ2 , ∆2 , 02 , 2 , 2 ⟩ является конечныйпреобразователь = ⟨1 × 2 , Σ1 , ∆2 , ⟨01 , 02 ⟩, 1 × 2 , ∪ ∪ , ∪ , ⟩, где:– = {⟨⟨, ⟩, , , ⟨′ , ′ ⟩⟩ |∃ ∈ ∆1 ∩ Σ2 : ⟨, , , ′ ⟩ ∈ 1 ∧ ⟨, , , ′ ⟩ ∈ 2 };– = {⟨⟨, ⟩, , , ⟨′ , ′ ⟩⟩ |⟨, , , ′ ⟩ ∈ 1 ∧ ⟨, , , ′ ⟩ ∈ 2 };– , = {⟨⟨, ⟩, , , ⟨, ′ ⟩⟩ |⟨, , , ′ ⟩ ∈ 2 ∧ ∈ 1 };– , = {⟨⟨, ⟩, , , ⟨′ , ⟩⟩ |⟨, , , ′ ⟩ ∈ 1 ∧ ∈ 2 }.В рамках данной работы конечные преобразователи и их композиция будутиспользоваться для лексического анализа динамически формируемых строковыхвыражений.1.3О применимости статического анализа строковых выраженийСтатический анализ динамически формируемых выражений важен для различных этапов работы с кодом, при решении многих задач [58].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
