Пре скоро 9 година Цлоудфларе је била мала компанија, а ја нисам радио за њу, био сам само купац. Месец дана након покретања Цлоудфларе-а, добио сам обавештење да је моја веб локација ДНС изгледа не ради. Цлоудфларе је променио , а ДНС је покварен.
Одмах сам написао Метју Принсу са насловом „Где је мој ДНС и он ми је послао дугачак одговор пун техничких детаља?“), на шта сам одговорио:
Од: Јохн Грахам-Цумминг
Датум: 7. октобар 2010, 9:14
Наслов: Ре: Где је мој ДНС?
За: Маттхев ПринцеСупер извештај, хвала. Свакако ћу позвати ако буде проблема. Вероватно је вредно написати пост о томе када прикупите све техничке информације. Мислим да ће људи уживати у отвореној и искреној причи. Нарочито ако му приложите графиконе који показују како је промет порастао од лансирања.
Имам добар надзор на свом сајту и добијам СМС о сваком неуспеху. Мониторинг показује да се квар догодио од 13:03:07 до 14:04:12. Тестови се спроводе сваких пет минута.
Сигуран сам да ћеш то схватити. Јесте ли сигурни да вам у Европи није потребна сопствена особа? 🙂
А он је одговорио:
Од: Маттхев Принце
Датум: 7. октобар 2010, 9:57
Наслов: Ре: Где је мој ДНС?
За: Јохн Грахам-ЦуммингХвала вам. Одговорили смо свима који су писали. Сада сам на путу за канцеларију и написаћемо нешто на блогу или закачити званичну објаву на нашу огласну таблу. Потпуно се слажем, искреност је све.
Сада је Цлоудфларе заиста велика компанија, ја радим за њу, а сада морам отворено да пишем о нашој грешци, њеним последицама и нашим поступцима.
Догађаји од 2. јула
2. јула смо увели ново правило у Управљаним правилима за ВАФ-ове због чега на сваком језгру процесора који обрађује ХТТП/ХТТПС саобраћај на Цлоудфларе мрежи широм света. Стално побољшавамо управљана правила за ВАФ-ове као одговор на нове рањивости и претње. У мају смо, на пример, пожурили ради заштите од озбиљне рањивости у СхареПоинт-у. Читава поента нашег ВАФ-а је могућност брзог и глобалног постављања правила.
Нажалост, ажурирање од прошлог четвртка садржало је регуларни израз који је потрошио превише ХТТП/ХТТПС ЦПУ ресурса на враћање уназад. Као резултат тога, страдале су наше основне функције проксија, ЦДН-а и ВАФ-а. Графикон показује да ресурси процесора за опслуживање ХТТП/ХТТПС саобраћаја достижу скоро 100% на серверима у нашој мрежи.
Употреба ЦПУ-а у једној тачки присуства током инцидента
Као резултат тога, наши клијенти (и клијенти наших клијената) су завршили са страницом о грешци 502 у Цлоудфларе доменима. 502 грешке су генерисали Цлоудфларе фронт-енд веб сервери који су још увек имали слободна језгра, али нису могли да комуницирају са процесима који рукују ХТТП/ХТТПС саобраћајем.
Знамо колико је ово непријатности изазвало нашим клијентима. Страшно нас је срамота. И овај неуспех нас је спречио да се ефикасно носимо са инцидентом.
Ако сте били један од ових купаца, вероватно сте били уплашени, љути и узнемирени. Штавише, нисмо имали а . Велика потрошња ЦПУ-а била је последица једног ВАФ правила са лоше сроченим регуларним изразом који је резултирао прекомерним враћањем уназад. Ево кривог израза: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Иако је ово само по себи занимљиво (и о томе ћу детаљније говорити у наставку), услуга Цлоудфларе је била искључена 27 минута не само због лошег регуларног израза. Требало нам је времена да опишемо редослед догађаја који су довели до неуспеха, па смо били спори са одговором. На крају поста ћу описати враћање уназад у регуларном изразу и рећи вам шта да радите са тим.
Шта се десило
Почнимо редом. Сва времена овде су у УТЦ.
У 13:42, инжењер у тиму заштитног зида направио је малу промену у правилима откривања коришћењем аутоматског процеса. Сходно томе, креиран је тикет захтева за промену. Такве карте управљамо преко Јира (снимак екрана испод).
Након 3 минута, појавила се прва страница ПагерДути-а која је пријавила проблем са ВАФ-ом. Ово је био синтетички тест који тестира функционалност ВАФ-ова (имамо их на стотине) изван Цлоудфларе-а ради праћења нормалног рада. Одмах су уследиле странице упозорења о другим Цлоудфларе енд-то-енд тестовима услуга, проблемима са глобалним саобраћајем, широко распрострањеним грешкама 502 и гомилом извештаја из наших тачака присутности (ПоП) у градовима широм света који указују на недостатак ЦПУ ресурса.
Примио сам неколико ових упозорења, излетео са састанка и кренуо за столом када је шеф нашег одељења за развој решења рекао да смо изгубили 80% саобраћаја. Отрчао сам до наших СРЕ инжењера, који су већ радили на проблему. Прво смо мислили да је то нека врста непознатог напада.
Цлоудфларе СРЕ инжењери су раштркани широм света и прате ситуацију даноноћно. Обично вас ова упозорења обавештавају о одређеним локалним проблемима ограниченог обима, прате се на интерним контролним таблама и решавају се више пута дневно. Али ове странице и обавештења указивали су на нешто заиста озбиљно, а СРЕ инжењери су одмах прогласили ниво озбиљности П0 и контактирали менаџмент и систем инжењере.
Наши лондонски инжењери су у том тренутку слушали предавање у главној сали. Предавање је морало бити прекинуто, сви су се окупили у великој конференцијској сали, а позвано је још специјалиста. Ово није био типичан проблем са којим би СРЕ могли сами да се изборе. Било је хитно укључити праве стручњаке.
У 14:00 смо утврдили да је проблем у ВАФ-у и да није било напада. Тим за перформансе је извукао податке ЦПУ-а и постало је јасно да је ВАФ крив. Други запослени потврдио је ову теорију користећи страце. Неко други је видео у евиденцији да постоји проблем са ВАФ-ом. У 14:02, цео тим је дошао код мене када је предложено коришћење глобалног убијања, механизма уграђеног у Цлоудфларе који искључује једну компоненту широм света.
Како смо урадили глобално убијање за ВАФ је друга прича. Није тако једноставно. Користимо сопствене производе, а од нашег сервиса није функционисало, нисмо могли да се аутентификујемо и пријавимо на интерну контролну таблу (када је све било поправљено, сазнали смо да су неки чланови тима изгубили приступ због безбедносне функције која онемогућава акредитиве ако се интерна контролна табла не користи за Дуго времена).
И нисмо могли да дођемо до наших интерних услуга, попут Јира или система изградње. Требао нам је механизам за заобилажење, који смо ретко користили (и ово ће такође морати да се разради). Коначно, један инжењер је успео да онемогући ВАФ у 14:07, а у 14:09 нивои саобраћаја и ЦПУ-а су се свуда вратили у нормалу. Остатак заштитних механизама Цлоудфларе-а функционисао је нормално.
Онда смо кренули са обнављањем ВАФ-а. Ситуација је била неуобичајена, па смо извршили негативне тестове (питајући се да ли је промена заиста проблем) и позитивне тестове (уверавајући се да је враћање функционисало) у једном граду користећи одвојен саобраћај, пребацујући купце који плаћају одатле.
У 14:52 смо се уверили да смо разумели разлог и извршили исправку и поново омогућили ВАФ.
Како функционише Цлоудфларе
Цлоудфларе има тим инжењера посвећених управљању правилима за ВАФ-ове. Настоје да побољшају стопу откривања, смање лажне позитивне резултате и брзо реагују на нове претње како се појаве. У последњих 60 дана обрађено је 476 захтева за промену управљаних правила за ВАФ (у просеку један свака 3 сата).
Ова конкретна промена је морала да се примени у режиму симулације, где стварни клијентски саобраћај пролази кроз правило, али ништа није блокирано. Овај режим користимо за тестирање ефикасности правила и мерење лажно позитивних и лажно негативних стопа. Али чак и у режиму симулације, правила се морају заиста извршити, а у овом случају правило је садржало регуларни израз који је трошио превише процесорских ресурса.
Као што можете да видите из захтева за промену изнад, имамо план примене, план враћања и везу до интерне стандардне оперативне процедуре (СОП) за ову врсту примене. СОП за промену правила омогућава његово објављивање глобално. Заправо, у Цлоудфларе-у се ствари раде потпуно другачије, а СОП налаже да софтвер за тестирање и интерну употребу прво пошаљемо на интерну тачку присутности (ПоП) (коју наши запослени користе), а затим малом броју клијената у изолованој локацији, затим великом броју клијената, па тек онда целом свету.
Овако то изгледа. Ми користимо гит интерно преко БитБуцкет-а. Инжењери који раде на променама шаљу код, који је направљен у ТеамЦити-у, а када изградња прође, додељују се рецензенти. Једном када је захтев за повлачење одобрен, код се саставља и изводи се серија тестова (поново).
Ако се изградња и тестови успешно заврше, у Јира се креира захтев за промену и одговарајући менаџер или вођа мора да одобри промену. Након одобрења, распоређивање се дешава у такозваној „ПоП менажерији“: ПАС, СВИЊА и (пас, свиња и канаринац).
ДОГ ПоП је Цлоудфларе ПоП (као и сваки други наш град) који користе само запослени у Цлоудфларе-у. ПоП за интерну употребу вам омогућава да ухватите проблеме пре него што саобраћај корисника почне да тече у решење. Корисна ствар.
Ако је ПАС тест успешан, код се помера у фазу ПИГ (заморац). Ово је Цлоудфларе ПоП, где мала количина бесплатног саобраћаја корисника тече кроз нови код.
Ако је све у реду, код иде у Цанари. Имамо три Цанари ПоП-а у различитим деловима света. У њима саобраћај плаћених и бесплатних клијената пролази кроз нови код, а ово је последња провера грешака.
Процес издавања софтвера у Цлоудфларе-у
Ако је код на Канару у реду, пуштамо га. Пролазак кроз све фазе - ПАС, СВИЊА, Канарин, цео свет - траје неколико сати или дана, у зависности од промене кода. Због разноликости Цлоудфларе мреже и клијената, ми темељно тестирамо код пре него што га глобално објавимо свим клијентима. Али ВАФ не прати посебно овај процес јер на претње треба брзо реаговати.
ВАФ претње
Током протеклих неколико година, дошло је до значајног повећања претњи у уобичајеним апликацијама. То је због веће доступности алата за тестирање софтвера. На пример, недавно смо писали о ).
Извор:
Врло често се прави доказ концепта који се одмах објављује на Гитхуб-у тако да тимови који одржавају апликацију могу брзо да је тестирају и осигурају да је адекватно обезбеђена. Стога, Цлоудфларе-у је потребна могућност да одговори на нове нападе што је брже могуће како би купци имали прилику да поправе свој софтвер.
Одличан пример брзог одговора Цлоудфларе-а је примена СхареПоинт заштите од рањивости у мају (). Скоро одмах након објављивања најава, приметили смо велики број покушаја да се искористи рањивост у СхареПоинт инсталацијама наших корисника. Наши момци стално прате нове претње и пишу правила како би заштитили наше клијенте.
Правило које је изазвало проблем у четвртак требало је да заштити од скриптовања на више локација (КССС). Овакви напади су такође постали много чешћи последњих година.
Извор:
Стандардна процедура за промену управљаног правила за ВАФ је спровођење тестирања континуиране интеграције (ЦИ) пре глобалне примене. Прошлог четвртка смо то урадили и поставили правила. У 13:31, инжењер је поднео одобрени захтев за повлачење са изменом.
У 13:37 ТеамЦити је прикупио правила, извршио тестове и дао зелено светло. ВАФ тест пакет тестира основну функционалност ВАФ-а и састоји се од великог броја јединичних тестова за појединачне функције. Након јединичних тестова, тестирали смо правила за ВАФ користећи огроман број ХТТП захтева. ХТТП захтеви проверавају које захтеве треба да блокира ВАФ (да пресретне напад) и који могу бити дозвољени (како не би блокирали све и избегли лажне позитивне резултате). Али нисмо тестирали прекомерну употребу ЦПУ-а, а испитивање евиденције претходних верзија ВАФ-а показује да се време извршавања теста правила није повећало и да је било тешко посумњати да неће бити довољно ресурса.
Тестови су прошли и ТеамЦити је почео аутоматски да примењује промену у 13:42.
Жива
Правила ВАФ-а се фокусирају на непосредну санацију претњи, тако да их примењујемо помоћу Куицксилвер-овог дистрибуираног складишта кључ/вредност, које глобално шири промене у секундама. Сви наши клијенти користе ову технологију када мењају конфигурацију на контролној табли или преко АПИ-ја и захваљујући њој на промене реагујемо муњевитом брзином.
Нисмо много причали о Куицксилверу. Раније смо користили као глобално дистрибуирано складиште кључ/вредност, али је било оперативних проблема са њим, па смо написали сопствену продавницу, реплицирану у више од 180 градова. Сада користимо Куицксилвер да преносимо промене конфигурације клијентима, ажурирамо ВАФ правила и дистрибуирамо ЈаваСцрипт код који су написали клијенти у Цлоудфларе Воркерс.
Потребно је само неколико секунди од клика на дугме на контролној табли или позивања АПИ-ја до промене конфигурације широм света. Купци су волели ову брзину подешавања. А Воркерс им омогућава скоро тренутну глобалну примену софтвера. У просеку, Куицксилвер пропагира око 350 промена у секунди.
А Куицксилвер је веома брз. У просеку смо постигли 99. перцентил од 2,29 секунди да бисмо пренели промене на сваки рачунар широм света. Брзина је обично добра ствар. На крају крајева, када омогућите функцију или обришете кеш, то се дешава скоро тренутно и свуда. Слање кода преко Цлоудфларе Воркерс-а одвија се истом брзином. Цлоудфларе обећава својим клијентима брза ажурирања у право време.
Али у овом случају брзина нам је изиграла окрутну шалу, а правила су се свуда променила за неколико секунди. Можда сте приметили да ВАФ код користи Луа. Цлоудфларе увелико користи Луа у производњи и детаљима ми . Луа ВАФ користи интерно и примењује враћање уназад за подударање. Она нема механизме за заштиту од израза који измичу контроли. У наставку ћу говорити више о томе и шта ми радимо у вези с тим.
Пре него што су правила примењена, све је ишло глатко: захтев за повлачење је креиран и одобрен, ЦИ/ЦД цевовод је прикупио и тестирао код, захтев за промену је поднет у складу са СОП-ом који регулише примену и враћање, и имплементација је завршена.
Цлоудфларе ВАФ процес имплементације
Нешто није у реду
Као што сам рекао, сваке недеље примењујемо десетине нових правила ВАФ-а и имамо много система за заштиту од негативних последица таквог примене. А када нешто крене наопако, обично је то сплет неколико околности одједном. Ако нађете само један разлог, ово је, наравно, умирујуће, али није увек тачно. Ово су разлози који су заједно довели до неуспеха наше ХТТП/ХТТПС услуге.
- Инжењер је написао регуларни израз који може довести до претераног .
- Функција која је могла да спречи да регуларни израз троши превише ЦПУ-а грешком је уклоњена у рефакторисању ВАФ-а неколико недеља раније — рефакторисање је било потребно да би ВАФ трошио мање ресурса.
- Механизам регуларних израза није имао гаранције сложености.
- Тестни пакет није могао да открије прекомерну потрошњу ЦПУ-а.
- СОП омогућава да се промене правила које нису хитне спроведу глобално без процеса у више корака.
- План враћања је захтевао покретање комплетне верзије ВАФ-а два пута, што је дуго трајало.
- Прво упозорење о глобалним проблемима у саобраћају покренуто је прекасно.
- Требало нам је неко време да ажурирамо страницу са статусом.
- Имали смо проблема са приступом системима због квара, а процедура заобилажења није била добро успостављена.
- СРЕ инжењери су изгубили приступ неким системима јер су њихови акредитиви истекли из безбедносних разлога.
- Наши клијенти нису имали приступ Цлоудфларе контролној табли или АПИ-ју јер пролазе кроз Цлоудфларе регион.
Шта се променило од прошлог четвртка
Прво, потпуно смо зауставили сав рад на издањима за ВАФ и радимо следеће:
- Поново уводимо заштиту од прекомерне употребе ЦПУ-а коју смо уклонили. (Спреман)
- Ручна провера свих 3868 правила у управљаним правилима за ВАФ да пронађе и исправи друге потенцијалне случајеве прекомерног враћања уназад. (Верификација је завршена)
- Укључујемо профилисање перформанси за сва правила у скупу тестова. (Очекивано: 19. јул)
- Прелазак на механизам регуларних израза или - оба обезбеђују гаранције за време рада. (Очекивано: 31. јул)
- Преписујемо СОП тако да примењујемо правила у фазама, као и други софтвер у Цлоудфларе-у, али у исто време имамо могућност да се хитно применимо глобално ако су напади већ почели.
- Развијамо могућност да хитно уклонимо Цлоудфларе контролну таблу и АПИ из Цлоудфларе региона.
- Аутоматско ажурирање страница .
Дугорочно се удаљавамо од Луа ВАФ-а који сам написао пре неколико година. Премештање ВАФ-а у . На овај начин ће ВАФ бити бржи и добити додатни ниво заштите.
Закључак
Овај квар је изазвао проблеме за нас и наше купце. Брзо смо реаговали да исправимо ситуацију и сада радимо на недостацима у процесима који су изазвали пад, као и да копамо још дубље да бисмо се заштитили од потенцијалних проблема са регуларним изразима у будућности приликом преласка на нову технологију.
Веома нам је непријатно због овог прекида и извињавамо се нашим клијентима. Надамо се да ће ове промене обезбедити да се овако нешто више не понови.
Апликација. Повратак на регуларне изразе
Да бисте разумели како је израз:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))потрошили све ресурсе ЦПУ-а, морате знати мало о томе како функционише стандардни механизам регуларних израза. Проблем је овде образац .*(?:.*=.*). (?: и одговарајући ) је група која не обухвата (то јест, израз у загради је груписан као један израз).
У контексту прекомерне потрошње ЦПУ-а, овај образац се може описати као .*.*=.*. У овом облику, образац изгледа непотребно сложен. Али што је још важније, у стварном свету, изрази (попут сложених израза у ВАФ правилима) који траже од машине да се подудара са фрагментом праћеним другим фрагментом могу довести до катастрофалног враћања уназад. И зато.
У регуларном изразу . значи да треба да одговарате једном карактеру, .* - "похлепно" подударају нула или више карактера, односно хватање максималног броја знакова, тако да .*.*=.* значи подударање нула или више знакова, затим подударање нула или више знакова, проналажење литерала = знак, подударање нула или више знакова.
Узмимо тест линију x=x. Одговара изразу .*.*=.*. .*.* пре него што се знак једнакости поклопи са првим x (једна од група .* одговара x, а други - нула знакова). .* после = утакмице трају x.
Ово поређење захтева 23 корака. Прва група .* в .*.*=.* делује похлепно и одговара читавом низу x=x. Мотор прелази у следећу групу .*. Немамо више ликова за подударање, па друга група .* одговара нула знакова (ово је дозвољено). Затим се мотор креће на знак =. Нема више симбола (прва група .* употребио цео израз x=x), не долази до поређења.
А онда се механизам регуларних израза враћа на почетак. Прелази у прву групу .* и упоређује га с x= (уместо x=x), а затим преузима другу групу .*. Друга група .* упоређује се са другом x, и опет немамо више знакова. А кад мотор опет стигне = в .*.*=.*, ништа не ради. И поново се повлачи.
Овај пут група .* још увек се поклапа x=, али друга група .* не више x, и нула знакова. Мотор покушава да пронађе буквални лик = у обрасцу .*.*=.*, али не излази (на крају крајева, прва група га је већ заузела .*). И поново се повлачи.
Овога пута прва група .* узима само прво х. Али друга група .* „похлепно” хвата =x. Да ли сте већ претпоставили шта ће се догодити? Мотор покушава да усклади буквално =, не успева и поново се враћа назад.
Прва група .* још увек одговара првом x. Друго .* само узима =. Наравно, мотор не може да парира дословном =, јер је друга група то већ урадила .*. И опет назадовање. И покушавамо да ускладимо низ од три карактера!
Као резултат, прва група .* одговара само првом x, друго .* - са нула знакова, а мотор се коначно поклапа са литералом = у изразу с = у реду. Следећа је последња група .* упоређује се са последњим x.
23 корака само за x=x. Погледајте кратак видео о коришћењу Перла , који показује како се јављају кораци и враћање уназад.
Ово је већ много посла, али шта ако уместо тога x=x имаћемо x=xx? То је 33 корака. А ако x=xxx? 45. Однос није линеаран. Графикон приказује поређење од x=x до x=xxxxxxxxxxxxxxxxxxxx (КСНУМКС x после =). Ако имамо 20 х после =, мотор завршава упаривање у 555 корака! (Штавише, ако смо изгубили x= а низ се једноставно састоји од 20 x, мотор ће предузети 4067 корака да схвати да нема подударања).
Овај видео приказује све повратне информације за поређење x=xxxxxxxxxxxxxxxxxxxx:
Проблем је у томе што како се величина стринга повећава, време подударања расте суперлинеарно. Али ствари могу постати још горе ако се регуларни израз мало измени. Рецимо да смо имали .*.*=.*; (то јест, на крају шаблона је била дословна тачка и зарез). На пример, да се подудара са изразом као foo=bar;.
А овде би повлачење било права катастрофа. За поређење x=x биће потребно 90 корака, а не 23. И тај број брзо расте. Упоредити x= и КСНУМКС x, потребно је 5353 корака. Ево графикона. Погледајте вредности осе Y у поређењу са претходним графиконом.
Ако сте заинтересовани, погледајте свих 5353 неуспешних корака за подударање x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Коришћењем лењог уместо похлепног упаривања, обим враћања се може контролисати. Ако променимо првобитни израз у .*?.*?=.*?, за поређење x=x биће потребно 11 корака (а не 23). Што се тиче x=xxxxxxxxxxxxxxxxxxxx. Све зато ? после .* говори мотору да одговара минималном броју знакова пре него што настави даље.
Али лења мапирања не решавају у потпуности проблем враћања назад. Ако заменимо катастрофалан пример .*.*=.*; на .*?.*?=.*?;, време извршења ће остати исто. x=x и даље захтева 555 корака, и x= и КСНУМКС x - КСНУМКС.
Једина ствар која се може урадити (осим потпуног поновног писања шаблона ради веће специфичности) је да се напусти механизам регуларних израза са његовим механизмом за враћање уназад. То је оно што ћемо радити у наредних неколико недеља.
Решење овог проблема познато је од 1968. године, када је Кент Томпсон написао чланак („Методе програмирања: Алгоритам претраге регуларног израза“). У чланку је описан механизам који вам омогућава да конвертујете регуларни израз у недетерминистичке машине коначних стања, а након промена стања у недетерминистичким коначним машинама користите алгоритам чије време извршавања линеарно зависи од упареног низа.
Методе програмирања
Алгоритам претраге регуларног израза
Кен Тхомпсон
Белл Телепхоне Лабораториес, Инц., Мурраи Хилл, Нев ЈерсеиОн описује метод за тражење одређеног низа знакова у тексту и разматра имплементацију овог метода у облику компајлера. Компајлер узима регуларни израз као изворни код и производи ИБМ 7094 програм као објектни код. Објектни програм узима улаз у облику текста за претрагу и емитује сигнал сваки пут када се низ текста упореди са датим регуларним изразом. Чланак даје примере, проблеме и решења.
Алгоритам
Претходни алгоритми претраге су резултирали враћањем уназад ако делимично успешна претрага није дала резултат.У режиму компилације, алгоритам не ради са симболима. Он прослеђује упутства компајлираном коду. Извршење је веома брзо – након прослеђивања података на врх тренутне листе, аутоматски тражи све могуће узастопне знакове у регуларном изразу.
Алгоритам за компилацију и претрагу је укључен у уређивач текста са дељењем времена као контекстуална претрага. Наравно, ово је далеко од једина примена таквог поступка претраге. На пример, варијанта овог алгоритма се користи као претрага симбола у табели у асемблеру.
Претпоставља се да је читалац упознат са регуларним изразима и рачунарским програмским језиком ИБМ 7094.Цомпилер
Компајлер се састоји од три фазе које раде паралелно. Прва фаза је филтрирање синтаксе, које омогућава да прођу само синтаксички исправни регуларни изрази. Овај корак такође умеће оператор „·“ да би се подударали са регуларним изразима. У другом кораку, регуларни израз се претвара у постфикс форму. У трећој фази креира се објектни код. Прве 2 фазе су очигледне и нећемо се задржавати на њима.
Томпсонов чланак не говори о недетерминистичким машинама коначног стања, али добро објашњава алгоритам линеарног времена и представља програм АЛГОЛ-60 који генерише код на асемблерском језику за ИБМ 7094. Имплементација је незгодна, али идеја је врло једноставна.
тренутна путања претраге. Представљен је иконицом ⊕ са једним улазом и два излаза.
На слици 1 приказане су функције трећег корака компилације када се трансформише пример регуларног израза. Прва три знака у примеру су а, б, ц, и сваки креира унос стека С[и] и поље ННОДЕ.ННОДЕ постојећем коду за генерисање резултујућег регуларног израза у једном уносу стека (погледајте слику 5)
Овако би изгледао регуларни израз .*.*=.*, ако замислите као на сликама из Томпсоновог чланка.
На сл. 0 има пет стања почевши од 0 и 3 циклуса који почињу из стања 1, 2 и 3. Ова три циклуса одговарају три .* у регуларном изразу. 3 овала са тачкама одговарају једном симболу. Овални са знаком = одговара буквалном карактеру =. Стање 4 је коначно. Ако га достигнемо, онда се регуларни израз подудара.
Да видимо како се такав дијаграм стања може користити за подударање регуларних израза .*.*=.*, погледаћемо подударање низова x=x. Програм почиње из стања 0, као што је приказано на сл. 1.
Да би овај алгоритам радио, државни строј мора бити у неколико стања истовремено. Недетерминистичка коначна машина направиће све могуће прелазе истовремено.
Пре него што има времена да прочита улазне податке, прелази у оба прва стања (1 и 2), као што је приказано на Сл. 2.
На сл. 2 показује шта се дешава када погледа у прву x в x=x. x може мапирати до горње тачке, прелазећи из стања 1 и назад у стање 1. Или x може мапирати до тачке испод, крећући се из стања 2 и назад у стање 2.
После подударања са првим x в x=x још увек смо у стањима 1 и 2. Не можемо да дођемо до стања 3 или 4 јер нам је потребан дословни карактер =.
Алгоритам затим разматра = в x=x. Као и к пре њега, може се упарити са било којом од две горње петље из стања 1 у стање 1 или из стања 2 у стање 2, али алгоритам може да се подудара са литералом = и пређите из стања 2 у стање 3 (и одмах 4). Ово је приказано на сл. 3.
Алгоритам затим прелази на последњи x в x=x. Из стања 1 и 2 исти прелази су могући назад у стања 1 и 2. Из стања 3 x може да се подудара са тачком на десној страни и врати се у стање 3.
У овој фази, сваки лик x=x узети у обзир, и пошто смо достигли стање 4, регуларни израз одговара том стрингу. Сваки знак се обрађује једном, тако да је овај алгоритам линеаран по дужини улазног низа. И без повлачења.
Очигледно, након достизања стања 4 (када се алгоритам поклапа x=) цео регуларни израз је упарен, а алгоритам се може прекинути без да се то уопште узме у обзир x.
Овај алгоритам линеарно зависи од величине улазног низа.
Извор: ввв.хабр.цом