Синтаксичний аналізатор
Давайте створимо компілятор!
Синтаксичний аналізатор
Тепер, коли ми пройшли процес прийняття рішень, ми можемо поспішити з розробкою синтаксичного аналізатора. Ви робили це зі мною кілька разів до цього, тому ви знаєте послідовність: ми почнемо з нової копії Cradle і додаватимемо процедури одна за одною. Тож давайте зробимо це.
Ми починаємо, як і у випадку з арифметикою, працюючи з булевими літералами, а не зі змінними. Це дає нам новий вид вхідного токена, тому нам також потрібна нова програма розпізнавання та нова процедура для читання екземплярів цього типу токенів. Давайте почнемо, визначивши ці дві нові процедури:
функція IsBoolean(c: char): Boolean;
IsBoolean := UpCase(c) in ['T', 'F'];
функція GetBoolean: Boolean;
if not IsBoolean(Look) then Expected('Boolean Literal');
GetBoolean := UpCase(Look) = 'T';
Внесіть ці підпрограми у програму. Ви можете протестувати їх, додавши до основної програми оператора друку:
Відкомпілюйте програму та протестуйте її. Як завжди поки не дуже вражає, але скоро буде.
Тепер, коли ми працювали з числовими даними, ми повинні були організувати генерацію коду для завантаження значень D0. Нам необхідно зробити те саме і для булевих даних. Звичайним способом кодування булевих змінних є використання 0 для представлення FALSE та іншого значення для TRUE. Багато мов, як наприклад C, використовують для його уявлення ціле число 1. Але я віддаю перевагу FFFF (або -1) тому що побітове NOT також поверне логічне NOT. Отже, нам потрібно видати правильний асемблерний код для завантаження цих значень. Перше засічення на синтаксичному аналізаторібулевих виразів (BoolExpression, звичайно):
if not IsBoolean(Look) then Expected('Boolean Literal');
if GetBoolean then
Додайте цю процедуру до вашого аналізатора і викличте її з основної програми (замінивши оператор друку, який ви щойно там помістили). Як ви можете бачити, ми ще не маємо значної частини синтаксичного аналізатора, але вихідний код починає виглядати більш реалістичним.
Потім, звичайно, ми маємо розширити визначення булевого виразу. У нас вже є правило у БНФ:
Я віддаю перевагу Паскалівській версії «orop» – OR і XOR. Але так як ми зберігаємо односимвольні токени, я кодуватиму їх знаками '' і '
'. Наступна версія BoolExpression – майже повна копія арифметичної процедури Expression:
while IsOrOp(Look) do begin
Зверніть увагу на нову процедуру IsOrOp, яка також є копією цього разу IsAddOp:
функція IsOrop(c: char): Boolean;
ОК, перейменуйте стару версію BoolExpression на BoolTerm, потім наберіть код, наведений вище. Відкомпілюйте та протестуйте цю версію. На цей момент вихідний код починає виглядати досить добрим. Звичайно, немає великого сенсу від булевої алгебри над постійними значеннями, але скоро ми розширимо булеві типи, з якими ми працюємо.
Можливо, ви вже припустили, який буде наступний крок: булевська версія Term.
Перейменуйте поточну процедуру BoolTerm на NotFactor і введіть наступну нову версію BoolTerm. Зауважте, що вона набагато простіша, ніж числова версія, тому що тут немає еквівалента поділу.
while Look = '&' do begin
Тепер ми майже вдома. Ми транслюємо складні булеві вирази, хоч тільки і для постійних значень. Наступний крок – врахувати NOT. Напишітьнаступну процедуру:
if Look = '!' then begin
І перейменуйте попередню процедуру на BoolFactor. Тепер спробуйте компілятор. До цього часу синтаксичний аналізатор повинен обробляти будь-який булевий вираз, який ви подбаєте йому підкинути. Чи працює? Чи відловлює він неправильно сформовані вирази?
Якщо ви стежили за тим, що ми робили в синтаксичному аналізаторі для математичних виразів, ви знаєте, що далі ми розширили визначення показника для включення змінних і круглих дужок. Ми не повинні робити це для показника булю, тому що про ці маленькі речі подбає наш наступний крок. Необхідний лише один додатковий рядок у BoolFactor, щоб подбати про стосунки:
if IsBoolean(Look) then
if GetBoolean then
Ви могли б поставити запитання, коли я збираюся надати булевські змінні і булевські вирази в дужках. Відповідаю: ніколи. Пам'ятайте, раніше ми прибрали їх із граматики. Зараз я збираюся кодувати граматику, яку ми вже погодили. Сам компілятор не може бачити різниці між булевими змінними чи виразами та арифметичними змінними чи виразами. все це буде оброблятися в Relation у будь-якому випадку.
Звичайно, знадобиться певний код для Relation. Однак, я не почуваюся комфортно, додаючи ще код, не перевіривши спершу той, що ми вже маємо. Отже, давайте зараз просто напишемо фіктивну версію Relation, яка нічого не робить за винятком того, що з'їдає поточний символ і виводить невелике повідомлення:
ОК, наберіть цей код та випробувайте його. Усі старі справи досі мають працювати. у вас має бути можливість генерувати код для AND, OR та NOT. Крім того, якщо ви наберете будь-який алфавітний символ, ви повинніотримати невеликий замінник , де має бути бульовий показник. Ви отримали це? Відмінно, тоді перейдемо до повної версії Relation.
Щоб отримати її, тим не менш, спочатку ми повинні покласти невелику основу. Згадайте, що відношення має форму:
функція IsRelop(c: char): Boolean;
Тепер згадайте, що ми використовуємо нуль або -1 в регістрі D0 для представлення логічного значення і те, що оператори циклу очікують, що буде встановлено відповідний прапор. При реалізації всього цього для 68 000 все стає трохи складним.
Так як оператори циклу виконуються тільки за прапорцями, було б добре (а також досить ефективно) просто встановити ці прапорці і нічого не завантажувати в D0. Це було б чудово для циклів та розгалужень, але запам'ятайте, що відносини можуть бути використані скрізь, де можуть бути використані булеві показники. Ми можемо зберігати його результат у булевій змінній. Так як ми не можемо знати поки що буде використовуватися результат, ми повинні врахувати обидва випадки.
Порівняння числових даних досить просто. 68000 має команду для цього. але вона встановлює прапорці, а не значення. Більше того, завжди будуть встановлюватися ті самі прапорці (нуль якщо рівно, і т.д.), в той час, як нам необхідний по-різному встановлений прапорець нуля для кожного різного оператора відносини.
Рішення полягає в інструкції Scc процесора 68000, яка встановлює значення байта 0000 або FFFF (кумедно як це працює!) Залежно від результату певної умови. Якщо зробимо байтом результату регістр D0, ми отримаємо необхідне логічне значення.
На жаль, є одне заключне ускладнення: на відміну від багатьох інших команд у наборі 68000, Scc не скидає прапорціумов відповідно до даних, що зберігаються. Тому ми повинні зробити останній крок, перевірити D0 та встановити відповідним чином прапорці. Це має бути схоже на оберт навколо місяця для отримання того, що ми хочемо: ми спочатку виконуємо перевірку, потім перевіряємо прапорці, щоб встановити дані в D0, потім тестуємо D0 щоб встановити прапорці знову. Це манівець, але це найпростіший спосіб отримати правильні прапорці і, зрештою, це всього лише пара інструкцій.
Я міг би згадати тут, що ця область, на мою думку, показує найбільші відмінності між ефективністю вручну написаного на асемблері та згенерованого компілятором коду. Ми вже бачили, що ми втрачаємо ефективність при арифметичних операціях, хоча пізніше я планую показати вам, як її трохи покращити. Ми також бачили, що керуючі конструкції власними силами можуть бути реалізовані досить ефективно. зазвичай дуже складно покращити код, згенерований для IF чи WHILE. Але практично кожен компілятор, який я коли-небудь бачив, генерує жахливий код порівняно з асемблером для обчислення булевих функцій і особливо відносин. Причина саме в тому, що я згадав вище. Коли я пишу код на асемблері, я рухаюся вперед і виконую перевірку найзручнішим для мене способом, а потім готую розгалуження так, щоб перехід був виконаний на потрібну гілку. Фактично, я «підлаштовую» кожне розгалуження під ситуацію. Компілятор не може зробити цього (практично) і він також не може знати, що нам не потрібно зберігати результат перевірки як булівську змінну. Тому він повинен генерувати код за дуже суворими правилами і часто закінчує збереженням результату як булевої змінної, яка ніколи не буде використана для чогось.
У будь-якому випадку митепер готові розглянути код для Relation. Він показаний нижче з супроводжуючими процедурами: