[ предыдущая страница
| содержание
| следующая страница
]
LL(1) - грамматики
Понятие множества выбора можно обобщить таким образом, чтобы применять его к КС-грамматикам произвольного вида.
LL(1)-грамматика - это такая КС(1)-грамматика, в которой множества выбора правил с одинаковыми левыми частями не пересекаются.
Обобщение понятия множества выбора позволяет использовать правила, начинающиеся с нетерминалов. В качестве примера можно представить LL(1)-грамматику, содержащую следующие правила:
S  AbB
S d
A Cab
A B
B cSd
B 
C a
C ed
То, что это LL(1)-грамматика, еще надо доказать, так как в противном случае результат разбора может оказаться непредсказуемым. Да и автомат с магазинной памятью мы построить не сможем из-за того, что не имеем дополнительной информации, требуемой для построения таблицы переходов. А она появляется в ходе доказательств.
В книге Льюиса и пр. [Льюис] приводится описание доказательства принадлежности заданной грамматики к LL(1)-грамматике. Оно занимает одиннадцать страниц, использует демонстрационные примеры, разреженные матрицы и т.д. Я неоднократно принимался за его чтение, но каждый раз с грустью убеждался, что мой IQ (надо как-нибудь, хоть разок, проверить его значение) является недостаточно высоким, чтобы осилить материал. Поэтому были попытки перескочить эти страницы, выбросить нисходящий разбор из головы и обратиться к другой религии, проповедующей восходящий разбор. Но и здесь мне не хватило веры в истинность избранного пути. Поэтому, как это часто бывает в жизни, я нашел одну маленькую религию, которую подогнал под свои воззрения. После этого я смог не только успокоить свою душу, но и нести новый свет в массы. Эта религия зиждется на диаграммах Вирта, источая дальше свои идеи на распознаватели и реализацию. Подробно она будет раскрыта в следующей теме. Ее применение позволило обойти мне непереваримое доказательство и остаться в лоне нисходящего разбора.
[ предыдущая страница
| содержание
| следующая страница
]
|