Задачи по программированию по курсу ЯПиМТ. Родионова Т.Е. - 31 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

31
вы. Полученная цепочка и будет искомой основой. Этот процесс продолжается до тех пор, пока входная це-
почка не свернется к начальному символу.
Грамматика является грамматикой простого предшествования, если она приведенная, не содержит е-
правил, и для любой пары символов выполняется не более одного отношения предшествования.
Рассмотрим грамматику, состоящую из правил:
S
→
aSSb
c
В качестве начала и конца цепочки используются маркеры # или $. Найдем отношения предшество-
вания.
1) =• Просматриваем правые части правил, получаем a=• S, S =• S, S =• b.
2) <• Ищем в правых частях правил пары смежных символов ХС, таких что Х находится в отноше-
нии
<•
с самым левым символом цепочки, выводимой из С.
Рассмотрим пару aS, получим a <• a, a <• c. Рассмотрим пару SS, получим S <• a, S <• c. Рассмот-
рим начальный маркер, получим $ <• a, $ <• c.
3)
•>
Ищем в правых частях правил пары смежных символов СХ. Затем ищем символы Y, которые
могут оказаться на правом конце цепочки, выводимой из С за один или более шагов, итерминалыd,
которые могут находиться в начале цепочки, выводимой из Х за нуль и более шагов. В нашем случае
это пары:
SS: b •> a, b •> c, c •> a, c •> c; Sb: b •> b, c •> b; конечный маркер:b•> $, c •> $.
Построим таблицу для этих отношений. Это квадратная матрица, строкиистолбцыкоторойпомече-
ны терминалами , нетерминалами и маркером (начала или конца цепочки). Пустая ячейка таблицы соответ-
ствует состоянию ошибки.
Sabc$
S=•<•=•<•
a=
•<• <•
b •> •> •> •>
c
•> •> •> •>
$ <• <•
Так как в одной ячейки управляющей таблицы записано не более одного отношения предшествова-
ния, то это грамматика предшествования, кроме того правые части всех правил различны, следовательно это
грамматика простого предшествования.
Построение алгоритма разбора. Символ $ будем использовать в качестве маркера для стека и право-
го концевого маркера входной цепочки. Действие f(x,a) зависит от верхнего символа стека и самого левого
символа необработанной части входной цепочки.
f(x,a) – перенос (сдвиг), если х
<•
a или х =
•
а.
f(x,a) – свертка, если х
•>
a.
f(x,a) – ошибка в противоположных случаях.
f($S$) – допуск цепочки.

Страницы