Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

Островная грамматика

Материал из Циклопедии
Перейти к навигации Перейти к поиску

Островная грамматика — это формальная грамматика, спроектированная для детального анализа определённых конструкций компьютерного языка, непосредственно интересующих создателя и/или пользователя грамматики, при игнорировании или по крайней мере невнимательном и толерантном отношении ко всем остальным конструкциям. Детально описанная часть языка при этом называется «островом», а слабоструктурированное описание всех остальных конструкций — «водой». Островная грамматика, реализованная в широкопрофильной системе метапрограммирования или грамматического обеспечения, также должна включать какое-то минимальное описание общей структуры программы.

Например, предположим, что нам нужно подсчитать индекс Маккейба, отвечающий за цикломатическую сложность программы, и в качестве метода мы выбираем именно грамматический подход с синтаксическим разбором исходного кода. Значение метрики Маккейба равно числу уникальных способов запуска программы — путей прохода через её поток управления, что жёстко связывает её с числом использований операторов ветвления: в первую очередь условного оператора (if/then/else) и оператора множественного ветвления (switch/case). При этом все остальные конструкции языка, осуществляющие вычисления, ввод-вывод, безусловную передачу управления и так далее, вообще говоря, для таких подсчётов не нужны, поскольку на значение метрики не влияют. При этом вполне может возникнуть ситуация, при которой какая-нибудь другая конструкция создаёт существенные проблемы — например, исходный код неоднороден и содержит тексты на разных диалектах одного языка программирования или на разных языках, встроенных один в другой, что выражается в появлении неоднозначностей в общей грамматике при попытке использовать её для синтаксического разбора (парсинга). Даже наличие целого арсенала методов для устранения такого рода неоднозначностей не спасает от того, что на это устранение нужно тратить время и искать соотвествующих специалистов. Подобная трата ресурсов не окупается, если часть дерева разбора, отвечающая за проблемный участок кода, никогда не понадобится — и в этом случае островная грамматика спасает ситуацию, скрывая все второстепенные конструкции под «водой» и оставляя лишь интересующий нас «остров», на который не жалко тратить ни энергию разработчиков при проектировании, ни машинное время при разборе и обходе.

Пример[править]

Островная грамматика на метаязыке Раскаль для языка программирования Java, различающая «остров» с условным оператором и «воду» со всем остальным, выглядит следующим образом:

module JavaIG

import ParseTree;

// Комментарии описываются полностью во избежание неоднозначностей
layout WS = L* !>> [\ \t\n\r/];
lexical L = [\ \t\n\r] | "//" ![\n]* $ | "/*" InComment* "*/" ;
lexical InComment = ![*] | [*] !>> [/];

// Вся «Ява» представляет собой произвольную последовательность островов и воды
start syntax Java = (Island | Water)+;

// Остров — это «if» и условие (тот факт, что за условием следует вложенный блок или блоки,
// мы намеренно игнорируем, так как на подсчёт метрики он не влияет)
syntax Island = "if" "(" BalancedParenthesis ")";
syntax BalancedParenthesis = BPElement+ () >> ")";
lexical BPElement = "(" BPElement* ")" | ![()];

// Вода
syntax Water = NotIf+;
lexical NotIf = JWord \ "if"; 
lexical JWord = ![\ \t\r\n]+ >> [\ \t\r\n];

Близкие методы[править]

Нечёткий разбор (fuzzy parsing) может считаться менее требовательным методом, в котором интересующий проектировщиков грамматики кусок языка описывается точно, а всё остальное не описывается вовсе, причём переход между ними обязан задаваться в виде «якорных терминалов». Скажем, в приведённом выше примере с метрикой Маккейба и островной грамматикой, содержащей операторы ветвления, якорным терминалом могла бы служить строка «if», следующие после которой токены должны подчиняться правилам условного оператора. Очевидным недостатком является то, что при нечётком разборе у него может произойти фальстарт — та же строка «if» может быть частью другого слова или строкой, выдаваемой на экран, а не собственно оператором. Достоинство нечёткого разбора при этом в отсутствии необходимости задавать даже минимальную структуру «воды».

Разбор неполных фраз (parsing incomplete sentences) работает на фразах, структура которых позволяет вкрапления неизвестных фрагментов неизвестной длины. Этот метод используется в вычислительной лингвистике для обработки естественных языков. На практике это эквивалентно наличию островов, внутри которых есть своя «вода» (называемая «озёрами» в продолжение аналогии).

Мостовые грамматики появились через несколько лет после островных и представляют собой их существенное развитие в рамках той же аналогии. Кроме «воды», «островов» и «озёр», этот подход включает «мосты» между островами как описание зависимостей между ними и «рифы», помогающие строительству и ремонту «мостов». «Рифы» концептуально можно считать переосмыслением «якорных терминалов» нечёткого разбора в рамках островного подхода. «Мосты» появлялись в научных публикациях и раньше, чем были предложены мостовые грамматики, но не отделялись от связанных с ними островов.

Скелетные грамматики — это формализация островного подхода, настойчиво предлагающая выводить толерантные грамматики из какой-то базовой, а не составлять их вручную. Несмотря на некоторые ограничения и на трансформационный подход, считающийся рядом учёных чуть более сложным, чем инженерный, скелетные грамматики позволяют довольно точно оценить уверенность, с которой получающаяся грамматика будет принимать программы, не соответствующие базовой, и таким образом оценивать и контролировать уровень толерантности.

Литература[править]

  • По островным грамматикам:
    • A. van Deursen, T. Kuipers. «Building Documentation Generators». ICSM 1999.
    • E.-J. Verhoeven. «Cobol Island Grammars in SDF», магистерская работа амстердамского университета, 2000.
    • L. Moonen. «Generating Robust Parsers using Island Grammars». WCRE 2001.
    • L. Moonen. «Lightweight Impact Analysis using Island Grammars». IWPC 2002.
  • По близким методам: