«ЛІНИВИЙ» аналізу вихідного коду на мові С І С + +

Четверг, 2017-01-19, 23:17

Приветствую Вас Гость | RSS

Главная » Статьи » Наука

«ЛІНИВИЙ» аналізу вихідного коду на мові С І С + +

Анотація. У статті описується метод побудови синтаксичного аналізатора, що дозволяє істотно скоротити необхідні для аналізу ресурси. Метод заснований на тому факті, що кожен вихідний файл підключає безліч заголовків, з яких використовується лише невелика кількість визначень. Розбір визначень із заголовків можна пропускати до моменту безпосереднього звернення до них, таким чином, невикористовувані визначення аналізуватися не будуть. Відмінною особливістю методу є необхідність внесення лише невеликої кількості змін в існуючий парсер. Метод реалізований в статичному аналізаторі Klocwork Insight.

Ключові слова: ледачий аналіз, синтаксичний аналіз, C / C + +.

1. Введення

У міру розвитку будь-якого продукту, обсяг програмного коду зростає. Найчастіше швидкість приросту рядків коду в проекті не лінійна за часом. Таке зростання, наприклад, показує ядро ​​системи Linux [1]. Як наслідок, зростає час компіляції проектів. Крім того, при роботі з великими проектами програмісти часто використовують інструменти аналізу і трансформації коду. Ці інструменти включають в себе рефакторінг коду, статичний аналіз, побудова графа залежностей проекту та інтелектуальне автодоповнення. Такі завдання зазвичай виконуються по дереву абстрактного синтаксису, яке виходить в результаті роботи синтаксичного аналізатора (парсера) [2]. Як правило, час роботи парсера порівнянно з часом подальшого аналізу, тому розробники компіляторів докладають чимало зусиль для мінімізації необхідної кількості ресурсів.

Проблема скорочення часу аналізу найбільш актуальна для мов С і C + +, так як вони не мають властивість інкапсуляції часу компіляції. Наприклад, для мови C + + це означає, що зміна захищеного члена класу зажадає повторної компіляції всього коду, в якому цей клас використовується. Одним з варіантів скоротити час компіляції коду є інкрементальний аналіз [3] - кешування використовуваних у файлі заголовків

для прискорення повторного аналізу. Однак, цей метод працює тільки при багаторазовому аналізі одного і того ж файлу, і вимагає роботи в інтегрованому середовищі розробки. Розглянемо метод синтаксичного аналізу, який дозволить прискорити перший розбір файлу, а також може використовуватися при повній збірці проекту.

2. Огляд існуючих рішень

Зазвичай структура проектів, написаних на мовах С і C + +, така: на початку кожного вихідного файлу записано директиви препроцесора для підключення заголовних файлів, потім слідують визначення, що відносяться безпосередньо до цього файлу. Нижче показаний приклад такого файлу.

# Include <windows.h>

# Include <iostream>

# Include <user types.h> typedef unsigned int boxes;

У підключаються файли виносяться декларації та визначення, які можуть використовуватися в багатьох файлах. Кожен файл може використовувати лише невелика кількість визначень з заголовного файлу, але змушений підключати його цілком. Крім того, одні й ті ж заголовки аналізуються багато разів. У результаті час компіляції файлу і всього проекту невиправдано збільшується. Одним з можливих рішень проблеми є виключення з компіляції невикористовуваних об'єктів. Таке рішення частково реалізовано в компіляторі MS Visual Studio [4].

У підключаються заголовках міститься багато шаблонів, багато їх яких ніколи не використовуються. Коли парсер виявляє заголовок-якого шаблону, він пропускає його тіло, зберігаючи контекст, необхідний для подальшого розбору. Якщо потім парсер виявить інстанціацій (ініціалізацію типом) шаблону, то буде виконано аналіз його тіла. Якщо ж такий інстанціацій не виявиться, то тіло шаблону проаналізовано не буде. У результаті такий код не викличе помилки компілятора:

template <typename Т> class error example {

> »> Example error <« <

};

Така поведінка парсера можна назвати "ледачим" - аналіз тіла шаблону відкладається настільки, наскільки можливо, або не виконується зовсім. Іншим прикладом «ледачого» поведінки є нескінченні списки в мові Haskell. Значення елемента такого списку обчислюється тільки при

безпосередньому зверненні до нього, якщо ж елемент не потрібно, то і значення його обчислено не буде.

«Лінивий» метод аналізу можна поширити і на інші суттєві частини коду мов С і С + + - тіла функцій, структур і класів, не обов'язково шаблонних.

3. «Лінивий» аналіз.

Для оцінки кількості об'єктів, які реально використовуються у файлах проекту, ми проаналізували декілька проектів з відкритим вихідним кодом. Безліч використовуваних функцій і класів визначається так. Переглянемо всі об'єкти у вихідному коді наступних типів. Якщо це клас, то переглядаємо його члени і функції-члени. Якщо це функція, то переглядаємо її тіло. Якщо зустрічається клас або функція, яких немає в множині переглянутих, то додаємо їх. Таким чином ми отримаємо безліч функцій і класів, які потрібні для транслювання даного вихідного файлу. Решта функцій і класи можна пропустити при аналізі. На рис. 1 представлено загальну кількість класів і функцій на проектах у порівнянні з кількістю використовуваних.

I Всі класи ■ Викорис. класи

100%

80%

60% 40%

20%

0%

г ®

Всі функції ■ Викорис. функції

100%

80% 60%

40% 20%

0%

*

Про? -У

Р $ м ^ &

&

Рис. 1. Співвідношення використаних і всіх об'єктів

Виходить, що при аналізі цих проектів можна пропускати більше половини рядків, що відносяться до класів, і майже 80% рядків функцій. Розглянемо докладніше, як буде працювати такий аналізатор.

4. Опис алгоритму.

Схема роботи компілятора виглядає так. Для мов С \ С + + спочатку вихідний текст обробляється препроцесором, який замінює макроси і розкриває директиви підключення заголовних файлів. Потім на стадії лексичного аналізу отриманий текст розбивається на розпізнавані одиниці тексту - лексеми, які передаються синтаксичному аналізу (парсеру). Синтаксичний аналіз визначає, чи може така послідовність лексем відповідати граматиці аналізованого мови, і будує дерево розбору, що відбиває синтаксичну структуру вихідної програми. Після синтаксичного аналізу або одночасно з ним виконується семантичний аналіз. Семантичний аналіз здійснює перевірку типів, обчислює значення виразів часу компіляції, дозволяє виклики функцій і постачає вузли дерева розбору атрибутами-семантичними елементами.

Як правило, парсер для мов С / С + + будується за алгоритмом висхідного синтаксичного розбору ЬА1Л (1). Такий парсер переглядає послідовність токенів зліва направо, приймаючи рішення про зрушення або згортку на підставі попереднього одного токену. При зсуві, поточний токен або нетермінал переноситься на стек; при згортку символи, відповідні правилу згортки, зі стека знімаються. Граматики мов С і С + + в особливості не є однозначними, і часто вибір продукції для згортки залежить від типу ідентифікатора. Тому при описі граматики мови нерідкі конфлікти виду зрушення \ згортка і згортка \ згортка. Такі конфлікти вирішуються за методом узагальненого 1Л (1) аналізу - стек дублюється для кожного з можливих варіантів, і аналіз проводиться для кожного з стеків окремо до тих пір, поки на одному з них не буде виявлена ​​помилка синтаксису, або обидва стека не прийдуть в однаковий стан.

Для додавання функціональності відкладеного розбору тел функцій і класів буде потрібно не велика кількість змін. Коли в процесі перегляду списку лексем парсер зустрічає символ відкриває фігурної дужки, він повинен пропустити всі лексеми аж до символу закриває фігурної дужки, із збереженням балансу дужок. Замість вузла дерева, відповідного тілу класу, парсер вставить спеціальний вузол, що містить необхідну інформацію, щоб забезпечити розбір тіла, якщо він знадобиться в подальшому. Ця інформація буде включати в себе покажчики на перший і останній символи тіла класу в послідовності лексем, а також покажчик на поточний область видимості. Надалі, якщо буде необхідно створити об'єкт класу або звернутися до об'єкта всередині області видимості класу, парсер встановить збережену область видимості в якості поточної і викличе дію для аналізу тіла класу. Як правило, цієї дію є процедурою того ж парсера, тому будуть потрібні зміни для забезпечення реєнтерабельним процедури.

Наступний фрагмент демонструє відкладений аналіз тіла функції.

int foo (int n) {if (n> 0)

return foo (n - 1); return 0;

}

int main () {/ / тіло функції main не пропускається

return foo (3); / / аналіз тіла функції foo

}

У цьому прикладі аналіз тіла функції foo буде відкладений до моменту виявлення її виклику в тілі функції main. В якості поточної лексеми в парсером буде встановлена ​​відкриває фігурна дужка в першому рядку, а в якості поточної області видимості буде встановлена ​​область видимості функції foo. У ході аналізу необхідно відстежувати рекурсивний виклик поточної функції і звернення до області видимості поточного класу, щоб не увійти в нескінченний цикл при спробі запустити аналіз за тією ж збереженої інформації. Для цього можна позначати вузол, з якого береться контекст для аналізу, як «використовуваний», і надалі не запускати аналіз при виявленні таких вузлів.

При аналізі тіла класу можна у свою чергу відкладати розбір тел функцій-членів і вкладених класів. Те ж вірно і для тіл звичайних функцій.

Природно, що синтаксичне дерево, побудоване при «ледачому» розборі включає не всі вузли з дерева, яке буде отримано при повному аналізі. На момент завершення аналізу в такому дереві будуть міститися спеціальні вузли із збереженою інформацією для тел класів і функцій, до яких не було звернень. Его необхідно враховувати при обході дерева, наприклад, з метою пошуку дефектів. Однак, відсутність дефектів для невикористаного коду цілком виправдано, адже такі дефекти не будуть впливати на якість програми. Крім того вони будуть виявлені після змін, що призводять до використання пропущеної частини коду.

При збереженні контексту для відкладеного розбору тіла класу - покажчиків на лексеми і області видимості, необхідно запам'ятовувати інформацію про момент, в який була збережена область видимості. Его потрібно для того, щоб уникнути помилок у ситуаціях, коли в область видимості додаються імена, які в ній вже є, але з іншими значеннями. Так, у наступному прикладі на момент оголошення функції foo в поточній області видимості ім'я х позначає змінну типу int. Якщо ми відкладемо розбір тіла функції до моменту виклику, то при відновленні області видимості як поточної,

ім'я х в ній буде позначати тип. Таким чином разом з посиланням на область видимості необхідно зберігати її стан. Наприклад, можна ввести поняття ревізії зразок систем контролю версій. При додаванні імені в область видимості, її ревізія буде збільшуватися на одиницю, а доданий ім'я буде зберігати номер ревізії. Потім значення ревізії можна буде використовувати при пошуку імені в області видимості - в даному прикладі тіло функції було збережено з областю видимості з ревізією 2, значить, всі імена з номером ревізії більше 2 були додані пізніше, і не можуть враховуватися при пошуку імен в процесі аналізу тіла функції.

template <int wheels> class Vehicle {};

int x; / / x: rev. 1

void foo () {/ / foo: rev. 2

x = 2;

}

typedef int x; / / x: rev. 3 foo ();

У цьому прикладі аналіз тіла функції буде відбуватися тільки, коли парсер визначить виклик функції foo. Для цього в якості поточної буде встановлена ​​глобальна область видимості з номером ревізії 2 - тобто на момент декларації функції foo. У процесі визначення, до якої з двох декларацій на верхньому рівні відноситься ім'я х в тілі функції, будуть використані ревізії. Декларація синоніма типу не потрапляє в список кандидатів: це ім'я було додано в область видимості з номером ревізії 3, тобто вже після оголошення тіла функції.

Так як шаблон Vehicle не використовується, то його тіло проаналізовано не буде. Лінивий аналіз має сенс проводити лише для елементів в заголовках, адже вихідні файли зазвичай використовують всі свої декларації, крім того їх розмір не великий порівняно з розмірами заголовків.

5. Результати.

У таблиці 1 представлено сумарний час синтаксичного і семантичного аналізу для всіх файлів проектів з використанням ледачого режиму і без.

проект рядків коду, тисяч звичайний «ледачий» режим, сек режим, сек збільшення швидкості аналізу

Blender 2.63 1,029 168 132 22%

Firefox 9.0 2,198 1,144 735 36%

Chromium 3,099 13,069 8,816 33%

OpenOffice 3 6,986 27,706 21,693 22%

Таб. 1.

Видно, що дані результати не показують такого скорочення часу, як очікувалося, за оцінками кількості рядків коду. Це пов'язано з тим, що залежність часу аналізу від кількості рядків коду не лінійна. Так, наприклад, при декларації змінної, створюється всього один семантичний елемент, який додається в поточну область видимості. При декларації масиву, таких елементів буде створено кілька, а при описі шаблону крім семантичних елементів необхідно зберігати і структуру шаблону.

Однак, отримані результати - прискорення від 22% до 36% - представляють істотне поліпшення часу синтаксичного аналізу.

6. Висновок.

Описаний метод дозволяє отримати виграш більше 20% часу синтаксичного аналізу проектів. Даний метод реалізований в інструменті статичного аналізу Klocwork Insight. Ще одним способом оптимізації часу виконання аналізу може стати суміщення інкрементального і ледачого аналізу при роботі в середовищах розробки.
Свежие новости шоу бизнеса России и другие культурные новости.

Категория: Наука | Добавил: prostranstvo (2013-05-18)
Просмотров: 549 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]