Примітивний інтерпретатор з нуля на Python (переклад) #1, Блог розробників phpBB

У цьому циклі статей спробую захопити частину цієї простоти шляхом написання простого інтерпретатора для звичайної імперативної мовиIMP(IMperative Language). Інтерпретатор буде написаний на Пітоні, тому що це проста та широко відома мова. Також, пітон-код схожий на псевдокод, і навіть якщо ви не знаєте його [пітон], вам вдасться зрозуміти код. Парсинг буде виконаний за допомогою простого набору комбінаторів, написаних з нуля (докладніше розповім у наступній частині). Жодних додаткових бібліотек не буде використано, крімsys(для I/O),re(регулярні вирази в лексері) таunittest(для перевірки працездатності нашого виробу) .

Сутність мови IMP

Насамперед, давайте обговоримо, для чого ми писатимемо інтерпретатор. IMP є нереально простою мовою з наступними конструкціями:

Присвоєння (всі змінні є глобальні і приймають лише integer):

Складові оператори (розділені;):

Це всього лише іграшкова мова. Але ви можете розширити його до рівня корисності, як у Python або Lua. Я лише хотів зберегти його настільки простим, як зможу.

А ось тут приклад програми, яка обчислює факторіал:

Структура інтерпретатора

Ядро інтерпретатора є нічим іншим як проміжним уявленням (intermediate representation, IR). Воно представлятиме наші IMP-програми в пам'яті. Так як IMP простий як 3 рублі, IR безпосередньо відповідатиме синтаксису мови; ми створимо за класом кожної одиниці синтаксису. Звичайно, у більш складній мові ви хотіли б використовувати ще й семантичну виставу, яка набагато легша для аналізу чи виконання.

Усього тристадії інтерпретації:

  • Розібрати символи вихідного коду на токени.
  • Зібрати всі токени в абстрактне синтаксичне дерево (abstract syntax tree, AST). AST і є наш IR.
  • Виконати AST та вивести результат в кінці.

Процес збирання токенів у AST називається парсингом. Парсер отримує структуру нашої програми у форму, яку ми можемо виконати.

примітивний

Ця стаття буде зосереджена виключно на лексері. Спочатку ми напишемо загальну лекс-бібліотеку, а потім уже лексер для IMP. Наступні частини будуть сфокусовані на парсері та виконавці.

Правду кажучи, лексичні операції дуже прості і ґрунтуються на регулярних виразах. Якщо ви з ними не знайомі, можете прочитати офіційну документацію.

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

Ось код з бібліотеки лексера:

Зазначимо, що порядок передачі у регулярні вирази є значним. Функція lex перебиратиме всі вирази і прийме лише перший знайдений збіг. Це означає, що при використанні цієї функції, перш за все нам слід передавати специфічні вирази (відповідні операторам і ключовим словам), а потім вже звичайні вирази (ідентифікатори та числа).

Лексер IMP

З урахуванням коду вище створення лексера для нашої мови стає дуже простим. Спочатку визначимо серію тегів для токенів. Для мови потрібно лише 3 теги.RESERVEDдля зарезервованих слів або операторів,INTдля чисел,IDдляідентифікаторів.

Після цього слідують усі наші оператори та зарезервовані слова.

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

Коли наші регекспи визначені, ми можемо створити обгортку над функцієюlex:

Якщо ви дочитали до цих слів, то вам, швидше за все, буде цікаво, як працює наше диво. Ось код для тесту: