Знайте, Intuit, лекция, описание на формалните граматики

Така стигаме до основната точка на представянето на учебния материал - описанието на така наречената официална граматиката. Значението на формални граматики в обработката на символни данни, всичко по компютърни науки е сравним със значението на аритметиката по математика, логика, философия и т.н. На принципите на формалната граматика и са предназначени за създаване на нови езици за програмиране, програми, написани за правопис и стил, програмирани "реч" интерфейси, създаване на програма за корекция на грешки и изпълнението на програмата "оптимизация". Въз основа на официална граматика успя да "декодират" хармонията в шедьоврите на велики архитекти, художници и композитори. (Между другото, повечето фуги на Бах написана по начин, който ги поражда е един от най граматики)!

Заключенията на теорията на формалните граматики се използват в езика за програмиране (например логически Prolog) за изграждането на деривация дървета.

Когато четете този раздел, може да се наложи да се отнасят както до предишния и следващите раздели. По-подробно в този раздел на материала е представена в [41].

10.1. азбука

Изучаването на всеки език на лицето започва с азбуката. Официалното граматиката на езика се определя независимо от неговия смисъл. Освен това, един и същ език, може да се конфигурира в няколко граматики! Това е като в училище - не, че важен резултат (който може да се прочете в края на урока) как да го получи - записано в решение на преносим компютър. Ето защо, ние стигаме до определянето на азбуката като формалност.

О р е н г п п д д азбука -. Е непразно множество ограничен набор от елементи.

"Класическото" език азбука - набор от знаци. В фонетиката - набор от публикувана човешка реч звучи. Музиката - набор от бележки и т.н.

С помощта на азбуката често е възможно да се опише един безкраен брой на думите. Множеството от всички думи, които могат да бъдат създадени от граматиката (с други думи, генеративната граматика) се нарича език. За разлика от езика на азбуката може да бъде безкраен.

Всеки краен последователност от символи от азбуката се нарича една дума, или по-професионално верига. Вериги, състоящи се от символите ще имат следната последователност: а, б, в, аа, AB, бв, ас. бб Авва, и други. Също така признава съществуването на празен низ L - пълна липса на характер. Също така важно е от порядъка на героите в низ. По този начин, верига АБ и ба - различни вериги. Следваща главни букви ще бъдат използвани като променливи и символи и малки букви ще означаваме вериги. Например:

верига, състояща се от символи и Т. S. V и в този ред.

О р е н г п д п д. Дължината на веригата е броят на символите в тази верига. Тя се нарича | х |. Например: | A | = 0, | A | = 1, | BA | = 2, | ABBA | = 4.

Ако х и у са струни, те ще бъдат слепване низ XY. Чрез пермутация вериги, в резултат на конкатенацията се променя (както в групата теория). Ако Z = XY - низ, тогава х - глава, и у - опашка верига. Ако ни е грижа за главата на веригата, ще означаваме:

и ако сме безразлични към опашката, ние ще напише:

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

Забележка в лявата едностранно рекурсия. Някои алгоритми, които прилагат обратен извод, а левостранен рекурсия може да попадне в "безкраен цикъл." Например, в граматика в [Пример 01] третото правило може да бъде изпълнена безкрайно: при достъп до правило: <чс>. = <чс><цифра> - програмата ще "обърне внимание", за да символа <чс> и "игнорира" символ <цифра>. Това може да се коригира и селекция от граматика. така реда за избор на правилата и фактите. Така например, в Prolog първо писмено правило, което води до спиране на рекурсия, и едва след това - всъщност рекурсивно правило.

Забележка. Тук има някои "разминаване" с одобрението на [параграф 3 от "Граматика"], който гласи, че в резултат на изхода не зависи от реда на правилата. Въпреки това, решението на проблема (в резултат на алгоритъма) не зависи от реда на правилата - той определя само дали ще има решение, издадено от краен брой стъпки, ако програмата е завършена нормално или системата ще се провалят. Това - не липсата на граматика. както и липсата на един алгоритъм, генериране на него.