Пример 4.2

Рассмотрим работу алгоритма на примере все той же грамматики G для упрошенных арифметических выражений с правилами:

Если наверху магазина появятся E+T, то сначала попытаемся сделать свертку, используя E® E+T, а потом E® T. Если же появятся T*F, то сначала попробуем T® T*F, а потом T® F. Для входа а*а восходящий алгоритм пройдет следующие конфигурации:

(q, 1, $, e) ÷¾² (q, 2, $a, m) ÷¾¹ (q, 2, $F, 5m) ÷¾¹ (q, 2, $T, 45m)

÷¾¹ (q, 2, $E, 245m) ÷¾² (q, 3, $E*, m245m) ÷¾² (q, 4, $E*a, mm245m)

÷¾¹ (q, 4, $E*F, 5mm245m) ÷¾¹ (q, 4, $E*T, 45mm245m)

÷¾¹ (q, 4, $E*E, 245mm245m) ÷¾⁴ (b, 4, $E*E, 245mm245m)

÷¾^5б (b, 4, $E*T, 45mm245m) ÷¾^5б (b, 4, $E*F, 5mm245m)

÷¾^5б (b, 4, $E*a, mm245m) ÷¾^5г (b, 3, $E*, m245m) ÷¾^5г (b, 2, $E, 245m)

÷¾² (q, 3, $T*, m45m) ÷¾² (q, 4, $T*a, mm45m) ÷¾¹ (q, 4, $T*F, 5mm45m)

÷¾¹ (q, 4, $T, 35mm45m) ÷¾¹ (q, 4, $E, 235mm45m) ÷¾³ (t, 4, $E, 235mm45m)

Таким образом, получается обращенный правый разбор h(235mm45m)=23545. 

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

Пусть для каждого символа из магазинных цепочек, участвующих в конфигурациях рассмотренных алгоритмов разбора с возвратами требуется только одна ячейка памяти и пусть число элементарных операций, необходимых для вычисления одного шага алгоритма ограничено. Тогда для входной цепочки длины n алгоритмам требуется емкость памяти С₁ * n и время C₂ⁿ , где C₁ и C₂ - некоторые константы. То есть магазинные списки линейно зависят от длины входной цепочки, а число шагов экспоненциально.

Известно несколько способов модернизации алгоритмов с возвратами, ускоряющих их работу.

(1) Можно упорядочить правила так, чтобы наиболее вероятные альтернативы испытывались первыми. Однако это не поможет в тех случаях, когда входная цепочка синтаксически неверна и для нее придется перебирать все возможные варианты.

(2) Можно ускорить возвраты. Например, в восходящем алгоритме записывать информацию, позволяющую сразу восстановить предыдущую конфигурацию, в которой была сделана свертка.

(3) Можно ограничить количество допустимых возвратов. В частности, в алгоритме нисходящего анализа можно упорядочить альтернативы так, чтобы первыми испытывались наиболее длинные из них. Как только альтернатива, из которой выводится префикс необходимой части входной цепочки, обнаружена, другие альтернативы исключаются из рассмотрения. Конечно, полученный таким образом префикс может оказаться “ошибочным” и тогда попытка разбора окончится неудачей. Но в практических ситуациях это редко создает серьезные проблемы.

(4) Можно заглядывать вперед на k входных символов, чтобы определить надо ли использовать данную альтернативу или свертку. Далее мы увидим, что с помощью подглядывания вперед можно полностью устранить необходимость возвратов.

Но все эти пути конечно полумеры, и на практике лучше использовать алгоритмы без возвратов (детерминированные).

Другая проблема, связанная с возвратным анализом - слабые возможности в смысле локализации, а тем более нейтрализации ошибок. Если входная цепочка не верна, то компилятор должен объявить, какие входные символы причастны к ошибке. Кроме того, когда ошибка найдена, компилятор должен исправить ее так, чтобы анализ мог продолжаться и обнаружить другие ошибки, если они попадутся. Если входные цепочки построены неправильно, то алгоритм с возвратами просто объявит об ошибке, оставив входной указатель на первом входном символе. Это, конечно же, можно обойти, усложнив алгоритм или добавляя в грамматику альтернативные правила, порождающие наиболее распространенные синтаксические ошибки. Благодаря ним синтаксически неправильные цепочки станут правильными с точки зрения новой грамматики. Появление в выходе номера такого “ошибочного” правила служит сигналом, локализующим ошибку во входной цепочке. Но сколько потребуется ошибочных правил? Методы, изложенные ниже, обладают большими способностями к обнаружению ошибок.

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

Поиск по сайту: