• Пред.Страница   След.Страница   Раздел   Содержание

     3.1 Распознаватели и LL(K) - грамматики
 

Моделирование работы недетерминированных магазинных распознавателей связано с поиском последовательности переходов из начального в одно из конечных состояний. Поиск состоит из отдельных шагов, каждый из которых может окончиться неудачно и привести к возврату в исходное состояние для выполнения следующего шага. Такой поиск с возвратом связан со значительными затратами времени, поэтому на практике используют более экономичные детерминированные распознаватели, работающие без возвратов. Эти распознаватели допускают только ограниченные классы КС-языков, которые однако отражают все синтаксические черты языков программирования.
Распознаватели можно разделить на две категории: нисходящие и восходящие. Каждая категория характеризуется порядком, в котором располагаются правила в дереве вывода. Нисходящие распознаватели обрабатывают правила сверху вниз, верхние правила раньше нижних, в то время как восходящие анализаторы используют нижние правила раньше тех, что расположены выше. Чтобы показать возможности детерминированных автоматов и способы их построения, в настоящем разделе рассматриваются нисходящие распознаватели, допускающие языки, порождаемые грамматиками вида LL(K).
 

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

 

---

• Пред.Страница   След.Страница   Раздел   Содержание