Проблемы алгоритм нисходящего разбора с возвратами

Главная проблема, возникающая при нисходящем анализе с возвратами - это число шагов, необходимых для разбора с помощью алгоритма, может быть огромным. Известно несколько приемов, помогающих слегка ускорить этот алгоритм. Мы укажем некоторые на них:

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

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

3. Можно добавить некоторую «бухгалтерию» (учет), позволяющую ускорить возвраты. Например, если мы знаем, что последние примененных правил не имеют применимых следующих альтернатив, то в случае неудачи можем при возврате пропустить эти альтернативы, сразу вернувшись к тому месту, где есть применимая альтернатива.

4. Можно ограничить количество допустимых возвратов.

Другая трудная проблема, связанная с возвратным анализом, - его слабые возможности в смысле локализации ошибок. Если входная цепочка синтаксически неправильна, то компилятор должен объявить, какие входные символы причастны к ошибке. Кроме того, когда найдена ошибка, компилятор должен исправить ее так, чтобы анализ мог продолжаться и обнаруживать другие ошибки, если они попадутся.

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

Дата добавления: 2014-01-07