Розрахункова робота №2
Лексичні та синтаксичні аналізатори
Мета: Вивчення принципів побудови та функціонування лексичних та синтаксичних аналізаторів.
Для полегшення побудови компіляторів, мови програмування описуються в термінах деякої граматики. Наприклад, оператор присвоювання може бути визначений в граматиці як ім’я змінної, за якою слідує оператор присвоювання (:=), за яким слідує вираз. Проблема компіляції може бути сформульована як проблема пошуку відповідності написаних програмістом речень, структурам, які визначені граматикою, і генерації відповідного коду для кожного речення.
Речення вихідної програми простіше представляти у вигляді послідовності лексем (tokens), ніж просто як строку символів. Лексемою може бути ключове слово, ім’я цілої змінної, арифметичний оператор і т.д.. Прогляд вихідного тексту, розпізнавання та класифікацію різних лексем робить частина компілятора яка називається лексичним аналізатором (сканером).
Як тільки лексеми виділені, кожне речення програми може бути розпізнане як деяка конструкція мови, як, наприклад, декларативні оператори або оператор присвоювання, описані за допомогою граматики. Синтаксичний аналіз виконується частиною компілятора під назвою синтаксичний аналізатор (parser).
Останнім кроком базової схеми процесу трансляції є генерація об’єктного коду. Більшість компіляторів генерує зразу програму в машинних кодах, а не програму на асемблері, призначену для наступної трансляції в машинні коди.
Лексичний аналіз
Лексичний аналіз включає в себе сканування компілюємої програми та розпізнавання лексем. Сканери зазвичай робляться таким чином, щоби вони могли розпізнавати ключові слова, оператори та ідентифікатори так само, як і цілі числа, числа з плаваючою комою, стрічки символів та інші аналогічні конструкції. Такі об’єкти, як ідентифікатори та цілі, зазвичай розпізнаються сканером як окремі лексеми. Однак є інший підхід, в рамках якого ці лексеми описуються правилами граматики. В цьому випадку сканер буде розпізнавати в якості окремих лексем одиничні символи А, В, 0, 1, і т.д. Далі в процесі граматичного розбору послідовність цих символів буде інтерпретована як окрема конструкція мови.
Результатом роботи сканера є послідовність лексем. Для підвищення ефективності наступних дій кожна лексема зазвичай представляється деяким кодом фіксованої довжини (наприклад цілим числом), а не у вигляді стрічки символів змінної довжини.
Якщо розпізнана лексема є ключовим словом або оператором, така схема кодування дає всю необхідну інформацію. У випадку ідентифікатора додатково необхідно конкретне ім’я розпізнаного ідентифікатора. Цього можна добитися за рахунок зберігання не тільки коду лексеми, але й додаткового специфікатора лексеми. Специфікатор повинен мати в собі ім’я ідентифікатора, значення цілого числа і т.д. – всю інформацію розпізнану сканером.
Зовсім не обов’язково, щоб сканер обробляв всю програму. Частіше сканер є процедурою, викликаємою в процесі граматичного розбору для отримання наступної лексеми.
В доповнення до своєї звичайної функції – розпізнавання лексем – сканер зазвичай також виконує читання стрічки вихідної програми, проте коментарії сканером ігноруються. Сканер також повинен враховувати мовно-залежну інформацію: чи є пробіли обмежувачами лексем або ні, чи можуть речення розміщуватись в декількох стрічках вхідного тексту чи для цього потрібні спеціальні ознаки продовження.
Синтаксичний аналіз
Під час синтаксичного аналізу, речення вихідної програми розпізнаються як мовні конструкції, що описані граматикою. Ми можемо дивитись на цей процес як на побудову дерева граматичного розбору речень, що транслюються. Методи граматичного розбору можна розбити на два великі класи – висхідні и нисхідні – в відповідності з порядком побудови дерева граматичного розбору. Нисхідні методи (зверху вниз) починають з правила граматики, яке визначає кінцеву ціль аналізу з кореня дерева граматичного розбору, і намагаються так його нарощувати, щоб наступні вузли дерева відповідали синт...