gr1 (1119735)
Текст из файла
(проверить корректность определения в конце предыдущей лекции - «... более одного дерева (sic!) вывода...»)
Пример (неоднозначность в ЯП).
Пусть у нас есть правило вида
S -> if b then S else S | if b then S | a
Вопрос: как разбирать следующую цепочку? -
if b then if b then a else a
Варианты:
if b then (if b then a) else a
if b then (if b then a else a)
(две картинки)
Здесь различна сама семантика выполнения условного оператора. Как же решать такую проблему? Можно, конечно, полностью запретить ситуации с подобной неоднозначностью, а можно положиться (в каждом конкретном случае) на алгоритм разбора, требуя от него выбора заранее предписанного варианта. Заметим, что в данном случае возможно описать другую грамматику, свободную от этой проблемы:
S -> if b then S | if b then S' else S | a
S' -> if b then S' else S' | a
Проблема однозначности грамматик в общем случае алгоритмически неразрешима, однако можно анализировать частные случаи. «Симптомами» неоднозначности грамматики можно считать правила вида:
A -> AA | alpha
A -> AalphaA | beta
A -> alphaA | Abeta | gamma
A -> alphaA | alphaAbeta | gamma
Зададимся вопросом: для любого ли языка можно записать однозначную грамматику, его порождающую? Оказывается, это не так. Будем называть язык неоднозначным, если его нельзя описать ни одной однозначной грамматикой.
Пример неоднозначного языка:
L = {aibjck, i=j либо j=k}
Неоднозначность L строго доказана. Не останавливаясь на доказательстве, поясним его схему «на пальцах». Чтобы построить цепочку с i=j, нужно контролировать выполнение именно этого равенства, а генерация произвольного числа k символов c будет выполняться независимо. Симметричная ситуация и с другим вариантом: отслеживание j=k и приписывание цепочки из i a. Ясно, что процесс генерации цепочки с самого начала может пойти либо по одному, либо по другому пути, однако и в том, и в другом случае возможно построить цепочку с i=j=k, которая, таким образом, будет иметь более одного дерева вывода.
Регулярные грамматики
Еще более сузим класс рассматриваемых грамматик и рассмотрим для него схему построения «синтаксических» деревьев. Когда мы рисовали деревья вывода для условного оператора, мы делали это по схеме «сверху вниз », т.е. от корня к вершине (для дерева как структуры данных корень обыкновенно представляется либо изображается сверху, что и дает название нашему методу). Берем цель грамматики и пытаемся «развернуть» ее различными способами, подставляя в получаемые цепочки выражения для возникающих при этом нетерминалов. Когда все листья дерева будут помечены лишь терминальными символами, построение дерева можно считать оконченным. При этом необходимо так или иначе следить за соответствием символов из разбираемой цепочки тем символам, которые возникают при построении дерева: наша цель, напомним, составить дерево разбора для некоторой конкретной цепочки. Можно, однако, действовать и иначе: исходить из поданных «на вход» терминальных символов и пытаться «свернуть» их в нетерминалы и, в конечном итоге, в цель грамматики, строя, таким образом, дерево «снизу вверх », от листьев к корню. Для регулярных грамматик такой метод особенно удобен. Чтобы работать с символами цепочки слева направа, нам нужна леволинейная грамматика:
Пример.
S -> A$
A -> Ab | Bb | b
B -> Aa
Символ $ - это так называемый маркер конца – удобный символ для обозначения конца цепочки. Его использование зачастую значительно упрощает работу. (Здесь и далее символ $ замещает символ перепендикуляра. Роману предлагается выполнить обратную замену для соответствия электронных лекций рукописным. - Д.Ч.)
Рассмотрим построение дерева разбора для цепочки babb$.
(картинка)
Ясно, что в каждый момент разбора достаточно только двух первых символов: при начале работы – стартовых символов цепочки, далее – только что построенного нетерминала и следующего входного символа.
(картинка-продолжение)
Заметим, что могут быть случаи и хуже:
(картинка)
Для цепочки B$ нет подходящей свертки, так что предложенная нам цепочка языку не принадлежит. Другой случай:
(картинка)
Цепочка уже закончилась, и дерево успешно построено, однако его корень не помечен S. Значит, и эта цепочка не принадлежит порождаемому нашей грамматикой языку.
Однако список проблем на этом не заканчивается. Заменим последнюю группу правил в грамматике на такую:
B -> Aa | b
или другую:
B -> Aa | Bb
Что же мы видим? У разных нетерминалов появляются одинаковые альтернативы, а значит, казавшийся нам столь простым алгоритм нужно для таких грамматик модифицировать, обходя в процессе работы целое дерево вложенных вариантов (с откатами назад). Обратим особое внимание на важный факт: анализ получается недетерминированным, хотя рассматриваемая грамматика однозначна! Запомним это и отметим также справедливость следующего утверждения: любой язык, который можно описать регулярной грамматикой, можно описать регулярной грамматикой «без одинаковых правых частей».
Конечные автоматы
Определение конечного автомата из дискретной математики, безусловно, хорошо известно всем. Однако мы будет рассматривать конечные автоматы в первую очередь как «распознаватели» языков, поэтому дадим более узкое, удобное нам определение.
Недетерминированный конечный автомат (НКА) – это пятерка (K, VT, F, H, S), где:
K – конечное множество состояний автомата,
VT – конечное множество входных символов,
F – функция переходов: F: K x VT -> P(K) (последним символом обозначено множество всех подмножеств K),
HEK – начальное состояние,
SCK – множество заключительных состояний.
(Надо заменить E на символ «принадлежит», а C на символ вложения. - Д.Ч.)
Определим еще несколько понятий. Будем говорить, что НКА допускает цепочку alpha=a1...an, если F(H,a1)=A1, F(A1,a2)=A2, ..., F(An-1,an)=AnES (символы равенства следует понимать здесь следующим образом: найдутся элементы A1, ..., An множества K такие, что A1 – элемент F(H,a1), A2 – элемент F(A1,a2), ..., An – элемент F(An-1,an)). (Опять нужно заменить символ E – Д.Ч.)
Язык, допускаемый (определяемый, распознаваемый) НКА – это множество всех допускаемых этим НКА цепочек.
Диаграмма состояний (ДС) НКА – это помеченный ориентированный граф такой, что:
-
его вершины помечены символами состояний из K,
-
вершины A и B соединяются дугой (от A к B), если ЭaEVT: F(A,a)=B, (снова символы – Д.Ч.) при этом дуга помечается всеми такими a.
Сформулируем без доказательства две теоремы.
Теорема 1. Для L=L(НКА) всегда найдется регулярная грамматика G: L(G)=L.
Теорема 2. Для L=L(G), где G – регулярная грамматика, всегда найдется НКА: L=L(НКА).
Из доказательств этих теорем извлечем лишь правила получения G из НКА и НКА из G соответственно.
-
НКА -> G (регулярная леволинейная)
(картинки)
-
Регулярная леволинейная G -> НКА
(еще картинки)
Пример.
НКА = ( {H,A,B,S}, {a,b,+,-}, F, H, {S} )
F: F(H,a)=A, F(H,b)=A;
F(A,+)=B, F(A,-)=B;
F(B,a)=A, F(B,b)=A;
F(A,$)=S (маркер конца обыкновенно не указывают явно в VT),
а для остальных пар F= (empty set) (снова особый символ – Д.Ч.)
ДС:
(картинка)
ДС весьма удобна: язык «виден» читателю. Будем теперь строить грамматику:
S -> A$
A -> Ba | Bb | a | b
B -> A+ | A-
Теперь рассмотрим обратный пример.
S -> A$
A -> Ab | Bb | b
B -> Aa
Строим НКА:
(картинка)
Получена, по сути дела, блок схема алгоритма разбора цепочки. На плюсах это может выглядеть примерно так: (выделить необходимые ключевые слова полужирным)
class scan // реализация НКА
{
enum state {H, A, B, S};
state CS; // current state
FILE *fp; // input file
char c;
public:
scan(const char *data);
~scan();
bool analyze();
};
scan::scan(const char *data)
{
fp = fopen(data, "r");
if (!fp)
throw data;
CS = H;
c = fgetc(fp);
}
scan::~scan()
{
fclose(fp); // если файл не был открыт, то объект
// не был создан => вызова не будет
}
bool scan::analyze()
{
try
{
do
{
switch(CS)
{
case H:
if (c=='b')
{
c = fgetc(fp); CS = A;
}
else
throw c; // упрощенно
break;
case A:
if (c=='a')
{
c = fgetc(fp); CS = B;
}
else if (c=='b')
{
c = fgetc(fp); // CS уже == B
}
else if (c=='$')
{
CS = S; // end
}
else
throw c;
case B:
if (c=='b')
{
c = fgetc(fp); CS = A;
}
else
throw c;
}//switch
} while(CS!=S); //do
}//try
catch(char c)
{
cout << "..." << c "..." << endl;
return false;
}
return true; // у меня этого почему-то нет – Д.Ч.
}//analyze()
int main()
{
bool res;
try
{
scan E("test.txt");
res = E.analyze();
cout << "Result is " << res << endl;
}
catch(const char *file)
{
cout << "Error opening file " << file << endl;
}
return 0;
}
Сделаем еще несколько замечаний. Во-первых, мы работали с очень удобной грамматикой: S в правилах вывода встречается только слева (ясно, что этого можно добиться всегда). Во-вторых, в приведенном коде нет проверки на наличие символов после '$' (вообще говоря, мы не слишком-то заботились о содержимом входного файла, считая, что '$' там обязательно обязательно встретится). Далее, в нашем примере анализ детерминирован, хотя, как уже отмечалось ранее, это не всегда справедливо (картинка) (опять же ограничимся замечанием, что построить детерминированный конечный автомат тем не менее возможно). Кроме того (а мы уже почти вплотную приблизились к построению лексического анализатора!) обратим внимание на то, что нашу схему очень легко модифицировать для решения родственных задач (рано или поздно нам придется «выдавать» на выход лексемы). Продолжим для иллюстрации этого утверждения рассмотрение нашего примера.
Зададимся вопросом: а какой язык распознает построенный нами НКА (и – по нему – алгоритм)? Ответом будет L = {b$, balphab$, alphaE{a,b}*, где нет двух a подряд} (опять альфа и опять «принадлежит»). Поставим теперь задачу определить длину максимальной последовательности подряд идущих b (не «разорванных» ни одной a). Решением можно считать несколько измененную диаграмму состояний:
(картинка)
Здесь дуги, кроме терминальных символов, инициирующих переходы, помечены также дополнительными действиями – то бишь соответствующими фрагментами кода. Достаточно перенести их в надлежащее место в программе, и программа наряду с проверкой на принадлежность цепочки нашему языку будет решать описанную задачу. Заметим, что алгоритмическая сложность по сравнению с общей схемой остается прежней.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.















