26) Дерево разбора в автоматной грамматике

27)Регуля́рные выраже́ния (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэ́кспы или ре́гексы) — это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов-джокеров, англ. wildcard characters). По сути это строка-образец (англ. pattern, по-русски её часто называют «шаблоном», «маской»), состоящая из символов и метасимволов и задающая правило поиска.

Регулярные выражения произвели прорыв в электронной обработке текстов в конце XX века. Набор утилит (включая редактор sed и фильтр grep), поставляемых в дистрибутивах UNIX, одним из первых способствовал популяризации регулярных выражений для обработки текстов. Многие современные языки программирования имеют встроенную поддержку регулярных выражений. Среди них ActionScript, Perl, Java[1], PHP, JavaScript, языки платформы .NET Framework[2], Python, Tcl, Ruby, Lua, Gambas и др.

Регулярные выражения используются некоторыми текстовыми редакторами и утилитами для поиска и подстановки текста. Например, при помощи регулярных выражений можно задать шаблоны, позволяющие:

найти все последовательности символов «кот» в любом контексте, как то: «кот», «котлета», «терракотовый»;

найти отдельно стоящее слово «кот» и заменить его на «кошка»;

найти слово «кот», которому предшествует слово «персидский» или «чеширский»;

убрать из текста все предложения, в которых упоминается слово кот или кошка. Далее http://ru.wikipedia.org/wiki/Регулярные_выражения

28) Синтаксический анализатор

Задача синтаксического анализатора – проверить правильность записи выражения и разбить его на лексемы. Лексемой называется неделимая часть выражения, состоящая, в общем случае, из нескольких символов. Для арифметических и логических выражений лексемами будут:

имена переменных;

имена функций;

константы;

операции – арифметические (+, -, *, /), логические (!, &&, ||) и сравнения (==, !=, >, >=, <, <=);

открывающая скобка;

закрывающая скобка.

Обычно лексемы разделяются пробелами, хотя возможны ситуации, когда появление новой лексемы обозначает конец предыдущей. Например, знак арифметической операции заканчивает имя стоящей перед ним переменной.

При реализации синтаксического анализатора надо все символы, которые могут встретиться в обрабатываемой строке, разбить на группы таким образом, чтобы все символы группы вызывали одинаковую реакцию синтаксического анализатора. Например, при разборе арифметических и логических выражений все цифры 0-9 будут вызывать одинаковую реакцию.

Кроме того, необходимо выделить состояния синтаксического анализатора. Состояние определяет, какие символы в данный момент могут быть на входе синтаксического анализатора, и какова будет реакция на этот символ. Например, если на вход синтаксического анализатора пришла цифра, то он переходит в состояние «Константа», и до завершения константы (т.е. до появления пробела, знака операции, закрывающей скобки или конца строки) на вход синтаксического анализатора могут приходить только цифры и точка, если константа вещественная. Причём, естественно, точка может встречаться только один раз, что приводит к делению состояния «Константа» на два состояния: «Константа до точки», в котором точка может появиться, и «Константа после точки», в котором появление точки будет считаться ошибкой.

Одно состояние является начальным – с него начинается работа синтаксического анализатора, и одно или несколько состояний должны быть конечными.

Далее строиться таблица, которая определяет реакцию синтаксического анализатора на входные символы в зависимости от состояния. Реакция обычно заключается в смене состояния синтаксического анализатора и ещё каких-то действиях, например, запись очередного символа во временную переменную, увеличение или уменьшение уровня вложенности при появлении скобок и т.д.

Обычно в программе синтаксический анализатор реализуется как бесконечный цикл (for ( ; ; ) { ... }) с выходами в случае ошибки или при достижении конца обрабатываемой строки (обратите внимание, что достижение конца строки ещё не означает правильность выражения). Внутри цикла пишется условный блок, например, по группам символов, и в каждой части этого условного блока – свой условный блок (или оператор-переключатель) по состояниям синтаксического анализатора.

Состояния синтаксического анализатора в программе для простоты обозначаются номерами, однако, чтобы не путаться в этих номерах, можно задать им осмысленные имена с помощью конструкции #define или константы перечислимого типа enum.

Если выражение записано верно, то в результате работы синтаксического анализатора должен появиться список лексем (можно реализовать его как массив, а не настоящий список). Поскольку элементы массива должны иметь одинаковый тип, надо выбрать такую структуру, с помощью которой можно представить все возможные лексемы. Это можно сделать, если, например, каждый элемент массива представляет собой структуру, состоящую из двух полей: тип лексемы и её номер в списке лексем этого типа.

Часть лексем в арифметических и логических выражениях состоят из одного символа, но имена переменных и функций и константы в общем случае состоят из нескольких символов. Поэтому входные символы надо записывать во временную переменную, и когда данная лексема заканчивается, проверять, что она из себя представляет.

Не забудьте, что одна и та же переменная может входить в выражение несколько раз, поэтому каждый раз, когда имя переменной сформировалось, надо проверять, была ли она уже в списке переменных.

Не забудьте, что при достижении конца обрабатываемого выражения надо проверить, что количество открывающих и закрывающих скобок было одинаковым (вложенность = 0).

Анализ арифметических выражений

Состояния

Операнд (исходное) – должен появиться операнд (константа, переменная, функция, выражение в скобках).

Оператор – должен появиться оператор.

Имя – имя переменной или функции началось, но ещё не закончилось.

Константа до точки – константа началась, но ещё не закончилась, точки не было.

Константа после точки – константа началась, но ещё не закончилась, точка была.

Параметры функции – это состояние возникает, когда после имени, идентифицированного как имя функции, появился пробел. Единственный возможный символ в этом состоянии – открывающая скобка.

Ошибки

Пропущен операнд

Неверно расставлены скобки

Неверный символ «...»

Пропущен оператор

Не заданы параметры функции «...»

Неизвестная функция «...»

Неверное имя «...»

Неверная константа «...»