Поред регуларних израза: Увод у рашчлањивање граматика без контекста

Важан и користан алат који је већ део арсенала већине програмера је поуздан регуларни израз . Али изван те леже граматике без контекста. Ово је једноставан концепт са фенси именом.

Регуларни израз је метода потврђивања и проналажења образаца у тексту. Врсте образаца (тзв. Граматике) које се могу описати и открити помоћу регуларног израза називају се регуларни језици . Регуларни језици су најједноставнији формални језици у хомској хијерархији .

Регуларни изрази су одлични за проналажење или потврђивање многих врста једноставних образаца, на пример бројева телефона, адреса е-поште и УРЛ адреса. Међутим, недостају када се примене на обрасце који могу имати рекурзивну структуру, као што су:

  • ХТМЛ / КСМЛ ознаке за отварање / затварање
  • отвори / затвори заграде {/} у програмским језицима
  • отвори / затвори заграде у аритметичким изразима

Да бисмо рашчланили ове врсте образаца, треба нам нешто моћније. Можемо прећи на следећи ниво формалних граматика званих контекстуалне граматике (ЦФГ).

Рашчлањивање математичких израза

Рашчлањивање скупа свих математичких израза је изван снаге правог регуларног израза. Разлог је тај што они могу садржати произвољно дубоко угнежђене парове заграда.

На пример, узмите у обзир израз: (2 + (3 * (7–4)))

Приметите да је структура аритметичког израза заправо стабло:

 + / \ 2 * / \ 3 - / \ 7 4

Структура стабла генерисана као резултат извођења ЦФГ парсера назива се стабло рашчлањивања .

Описивање граматика без контекста

Постоје две популарне методе изражавања ЦФГ граматика:

  1. Проширени образац Бацхус-Наур (ЕБНФ) - описује ЦФГ у смислу правила производње . То су правила која, када се примењују, могу створити све могуће правне фразе на језику.
  2. Граматика рашчлањивања израза (ПЕГ) - описује ЦФГ у смислу правила препознавања . То су правила која се могу користити за подударање важећих фраза у језику.

ПЕГ формализам има предност у односу на ЕБНФ у томе што је мапирање у парсер једнозначно и може се лако аутоматизовати.

Следи једноставан ПЕГ подигнут са његове Википедиа странице који описује математичке формуле које примењују основне четири операције на ненегативне

цели бројеви.

Expr ← SumSum ← Product ((‘+’ / ‘-’) Product)*Product ← Value ((‘*’ / ‘/’) Value)*Value ← [0–9]+ / ‘(‘ Expr ‘)’

Једноставно, ово можемо прочитати као:

  • Expr је Sum
  • SumProductпрати нула или више под-образаца који се састоје од „+“ или „-“, а иза њих стоји аProduct
  • ProductValueпрати нула или више под-образаца који се састоје од „*“ или „/“, а иза њих стоји аValue
  • Valueје један или више чланова скупа знакова {0, .. 9}, или је отворена заграда “(„ иза које следе а Exprи затварајућа заграда „)“.

Генератори рашчлањивача наспрам рашчлањивања библиотека

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

1. Користите генератор рашчлањивача - алат који генерише изворни код за рашчлањивач из апстрактне дефиниције рашчлањивача. Неки популарни примери у ЈаваСцрипт-у укључују Јисон, ПЕГ.јс, неарлеи и АНТЛР.

2. Користите библиотеку за рашчлањивање - библиотеку која омогућава изражавање правила рашчлањивања као АПИ. Неки примери у ЈаваСцрипт-у укључују Мина, Парсиммон и Цхевротаин.

Моја жеља је да користим рашчлањивање библиотека, јер их је лакше разумети, отклонити грешке, одржавати и прилагодити.

Писање парсера у ТипеСцрипт / ЈаваСцрипт помоћу Мина Парсинг Либрари

Недавно је пројекат на којем сам радио (језик Херон) захтевао библиотеку за рашчлањивање која се може покретати у прегледачу. Сматрао сам да су сложеност и трошкови постојећих библиотека превелики. С обзиром на то да сам имао претходно искуство у писању рашчлањивања библиотека на Ц ++ и Ц #, одлучио сам да напишем парсерску библиотеку Мина користећи ТипеСцрипт.

Мина користи течну синтаксу (уланчавање метода) да би олакшала дефинисање парсера као скупа правила (субпарсер) који подсећају на ПЕГ граматику.

Следећи пример је из Мина ГитХуб репо-а:

Од конкретног стабла синтаксе (ЦСТ) до апстрактног стабла синтаксе (АСТ)

Када парсер обради улаз, свако успешно подударно правило (ака граматичка производња) може се пресликати на чвор у стаблу рашчлањивања. Ово дословно мапирање производних правила на чворове у дрвету је конкретно стабло синтаксе (ЦСТ).

У неким случајевима, ЦСТ је ограничене употребе, јер садржи пуно синтаксичке нереда, на пример коментаре у изворном коду или да ли стринг литерал има двоструке наводнике или појединачне наводнике. Може садржати резултате правила која су креирана како би се граматика олакшала за употребу, али не представља предвиђену структуру стабла за анализу.

Најједноставније је направити чворове у излазном стаблу само за одређена правила и прескочити друга правила. Ова поједностављена верзија стабла рашчлањивања назива се апстрактно стабло синтаксе (АСТ) . На АСТ се може извршити више пролаза како би се трансформисао у алтернативне АСТ репрезентације, како би се поједноставили каснији кораци обраде.

У Мини се АСТ генерише стварањем чворова од правила означених са astсвојством. Технички, ово својство враћа ново правило које има унутрашњи скуп својстава који говори анализатору да генерише чвор за рашчлањивање у стаблу за рашчлањивање.

Коришћење генерисаног Мина апстрактног стабла синтаксе

Ево примера коришћења Мина-дефинисаног парсера у „Ноде.ЈС“ за процену аритметичког израза:

Завршне речи

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

Мина је написана на ТипеСцрипт-у (који има познату синтаксу за већину програмера), садржана је у једној датотеци без зависности и мања је од 1200 редова, укључујући детаљну документацију.

Ако сте заинтересовани да видите Мину како примењује сложенији сценарио, погледајте програмски језик Цхицкадее. Ово је у потпуности имплементирано у ТипеСцрипт и зависи само од Мина библиотеке за рашчлањивање. Цхицкадее је малени програмски језик дизајниран посебно да помогне људима да науче о техникама примене програмских језика.

Ако вам се свидео овај чланак, јавите ми и размислите о подели са пријатељима и колегама.