Қазіргі уақытта жағдай келесідей көрінеді: DSL құру процесінде (біздің жағдайда қарапайым арифметикалық өрнек тілі) біз шыңдардың келесі түрлерімен AST құрылымын анықтадық:
қосу, алу, көбейту және бөлудің екілік операторлары;
біртұтас таңбаны өзгерту (терістеу) операторы;
сандық тұрақтылар.
Ағаш ретінде ұсынылған өрнектің мәнін бағалай алатын аудармашы да жасалды. Сонымен қатар, интерпретатор есептеу көлемін азайту үшін өрнектерді оңтайландыру функциясын қамтиды.
Аудармашы коды келесідей көрінеді:
(1-тізім).
Листинг 1. AST және өрнек тілінің интерпретаторы
com.tedneward.calcdsl пакеті
{
жеке[calcdsl] дерексіз класс Expr
жеке[calcdsl] Case класы Айнымалы (атауы: Жол) Expr кеңейтеді
жеке[calcdsl] іс класы Number(мән: Double) Expr кеңейтеді
жеке[calcdsl] Case класы UnaryOp(оператор : String, arg : Expr) Expr кеңейтеді
жеке[calcdsl] Case класы BinaryOp(оператор: Жол, сол жақта: Expr, оң жақта: Expr)
Expr ұзартады
объект Calc
{
/**
* Өрнектерді жеңілдету функциясы (математикалық терминдер).
*/
def simplify(e : Expr) : Expr =
{
сәйкестік {
// Қос терістеу операндтың мәнін өзгертпейді
Case UnaryOp(«-«, UnaryOp(«-«, x)) => x
// «+» таңбасы операндтың мәнін өзгертпейді
Case UnaryOp(«+», x) => x
// x-ті 1-ге көбейту х-ке тең
case BinaryOp(«*», x, Number(1)) => x
// 1-ді х-ке көбейту х тең
case BinaryOp(«*», Сан(1), x) => x
// x-ті 0-ге көбейту 0-ге тең
case BinaryOp(«*», x, Сан(0)) => Сан(0)
// 0-ді x-ке көбейту 0-ге тең
case BinaryOp(«*», Сан(0), x) => Сан(0)
// х-ті 1-ге бөлу х-ке тең
case BinaryOp(«/», x, Number(1)) => x
// 1-ге х-ті қосу х-ке тең
case BinaryOp(«+», x, Number(0)) => x
// 1-ді x-ке қосу х-ке тең
case BinaryOp(«+», Сан(0), x) => x
// Басқа жеңілдету опциялары жоқ
жағдай _ => e
}
}
def evaluate(e : Expr) : Double =
{
жеңілдету(е) сәйкестік {
Іс нөмірі(x) => x
Case UnaryOp(«-«, x) => -(бағалау(x))
case BinaryOp(«+», x1, x2) => (бағалау(x1) + бағалау(x2))
case BinaryOp(«-«, x1, x2) => (бағалау(x1) — бағалау(x2))
case BinaryOp(«*», x1, x2) => (бағалау(x1) * бағалау(x2))
case BinaryOp(«/», x1, x2) => (бағалау(x1) / бағалау(x2))
}
}
}
}
Алдыңғы мақаланы оқығандар жаттығу ретінде өрнекті жеңілдету 1-листингтегідей тек жоғарғы жағында емес, ағаштың ерікті деңгейінде орындалатындай етіп оңтайландыруды жақсарту ұсынылғанын есте сақтайды. Ең қарапайым нұсқа Лекс Spoon ұсынған). Ол оңайлату функциясы алдымен операндтардың әрқайсысы үшін рекурсивті шақырылады, содан кейін операцияның өзі жоғарырақ деңгейде жеңілдетіледі (2-тізім).
Листинг 2. Жақсартылған өрнекті жеңілдету функциясы
/*
* Lex нұсқасы:
*/
def simplify(e: Expr): Expr = {
// алдымен ішкі өрнектерді жеңілдетіңіз
val simpSubs = e сәйкестік {
// өрнектің екі бөлігін де жеңілдетіңіз
case BinaryOp(оп, сол, оң) => BinaryOp(оп, жеңілдету(сол), жеңілдету(оң))
// операндты жеңілдету
case UnaryOp(op, operand) => UnaryOp(op, simplify(operand))
// мұнда оңайлататын ештеңе жоқ
жағдай _ => e
}
// енді біз өрнектің өзін жеңілдетеміз
// барлық кірістірілген өрнектер жеңілдетілген
def simplifyTop(x: Expr) = x сәйкестік {
// Қос терістеу операндтың мәнін өзгертпейді
Case UnaryOp(«-«, UnaryOp(«-«, x)) => x
// «+» таңбасы операндтың мәнін өзгертпейді
Case UnaryOp(«+», x) => x
// x-ті 1-ге көбейту х-ке тең
case BinaryOp(«*», x, Number(1)) => x
// 1-ді х-ке көбейту х тең
case BinaryOp(«*», Сан(1), x) => x
// x-ті 0-ге көбейту 0-ге тең
case BinaryOp(«*», x, Сан(0)) => Сан(0)
// 0-ді x-ке көбейту 0-ге тең
case BinaryOp(«*», Сан(0), x) => Сан(0)
// х-ті 1-ге бөлу х-ке тең
case BinaryOp(«/», x, Number(1)) => x
// 1-ге х-ті қосу х-ке тең
case BinaryOp(«+», x, Number(0)) => x
// 1-ді x-ке қосу х-ке тең
case BinaryOp(«+», Сан(0), x) => x
// Басқа жеңілдету опциялары жоқ
жағдай _ => e
}
simplifyTop(simpSubs)
}
Рахмет Лекс!
Талдау
Қазіргі уақытта біздің алдымызда DSL құру тапсырмасының екінші бөлігі – мәтіндік формада берілген өрнекті AST-ге түрлендіретін программалық модуль құру тұр. Бұл процесс «талдау» деп аталады және бірнеше фазалардан тұрады: токенизация, лексикалық талдау және талдау.
Тарихи тұрғыдан талдауға арналған бағдарламаларды жасаудың екі жолы бар (талдауыштар):
қолмен;
автоматтандырылған құралдарды қолдану (талдаушы генераторлар).
Бірінші нұсқа — әзірлеуші кіріс ағынындағы әрбір таңбаны талдау үшін кодты дербес жазады. Бұл жағдайда символды өңдеу, әдетте, таңбаның өзімен ғана емес, оған дейін (және одан кейін де) талданғандармен де анықталады. Бұл әдіс қарапайым тілдер үшін жақсы жұмыс істейді, бірақ жетілдірілген синтаксисі бар тілдер үшін өте қиын.
Балама — талдаушы генераторларды пайдалану. Тарихи түрде екі генератор ең үлкен танымалдыққа ие болды — lex (лексикалық анализатор генераторы) және yacc (Yet Another Compiler Compiler — талдаушы генератор). Бұл бағдарламалардың арқасында талдаушы әзірлеушілер оларды қолмен жасаудың қажеті жоқ, лексика енгізуіне тіл лексикасының арнайы сипаттамасын беру жеткілікті, содан кейін ол болашақ талдаушының ең төменгі деңгейлі бөлігін автоматты түрде жасайды. Содан кейін алынған лексикалық анализатор тілдің грамматикалық ережелерін сипаттайтын файлмен бірге талдау кодын генерациялайтын yacc кірісіне беріледі (тіл грамматикасы, атап айтқанда, кілт сөздердің тізімін, ережелерді анықтайды. код блоктарын сипаттау және т.б.).
Бұл процесс есептеу ғылымдарының теориясы бойынша оқулықтарда егжей-тегжейлі сипатталған, сондықтан біз LARL және LR грамматикасының ақырлы автоматтары мен талдаушылары туралы егжей-тегжейлі мәліметтерді қарастырмаймыз. Осы мәліметтерге қызығушылық танытқандар осы тақырып бойынша мақалалар мен кітаптарға сілтеме жасай алады.
Әрі қарай біз Scala-ның үшінші мүмкіндігіне көшеміз, ол талдаушыларды — талдаушы комбинаторларды құруға қызмет етеді. Бұл мүмкіндік толығымен Scala функционалдық бөлігіне жатады. Талдаушы комбинаторлар тілдің әртүрлі бөліктерін тіл спецификациясына ұқсайтын құрамдас бөліктерге біріктіруге және кодты құруды қажет етпей талдау мәселесін шешуге мүмкіндік береді.
Талдаушы комбинаторлар
Талдаушы комбинаторларды құру мақсаттары мен мүмкіндіктерін түсіну үшін тілдің грамматикасын Backus-Naur формасы (BNF) сияқты сипаттау тәсілімен таныс болған жөн. Мысалы, біздің арифметикалық өрнектер тілімізді BNF-те былай сипаттауға болады (3-тізім).