Общие алгоритмы грамматического разбора

Общие алгоритмы грамматического разбора. После появления работы Хомского со временем стало ясно, что каждый тип формальной грамматики тесно связан с определенным автоматом – простой абстрактной машиной, которая обычно определяется как машина, считывающая с входной рабочей ленты последовательность символов, хранящихся в ее ячейках, и производящая выходную ленту, в ячейках которой содержатся символы другой последовательности. К сожалению, здесь возникает проблема. Поскольку НФБ-грамматика может оказаться неоднозначной, соответствующий ей автомат должен быть недетерминированным (то есть может быть несколько вариантов перехода, из которых автомат должен выбрать наиболее подходящий).
Хотя регулярной грамматике всегда соответствует детерминированный аппарат, в случае НФБ-грамматики это верно, только если грамматика является однозначной и выполнены некоторые другие требования. Для однозначных НФБ-грамматик были разработаны методы непосредственного грамматического разбора. Одним из самых первых был метод рекурсивного спуска. Большим шагом вперед стало открытие Кнутом класса так называемых LR-грамматик (left to right parsing algorithms – грамматика с ограниченным левым контекстом), которые описывают все НФБ-грамматики, распознаваемые детерминированным МП-автоматом. Класс LR(1)-грамматик включает все такие грамматики, в которых требуется знать один только следующий символ, чтобы в процессе грамматического разбора принять правильное решение. SLR- (Simple LR – простая LR) и LALR- (Lookahead LR – LR с «заглядыванием вперед») грамматики являются подклассами класса LR-грамматик, которые приводят к эффективным методам грамматического разбора. Альтернативой является нисходящий метод LL-грамматики, обобщающий метод рекурсивного спуска. Большинство современных языков программирования разработано на основе одной из грамматик, SLR, LR или LL, и для них можно использовать инструменты генерации распознавателей типа YACC для автоматического создания распознавателя, соответствующего заданной грамматике.
Детерминированные МП-автоматы эквивалентны LR(k)-грамматикам и имеют значение при разработке практических компиляторов для языков программирования. В большинстве языков, построенных на основе грамматик, для определения синтаксиса используется некоторая LR(k)- грамматика.
Грамматический разбор на основе метода рекурсивного спуска. Метод рекурсивного спуска является относительно простым в описании и реализации, и на его примере можно показать, как связано формальное описание языка программирования с возможностью генерации выполняемого кода для программ на этом языке.
Напомним, что мы всегда можем переписать грамматику, используя расширенную НФБ-нотацию. Например, для синтаксиса оператора присваивания, арифметическое выражение описывается следующим образом:
<арифметическое выражение> ::= <терм> {[+|-]<терм>}*
Это означает, что в первую очередь должна распознаваться синтаксическая категория <терм>. Если следующим символом окажется «+» или «–», то за ним должна последовать другая синтаксическая категория, <терм>. Предположим, что переменная nextchar всегда содержит первый символ соответствующего нетерминального символа, а функция getchar считывает символ. Тогда мы можем непосредственно переписать прежнее правило, записанное в расширенной НФБ-нотации, в виде следующей рекурсивной процедуры:
algorithm assignStmt
variable ()
if nextchar <> '='
error ()
else
nextchar = getchar ()
expression ()

algorithm expression
term ()
while nextchar == '+' or nextchar == '-'
nextchar = getchar ()
term ()

algorithm term
primary ()
while nextchar == '*' or nextchar == '/'
nextchar = getchar
primary ()

algorithm primary
if nextchar == letter
variable
else if nextchar == digit
number
else if nextchar == '('
nextchar = getchar ()
expression ()
if nextchar = ')'
nextchar = getchar
else
error ()
else
error ()

algorithm variable
identifier ()
if nextchar = '['
nextchar := getchar ()
subList ()
if nextchar = ']'
nextchar = getchar ()
else
error ()

algorithm subList
expression ()
while nextchar == ','
nextchar = getchar ()
expression ()
В листинге Identifier и Number – это функции, предназначенные для чтения идентификаторов и чисел соответственно при помощи лексического распознавателя на основе КА.
В листинге полностью представлен распознаватель на основе метода рекурсивного спуска для операторов присваивания. Чтобы закончить разговор о грамматическом разборе, следует указать, что постфиксная запись выражения tenth + term2 выглядит следующим образом: term1 term2 +. Как будет показано далее, преобразование операторов исходной программы в постфиксную запись позволяет использовать удобную в применении стратегию вычисления выражений. Если у нас имеются процедуры для распознавания арифметических выражений, то не составляет труда произвести постфиксную запись этих выражений. Предположим, что каждая процедура производит постфиксную запись для собственных подвыражений, используя процедуру output. Постфиксная запись для арифметического выражения в процедуре Expression может быть получена следующим образом:
algorithm expression
term ()
while nextchar == '+' or nextchar == '-'
plustype = nextchar
nextchar = getchar ()
term ()
output (plustype)
Все остальные процедуры можно модифицировать аналогичным образом. Постфиксная запись для оператора переменная = выражение выглядит как переменная выражение =, для выражения множитель1 * множитель2 – соответственно множитель1 множитель2 * и т. д.



Приложенные файлы

  • doc 15087906
    Размер файла: 41 kB Загрузок: 0

Добавить комментарий