Генератор синтаксических анализаторов для решения задач автоматизированного реинжиниринга программ Дипломная работа студента 544 группы Чемоданова Ильи Сергеевича Санкт-Петербургский Государственный Университет Математико-механический факультет Кафедра системного программирования Научный руководитель: Я.А. Кириленко Рецензент: к.ф.-м.н А.С. Лукичев

Введение Специфика синтаксического анализа при реинжиниринге устаревших (legacy) языков: Специфика синтаксического анализа при реинжиниринге устаревших (legacy) языков: Сложные грамматики Сложные грамматики Не всегда КС, неоднозначные Не всегда КС, неоднозначные Не БНФ Не БНФ Множество схожих конструкций Множество схожих конструкций Диалекты (Relativity MW: Cobol – 18 диалектов, Natural – 4 диалекта, PL/I – 2 диалекта) Диалекты (Relativity MW: Cobol – 18 диалектов, Natural – 4 диалекта, PL/I – 2 диалекта) Выражения Выражения

Постановка задачи Предложить прототип инструмента: Предложить прототип инструмента: с выразительным и удобным входным языком с выразительным и удобным входным языком в большей степени отвечающего перечисленным требованиям по сравнению с существующими разработками в большей степени отвечающего перечисленным требованиям по сравнению с существующими разработками

YARD Конструкции расширенной формы Бэкуса-Наура ( *, +, ?) Конструкции расширенной формы Бэкуса-Наура ( *, +, ?) Именование семантических значений Именование семантических значений Анонимные нетерминалы ( a : ( b | c ) d ( e | f ); ) Анонимные нетерминалы ( a : ( b | c ) d ( e | f ); ) Наследуемые атрибуты ( a[x]: y = b { x + y }) Наследуемые атрибуты ( a[x]: y = b { x + y }) Макроправила ( seplist > ) Макроправила ( seplist > ) Предикаты (резольверы) Предикаты (резольверы)

Реализация Внутренний алгоритм: GLR Внутренний алгоритм: GLR x* x_list : x x_list | /* empty */ ; x* x_list : x x_list | /* empty */ ; a : ( b | c ) d ( e | f ); a : alt_1 d alt_2 ; a : ( b | c ) d ( e | f ); a : alt_1 d alt_2 ; a[x] : y = b { x + y } a: b { fun x -> x + $1} a[x] : y = b { x + y } a: b { fun x -> x + $1} c : z=d r=a[z] {r }; c : z=d r=a[z] {r }; c : d a { let z = $1 in let r = $2 z in (r) } c : d a { let z = $1 in let r = $2 z in (r) } sepList > sepList > stmt_sepList : stmt ( SEMI stmt )* ; stmt_sepList : stmt ( SEMI stmt )* ; Предикат – фильтр на дереве Предикат – фильтр на дереве

Пример с калькулятором (YARD) binExpr > : l=operand r=( op=binOp r=operand { (op, r) } )* { List.fold_left ( fun l (op,r) -> op l r ) l r } ; { List.fold_left ( fun l (op,r) -> op l r ) l r } ; termOp: PLUS { ( +. ) } | MINUS { ( -. ) } ; factorOp : MULT { ( *. ) } | DIV { ( /. ) } ; powOp: "^" { ( ** ) } ; powExpr: n=NUMBER { float n } | "(" e=expr ")" { e } ; factor: res=binExpr > { res } ; term: res=binExpr > { res } ; expr: res=binExpr > { res } ;

Пример с калькулятором (ANTLR) options { language="Cpp"; } { #include } class CalcParser extends Parser; expr returns [float res] { res = 0; float r = 0; float r = 0; bool plus = false; bool plus = false;} :res=term ( ( PLUS { plus = true; } | MINUS { plus = false; } ) r=term ( ( PLUS { plus = true; } | MINUS { plus = false; } ) r=term { if (plus) res += r; else res -= r; } { if (plus) res += r; else res -= r; } )* )*;

term returns [float res] { res = 0; float r = 0; bool mult = false; bool mult = false;} : res=factor ( ( MULT { mult = true; } | DIV { mult = false; } ) r=factor ( ( MULT { mult = true; } | DIV { mult = false; } ) r=factor { if (mult) res *= r; else res /= r; } { if (mult) res *= r; else res /= r; } )* )*; factor returns [float res] { res = 0; float r = 0; } : res=powExpr ( POW r=powExpr { res = pow(res, r); } )* ; powExpr returns [float res] { res = 0; } :i:INT { res = atof(i->getText().c_str()); } | LPAREN res=expr RPAREN ; Пример с калькулятором (ANTLR)

Результаты работы Сформулированы требования к генератору Сформулированы требования к генератору Выполнен обзор современных инструментов автоматизации создания синтаксических анализаторов Выполнен обзор современных инструментов автоматизации создания синтаксических анализаторов Предложен входной язык инструмента на основе проведенных исследований Предложен входной язык инструмента на основе проведенных исследований Реализован прототип предложенного инструмента Реализован прототип предложенного инструмента