Компилатори и граматики

Преобразуването на инфиксен израз в постфиксен се нуждае от стек за оператори, за да се запазят операциите в правилния ред. Операндите се добавят в постфиксния израз, когато се срещнат.

Проверка на типовете се извършва преди синтактичния анализ, за да се гарантира, че операциите между различните типове данни са валидни. Тя не се прави след синтактичния анализ, а предварително, за да се елиминират грешки в кода.

Правилото A -> ε е нарушение на изискванията за операторна граматика, защото може да не се извърши никаква работа, създавайки празен низ. Резултатът ще е непредсказуем и не се спазват правилата на операторната граматика.

Лексическият анализ е фазата, която преобразува входящ текст в поток от атоми (tokens). Тези атоми представляват ключови думи, оператори, константи и други елементи на языка, които се използват след това в синтактичния анализ.

Предимствата на преминаването на аргументи чрез програмния стек са, че не се изисква static memory allocation и се правят автоматични чистене. Възможни са и рекурсивни calls. Но не всички функции се предават през steka - например, функциите, които се предават като аргумент (както в C++), се предават чрез адреси.

Когато синтактичния анализатор (парсера) започне създаването на дървото от стартовия символ и след това опита да преобразува стартовия символ във входа.

Когато синтактичния анализатор (парсера) започне създаването на дървото от входа и след това опита да преобразува входа към стартовия символ.

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

Вид рекурсивно спускане, което не изисква връщане назад (backtracking), т.е. не се връща назад и не изпробва различни възможности.

Вид рекурсивно спускане, при което парсера може да е непредсказуем, т.е. може да се наложи връщане назад (backtracking).

Предсказващите анализатори приемат само LL(k) граматики, т.е. ограничен клас граматики, които гарантират, че парсера може да предскаже правилния път.

Синтактичния анализатор отгоре-надолу генерира дясно извеждане (производно) на входа.

Няма описание на синтактичния анализ отдолу нагоре, в материала.

Синтактичният анализатор отдолу-нагоре извършва синтактичен анализ, започвайки от най-малките части на граматиката и постепенно изграждайки по-сложни структури. Този процес може да се сравни с изграждането на кула от блокове, като се започне от основата и се добавят все повече блокове отгоре. В този процес се използва дясно извеждане наобратно.

Преместването (relocation) е процес на заменяне на символните референции или имената на библиотеките с актуални използваеми адреси в паметта преди изпълнението на програмата.

Лексическият анализ е първата фаза от компилатора. Той сканира кода и го разделя на единични лексеми (токени).

Лексическият анализатор е модул, който сканира входния код и го разделя на отделни токени. Той е отговорен за премахване на безполезни елементи, като например бели пространства и коментари, и за разпознаване на ключови думи, идентификатори, оператори и т.н.

Ако лексическият анализатор открие невалиден токен, той обикновено генерира грешка, сигнализирайки за проблем в кода.

Лексическият анализатор преглежда кода символ по символ, за да изгради токени.

Тази имплементация използва хэш таблици, за да организира елементи в символна таблица, в която ключовете са местоположенията на референциите.

Рекурсивното спускане е синтактичен анализатор отгоре-надолу, който започва от стартовия символ и рекурсивно разширява правилата на граматиката, докато се получи изходният код.

LR(k) и SLR(k) са синтактични анализатори отдолу-нагоре, които се движат по изходния код от ляво на дясно, като използват стек за да запазят предходно прочетените символи.

LL(k) е синтактичен анализатор отгоре-надолу, който проверява следващите k символа в изходния код, за да избере правилото, което да приложи.

Синтактичният анализ е част от процеса на компилиране, която проверява дали кодът е граматично правилен (съответства на граматиката на езика).

LALR(1) е синтактичен analyзатор отдолу-нагоре, който е по-мощен от SLR(1), но по-малко мощен от LR(1). YACC е инструмент, който генерира LALR(1) анализатори.

Граматика, в която лявата страна на всяко правило е само един нетерминален символ, а дясната страна може да съдържа комбинация от терминални и нетерминални символи.

Низът може да се изведе от правилата на граматиката с правилната последователност на операциите.

Граматиката може да се анализира с помощта на LL(1) алгоритъм. LL(1) алгоритъмът се използва за определяне на последователността, в която да се прилагат правилата.

И двете страни на правилата на граматиката съдържат само терминални символи, които не се заменят.

Граматика, чиито правила задават правила за замяна само на нетерминални символи.

Граматиката G = { VT, VN, P, S} се дефинира с VT={a, b}, VN = {A, B}, S={A} и P={Pi | i= 1,3}: P1 : S -> AB, P2: A -> aA | ε, P3: В -> b | bB. Низът aaabb може да се изведе с правилата в следния ред: p1 -> p2 -> p2 -> p2 -> p2 -> p3 -> p3.

В кода на програма се срещат както терминални, така и нетерминални символи. Терминалните символи са символите на програмния език, които не могат да бъдат разчленени за по-малки части (като 'a', 'b', '+', '-', '=', '(' и ')'). Нетерминалните символи представляват граматични правила, които дефинират как се съставят по-големи части от кода (като 'израз', 'оператор', 'променлива').

В дадения контекст, терминът „противоречие“ може да се отнася до ситуация, в която правилата в граматиката водят до невъзможен извод или до неяснота.

Лексическият анализ е първата фаза на компилатора. Той сканира входния текст и го разделя на малки единици, наречени „атоми“ (tokens). Атомите представляват ключови думи, оператори, константи и други елементи на програмния език.

Програмите обработват данни чрез различни процеси. Тези процеси могат да бъдат организирани в структури, наречени „стекове“. Стекът е data structure, в която информацията се съхранява по ред „последен във, първи извън“.