la-jezici

Слово, азбука, реч, језик

Компилатор преводи изворни на циљни језик.

Појам језика мора бити прецизно дефинисан (то укључује дефиницију лексике, синтаксе и семантике)

Прецизним дефиницијама језика бави се формална теорија језика или теорија формалних језика (енгл. formal language theory)

Формална дефиниција појма језика се не бави само дефинисањем комплетног програмског језика, већ је много једноставнија и флексибилнија.

На пример, у лексичкој анализи разматрамо различите скупове ниски

скуп свих идентификатора (њему припадају x, prvi_sabirak, sabirak1, …)
скуп свих реалних константи (њему припадају 3.2, -2, -8.2e4)
…

Сви ови скупови се називају језици и обухваћени су формалном дефиницијом појма језика

Формално: Језик је било који скуп речи

Шта су речи? Морамо кренути од самог почетка.

Азбука (алфабет, абецеда) је било који непразан, коначан скуп карактера (симбола, слова). Азбуке ћемо обично обележавати словима \(\Sigma\), \(\Sigma'\), \(\Gamma\), \(\ldots\)

\(\Sigma = \{a, b, c\}\),
\(\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\)
ASCII
UNICODE
…
Ни један симбол азбуке се не може представити помоћу других симбола (не може да важи \(a = bc\) за неке \(a, b, c \in \Sigma\))

Реч (ниска, стринг) над азбуком \(\Sigma\) је било који коначан низ карактера из те азбуке.

\(babac\) је једна реч над азбуком \(\Sigma = \{a, b, c\}\).
дужина речи је број њених карактера
\(x = a_0a_1\ldots a_{n-1}\), где \(a_i \in \Sigma\) је једна реч дужине \(n\)
речи ћемо обично обележавати малим словима \(x, y, z, w, s, t, \ldots\), а слова малим словима \(a, b, c, \ldots\)
корисно нам је да дефинишемо и празну реч – реч дужине 0, коју ћемо увек обележавати са \(\varepsilon\)

Скуп свих речи над азбуком \(\Sigma\) обележавамо са \(\Sigma^*\).

Нпр. ако је азбука \(\Sigma = \{a, b\}\), тада је \(\Sigma^* = \{\varepsilon, a, b, aa, ab, ba, bb, aaa, aab, \ldots \}\)
Скуп свих речи је увек бесконачан (пребројив).

Језик \(L\) је произвољни подскуп \(\Sigma^*\) (\(L \subseteq \Sigma^*\))

Нпр. \(L_1 = \{ab, aabb, aaabbb, \ldots\}\) је један језик над азбуком \(\Sigma = \{a, b\}\)
Нпр. \(\emptyset\) је један језик (над било којом азбуком)
Нпр. \(\Sigma^*\) је један језик над азбуком \(\Sigma\)
Нпр. скуп свих исправних идентификатора у C-у је један језик над азбуком ASCII
Нпр. скуп свих исправних C програма је један језик над азбуком ASCII (необично, сваки програм је једна реч у том језику)

Описивање формалног језика

Јако често се у компилацији јавља проблем провере да ли дата реч припада датом језику

Нпр. да ли v0 и да ли 3d припадају језику исправних C идентификатора
Нпр. да ли \(aaaabbbb\) и да ли \(aaabb\) припадају језику \(L_1\)

Потребно је пронаћи аутоматско решење овог проблема

Морамо пронаћи начин који програмеру омогућава да једноставно рачунару опише језик
Морамо пронаћи начин да се на основу тог описа аутоматски генерише програм (функција) која проверава да ли било која дата реч припада језику

Компромис између изражајности и сложености препознавања

ако је формализам за опис језика сиромашан, не можемо описати било који језик, али је аутоматска провера припадности речи језику једноставна и ефикасна
ако је формализам за опис језика богат, можемо описати шире класе језика, али је препознавање теже (и када се аутоматизује, оно може бити неефикасно)
пребогати формализми су чак такви да уопште није могуће направити алгоритам провере да ли речи припадају том језику
За лексичку анализу довољно је разматрати веома сиромашну класу језика који се зову регуларни језици
За синтаксичку анализу потребно је разматрати једну ширу класу језика који се зову контекстно слободни језици

Језик је скуп, па се може описати на све уобичајене начине којима описујемо скупове

набрајање елемената, нпр. \(L = \{\varepsilon, a, aa, aaa, aaa, aaaa, \ldots\}\)
за коначне језике набрајање је у реду, али може бити изразито неудобно, а за бесконачне језике набрајање је непрецизно (увек ставимо … и ослањамо се на то да је читалац довољно ителигентан да разуме)
компрехенсија, нпр. \(L = \{a^k\ |\ k \geq 0\}\)
пребогати формализам – није могуће аутоматизовати проверу

Операције над језицима и регуларни језици

Идентификатор почиње словом или подвлаком, након чега се нула или више пута јавља слово, подвлака или цифра

многи језици значајни за лексичку анализу се могу описати на сличан начин

расчланимо шта је овде употребљено:

слово, цифра, подвлака – елементарни карактери
слово ИЛИ подвлака – бирање између две алтернативе
јавља се … ПА ОНДА … – надовезивање два дела речи
НУЛА ИЛИ ВИШЕ ПОНАВЉАЊА … – произвољни број понављања неких делова речи

Језици који се могу описати само коришћењем ових операција називају се регуларни језици

Горњи опис је дат само да бисте стекли интуицију о чему се говори у наставку – сада ћемо исто изложити на потпуно прецизан и формалан начин.

Операције над речима

Основна операција над две дате речи је њихово надовезивање тј. конкатенација

конкатенацију речи \(x\) и \(y\) (обе из \(\Sigma^*\)) означавамо са \(x\cdot y\) или још краће \(xy\)

Нпр. \(aba \cdot baa = ababaa\)

\((\Sigma^*, \cdot)\) је слободни моноид:

затвореност (за сваке две речи \(x, y \in \Sigma^*\) важи \(xy \in \Sigma^*\))
асоцијативност (за сваке три речи \(x, y, z \in \Sigma^*\) важи \((xy)z = x(yz)\))
неутрал је \(\varepsilon\) (важи \(\varepsilon x = x \varepsilon = x\))

Конкатенација није комутативна операција

Нпр. \(aba \cdot bab \neq bab \cdot aba\)
Вежба – пронаћи потребан и довољан услов да за две речи \(x, y \in \Sigma^*\) важи \(xy=yx\)

Конкатенација нема инверз

Можемо дефинисати и степен речи \(x^n = \underbrace{x\cdot x \cdot \ldots \cdot x}_n\)

рекурзивна дефиниција: \(x^0 = \varepsilon\), \(x^n = x\cdot x^{n-1}\), за \(n > 0\)

Операције над језицима

… ИЛИ … – ово одговара унији језика

језици су скупови, па се на њих примењују све уобичајене скуповне операције (подразумевамо увек да су језици над истом азбуком \(\Sigma\))

\(L_1 \cup L_2 = \{x \in \Sigma^* \ |\ x \in L_1 \vee x \in L_2\}\)
\(L_1 \cap L_2 = \{x \in \Sigma^* \ |\ x \in L_1 \wedge x \in L_2\}\)
\(L_1 \setminus L_2 = \{x \in \Sigma^* \ |\ x \in L_1 \wedge x \notin L_2\}\)
\(L^c = \Sigma^* \setminus L = \{x \in \Sigma^*\ |\ x \notin L \}\)
\(L_1 \times L_2 = \{(x, y)\ |\ x \in L_1 \wedge y \in L_2\}\)

Важе неке уобичајене алгебарске законитости. Нпр.

\(L_1 \cup L_2 = L_2 \cup L_1\)
\(L \cup \emptyset = \emptyset \cup L = L\)
\(L \cap \emptyset = \emptyset \cap L = \emptyset\)
\(L \cup \Sigma^* = \Sigma^* \cup L = \Sigma^*\)
\(L \cap \Sigma^* = \Sigma^* \cap L = L\)
…

… ПА ОНДА … – ово одговара производу језика

производ два језика – конкатенација примењена на све парове речи који припадају Декартовом производу

\(L_1 \cdot L_2 = \{xy \in \Sigma^* \ |\ x \in L_1 \wedge y \in L_2\}\)
Пр. \(L_1 = \{\mathit{BG}, \mathit{NS}, \mathit{KG}, \mathit{NI}\}\), \(L_2 = \{\mathit{000}, \mathit{001}, \mathit{002}, \ldots, 999\}\), \(L_1\cdot L_2 = \{BG000, BG001, \ldots, BG999, NS000, NS001, \ldots, NS999, \ldots, NI999\}\)
Алгебарска својства конкатенације се преносе на производ.
Затвореност: производ два језика над \(\Sigma\) је језик над \(\Sigma\)
Асоцијативност: за свака три језика над \(\Sigma\) важи \(L_1 \cdot (L_2 \cdot L_3) = (L_1 \cdot L_2) \cdot L_3\)
Неутрал је \(\{\varepsilon\}\) – важи \(L \cdot \{\varepsilon\} = \{\varepsilon\} \cdot L = L\).
Важи \(\emptyset \cdot L = L \cdot \emptyset = \emptyset\).
производ не мора бити комутативан
производ је дистрибутиван у односу на унију тј. важи \(L_1 \cdot (L_2 \cup L_3) = L_1\cdot L_2 \cup L_1\cdot L_3\)
Да ли је \(|L_1 \cdot L_2| = |L_1| \cdot |L_2|\)?

… СЕ ПОНАВЉА НУЛА ИЛИ ВИШЕ ПУТА – ово одговара Клинијевом затворењу језика

степен језика – понављање производа

\(L^n = \underbrace{L\cdot L\cdot \ldots\cdot L}_n\)
рекурзивна дефиниција: \(L^0 = \{\varepsilon\}\), \(L^n = L \cdot L^{n-1}\), за \(n > 0\)
Важи \(L^1 = L\)
\(\{a, ba, ab\}^2 = \{aa, aba, aab, baa, baba, baab, aba, abba, abab\}\)

Клинијево затворење (итерација) – унија свих степена језика

\(L^* = \bigcup_{n=0}^{+\infty} L^n\)
Пр. \(\{ab, ba\}^* = \{\varepsilon\} \cup \{ab, ba\} \cup \{abab, abba, baab, baba\} \cup \{ababab, ababba, abbaab, \ldots\} \cup \ldots = \{\varepsilon, ab, ba, abab, abba, baab, baba, ababab, ababba, abbaab, \ldots\}\)
Важи \(\emptyset^* = \{\varepsilon\}* = \{\varepsilon\}\)

Регуларни језици

Тривијални језици су регуларни:

језик \(\emptyset\)
језик \(\{\varepsilon\}\)
сви језици облика \(\{a\}\), за \(a \in \Sigma\)

Ако су регуларни \(L_1\) и \(L_2\), тада је регуларан и \(L_1 \cup L_2\)

Ако су регуларни \(L_1\) и \(L_2\), тада је регуларан и \(L_1 \cdot L_2\)

Ако је регуларaн \(L\), тада је регуларан и \(L^*\)

Регуларни језици се могу добити само применом горе наведених правила

Пр. \((\{a\} \cup \{b\})\cdot (\{a\} \cup \{b\} \cup \{1\})^* = \{a, b, aa, ab, a1, ba, bb, b1, aaa, aab, aa1, \ldots \}\) – почиње са \(a\) или са \(b\), за чим иде нула или више \(a\), \(b\) или \(1\)

Регуларни изрази

Регуларни изрази су компактнија нотација за запис регуларних језика

Нпр. претходни језик можемо краће записати као \((a|b)(a|b|1)^*\)

\(\emptyset\) је регуларни израз који описује језик \(\emptyset\)

\(\varepsilon\) је регуларни израз који описује језик \(\{\varepsilon\}\)

за свако слово \(a \in \Sigma\), \(а\) је регуларни израз који описује језика \(\{a\}\)

Ако је \(r_1\) регуларни израз који описује језик \(L_1\) и ако је \(r_2\) регуларни израз који описује језик \(L_2\), тада је \(r_1|r_2\) регуларни израз који описује језик \(L_1 \cup L_2\)

Ако је \(r_1\) регуларни израз који описује језик \(L_1\) и ако је \(r_2\) регуларни израз који описује језик \(L_2\), тада је \(r_1r_2\) регуларни израз који описује језик \(L_1 \cdot L_2\)

Ако је \(r\) регуларни израз који описује језик \(L\), тада је \(r^*\) регуларни израз који описује језик \(L^*\)

Регуларни изрази се могу добити само коначном применом претходних правила.

Приликом записа регуларних израза користе се заграде – ако се изоставе, подразумева се да је приоритет оператора редом \(*, \cdot, |\). Нпр. \(ab*|cd\) се тумачи као \((a(b^*))|(cd)\)

Проширени регуларни изрази

Поред основних оператора у пракси се користе и други, који додатно скраћују запис (али који обично не повећавају изражајност).

Нпр. позитивно затворење

ако регуларни израз \(r\) означава језик \(L\), тада израз \(r^+\) означава језик \(L^+ = \bigcup_{k=1}^{+\infty} L^k = LL^*\)
Важи \(L^* = L^+ \cup \{\varepsilon\}\), док \(L^+ = L^* \setminus \{\varepsilon\}\) важи само ако \(\varepsilon \notin L\).
… СЕ ПОНАВЉА ЈЕДАН ИЛИ ВИШЕ ПУТА

Нпр. опционо појављивање

ако регуларни израз \(r\) означава језик \(L\), тада израз \(r?\) означава језик \(L \cup {\varepsilon}\)
… СЕ ПОНАВЉА НУЛА ИЛИ ЈЕДАН ПУТ

Нпр. број појављивања

ако регуларни израз \(r\) означава језик \(L\), тада \(r\{m\}\) означава језик \(L^m = \underbrace{L\ldots L}_m\)
… СЕ ПОНАВЉА ТАЧНО \(m\) пута

Нпр. распон броја појављивања

ако регуларни израз \(r\) означава језик \(L\), тада \(r\{m, n\}\) означава језик \(\bigcup_{k=m}^n L^k\)
… СЕ ПОНАВЉА ИЗМЕЂУ \(m\) и \(n\) пута

Нпр. карактерске класе

регуларни израз [aeiou] једнак је изразу a|e|i|o|u – један од наведених карактера,
регуларни израз [^aeiou] – било који карактер осим наведених
регуларни израз [a-z] – мало слово

Нпр. било који карактер

. означава било који карактер из азбуке (осим евентуално преласка у нови ред)
Зато ако желимо препознавање тачке, морамо писати \. или [.]

Подршка у програмским језицима и алатима

grep — g/re/p (globally search for a regular expression and print matching lines)

sed — stream editor

lex – генератор лексичких анализатора

Python 3 — import re

for line in sys.stdin:
    if re.search(r'[0-9]+[.][0-9]+', line):
        print(line)

C++11 — #include <regex>

C# — using System.Text.RegularExpressions;

Java — import java.util.regex.*

JavaScript — new RegExp(...)