Сборник по задачам и примерам Assembler


Синтаксический анализ - часть 3


При реализации метода рекурсивного спуска в чистом виде возможны сложности. Посмотрим на правила грамматики, подобные следующим:

dec-list => dec | dec-list ; dec

id-list=> ID | id-list . ID

term => factor | term * factor | term div factor

strut-list => stmt | stmt-list ; stmt

Видно, что эти правила леворекурсивны. Например, рассмотрим следующее правило:

id-list => ID | ID-LIST , ID

В этом правиле вторая альтернатива начинается с нетерминала ID-LIST, то есть в процессе разбора при обращении к процедуре, соответствующей этому нетерминалу, получится бесконечный цикл. Ее необходимо устранить. Для этого соответствующие правила подправляются следующим образом:

dec-list => dec | dec-list ; dec id-HSts» ID I {. ID}

stmt-list => stmt | {: stmt} exp => term {+ term | - term}
term => factor {* factor | div factor}

Теперь для принятия решения о дальнейшем пути выполнения рекурсивной процедуры необходимо просматривать один символ вперед. Если он совпадает с тем, что в правиле, то процедура рекурсивно вызывается снова. Если этот символ любой другой, то производится возврат из этой процедуры. Таким образом, процесс написания программы неявно представляет собой строительство дерева разбора начиная от его корня — начального символа языка. То есть это действительно нисходящий метод.

Остается заметить еще одно достоинство метода рекурсивного спуска. Если очередная языковая конструкция распознана, то почему бы сразу в соответствующей рекурсивной процедуре не «навесить» семантику, то есть генерацию кода.

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

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

 




Начало  Назад  



Книжный магазин