Все существующие программы. Часть 7
Все, вроде бы идет нормально. У нас есть каркас рекурсивного решения для перебора всех строк некоторой грамматики, и оно кажется обоснованным. Давайте рассмотрим одну более сложную грамматику из предыдущего сообщения:
DECL: MODIFIER class ID BASE { }
MODIFIER: NIL | public | internal
BASE: NIL | : ID
ID: a | b | c | d
Рассмотрим самую короткую строку в этом языке class a { }. Вывод этой строки в DECL[5]:
DECL
MODIFIER class ID BASE { }
NIL class ID BASE { }
class ID BASE { }
class a BASE { }
class a { }
(Помните, что мы рассматриваем NIL, как хитрый способ записи пустой строки. Здесь мы заменяем BASE на NIL и он просто исчезает.)
Как мы нашли решение DECL[5] с помощью нашего алгоритма? Очень просто: просто решили все подзадачи и объединили результаты:
MODIFIER[0] class[0] ID[0] BASE[0] {[0] }[4]
MODIFIER[0] class[0] ID[0] BASE[0] {[1] }[3]
MODIFIER[0] class[0] ID[0] BASE[0] {[2] }[2]
MODIFIER[0] class[0] ID[0] BASE[0] {[3] }[1]
… еще сотня вариантов…
MODIFIER[3] class[1] ID[0] BASE[0] {[0] }[0]
MODIFIER[4] class[0] ID[0] BASE[0] {[0] }[0]
Мда… Даже если мы оптимизируем алгоритм таким образом, что будем пропускать некоторые варианты, предполагая, что X[0] является нетерминальным, а X[n>0] терминальным символом, реализовать этот алгоритм все еще будет очень не просто. У нас не было такой проблемы в предыдущих примерах, поскольку у нас всегда был один-два терма для конкретной замены. Если бы мы смогли добиться того, чтобы у нас было только два терма на одну подстановку (production).
Хмм…
Давайте вернемся назад, когда у нас была такая грамматика:
S: N | S + N
N: 1 | 2 | 3
мы заметили, что это язык, аналогичный следующей грамматике:
S: N | S P
P: + N
N: 1 | 2 | 3
? Обратите внимание, что мы преобразовали грамматику, в которой было правило с тремя термами в другую грамматику, в которой каждое правило состояло только из одного или двух термов. Так, а что будет, если мы воспользуемся этим же приемом?
S: N NIL | S P
P: + N
N: 1 NIL | 2 NIL | 3 NIL
Это явно тот же самый язык. Мы можем взять любую грамматику и преобразовать ее в эквивалентную, которая будет содержать два терма для каждой замены. Мы либо добавим NIL для «одиночной» подстановки или преобразуем n-арную подстановку к n одиночным подстановкам путем создания новых правил замены.
Ниже приведена однозначная грамматика, которая позволяет объявить открытые обобщенные классы с базовыми типами и вложенными классами:
CLASSLIST: CLASSDECL CLASSLIST | NIL
CLASSDECL: public class ID PARAMSLIST BASE { CLASSLIST }
PARAMSLIST: NIL | < PARAMSLISTBODY >
PARAMSLISTBODY: ID | ID , PARAMSLISTBODY
BASE: NIL | : TYPE
TYPE: ID TYPEARGS | ID TYPEARGS . TYPE
TYPEARGS: NIL | < ARGLISTBODY >
ARGLISTBODY: TYPE | TYPE , ARGLISTBODY
ID: a | b | c | d
Мы можем свести к грамматике, которая имеет два терма на одну подстановку, например, следующим образом:
CLASSLIST: CLASSDECL CLASSLIST | NIL NIL
CLASSDECL: HEADER CLASSBODY
HEADER: CLSNAME BASE
CLSNAME: PUBCLS CLASSNAME
PUBCLS: public class
CLASSNAME: ID PARAMSLIST
PARAMSLIST: NIL NIL | < PARAMSLISTEND
PARAMSLISTEND: PARAMSLISTBODY >
PARAMSLISTBODY: ID PARAMSLISTREST
PARAMSLISTREST: NIL NIL | , PARAMSLISTBODY
BASE: NIL NIL | : TYPE
TYPE: NODOTTYPE NIL | TYPEDOT TYPE
NODOTTYPE: ID TYPEARGS
TYPEDOT: NODOTTYPE .
TYPEARGS: NIL NIL | < ARGLISTEND
ARGLISTEND: ARGLISTBODY >
ARGLISTBODY: TYPE ARGLISTREST
ARGLISTREST: NIL NIL | , ARGLISTBODY
CLASSBODY: { CLASSBODYEND
CLASSBODYEND: CLASSLIST }
ID: a NIL | b NIL | c NIL | d NIL
Конечно, этот вариант сложнее читать, но он определяет тот же самый язык. И фактически, мы можем, хотя и не будем этого делать, написать программу, которая принимает грамматику в первой форме и автоматически создает грамматику во второй.
В следующий раз: Похоже, что мы уже готовы приступить к написанию кода!